Inkscape: Geom::PathIntersectionGraph Class Reference

Searching...

No Matches

Intermediate data for computing Boolean operations on paths. More...

#include <intersection-graph.h>

Classes
struct	IntersectionVertex

struct	PathData
	Stores processed intersection information for a single path in an operand path-vector. More...

Public Member Functions
	PathIntersectionGraph (PathVector const &a, PathVector const &b, Coord precision=EPSILON)
	Construct a path intersection graph for two shapes described via their boundaries.

PathVector	getUnion ()
	Get the union of the shapes, A ∪ B.

PathVector	getIntersection ()
	Get the intersection of the shapes, A ∩ B.

PathVector	getAminusB ()
	Get the difference of the shapes, A ∖ B.

PathVector	getBminusA ()
	Get the opposite difference of the shapes, B ∖ A.

PathVector	getXOR ()
	Get the symmetric difference of the shapes, A ∆ B.

std::size_t	size () const
	Returns the number of intersections used when computing Boolean operations.

std::vector< Point >	intersectionPoints (bool defective=false) const
	Get the geometric points where the two path-vectors intersect.

std::vector< Point >	windingPoints () const
	Get the geometric points located on path portions between consecutive intersections.

void	fragments (PathVector &in, PathVector &out) const

bool	valid () const

Private Types
enum	InOutFlag { INSIDE , OUTSIDE , BOTH }

typedef boost::intrusive::list< IntersectionVertex, boost::intrusive::member_hook< IntersectionVertex, boost::intrusive::list_member_hook<>, &IntersectionVertex::_hook > >	IntersectionList

typedef boost::intrusive::list< IntersectionVertex, boost::intrusive::member_hook< IntersectionVertex, boost::intrusive::list_member_hook<>, &IntersectionVertex::_proc_hook > >	UnprocessedList

typedef IntersectionList::iterator	ILIter

typedef IntersectionList::const_iterator	CILIter

Private Member Functions
PathVector	_getResult (bool enter_a, bool enter_b)
	Compute the partial result of a boolean operation by looking at components containing intersections and stitching the correct path portions between them, depending on the truth table of the operation.

void	_handleNonintersectingPaths (PathVector &result, unsigned which, bool inside)
	Select intersection-free path components ahead of a boolean operation based on whether they should be a part of that operation's result.

void	_prepareArguments ()
	Prepare the operands stored in PathIntersectionGraph::_pv by closing all of their constituent paths and removing degenerate segments from them.

bool	_prepareIntersectionLists (Coord precision)
	Compute the lists of intersections between the constituent paths of both operands.

void	_assignEdgeWindingParities (Coord precision)
	Determine whether path portions between consecutive intersections lie inside or outside of the other path-vector.

void	_assignComponentStatusFromDegenerateIntersections ()
	Detect the situation where a path is either entirely inside or entirely outside of the other path-vector and set the status flag accordingly.

void	_removeDegenerateIntersections ()
	Remove intersections that don't change between in/out.

void	_verify ()
	Verify that all paths contain an even number of intersections and that the intersection graph does not contain leaves (degree one vertices).

ILIter	_getNeighbor (ILIter iter)
	Get an iterator to the corresponding crossing on the other path-vector.

PathData &	_getPathData (ILIter iter)
	Get the path data for the path containing the intersection given an iterator to the intersection.

Private Attributes
PathVector	_pv [2]
	Stores the two operand path-vectors, A at _pv[0] and B at _pv[1].

boost::ptr_vector< IntersectionVertex >	_xs
	Stores all crossings between the two shapes.

boost::ptr_vector< PathData >	_components [2]
	Stores the crossing information for the operands.

UnprocessedList	_ulist
	Temporarily holds all unprocessed during a boolean operation.

bool	_graph_valid
	Whether all intersections are regular.

std::vector< Point >	_winding_points
	Stores sample points located on paths of the operand path-vectors, between consecutive intersections.

Friends
std::ostream &	operator<< (std::ostream &, PathIntersectionGraph const &)
	Format the PathIntersectionGraph for output.

Detailed Description

Intermediate data for computing Boolean operations on paths.

This class implements the Greiner-Hormann clipping algorithm, with improvements inspired by Foster and Overfelt as well as some original contributions.

