src/clipper.hpp

filter: Statementstmt 100% 2 / 2 Branchbran n/a Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 100% 2 / 2 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« src/myinit.h ↑ Summary src/offset.h »
1 /*******************************************************************************
2 * *
3 * Author : Angus Johnson *
4 * Version : 5.1.5 *
5 * Date : 4 May 2013 *
6 * Website : http://www.angusj.com *
7 * Copyright : Angus Johnson 2010-2013 *
8 * *
9 * License: *
10 * Use, modification & distribution is subject to Boost Software License Ver 1. *
11 * http://www.boost.org/LICENSE_1_0.txt *
12 * *
13 * Attributions: *
14 * The code in this library is an extension of Bala Vatti's clipping algorithm: *
15 * "A generic solution to polygon clipping" *
16 * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
17 * http://portal.acm.org/citation.cfm?id=129906 *
18 * *
19 * Computer graphics and geometric modeling: implementation and algorithms *
20 * By Max K. Agoston *
21 * Springer; 1 edition (January 4, 2005) *
22 * http://books.google.com/books?q=vatti+clipping+agoston *
23 * *
24 * See also: *
25 * "Polygon Offsetting by Computing Winding Numbers" *
26 * Paper no. DETC2005-85513 pp. 565-575 *
27 * ASME 2005 International Design Engineering Technical Conferences *
28 * and Computers and Information in Engineering Conference (IDETC/CIE2005) *
29 * September 24-28, 2005 , Long Beach, California, USA *
30 * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
31 * *
32 *******************************************************************************/
33
34 #ifndef clipper_hpp
35 #define clipper_hpp
36
37 #include <vector>
38 #include <stdexcept>
39 #include <cstring>
40 #include <cstdlib>
41 #include <ostream>
42
43 namespace ClipperLib {
44
45 enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
46 enum PolyType { ptSubject, ptClip };
47 //By far the most widely used winding rules for polygon filling are
48 //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32)
49 //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL)
50 //see http://glprogramming.com/red/chapter11.html
51 enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
52
53 typedef signed long long long64;
54 typedef unsigned long long ulong64;
55
56 struct IntPoint {
57 public:
58 long64 X;
59 long64 Y;
60 1553 IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {};
61 friend std::ostream& operator <<(std::ostream &s, IntPoint &p);
62 };
63
64 typedef std::vector< IntPoint > Polygon;
65 typedef std::vector< Polygon > Polygons;
66
67
68 std::ostream& operator <<(std::ostream &s, Polygon &p);
69 std::ostream& operator <<(std::ostream &s, Polygons &p);
70
71 class PolyNode;
72 typedef std::vector< PolyNode* > PolyNodes;
73
74 class PolyNode
75 {
76 public:
77 PolyNode();
78 Polygon Contour;
79 PolyNodes Childs;
80 PolyNode* Parent;
81 PolyNode* GetNext() const;
82 bool IsHole() const;
83 int ChildCount() const;
84 private:
85 PolyNode* GetNextSiblingUp() const;
86 unsigned Index; //node index in Parent.Childs
87 void AddChild(PolyNode& child);
88 friend class Clipper; //to access Index
89 };
90
91 class PolyTree: public PolyNode
92 {
93 public:
94 6 ~PolyTree(){Clear();};
95 PolyNode* GetFirst() const;
96 void Clear();
97 int Total() const;
98 private:
99 PolyNodes AllNodes;
100 friend class Clipper; //to access AllNodes
101 };
102
103 enum JoinType { jtSquare, jtRound, jtMiter };
104
105 bool Orientation(const Polygon &poly);
106 double Area(const Polygon &poly);
107
108 void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
109 double delta, JoinType jointype = jtSquare, double limit = 0, bool autoFix = true);
110
111 void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
112 void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd);
113 void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd);
114
115 void CleanPolygon(Polygon& in_poly, Polygon& out_poly, double distance = 1.415);
116 void CleanPolygons(Polygons& in_polys, Polygons& out_polys, double distance = 1.415);
117
118 void PolyTreeToPolygons(PolyTree& polytree, Polygons& polygons);
119
120 void ReversePolygon(Polygon& p);
121 void ReversePolygons(Polygons& p);
122
123 //used internally ...
124 enum EdgeSide { esLeft = 1, esRight = 2};
125 enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
126
127 struct TEdge {
128 long64 xbot;
129 long64 ybot;
130 long64 xcurr;
131 long64 ycurr;
132 long64 xtop;
133 long64 ytop;
134 double dx;
135 long64 deltaX;
136 long64 deltaY;
137 PolyType polyType;
138 EdgeSide side;
139 int windDelta; //1 or -1 depending on winding direction
140 int windCnt;
141 int windCnt2; //winding count of the opposite polytype
142 int outIdx;
143 TEdge *next;
144 TEdge *prev;
145 TEdge *nextInLML;
146 TEdge *nextInAEL;
147 TEdge *prevInAEL;
148 TEdge *nextInSEL;
149 TEdge *prevInSEL;
150 };
151
152 struct IntersectNode {
153 TEdge *edge1;
154 TEdge *edge2;
155 IntPoint pt;
156 IntersectNode *next;
157 };
158
159 struct LocalMinima {
160 long64 Y;
161 TEdge *leftBound;
162 TEdge *rightBound;
163 LocalMinima *next;
164 };
165
166 struct Scanbeam {
167 long64 Y;
168 Scanbeam *next;
169 };
170
171 struct OutPt; //forward declaration
172
173 struct OutRec {
174 int idx;
175 bool isHole;
176 OutRec *FirstLeft; //see comments in clipper.pas
177 PolyNode *polyNode;
178 OutPt *pts;
179 OutPt *bottomPt;
180 };
181
182 struct OutPt {
183 int idx;
184 IntPoint pt;
185 OutPt *next;
186 OutPt *prev;
187 };
188
189 struct JoinRec {
190 IntPoint pt1a;
191 IntPoint pt1b;
192 int poly1Idx;
193 IntPoint pt2a;
194 IntPoint pt2b;
195 int poly2Idx;
196 };
197
198 struct HorzJoinRec {
199 TEdge *edge;
200 int savedIdx;
201 };
202
203 struct IntRect { long64 left; long64 top; long64 right; long64 bottom; };
204
205 typedef std::vector < OutRec* > PolyOutList;
206 typedef std::vector < TEdge* > EdgeList;
207 typedef std::vector < JoinRec* > JoinList;
208 typedef std::vector < HorzJoinRec* > HorzJoinList;
209
210 //ClipperBase is the ancestor to the Clipper class. It should not be
211 //instantiated directly. This class simply abstracts the conversion of sets of
212 //polygon coordinates into edge objects that are stored in a LocalMinima list.
213 class ClipperBase
214 {
215 public:
216 ClipperBase();
217 virtual ~ClipperBase();
218 bool AddPolygon(const Polygon &pg, PolyType polyType);
219 bool AddPolygons( const Polygons &ppg, PolyType polyType);
220 virtual void Clear();
221 IntRect GetBounds();
222 protected:
223 void DisposeLocalMinimaList();
224 TEdge* AddBoundsToLML(TEdge *e);
225 void PopLocalMinima();
226 virtual void Reset();
227 void InsertLocalMinima(LocalMinima *newLm);
228 LocalMinima *m_CurrentLM;
229 LocalMinima *m_MinimaList;
230 bool m_UseFullRange;
231 EdgeList m_edges;
232 };
233
234 class Clipper : public virtual ClipperBase
235 {
236 public:
237 Clipper();
238 ~Clipper();
239 bool Execute(ClipType clipType,
240 Polygons &solution,
241 PolyFillType subjFillType = pftEvenOdd,
242 PolyFillType clipFillType = pftEvenOdd);
243 bool Execute(ClipType clipType,
244 PolyTree &polytree,
245 PolyFillType subjFillType = pftEvenOdd,
246 PolyFillType clipFillType = pftEvenOdd);
247 void Clear();
248 bool ReverseSolution() {return m_ReverseOutput;};
249 void ReverseSolution(bool value) {m_ReverseOutput = value;};
250 bool ForceSimple() {return m_ForceSimple;};
251 void ForceSimple(bool value) {m_ForceSimple = value;};
252 protected:
253 void Reset();
254 virtual bool ExecuteInternal();
255 private:
256 PolyOutList m_PolyOuts;
257 JoinList m_Joins;
258 HorzJoinList m_HorizJoins;
259 ClipType m_ClipType;
260 Scanbeam *m_Scanbeam;
261 TEdge *m_ActiveEdges;
262 TEdge *m_SortedEdges;
263 IntersectNode *m_IntersectNodes;
264 bool m_ExecuteLocked;
265 PolyFillType m_ClipFillType;
266 PolyFillType m_SubjFillType;
267 bool m_ReverseOutput;
268 bool m_UsingPolyTree;
269 bool m_ForceSimple;
270 void DisposeScanbeamList();
271 void SetWindingCount(TEdge& edge);
272 bool IsEvenOddFillType(const TEdge& edge) const;
273 bool IsEvenOddAltFillType(const TEdge& edge) const;
274 void InsertScanbeam(const long64 Y);
275 long64 PopScanbeam();
276 void InsertLocalMinimaIntoAEL(const long64 botY);
277 void InsertEdgeIntoAEL(TEdge *edge);
278 void AddEdgeToSEL(TEdge *edge);
279 void CopyAELToSEL();
280 void DeleteFromSEL(TEdge *e);
281 void DeleteFromAEL(TEdge *e);
282 void UpdateEdgeIntoAEL(TEdge *&e);
283 void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2);
284 bool IsContributing(const TEdge& edge) const;
285 bool IsTopHorz(const long64 XPos);
286 void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2);
287 void DoMaxima(TEdge *e, long64 topY);
288 void ProcessHorizontals();
289 void ProcessHorizontal(TEdge *horzEdge);
290 void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
291 void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt);
292 OutRec* GetOutRec(int idx);
293 void AppendPolygon(TEdge *e1, TEdge *e2);
294 void IntersectEdges(TEdge *e1, TEdge *e2,
295 const IntPoint &pt, const IntersectProtects protects);
296 OutRec* CreateOutRec();
297 void AddOutPt(TEdge *e, const IntPoint &pt);
298 void DisposeAllPolyPts();
299 void DisposeOutRec(PolyOutList::size_type index);
300 bool ProcessIntersections(const long64 botY, const long64 topY);
301 void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt);
302 void BuildIntersectList(const long64 botY, const long64 topY);
303 void ProcessIntersectList();
304 void ProcessEdgesAtTopOfScanbeam(const long64 topY);
305 void BuildResult(Polygons& polys);
306 void BuildResult2(PolyTree& polytree);
307 void SetHoleState(TEdge *e, OutRec *outrec);
308 void DisposeIntersectNodes();
309 bool FixupIntersectionOrder();
310 void FixupOutPolygon(OutRec &outrec);
311 bool IsHole(TEdge *e);
312 void FixHoleLinkage(OutRec &outrec);
313 void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1);
314 void ClearJoins();
315 void AddHorzJoin(TEdge *e, int idx);
316 void ClearHorzJoins();
317 bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2);
318 void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx);
319 void JoinCommonEdges();
320 void DoSimplePolygons();
321 void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
322 void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec);
323 };
324
325 //------------------------------------------------------------------------------
326 //------------------------------------------------------------------------------
327
328 class clipperException : public std::exception
329 {
330 public:
331 clipperException(const char* description): m_descr(description) {}
332 virtual ~clipperException() throw() {}
333 virtual const char* what() const throw() {return m_descr.c_str();}
334 private:
335 std::string m_descr;
336 };
337 //------------------------------------------------------------------------------
338
339 } //ClipperLib namespace
340
341 #endif //clipper_hpp
342
343
« src/myinit.h ↑ Summary src/offset.h »