GCC Code Coverage Report

Line	Branch	Exec	Source
1			/**
2			* \file
3			* \brief Path intersection graph
4			*//*
5			* Authors:
6			* Krzysztof Kosiński <tweenk.pl@gmail.com>
7			*
8			* Copyright 2015 Authors
9			*
10			* This library is free software; you can redistribute it and/or
11			* modify it either under the terms of the GNU Lesser General Public
12			* License version 2.1 as published by the Free Software Foundation
13			* (the "LGPL") or, at your option, under the terms of the Mozilla
14			* Public License Version 1.1 (the "MPL"). If you do not alter this
15			* notice, a recipient may use your version of this file under either
16			* the MPL or the LGPL.
17			*
18			* You should have received a copy of the LGPL along with this library
19			* in the file COPYING-LGPL-2.1; if not, write to the Free Software
20			* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21			* You should have received a copy of the MPL along with this library
22			* in the file COPYING-MPL-1.1
23			*
24			* The contents of this file are subject to the Mozilla Public License
25			* Version 1.1 (the "License"); you may not use this file except in
26			* compliance with the License. You may obtain a copy of the License at
27			* http://www.mozilla.org/MPL/
28			*
29			* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30			* OF ANY KIND, either express or implied. See the LGPL or the MPL for
31			* the specific language governing rights and limitations.
32			*/
33
34			#ifndef SEEN_LIB2GEOM_INTERSECTION_GRAPH_H
35			#define SEEN_LIB2GEOM_INTERSECTION_GRAPH_H
36
37			#include <set>
38			#include <vector>
39			#include <boost/ptr_container/ptr_vector.hpp>
40			#include <boost/intrusive/list.hpp>
41			#include <2geom/forward.h>
42			#include <2geom/pathvector.h>
43
44			namespace Geom {
45
46			/** @class PathIntersectionGraph
47			* @brief Intermediate data for computing Boolean operations on paths.
48			*
49			* This class implements the Greiner-Hormann clipping algorithm,
50			* with improvements inspired by Foster and Overfelt as well as some
51			* original contributions.
52			*
53			* For the purposes of boolean operations, a shape is defined as a PathVector
54			* using the "even-odd" rule, i.e., regions with odd winding are considered part
55			* of the shape, whereas regions with even winding are not.
56			*
57			* For this reason, the two path-vectors are sometimes called "shapes" or "operands" of
58			* the boolean operation. Each path-vector may contain several paths, which are called
59			* either "paths" or "components" in the documentation.
60			*
61			* @ingroup Paths
62			*/
63			class PathIntersectionGraph
64			{
65			// this is called PathIntersectionGraph so that we can also have a class for polygons,
66			// e.g. PolygonIntersectionGraph, which is going to be significantly faster
67			public:
68			/** @brief Construct a path intersection graph for two shapes described via their boundaries.
69			* The boundaries are passed as path-vectors.
70			*
71			* @param a – the first operand, also referred to as operand A.
72			* @param b – the second operand, also referred to as operand B.
73			* @param precision – precision setting used for intersection calculations.
74			*/
75			PathIntersectionGraph(PathVector const &a, PathVector const &b, Coord precision = EPSILON);
76
77			/**
78			* @brief Get the union of the shapes, A ∪ B.
79			*
80			* A point belongs to the union if and only if it belongs to at least one of the operands.
81			*
82			* @return A path-vector describing the union of the operands A and B.
83			*/
84			PathVector getUnion();
85
86			/**
87			* @brief Get the intersection of the shapes, A ∩ B.
88			*
89			* A point belongs to the intersection if and only if it belongs to both shapes.
90			*
91			* @return A path-vector describing the intersection of the operands A and B.
92			*/
93			PathVector getIntersection();
94
95			/**
96			* @brief Get the difference of the shapes, A ∖ B.
97			*
98			* A point belongs to the difference if and only if it belongs to A but not to B.
99			*
100			* @return A path-vector describing the difference of the operands A and B.
101			*/
102			PathVector getAminusB();
103
104			/**
105			* @brief Get the opposite difference of the shapes, B ∖ A.
106			*
107			* A point belongs to the difference if and only if it belongs to B but not to A.
108			*
109			* @return A path-vector describing the difference of the operands B and A.
110			*/
111			PathVector getBminusA();
112
113			/**
114			* @brief Get the symmetric difference of the shapes, A ∆ B.
115			*
116			* A point belongs to the symmetric difference if and only if it belongs to one of the two
117			* shapes A or B, but not both. This is equivalent to the logical XOR operation: the elements
118			* of A ∆ B are points which are in A XOR in B.
119			*
120			* @return A path-vector describing the symmetric difference of the operands A and B.
121			*/
122			PathVector getXOR();
123
124			/// Returns the number of intersections used when computing Boolean operations.
125			std::size_t size() const;
126
127			/**
128			* @brief Get the geometric points where the two path-vectors intersect.
129			*
130			* Degenerate intersection points, where the shapes merely "kiss", are not retured.
131			*
132			* @param defective – whether to return only the defective crossings or only the true crossings.
133			* @return If defective is true, returns a vector containing all defective intersection points,
134			* i.e., points that are neither true transverse intersections nor degenerate intersections.
135			* If defective is false, returns all true transverse intersections.
136			*/
137			std::vector<Point> intersectionPoints(bool defective = false) const;
138
139			/**
140			* @brief Get the geometric points located on path portions between consecutive intersections.
141			*
142			* These points were used for the winding number calculations which determined which path portions
143			* lie inside the other shape and which lie outside.
144			*
145			* @return A vector containing all sample points used for winding calculations.
146			*/
147			std::vector<Point> windingPoints() const {
148			return _winding_points;
149			}
150
151			void fragments(PathVector &in, PathVector &out) const;
152
153
154			bool valid() const { return _graph_valid; }
155
156			private:
157			enum InOutFlag {
158			INSIDE,
159			OUTSIDE,
160			BOTH
161			};
162
163			struct IntersectionVertex {
164			boost::intrusive::list_member_hook<> _hook;
165			boost::intrusive::list_member_hook<> _proc_hook;
166			PathVectorTime pos; ///< Intersection time.
167			Point p; ///< Geometric position of the intersection point; guarantees that endpoints are exact.
168			IntersectionVertex *neighbor; ///< A pointer to the corresponding vertex on the other shape.
169			/** Tells us whether the edge originating at this intersection lies inside or outside of
170			* the shape given by the other path-vector. The "edge originating" at this intersection is
171			* the portion of the path between this intersection and the next intersection, in the
172			* direction of increasing path time. */
173			InOutFlag next_edge;
174			unsigned which; ///< Index of the operand path-vector that this intersection vertex lies on.
175			/** Whether the intersection is defective, which means that for some reason the paths
176			* neither cross transversally through each other nor "kiss" at a common tangency point.
177			*/
178			bool defective;
179			};
180
181			typedef boost::intrusive::list
182			< IntersectionVertex
183			, boost::intrusive::member_hook
184			< IntersectionVertex
185			, boost::intrusive::list_member_hook<>
186			, &IntersectionVertex::_hook
187			>
188			> IntersectionList;
189
190			typedef boost::intrusive::list
191			< IntersectionVertex
192			, boost::intrusive::member_hook
193			< IntersectionVertex
194			, boost::intrusive::list_member_hook<>
195			, &IntersectionVertex::_proc_hook
196			>
197			> UnprocessedList;
198
199			/// Stores processed intersection information for a single path in an operand path-vector.
200			struct PathData {
201			IntersectionList xlist; ///< List of crossings on this particular path.
202			std::size_t path_index; ///< Index of the path in its path-vector.
203			int which; ///< Index of the path-vector (in PathIntersectionGraph::_pv) that the path belongs to.
204			/** Whether this path as a whole is contained INSIDE or OUTSIDE relative to the other path-vector.
205			* The value BOTH means that some portions of the path are inside while others are outside.
206			*/
207			InOutFlag status;
208
209		8	PathData(int w, std::size_t pi)
210		16	: path_index(pi)
211		8	, which(w)
212		8	, status(BOTH)
213		8	{}
214			};
215
216			struct IntersectionVertexLess;
217			typedef IntersectionList::iterator ILIter;
218			typedef IntersectionList::const_iterator CILIter;
219
220			PathVector _getResult(bool enter_a, bool enter_b);
221			void _handleNonintersectingPaths(PathVector &result, unsigned which, bool inside);
222			void _prepareArguments();
223			bool _prepareIntersectionLists(Coord precision);
224			void _assignEdgeWindingParities(Coord precision);
225			void _assignComponentStatusFromDegenerateIntersections();
226			void _removeDegenerateIntersections();
227			void _verify();
228
229			ILIter _getNeighbor(ILIter iter);
230			PathData &_getPathData(ILIter iter);
231
232			PathVector _pv[2]; ///< Stores the two operand path-vectors, A at _pv[0] and B at _pv[1].
233			boost::ptr_vector<IntersectionVertex> _xs; ///< Stores all crossings between the two shapes.
234			boost::ptr_vector<PathData> _components[2]; ///< Stores the crossing information for the operands.
235			UnprocessedList _ulist; ///< Temporarily holds all unprocessed during a boolean operation.
236			bool _graph_valid; ///< Whether all intersections are regular.
237			/** Stores sample points located on paths of the operand path-vectors,
238			* between consecutive intersections.
239			*/
240			std::vector<Point> _winding_points;
241
242			friend std::ostream &operator<<(std::ostream &, PathIntersectionGraph const &);
243			};
244
245			std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig);
246
247			} // namespace Geom
248
249			#endif // SEEN_LIB2GEOM_PATH_GRAPH_H
250			/*
251			Local Variables:
252			mode:c++
253			c-file-style:"stroustrup"
254			c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
255			indent-tabs-mode:nil
256			fill-column:99
257			End:
258			*/
259			// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
260