For the purposes of boolean operations, a shape is defined as a PathVector using the "even-odd" rule, i.e., regions with odd winding are considered part of the shape, whereas regions with even winding are not.

For this reason, the two path-vectors are sometimes called "shapes" or "operands" of the boolean operation. Each path-vector may contain several paths, which are called either "paths" or "components" in the documentation.

Definition at line 63 of file intersection-graph.h.

Member Typedef Documentation

◆ CILIter

typedef IntersectionList::const_iterator Geom::PathIntersectionGraph::CILIter

private

Definition at line 218 of file intersection-graph.h.

◆ ILIter

typedef IntersectionList::iterator Geom::PathIntersectionGraph::ILIter

private

Definition at line 217 of file intersection-graph.h.

◆ IntersectionList

typedef boost::intrusive::list< IntersectionVertex , boost::intrusive::member_hook < IntersectionVertex , boost::intrusive::list_member_hook<> , &IntersectionVertex::_hook > > Geom::PathIntersectionGraph::IntersectionList

private

Definition at line 188 of file intersection-graph.h.

◆ UnprocessedList

typedef boost::intrusive::list< IntersectionVertex , boost::intrusive::member_hook < IntersectionVertex , boost::intrusive::list_member_hook<> , &IntersectionVertex::_proc_hook > > Geom::PathIntersectionGraph::UnprocessedList

private

Definition at line 197 of file intersection-graph.h.

Member Enumeration Documentation

◆ InOutFlag

enum Geom::PathIntersectionGraph::InOutFlag

private

Enumerator
INSIDE
OUTSIDE
BOTH

Definition at line 157 of file intersection-graph.h.

Constructor & Destructor Documentation

◆ PathIntersectionGraph()

Geom::PathIntersectionGraph::PathIntersectionGraph	(	PathVector const &	a,
		PathVector const &	b,
		Coord	precision = `EPSILON`
	)

Construct a path intersection graph for two shapes described via their boundaries.

The boundaries are passed as path-vectors.

Parameters

a	– the first operand, also referred to as operand A.
b	– the second operand, also referred to as operand B.
precision	– precision setting used for intersection calculations.

Definition at line 50 of file intersection-graph.cpp.

References _assignComponentStatusFromDegenerateIntersections(), _assignEdgeWindingParities(), _graph_valid, _prepareArguments(), _prepareIntersectionLists(), _pv, _removeDegenerateIntersections(), _verify(), and Geom::PathVector::empty().

Member Function Documentation

◆ _assignComponentStatusFromDegenerateIntersections()

void Geom::PathIntersectionGraph::_assignComponentStatusFromDegenerateIntersections ( )

private

Detect the situation where a path is either entirely inside or entirely outside of the other path-vector and set the status flag accordingly.

Definition at line 183 of file intersection-graph.cpp.

References _components, INSIDE, and OUTSIDE.

Referenced by PathIntersectionGraph().

◆ _assignEdgeWindingParities()

void Geom::PathIntersectionGraph::_assignEdgeWindingParities ( Coord precision )

private

Determine whether path portions between consecutive intersections lie inside or outside of the other path-vector.

< The index of the other operand

Path time interval from the current crossing to the next one

Definition at line 152 of file intersection-graph.cpp.

References _components, _pv, _winding_points, Geom::cyclic_next(), INSIDE, Geom::PathInterval::inside(), OUTSIDE, Geom::PathVector::pointAt(), Geom::PathVector::size(), w, and Geom::PathVector::winding().

Referenced by PathIntersectionGraph().

◆ _getNeighbor()

PathIntersectionGraph::ILIter Geom::PathIntersectionGraph::_getNeighbor ( ILIter iter )

private

Get an iterator to the corresponding crossing on the other path-vector.

Parameters

ILIter – an iterator to a list of intersections in one of the path-vectors.

Returns: An iterator to the corresponding intersection in the other path-vector.

Definition at line 495 of file intersection-graph.cpp.

References _components.

Referenced by _getResult(), and _removeDegenerateIntersections().

◆ _getPathData()

PathIntersectionGraph::PathData & Geom::PathIntersectionGraph::_getPathData ( ILIter iter )

private

Get the path data for the path containing the intersection given an iterator to the intersection.

Definition at line 503 of file intersection-graph.cpp.

References _components.

Referenced by _removeDegenerateIntersections().

◆ _getResult()

PathVector Geom::PathIntersectionGraph::_getResult	(	bool	enter_a,
		bool	enter_b
	)

private

Compute the partial result of a boolean operation by looking at components containing intersections and stitching the correct path portions between them, depending on the truth table of the operation.

Parameters

enter_a	– whether the path portions contained inside operand A should be part of the boundary of the boolean operation's result.
enter_b	– whether the path portions contained inside operand B should be part of the boundary of the boolean operation's result.

These two flags completely determine how to resolve the crossings when building the result and therefore encode which boolean operation we are performing. For example, the boolean intersection corresponds to enter_a == true and enter_b == true, as can be seen by looking at a Venn diagram.

< Whether to traverse the current component in the backwards direction.

< Index of the path in its PathVector

Definition at line 363 of file intersection-graph.cpp.

References _components, _getNeighbor(), _pv, _ulist, _xs, Geom::PathVector::clear(), Geom::cyclic_next(), Geom::cyclic_prior(), Geom::PathVector::erase(), Geom::PathInterval::from_direction(), Geom::GEOM_ERR_INTERSECGRAPH, INSIDE, Geom::PathVectorTime::path_index, Geom::PathIntersectionGraph::IntersectionVertex::pos, result, Geom::reverse(), size(), Geom::PathVector::size(), w, and Geom::PathIntersectionGraph::IntersectionVertex::which.

Referenced by getAminusB(), getBminusA(), getIntersection(), and getUnion().

◆ _handleNonintersectingPaths()

void Geom::PathIntersectionGraph::_handleNonintersectingPaths	(	PathVector &	result,
		unsigned	which,
		bool	inside
	)

private

Select intersection-free path components ahead of a boolean operation based on whether they should be a part of that operation's result.

Every component that has intersections will be processed by _getResult(). Here we take care of paths that don't have any intersections. They are either completely inside or completely outside the other path-vector.

Parameters

result	– output parameter to store the selected components.
which	– which of the two operands to search for intersection-free paths.
inside	– If set to true, add paths entirely contained inside the other path-vector to the result. If set to false, add paths entirely outside of the other path-vector instead.

Definition at line 461 of file intersection-graph.cpp.

References _components, _pv, INSIDE, OUTSIDE, result, Geom::PathVector::size(), w, and Geom::PathVector::winding().

Referenced by getAminusB(), getBminusA(), getIntersection(), and getUnion().

◆ _prepareArguments()

void Geom::PathIntersectionGraph::_prepareArguments ( )

private

Prepare the operands stored in PathIntersectionGraph::_pv by closing all of their constituent paths and removing degenerate segments from them.

Definition at line 77 of file intersection-graph.cpp.

References _pv, size(), and w.

Referenced by PathIntersectionGraph().

◆ _prepareIntersectionLists()

bool Geom::PathIntersectionGraph::_prepareIntersectionLists ( Coord precision )

private

Compute the lists of intersections between the constituent paths of both operands.

Parameters

precision – the precision setting for the sweepline algorithm.

Returns: Whether any intersections were found.

Definition at line 105 of file intersection-graph.cpp.

References _components, _pv, _xs, Geom::PathIntersectionGraph::IntersectionVertex::defective, Geom::PathVector::intersect(), Geom::PathIntersectionGraph::IntersectionVertex::neighbor, Geom::PathIntersectionGraph::IntersectionVertex::next_edge, OUTSIDE, Geom::PathIntersectionGraph::IntersectionVertex::p, Geom::PathVectorTime::path_index, Geom::PathIntersectionGraph::IntersectionVertex::pos, Geom::PathVector::size(), w, and Geom::PathIntersectionGraph::IntersectionVertex::which.

Referenced by PathIntersectionGraph().

◆ _removeDegenerateIntersections()

void Geom::PathIntersectionGraph::_removeDegenerateIntersections ( )

private

Remove intersections that don't change between in/out.

In general, a degenerate intersection can happen at a point where two shapes "kiss" (are tangent) but do not cross into each other.

< Whether this is the last remaining crossing.

Definition at line 209 of file intersection-graph.cpp.

References _components, _getNeighbor(), _getPathData(), _graph_valid, Geom::cyclic_next(), Geom::cyclic_prior(), and Geom::PathIntersectionGraph::PathData::xlist.

Referenced by PathIntersectionGraph().

◆ _verify()

void Geom::PathIntersectionGraph::_verify ( )

private

Verify that all paths contain an even number of intersections and that the intersection graph does not contain leaves (degree one vertices).

Definition at line 248 of file intersection-graph.cpp.

References _components, and Geom::cyclic_next().

Referenced by PathIntersectionGraph().

◆ fragments()

void Geom::PathIntersectionGraph::fragments	(	PathVector &	in,
		PathVector &	out
	)		const

Definition at line 328 of file intersection-graph.cpp.

References _components, _pv, Geom::cyclic_next(), INSIDE, Geom::PathVector::push_back(), Geom::Path::setStitching(), Geom::PathVector::size(), and w.

◆ getAminusB()

PathVector Geom::PathIntersectionGraph::getAminusB ( )

Get the difference of the shapes, A ∖ B.

A point belongs to the difference if and only if it belongs to A but not to B.

Returns: A path-vector describing the difference of the operands A and B.

Definition at line 280 of file intersection-graph.cpp.

References _getResult(), _handleNonintersectingPaths(), and result.

Referenced by getXOR(), TEST_F(), TEST_F(), and TEST_F().

◆ getBminusA()

PathVector Geom::PathIntersectionGraph::getBminusA ( )

Get the opposite difference of the shapes, B ∖ A.

A point belongs to the difference if and only if it belongs to B but not to A.

Returns: A path-vector describing the difference of the operands B and A.

Definition at line 288 of file intersection-graph.cpp.

References _getResult(), _handleNonintersectingPaths(), and result.

Referenced by getXOR(), TEST_F(), TEST_F(), and TEST_F().

◆ getIntersection()

PathVector Geom::PathIntersectionGraph::getIntersection ( )

Get the intersection of the shapes, A ∩ B.

A point belongs to the intersection if and only if it belongs to both shapes.

Returns: A path-vector describing the intersection of the operands A and B.

Definition at line 272 of file intersection-graph.cpp.

References _getResult(), _handleNonintersectingPaths(), and result.

Referenced by main(), TEST_F(), TEST_F(), and TEST_F().

◆ getUnion()

PathVector Geom::PathIntersectionGraph::getUnion ( )

Get the union of the shapes, A ∪ B.

A point belongs to the union if and only if it belongs to at least one of the operands.

Returns: A path-vector describing the union of the operands A and B.

Definition at line 264 of file intersection-graph.cpp.

References _getResult(), _handleNonintersectingPaths(), and result.

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ getXOR()

PathVector Geom::PathIntersectionGraph::getXOR ( )

Get the symmetric difference of the shapes, A ∆ B.

A point belongs to the symmetric difference if and only if it belongs to one of the two shapes A or B, but not both. This is equivalent to the logical XOR operation: the elements of A ∆ B are points which are in A XOR in B.

Returns: A path-vector describing the symmetric difference of the operands A and B.

Definition at line 296 of file intersection-graph.cpp.

References Geom::PathVector::begin(), Geom::PathVector::end(), getAminusB(), and getBminusA().

Referenced by TEST_F(), and TEST_F().

◆ intersectionPoints()

std::vector< Point > Geom::PathIntersectionGraph::intersectionPoints ( bool defective = false ) const

Get the geometric points where the two path-vectors intersect.

Degenerate intersection points, where the shapes merely "kiss", are not retured.

Parameters

defective – whether to return only the defective crossings or only the true crossings.

Returns: If defective is true, returns a vector containing all defective intersection points, i.e., points that are neither true transverse intersections nor degenerate intersections. If defective is false, returns all true transverse intersections.

Definition at line 314 of file intersection-graph.cpp.

References _components, and result.

Referenced by main().

◆ size()

std::size_t Geom::PathIntersectionGraph::size ( ) const

Returns the number of intersections used when computing Boolean operations.

Definition at line 305 of file intersection-graph.cpp.

References _components, result, and Geom::PathVector::size().

Referenced by _getResult(), and _prepareArguments().

◆ valid()

bool Geom::PathIntersectionGraph::valid ( ) const

inline

Definition at line 154 of file intersection-graph.h.

References _graph_valid.

◆ windingPoints()

std::vector< Point > Geom::PathIntersectionGraph::windingPoints ( ) const

inline

Get the geometric points located on path portions between consecutive intersections.

These points were used for the winding number calculations which determined which path portions lie inside the other shape and which lie outside.

Returns: A vector containing all sample points used for winding calculations.

Definition at line 147 of file intersection-graph.h.

References _winding_points.

Friends And Related Symbol Documentation

◆ operator<<

std::ostream & operator<<	(	std::ostream &	os,
		PathIntersectionGraph const &	pig
	)

friend

Format the PathIntersectionGraph for output.

Definition at line 509 of file intersection-graph.cpp.

Member Data Documentation

◆ _components

boost::ptr_vector<PathData> Geom::PathIntersectionGraph::_components[2]

private

Stores the crossing information for the operands.

Definition at line 234 of file intersection-graph.h.

Referenced by _assignComponentStatusFromDegenerateIntersections(), _assignEdgeWindingParities(), _getNeighbor(), _getPathData(), _getResult(), _handleNonintersectingPaths(), _prepareIntersectionLists(), _removeDegenerateIntersections(), _verify(), fragments(), intersectionPoints(), and size().

◆ _graph_valid

bool Geom::PathIntersectionGraph::_graph_valid

private

Whether all intersections are regular.

Definition at line 236 of file intersection-graph.h.

Referenced by _removeDegenerateIntersections(), PathIntersectionGraph(), and valid().

◆ _pv

PathVector Geom::PathIntersectionGraph::_pv[2]

private

Stores the two operand path-vectors, A at _pv[0] and B at _pv[1].

Definition at line 232 of file intersection-graph.h.

Referenced by _assignEdgeWindingParities(), _getResult(), _handleNonintersectingPaths(), _prepareArguments(), _prepareIntersectionLists(), fragments(), and PathIntersectionGraph().

◆ _ulist

UnprocessedList Geom::PathIntersectionGraph::_ulist

private

Temporarily holds all unprocessed during a boolean operation.

Definition at line 235 of file intersection-graph.h.

Referenced by _getResult().

◆ _winding_points

std::vector<Point> Geom::PathIntersectionGraph::_winding_points

private

Stores sample points located on paths of the operand path-vectors, between consecutive intersections.

Definition at line 240 of file intersection-graph.h.

Referenced by _assignEdgeWindingParities(), and windingPoints().

◆ _xs

boost::ptr_vector<IntersectionVertex> Geom::PathIntersectionGraph::_xs

private

Stores all crossings between the two shapes.

Definition at line 233 of file intersection-graph.h.

Referenced by _getResult(), and _prepareIntersectionLists().

The documentation for this class was generated from the following files:

/builds/inkscape/inkscape/src/3rdparty/2geom/include/2geom/intersection-graph.h
/builds/inkscape/inkscape/src/3rdparty/2geom/src/2geom/intersection-graph.cpp

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ CILIter

◆ ILIter

◆ IntersectionList

◆ UnprocessedList

Member Enumeration Documentation

◆ InOutFlag

Constructor & Destructor Documentation

◆ PathIntersectionGraph()

Member Function Documentation

◆ _assignComponentStatusFromDegenerateIntersections()

◆ _assignEdgeWindingParities()

◆ _getNeighbor()

◆ _getPathData()

◆ _getResult()

◆ _handleNonintersectingPaths()

◆ _prepareArguments()

◆ _prepareIntersectionLists()

◆ _removeDegenerateIntersections()

◆ _verify()

◆ fragments()

◆ getAminusB()

◆ getBminusA()

◆ getIntersection()

◆ getUnion()

◆ getXOR()

◆ intersectionPoints()

◆ size()

◆ valid()

◆ windingPoints()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ _components

◆ _graph_valid

◆ _pv

◆ _ulist

◆ _winding_points

◆ _xs