1 /*******************************************************************************
2 * *
3 * Author : Angus Johnson *
4 * Version : 6.2.9 *
5 * Date : 16 February 2015 *
6 * Website : http://www.angusj.com *
7 * Copyright : Angus Johnson 2010-2015 *
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 /*******************************************************************************
35 * *
36 * This is a translation of the Delphi Clipper library and the naming style *
37 * used has retained a Delphi flavour. *
38 * *
39 *******************************************************************************/
40
41 #include "clipper.hpp"
42 #include <cmath>
43 #include <vector>
44 #include <algorithm>
45 #include <stdexcept>
46 #include <cstring>
47 #include <cstdlib>
48 #include <ostream>
49 #include <functional>
50 #include <assert.h>
51 #include <libslic3r/Int128.hpp>
52
53 // Profiling support using the Shiny intrusive profiler
54 //#define CLIPPERLIB_PROFILE
55 #if defined(SLIC3R_PROFILE) && defined(CLIPPERLIB_PROFILE)
56 #include <Shiny/Shiny.h>
57 #define CLIPPERLIB_PROFILE_FUNC() PROFILE_FUNC()
58 #define CLIPPERLIB_PROFILE_BLOCK(name) PROFILE_BLOCK(name)
59 #else
60 #define CLIPPERLIB_PROFILE_FUNC()
61 #define CLIPPERLIB_PROFILE_BLOCK(name)
62 #endif
63
64 #ifdef use_xyz
65 namespace ClipperLib_Z {
66 #else /* use_xyz */
67 namespace ClipperLib {
68 #endif /* use_xyz */
69
70 static double const pi = 3.141592653589793238;
71 static double const two_pi = pi *2;
72 static double const def_arc_tolerance = 0.25;
73
74 enum Direction { dRightToLeft, dLeftToRight };
75
76 static int const Unassigned = -1; //edge not currently 'owning' a solution
77 static int const Skip = -2; //edge that would otherwise close a path
78
79 #define HORIZONTAL (-1.0E+40)
80 #define TOLERANCE (1.0e-20)
81 #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))
82
83 // Output polygon.
84 struct OutRec {
85 int Idx;
86 bool IsHole;
87 bool IsOpen;
88 //The 'FirstLeft' field points to another OutRec that contains or is the
89 //'parent' of OutRec. It is 'first left' because the ActiveEdgeList (AEL) is
90 //parsed left from the current edge (owning OutRec) until the owner OutRec
91 //is found. This field simplifies sorting the polygons into a tree structure
92 //which reflects the parent/child relationships of all polygons.
93 //This field should be renamed Parent, and will be later.
94 OutRec *FirstLeft;
95 // Used only by void Clipper::BuildResult2(PolyTree& polytree)
96 PolyNode *PolyNd;
97 // Linked list of output points, dynamically allocated.
98 OutPt *Pts;
99 OutPt *BottomPt;
100 };
101
102 //------------------------------------------------------------------------------
103
Round(double val)104 inline cInt Round(double val)
105 {
106 return static_cast<cInt>((val < 0) ? (val - 0.5) : (val + 0.5));
107 }
108
109 //------------------------------------------------------------------------------
110 // PolyTree methods ...
111 //------------------------------------------------------------------------------
112
Total() const113 int PolyTree::Total() const
114 {
115 int result = (int)AllNodes.size();
116 //with negative offsets, ignore the hidden outer polygon ...
117 if (result > 0 && Childs.front() != &AllNodes.front()) result--;
118 return result;
119 }
120
121 //------------------------------------------------------------------------------
122 // PolyNode methods ...
123 //------------------------------------------------------------------------------
124
AddChild(PolyNode & child)125 void PolyNode::AddChild(PolyNode& child)
126 {
127 unsigned cnt = (unsigned)Childs.size();
128 Childs.push_back(&child);
129 child.Parent = this;
130 child.Index = cnt;
131 }
132 //------------------------------------------------------------------------------
133
134 // Edge delimits a hole if it has an odd number of parent loops.
IsHole() const135 bool PolyNode::IsHole() const
136 {
137 bool result = true;
138 PolyNode* node = Parent;
139 while (node)
140 {
141 result = !result;
142 node = node->Parent;
143 }
144 return result;
145 }
146
147 //------------------------------------------------------------------------------
148 // Miscellaneous global functions
149 //------------------------------------------------------------------------------
150
Area(const Path & poly)151 double Area(const Path &poly)
152 {
153 int size = (int)poly.size();
154 if (size < 3) return 0;
155
156 double a = 0;
157 for (int i = 0, j = size -1; i < size; ++i)
158 {
159 a += ((double)poly[j].X + poly[i].X) * ((double)poly[j].Y - poly[i].Y);
160 j = i;
161 }
162 return -a * 0.5;
163 }
164 //------------------------------------------------------------------------------
165
Area(const OutRec & outRec)166 double Area(const OutRec &outRec)
167 {
168 OutPt *op = outRec.Pts;
169 if (!op) return 0;
170 double a = 0;
171 do {
172 a += (double)(op->Prev->Pt.X + op->Pt.X) * (double)(op->Prev->Pt.Y - op->Pt.Y);
173 op = op->Next;
174 } while (op != outRec.Pts);
175 return a * 0.5;
176 }
177 //------------------------------------------------------------------------------
178
PointIsVertex(const IntPoint & Pt,OutPt * pp)179 bool PointIsVertex(const IntPoint &Pt, OutPt *pp)
180 {
181 OutPt *pp2 = pp;
182 do
183 {
184 if (pp2->Pt == Pt) return true;
185 pp2 = pp2->Next;
186 }
187 while (pp2 != pp);
188 return false;
189 }
190 //------------------------------------------------------------------------------
191
192 //See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
193 //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
PointInPolygon(const IntPoint & pt,const Path & path)194 int PointInPolygon(const IntPoint &pt, const Path &path)
195 {
196 //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
197 int result = 0;
198 size_t cnt = path.size();
199 if (cnt < 3) return 0;
200 IntPoint ip = path[0];
201 for(size_t i = 1; i <= cnt; ++i)
202 {
203 IntPoint ipNext = (i == cnt ? path[0] : path[i]);
204 if (ipNext.Y == pt.Y && ((ipNext.X == pt.X) || (ip.Y == pt.Y && ((ipNext.X > pt.X) == (ip.X < pt.X)))))
205 return -1;
206 if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
207 {
208 if (ip.X >= pt.X)
209 {
210 if (ipNext.X > pt.X) result = 1 - result;
211 else
212 {
213 double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
214 if (!d) return -1;
215 if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
216 }
217 } else
218 {
219 if (ipNext.X > pt.X)
220 {
221 double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
222 if (!d) return -1;
223 if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
224 }
225 }
226 }
227 ip = ipNext;
228 }
229 return result;
230 }
231 //------------------------------------------------------------------------------
232
233 // Called by Poly2ContainsPoly1()
PointInPolygon(const IntPoint & pt,OutPt * op)234 int PointInPolygon (const IntPoint &pt, OutPt *op)
235 {
236 //returns 0 if false, +1 if true, -1 if pt ON polygon boundary
237 int result = 0;
238 OutPt* startOp = op;
239 do
240 {
241 if (op->Next->Pt.Y == pt.Y)
242 {
243 if ((op->Next->Pt.X == pt.X) || (op->Pt.Y == pt.Y &&
244 ((op->Next->Pt.X > pt.X) == (op->Pt.X < pt.X)))) return -1;
245 }
246 if ((op->Pt.Y < pt.Y) != (op->Next->Pt.Y < pt.Y))
247 {
248 if (op->Pt.X >= pt.X)
249 {
250 if (op->Next->Pt.X > pt.X) result = 1 - result;
251 else
252 {
253 double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) - (double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
254 if (!d) return -1;
255 if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
256 }
257 } else
258 {
259 if (op->Next->Pt.X > pt.X)
260 {
261 double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) - (double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
262 if (!d) return -1;
263 if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
264 }
265 }
266 }
267 op = op->Next;
268 } while (startOp != op);
269 return result;
270 }
271 //------------------------------------------------------------------------------
272
273 // This is potentially very expensive! O(n^2)!
Poly2ContainsPoly1(OutPt * OutPt1,OutPt * OutPt2)274 bool Poly2ContainsPoly1(OutPt *OutPt1, OutPt *OutPt2)
275 {
276 CLIPPERLIB_PROFILE_FUNC();
277 OutPt* op = OutPt1;
278 do
279 {
280 //nb: PointInPolygon returns 0 if false, +1 if true, -1 if pt on polygon
281 int res = PointInPolygon(op->Pt, OutPt2);
282 if (res >= 0) return res > 0;
283 op = op->Next;
284 }
285 while (op != OutPt1);
286 return true;
287 }
288 //----------------------------------------------------------------------
289
SlopesEqual(const cInt dx1,const cInt dy1,const cInt dx2,const cInt dy2,bool UseFullInt64Range)290 inline bool SlopesEqual(const cInt dx1, const cInt dy1, const cInt dx2, const cInt dy2, bool UseFullInt64Range) {
291 return (UseFullInt64Range) ?
292 // |dx1| < 2^63, |dx2| < 2^63 etc,
293 Int128::sign_determinant_2x2_filtered(dx1, dy1, dx2, dy2) == 0 :
294 // Int128::sign_determinant_2x2(dx1, dy1, dx2, dy2) == 0 :
295 // |dx1| < 2^31, |dx2| < 2^31 etc,
296 // therefore the following computation could be done with 64bit arithmetics.
297 dy1 * dx2 == dx1 * dy2;
298 }
SlopesEqual(const TEdge & e1,const TEdge & e2,bool UseFullInt64Range)299 inline bool SlopesEqual(const TEdge &e1, const TEdge &e2, bool UseFullInt64Range)
300 { return SlopesEqual(e1.Delta.X, e1.Delta.Y, e2.Delta.X, e2.Delta.Y, UseFullInt64Range); }
SlopesEqual(const IntPoint & pt1,const IntPoint & pt2,const IntPoint & pt3,bool UseFullInt64Range)301 inline bool SlopesEqual(const IntPoint &pt1, const IntPoint &pt2, const IntPoint &pt3, bool UseFullInt64Range)
302 { return SlopesEqual(pt1.X-pt2.X, pt1.Y-pt2.Y, pt2.X-pt3.X, pt2.Y-pt3.Y, UseFullInt64Range); }
SlopesEqual(const IntPoint & pt1,const IntPoint & pt2,const IntPoint & pt3,const IntPoint & pt4,bool UseFullInt64Range)303 inline bool SlopesEqual(const IntPoint &pt1, const IntPoint &pt2, const IntPoint &pt3, const IntPoint &pt4, bool UseFullInt64Range)
304 { return SlopesEqual(pt1.X-pt2.X, pt1.Y-pt2.Y, pt3.X-pt4.X, pt3.Y-pt4.Y, UseFullInt64Range); }
305
306 //------------------------------------------------------------------------------
307
IsHorizontal(TEdge & e)308 inline bool IsHorizontal(TEdge &e)
309 {
310 return e.Delta.Y == 0;
311 }
312 //------------------------------------------------------------------------------
313
GetDx(const IntPoint & pt1,const IntPoint & pt2)314 inline double GetDx(const IntPoint &pt1, const IntPoint &pt2)
315 {
316 return (pt1.Y == pt2.Y) ?
317 HORIZONTAL : (double)(pt2.X - pt1.X) / (pt2.Y - pt1.Y);
318 }
319 //---------------------------------------------------------------------------
320
TopX(TEdge & edge,const cInt currentY)321 inline cInt TopX(TEdge &edge, const cInt currentY)
322 {
323 return (currentY == edge.Top.Y) ?
324 edge.Top.X :
325 edge.Bot.X + Round(edge.Dx *(currentY - edge.Bot.Y));
326 }
327 //------------------------------------------------------------------------------
328
IntersectPoint(TEdge & Edge1,TEdge & Edge2,IntPoint & ip)329 void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip)
330 {
331 #ifdef use_xyz
332 ip.Z = 0;
333 #endif
334
335 double b1, b2;
336 if (Edge1.Dx == Edge2.Dx)
337 {
338 ip.Y = Edge1.Curr.Y;
339 ip.X = TopX(Edge1, ip.Y);
340 return;
341 }
342 else if (Edge1.Delta.X == 0)
343 {
344 ip.X = Edge1.Bot.X;
345 if (IsHorizontal(Edge2))
346 ip.Y = Edge2.Bot.Y;
347 else
348 {
349 b2 = Edge2.Bot.Y - (Edge2.Bot.X / Edge2.Dx);
350 ip.Y = Round(ip.X / Edge2.Dx + b2);
351 }
352 }
353 else if (Edge2.Delta.X == 0)
354 {
355 ip.X = Edge2.Bot.X;
356 if (IsHorizontal(Edge1))
357 ip.Y = Edge1.Bot.Y;
358 else
359 {
360 b1 = Edge1.Bot.Y - (Edge1.Bot.X / Edge1.Dx);
361 ip.Y = Round(ip.X / Edge1.Dx + b1);
362 }
363 }
364 else
365 {
366 b1 = Edge1.Bot.X - Edge1.Bot.Y * Edge1.Dx;
367 b2 = Edge2.Bot.X - Edge2.Bot.Y * Edge2.Dx;
368 double q = (b2-b1) / (Edge1.Dx - Edge2.Dx);
369 ip.Y = Round(q);
370 ip.X = (std::fabs(Edge1.Dx) < std::fabs(Edge2.Dx)) ?
371 Round(Edge1.Dx * q + b1) :
372 Round(Edge2.Dx * q + b2);
373 }
374
375 if (ip.Y < Edge1.Top.Y || ip.Y < Edge2.Top.Y)
376 {
377 if (Edge1.Top.Y > Edge2.Top.Y)
378 ip.Y = Edge1.Top.Y;
379 else
380 ip.Y = Edge2.Top.Y;
381 if (std::fabs(Edge1.Dx) < std::fabs(Edge2.Dx))
382 ip.X = TopX(Edge1, ip.Y);
383 else
384 ip.X = TopX(Edge2, ip.Y);
385 }
386 //finally, don't allow 'ip' to be BELOW curr.Y (ie bottom of scanbeam) ...
387 if (ip.Y > Edge1.Curr.Y)
388 {
389 ip.Y = Edge1.Curr.Y;
390 //use the more vertical edge to derive X ...
391 if (std::fabs(Edge1.Dx) > std::fabs(Edge2.Dx))
392 ip.X = TopX(Edge2, ip.Y); else
393 ip.X = TopX(Edge1, ip.Y);
394 }
395 }
396 //------------------------------------------------------------------------------
397
398 // Reverse a linked loop of points representing a closed polygon.
399 // This has a time complexity of O(n)
ReversePolyPtLinks(OutPt * pp)400 void ReversePolyPtLinks(OutPt *pp)
401 {
402 if (!pp) return;
403 OutPt *pp1 = pp;
404 do {
405 OutPt *pp2 = pp1->Next;
406 pp1->Next = pp1->Prev;
407 pp1->Prev = pp2;
408 pp1 = pp2;
409 } while( pp1 != pp );
410 }
411 //------------------------------------------------------------------------------
412
InitEdge(TEdge * e,TEdge * eNext,TEdge * ePrev,const IntPoint & Pt)413 inline void InitEdge(TEdge* e, TEdge* eNext, TEdge* ePrev, const IntPoint& Pt)
414 {
415 std::memset(e, 0, sizeof(TEdge));
416 e->Next = eNext;
417 e->Prev = ePrev;
418 e->Curr = Pt;
419 e->OutIdx = Unassigned;
420 }
421 //------------------------------------------------------------------------------
422
InitEdge2(TEdge & e,PolyType Pt)423 void InitEdge2(TEdge& e, PolyType Pt)
424 {
425 if (e.Curr.Y >= e.Next->Curr.Y)
426 {
427 e.Bot = e.Curr;
428 e.Top = e.Next->Curr;
429 } else
430 {
431 e.Top = e.Curr;
432 e.Bot = e.Next->Curr;
433 }
434
435 e.Delta.X = (e.Top.X - e.Bot.X);
436 e.Delta.Y = (e.Top.Y - e.Bot.Y);
437
438 if (e.Delta.Y == 0) e.Dx = HORIZONTAL;
439 else e.Dx = (double)(e.Delta.X) / e.Delta.Y;
440
441 e.PolyTyp = Pt;
442 }
443 //------------------------------------------------------------------------------
444
445 // Called from ClipperBase::AddPathInternal() to remove collinear and duplicate points.
RemoveEdge(TEdge * e)446 inline TEdge* RemoveEdge(TEdge* e)
447 {
448 //removes e from double_linked_list (but without removing from memory)
449 e->Prev->Next = e->Next;
450 e->Next->Prev = e->Prev;
451 TEdge* result = e->Next;
452 e->Prev = 0; //flag as removed (see ClipperBase.Clear)
453 return result;
454 }
455 //------------------------------------------------------------------------------
456
ReverseHorizontal(TEdge & e)457 inline void ReverseHorizontal(TEdge &e)
458 {
459 //swap horizontal edges' Top and Bottom x's so they follow the natural
460 //progression of the bounds - ie so their xbots will align with the
461 //adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
462 std::swap(e.Top.X, e.Bot.X);
463 #ifdef use_xyz
464 std::swap(e.Top.Z, e.Bot.Z);
465 #endif
466 }
467 //------------------------------------------------------------------------------
468
GetOverlapSegment(IntPoint pt1a,IntPoint pt1b,IntPoint pt2a,IntPoint pt2b,IntPoint & pt1,IntPoint & pt2)469 bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
470 IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
471 {
472 //precondition: segments are Collinear.
473 if (std::abs(pt1a.X - pt1b.X) > std::abs(pt1a.Y - pt1b.Y))
474 {
475 if (pt1a.X > pt1b.X) std::swap(pt1a, pt1b);
476 if (pt2a.X > pt2b.X) std::swap(pt2a, pt2b);
477 if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
478 if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
479 return pt1.X < pt2.X;
480 } else
481 {
482 if (pt1a.Y < pt1b.Y) std::swap(pt1a, pt1b);
483 if (pt2a.Y < pt2b.Y) std::swap(pt2a, pt2b);
484 if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
485 if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
486 return pt1.Y > pt2.Y;
487 }
488 }
489 //------------------------------------------------------------------------------
490
FirstIsBottomPt(const OutPt * btmPt1,const OutPt * btmPt2)491 bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
492 {
493 OutPt *p = btmPt1->Prev;
494 while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Prev;
495 double dx1p = std::fabs(GetDx(btmPt1->Pt, p->Pt));
496 p = btmPt1->Next;
497 while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Next;
498 double dx1n = std::fabs(GetDx(btmPt1->Pt, p->Pt));
499
500 p = btmPt2->Prev;
501 while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Prev;
502 double dx2p = std::fabs(GetDx(btmPt2->Pt, p->Pt));
503 p = btmPt2->Next;
504 while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Next;
505 double dx2n = std::fabs(GetDx(btmPt2->Pt, p->Pt));
506 return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
507 }
508 //------------------------------------------------------------------------------
509
510 // Called by GetLowermostRec()
GetBottomPt(OutPt * pp)511 OutPt* GetBottomPt(OutPt *pp)
512 {
513 OutPt* dups = 0;
514 OutPt* p = pp->Next;
515 while (p != pp)
516 {
517 if (p->Pt.Y > pp->Pt.Y)
518 {
519 pp = p;
520 dups = 0;
521 }
522 else if (p->Pt.Y == pp->Pt.Y && p->Pt.X <= pp->Pt.X)
523 {
524 if (p->Pt.X < pp->Pt.X)
525 {
526 dups = 0;
527 pp = p;
528 } else
529 {
530 if (p->Next != pp && p->Prev != pp) dups = p;
531 }
532 }
533 p = p->Next;
534 }
535 if (dups)
536 {
537 //there appears to be at least 2 vertices at BottomPt so ...
538 while (dups != p)
539 {
540 if (!FirstIsBottomPt(p, dups)) pp = dups;
541 dups = dups->Next;
542 while (dups->Pt != pp->Pt) dups = dups->Next;
543 }
544 }
545 return pp;
546 }
547 //------------------------------------------------------------------------------
548
Pt2IsBetweenPt1AndPt3(const IntPoint & pt1,const IntPoint & pt2,const IntPoint & pt3)549 bool Pt2IsBetweenPt1AndPt3(const IntPoint &pt1,
550 const IntPoint &pt2, const IntPoint &pt3)
551 {
552 if ((pt1 == pt3) || (pt1 == pt2) || (pt3 == pt2))
553 return false;
554 else if (pt1.X != pt3.X)
555 return (pt2.X > pt1.X) == (pt2.X < pt3.X);
556 else
557 return (pt2.Y > pt1.Y) == (pt2.Y < pt3.Y);
558 }
559 //------------------------------------------------------------------------------
560
HorzSegmentsOverlap(cInt seg1a,cInt seg1b,cInt seg2a,cInt seg2b)561 bool HorzSegmentsOverlap(cInt seg1a, cInt seg1b, cInt seg2a, cInt seg2b)
562 {
563 if (seg1a > seg1b) std::swap(seg1a, seg1b);
564 if (seg2a > seg2b) std::swap(seg2a, seg2b);
565 return (seg1a < seg2b) && (seg2a < seg1b);
566 }
567
568 //------------------------------------------------------------------------------
569 // ClipperBase class methods ...
570 //------------------------------------------------------------------------------
571
572 // Called from ClipperBase::AddPath() to verify the scale of the input polygon coordinates.
RangeTest(const IntPoint & Pt,bool & useFullRange)573 inline void RangeTest(const IntPoint& Pt, bool& useFullRange)
574 {
575 if (useFullRange)
576 {
577 if (Pt.X > hiRange || Pt.Y > hiRange || -Pt.X > hiRange || -Pt.Y > hiRange)
578 throw clipperException("Coordinate outside allowed range");
579 }
580 else if (Pt.X > loRange|| Pt.Y > loRange || -Pt.X > loRange || -Pt.Y > loRange)
581 {
582 useFullRange = true;
583 RangeTest(Pt, useFullRange);
584 }
585 }
586 //------------------------------------------------------------------------------
587
588 // Called from ClipperBase::AddPath() to construct the Local Minima List.
589 // Find a local minimum edge on the path starting with E.
FindNextLocMin(TEdge * E)590 inline TEdge* FindNextLocMin(TEdge* E)
591 {
592 for (;;)
593 {
594 while (E->Bot != E->Prev->Bot || E->Curr == E->Top) E = E->Next;
595 if (!IsHorizontal(*E) && !IsHorizontal(*E->Prev)) break;
596 while (IsHorizontal(*E->Prev)) E = E->Prev;
597 TEdge* E2 = E;
598 while (IsHorizontal(*E)) E = E->Next;
599 if (E->Top.Y == E->Prev->Bot.Y) continue; //ie just an intermediate horz.
600 if (E2->Prev->Bot.X < E->Bot.X) E = E2;
601 break;
602 }
603 return E;
604 }
605 //------------------------------------------------------------------------------
606
607 // Called from ClipperBase::AddPath().
ProcessBound(TEdge * E,bool NextIsForward)608 TEdge* ClipperBase::ProcessBound(TEdge* E, bool NextIsForward)
609 {
610 TEdge *Result = E;
611 TEdge *Horz = 0;
612
613 if (E->OutIdx == Skip)
614 {
615 //if edges still remain in the current bound beyond the skip edge then
616 //create another LocMin and call ProcessBound once more
617 if (NextIsForward)
618 {
619 while (E->Top.Y == E->Next->Bot.Y) E = E->Next;
620 //don't include top horizontals when parsing a bound a second time,
621 //they will be contained in the opposite bound ...
622 while (E != Result && IsHorizontal(*E)) E = E->Prev;
623 }
624 else
625 {
626 while (E->Top.Y == E->Prev->Bot.Y) E = E->Prev;
627 while (E != Result && IsHorizontal(*E)) E = E->Next;
628 }
629
630 if (E == Result)
631 {
632 if (NextIsForward) Result = E->Next;
633 else Result = E->Prev;
634 }
635 else
636 {
637 //there are more edges in the bound beyond result starting with E
638 if (NextIsForward)
639 E = Result->Next;
640 else
641 E = Result->Prev;
642 LocalMinimum locMin;
643 locMin.Y = E->Bot.Y;
644 locMin.LeftBound = 0;
645 locMin.RightBound = E;
646 E->WindDelta = 0;
647 Result = ProcessBound(E, NextIsForward);
648 m_MinimaList.push_back(locMin);
649 }
650 return Result;
651 }
652
653 TEdge *EStart;
654
655 if (IsHorizontal(*E))
656 {
657 //We need to be careful with open paths because this may not be a
658 //true local minima (ie E may be following a skip edge).
659 //Also, consecutive horz. edges may start heading left before going right.
660 if (NextIsForward)
661 EStart = E->Prev;
662 else
663 EStart = E->Next;
664 if (IsHorizontal(*EStart)) //ie an adjoining horizontal skip edge
665 {
666 if (EStart->Bot.X != E->Bot.X && EStart->Top.X != E->Bot.X)
667 ReverseHorizontal(*E);
668 }
669 else if (EStart->Bot.X != E->Bot.X)
670 ReverseHorizontal(*E);
671 }
672
673 EStart = E;
674 if (NextIsForward)
675 {
676 while (Result->Top.Y == Result->Next->Bot.Y && Result->Next->OutIdx != Skip)
677 Result = Result->Next;
678 if (IsHorizontal(*Result) && Result->Next->OutIdx != Skip)
679 {
680 //nb: at the top of a bound, horizontals are added to the bound
681 //only when the preceding edge attaches to the horizontal's left vertex
682 //unless a Skip edge is encountered when that becomes the top divide
683 Horz = Result;
684 while (IsHorizontal(*Horz->Prev)) Horz = Horz->Prev;
685 if (Horz->Prev->Top.X > Result->Next->Top.X) Result = Horz->Prev;
686 }
687 while (E != Result)
688 {
689 E->NextInLML = E->Next;
690 if (IsHorizontal(*E) && E != EStart &&
691 E->Bot.X != E->Prev->Top.X) ReverseHorizontal(*E);
692 E = E->Next;
693 }
694 if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Prev->Top.X)
695 ReverseHorizontal(*E);
696 Result = Result->Next; //move to the edge just beyond current bound
697 } else
698 {
699 while (Result->Top.Y == Result->Prev->Bot.Y && Result->Prev->OutIdx != Skip)
700 Result = Result->Prev;
701 if (IsHorizontal(*Result) && Result->Prev->OutIdx != Skip)
702 {
703 Horz = Result;
704 while (IsHorizontal(*Horz->Next)) Horz = Horz->Next;
705 if (Horz->Next->Top.X == Result->Prev->Top.X ||
706 Horz->Next->Top.X > Result->Prev->Top.X) Result = Horz->Next;
707 }
708
709 while (E != Result)
710 {
711 E->NextInLML = E->Prev;
712 if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Next->Top.X)
713 ReverseHorizontal(*E);
714 E = E->Prev;
715 }
716 if (IsHorizontal(*E) && E != EStart && E->Bot.X != E->Next->Top.X)
717 ReverseHorizontal(*E);
718 Result = Result->Prev; //move to the edge just beyond current bound
719 }
720
721 return Result;
722 }
723 //------------------------------------------------------------------------------
724
AddPath(const Path & pg,PolyType PolyTyp,bool Closed)725 bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
726 {
727 CLIPPERLIB_PROFILE_FUNC();
728 // Remove duplicate end point from a closed input path.
729 // Remove duplicate points from the end of the input path.
730 int highI = (int)pg.size() -1;
731 if (Closed)
732 while (highI > 0 && (pg[highI] == pg[0]))
733 --highI;
734 while (highI > 0 && (pg[highI] == pg[highI -1]))
735 --highI;
736 if ((Closed && highI < 2) || (!Closed && highI < 1))
737 return false;
738
739 // Allocate a new edge array.
740 std::vector<TEdge> edges(highI + 1);
741 // Fill in the edge array.
742 bool result = AddPathInternal(pg, highI, PolyTyp, Closed, edges.data());
743 if (result)
744 // Success, remember the edge array.
745 m_edges.emplace_back(std::move(edges));
746 return result;
747 }
748
AddPaths(const Paths & ppg,PolyType PolyTyp,bool Closed)749 bool ClipperBase::AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed)
750 {
751 CLIPPERLIB_PROFILE_FUNC();
752 std::vector<int> num_edges(ppg.size(), 0);
753 int num_edges_total = 0;
754 for (size_t i = 0; i < ppg.size(); ++ i) {
755 const Path &pg = ppg[i];
756 // Remove duplicate end point from a closed input path.
757 // Remove duplicate points from the end of the input path.
758 int highI = (int)pg.size() -1;
759 if (Closed)
760 while (highI > 0 && (pg[highI] == pg[0]))
761 --highI;
762 while (highI > 0 && (pg[highI] == pg[highI -1]))
763 --highI;
764 if ((Closed && highI < 2) || (!Closed && highI < 1))
765 highI = -1;
766 num_edges[i] = highI + 1;
767 num_edges_total += highI + 1;
768 }
769 if (num_edges_total == 0)
770 return false;
771
772 // Allocate a new edge array.
773 std::vector<TEdge> edges(num_edges_total);
774 // Fill in the edge array.
775 bool result = false;
776 TEdge *p_edge = edges.data();
777 for (Paths::size_type i = 0; i < ppg.size(); ++i)
778 if (num_edges[i]) {
779 bool res = AddPathInternal(ppg[i], num_edges[i] - 1, PolyTyp, Closed, p_edge);
780 if (res) {
781 p_edge += num_edges[i];
782 result = true;
783 }
784 }
785 if (result)
786 // At least some edges were generated. Remember the edge array.
787 m_edges.emplace_back(std::move(edges));
788 return result;
789 }
790
AddPathInternal(const Path & pg,int highI,PolyType PolyTyp,bool Closed,TEdge * edges)791 bool ClipperBase::AddPathInternal(const Path &pg, int highI, PolyType PolyTyp, bool Closed, TEdge* edges)
792 {
793 CLIPPERLIB_PROFILE_FUNC();
794 #ifdef use_lines
795 if (!Closed && PolyTyp == ptClip)
796 throw clipperException("AddPath: Open paths must be subject.");
797 #else
798 if (!Closed)
799 throw clipperException("AddPath: Open paths have been disabled.");
800 #endif
801
802 assert(highI >= 0 && highI < pg.size());
803
804 //1. Basic (first) edge initialization ...
805 try
806 {
807 edges[1].Curr = pg[1];
808 RangeTest(pg[0], m_UseFullRange);
809 RangeTest(pg[highI], m_UseFullRange);
810 InitEdge(&edges[0], &edges[1], &edges[highI], pg[0]);
811 InitEdge(&edges[highI], &edges[0], &edges[highI-1], pg[highI]);
812 for (int i = highI - 1; i >= 1; --i)
813 {
814 RangeTest(pg[i], m_UseFullRange);
815 InitEdge(&edges[i], &edges[i+1], &edges[i-1], pg[i]);
816 }
817 }
818 catch(...)
819 {
820 throw; //range test fails
821 }
822 TEdge *eStart = &edges[0];
823
824 //2. Remove duplicate vertices, and (when closed) collinear edges ...
825 TEdge *E = eStart, *eLoopStop = eStart;
826 for (;;)
827 {
828 //nb: allows matching start and end points when not Closed ...
829 if (E->Curr == E->Next->Curr && (Closed || E->Next != eStart))
830 {
831 if (E == E->Next) break;
832 if (E == eStart) eStart = E->Next;
833 E = RemoveEdge(E);
834 eLoopStop = E;
835 continue;
836 }
837 if (E->Prev == E->Next)
838 break; //only two vertices
839 else if (Closed &&
840 SlopesEqual(E->Prev->Curr, E->Curr, E->Next->Curr, m_UseFullRange) &&
841 (!m_PreserveCollinear ||
842 !Pt2IsBetweenPt1AndPt3(E->Prev->Curr, E->Curr, E->Next->Curr)))
843 {
844 //Collinear edges are allowed for open paths but in closed paths
845 //the default is to merge adjacent collinear edges into a single edge.
846 //However, if the PreserveCollinear property is enabled, only overlapping
847 //collinear edges (ie spikes) will be removed from closed paths.
848 if (E == eStart) eStart = E->Next;
849 E = RemoveEdge(E);
850 E = E->Prev;
851 eLoopStop = E;
852 continue;
853 }
854 E = E->Next;
855 if ((E == eLoopStop) || (!Closed && E->Next == eStart)) break;
856 }
857
858 if ((!Closed && (E == E->Next)) || (Closed && (E->Prev == E->Next)))
859 {
860 return false;
861 }
862
863 if (!Closed)
864 {
865 m_HasOpenPaths = true;
866 eStart->Prev->OutIdx = Skip;
867 }
868
869 //3. Do second stage of edge initialization ...
870 // IsFlat means all vertices have the same Y coordinate.
871 bool IsFlat = true;
872 E = eStart;
873 do
874 {
875 InitEdge2(*E, PolyTyp);
876 E = E->Next;
877 if (IsFlat && E->Curr.Y != eStart->Curr.Y) IsFlat = false;
878 }
879 while (E != eStart);
880
881 //4. Finally, add edge bounds to LocalMinima list ...
882
883 //Totally flat paths must be handled differently when adding them
884 //to LocalMinima list to avoid endless loops etc ...
885 if (IsFlat)
886 {
887 if (Closed)
888 {
889 return false;
890 }
891 E->Prev->OutIdx = Skip;
892 LocalMinimum locMin;
893 locMin.Y = E->Bot.Y;
894 locMin.LeftBound = 0;
895 locMin.RightBound = E;
896 locMin.RightBound->Side = esRight;
897 locMin.RightBound->WindDelta = 0;
898 for (;;)
899 {
900 if (E->Bot.X != E->Prev->Top.X) ReverseHorizontal(*E);
901 if (E->Next->OutIdx == Skip) break;
902 E->NextInLML = E->Next;
903 E = E->Next;
904 }
905 m_MinimaList.push_back(locMin);
906 return true;
907 }
908
909 bool leftBoundIsForward;
910 TEdge* EMin = 0;
911
912 //workaround to avoid an endless loop in the while loop below when
913 //open paths have matching start and end points ...
914 if (E->Prev->Bot == E->Prev->Top) E = E->Next;
915
916 // Find local minima and store them into a Local Minima List.
917 // Multiple Local Minima could be created for a single path.
918 for (;;)
919 {
920 E = FindNextLocMin(E);
921 if (E == EMin) break;
922 else if (!EMin) EMin = E;
923
924 //E and E.Prev now share a local minima (left aligned if horizontal).
925 //Compare their slopes to find which starts which bound ...
926 LocalMinimum locMin;
927 locMin.Y = E->Bot.Y;
928 if (E->Dx < E->Prev->Dx)
929 {
930 locMin.LeftBound = E->Prev;
931 locMin.RightBound = E;
932 leftBoundIsForward = false; //Q.nextInLML = Q.prev
933 } else
934 {
935 locMin.LeftBound = E;
936 locMin.RightBound = E->Prev;
937 leftBoundIsForward = true; //Q.nextInLML = Q.next
938 }
939 locMin.LeftBound->Side = esLeft;
940 locMin.RightBound->Side = esRight;
941
942 if (!Closed) locMin.LeftBound->WindDelta = 0;
943 else if (locMin.LeftBound->Next == locMin.RightBound)
944 locMin.LeftBound->WindDelta = -1;
945 else locMin.LeftBound->WindDelta = 1;
946 locMin.RightBound->WindDelta = -locMin.LeftBound->WindDelta;
947
948 E = ProcessBound(locMin.LeftBound, leftBoundIsForward);
949 if (E->OutIdx == Skip) E = ProcessBound(E, leftBoundIsForward);
950
951 TEdge* E2 = ProcessBound(locMin.RightBound, !leftBoundIsForward);
952 if (E2->OutIdx == Skip) E2 = ProcessBound(E2, !leftBoundIsForward);
953
954 if (locMin.LeftBound->OutIdx == Skip)
955 locMin.LeftBound = 0;
956 else if (locMin.RightBound->OutIdx == Skip)
957 locMin.RightBound = 0;
958 m_MinimaList.push_back(locMin);
959 if (!leftBoundIsForward) E = E2;
960 }
961 return true;
962 }
963 //------------------------------------------------------------------------------
964
Clear()965 void ClipperBase::Clear()
966 {
967 CLIPPERLIB_PROFILE_FUNC();
968 m_MinimaList.clear();
969 m_edges.clear();
970 m_UseFullRange = false;
971 m_HasOpenPaths = false;
972 }
973 //------------------------------------------------------------------------------
974
975 // Initialize the Local Minima List:
976 // Sort the LML entries, initialize the left / right bound edges of each Local Minima.
Reset()977 void ClipperBase::Reset()
978 {
979 CLIPPERLIB_PROFILE_FUNC();
980 if (m_MinimaList.empty()) return; //ie nothing to process
981 std::sort(m_MinimaList.begin(), m_MinimaList.end(), [](const LocalMinimum& lm1, const LocalMinimum& lm2){ return lm1.Y < lm2.Y; });
982
983 //reset all edges ...
984 for (LocalMinimum &lm : m_MinimaList) {
985 TEdge* e = lm.LeftBound;
986 if (e)
987 {
988 e->Curr = e->Bot;
989 e->Side = esLeft;
990 e->OutIdx = Unassigned;
991 }
992
993 e = lm.RightBound;
994 if (e)
995 {
996 e->Curr = e->Bot;
997 e->Side = esRight;
998 e->OutIdx = Unassigned;
999 }
1000 }
1001 }
1002 //------------------------------------------------------------------------------
1003
1004 // Get bounds of the edges referenced by the Local Minima List.
1005 // Returns (0,0,0,0) for an empty rectangle.
GetBounds()1006 IntRect ClipperBase::GetBounds()
1007 {
1008 CLIPPERLIB_PROFILE_FUNC();
1009 IntRect result;
1010 auto lm = m_MinimaList.begin();
1011 if (lm == m_MinimaList.end())
1012 {
1013 result.left = result.top = result.right = result.bottom = 0;
1014 return result;
1015 }
1016 result.left = lm->LeftBound->Bot.X;
1017 result.top = lm->LeftBound->Bot.Y;
1018 result.right = lm->LeftBound->Bot.X;
1019 result.bottom = lm->LeftBound->Bot.Y;
1020 while (lm != m_MinimaList.end())
1021 {
1022 result.bottom = std::max(result.bottom, lm->LeftBound->Bot.Y);
1023 TEdge* e = lm->LeftBound;
1024 for (;;) {
1025 TEdge* bottomE = e;
1026 while (e->NextInLML)
1027 {
1028 if (e->Bot.X < result.left) result.left = e->Bot.X;
1029 if (e->Bot.X > result.right) result.right = e->Bot.X;
1030 e = e->NextInLML;
1031 }
1032 result.left = std::min(result.left, e->Bot.X);
1033 result.right = std::max(result.right, e->Bot.X);
1034 result.left = std::min(result.left, e->Top.X);
1035 result.right = std::max(result.right, e->Top.X);
1036 result.top = std::min(result.top, e->Top.Y);
1037 if (bottomE == lm->LeftBound) e = lm->RightBound;
1038 else break;
1039 }
1040 ++lm;
1041 }
1042 return result;
1043 }
1044
1045 //------------------------------------------------------------------------------
1046 // TClipper methods ...
1047 //------------------------------------------------------------------------------
1048
Clipper(int initOptions)1049 Clipper::Clipper(int initOptions) :
1050 ClipperBase(),
1051 m_OutPtsFree(nullptr),
1052 m_OutPtsChunkSize(32),
1053 m_OutPtsChunkLast(32),
1054 m_ActiveEdges(nullptr),
1055 m_SortedEdges(nullptr)
1056 {
1057 m_ReverseOutput = ((initOptions & ioReverseSolution) != 0);
1058 m_StrictSimple = ((initOptions & ioStrictlySimple) != 0);
1059 m_PreserveCollinear = ((initOptions & ioPreserveCollinear) != 0);
1060 m_HasOpenPaths = false;
1061 #ifdef use_xyz
1062 m_ZFill = 0;
1063 #endif
1064 }
1065 //------------------------------------------------------------------------------
1066
Reset()1067 void Clipper::Reset()
1068 {
1069 CLIPPERLIB_PROFILE_FUNC();
1070 ClipperBase::Reset();
1071 m_Scanbeam = std::priority_queue<cInt>();
1072 m_Maxima.clear();
1073 m_ActiveEdges = 0;
1074 m_SortedEdges = 0;
1075 for (auto lm = m_MinimaList.rbegin(); lm != m_MinimaList.rend(); ++lm)
1076 m_Scanbeam.push(lm->Y);
1077 }
1078
1079 //------------------------------------------------------------------------------
1080
Execute(ClipType clipType,Paths & solution,PolyFillType subjFillType,PolyFillType clipFillType)1081 bool Clipper::Execute(ClipType clipType, Paths &solution,
1082 PolyFillType subjFillType, PolyFillType clipFillType)
1083 {
1084 CLIPPERLIB_PROFILE_FUNC();
1085 if (m_HasOpenPaths)
1086 throw clipperException("Error: PolyTree struct is needed for open path clipping.");
1087 solution.resize(0);
1088 m_SubjFillType = subjFillType;
1089 m_ClipFillType = clipFillType;
1090 m_ClipType = clipType;
1091 m_UsingPolyTree = false;
1092 bool succeeded = ExecuteInternal();
1093 if (succeeded) BuildResult(solution);
1094 DisposeAllOutRecs();
1095 return succeeded;
1096 }
1097 //------------------------------------------------------------------------------
1098
Execute(ClipType clipType,PolyTree & polytree,PolyFillType subjFillType,PolyFillType clipFillType)1099 bool Clipper::Execute(ClipType clipType, PolyTree& polytree,
1100 PolyFillType subjFillType, PolyFillType clipFillType)
1101 {
1102 CLIPPERLIB_PROFILE_FUNC();
1103 m_SubjFillType = subjFillType;
1104 m_ClipFillType = clipFillType;
1105 m_ClipType = clipType;
1106 m_UsingPolyTree = true;
1107 bool succeeded = ExecuteInternal();
1108 if (succeeded) BuildResult2(polytree);
1109 DisposeAllOutRecs();
1110 return succeeded;
1111 }
1112 //------------------------------------------------------------------------------
1113
ExecuteInternal()1114 bool Clipper::ExecuteInternal()
1115 {
1116 CLIPPERLIB_PROFILE_FUNC();
1117 bool succeeded = true;
1118 try {
1119 CLIPPERLIB_PROFILE_BLOCK(Clipper_ExecuteInternal_Process);
1120 Reset();
1121 if (m_MinimaList.empty()) return true;
1122 cInt botY = m_Scanbeam.top();
1123 do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && botY == m_Scanbeam.top());
1124 do {
1125 InsertLocalMinimaIntoAEL(botY);
1126 ProcessHorizontals();
1127 m_GhostJoins.clear();
1128 if (m_Scanbeam.empty()) break;
1129 cInt topY = m_Scanbeam.top();
1130 do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && topY == m_Scanbeam.top());
1131 succeeded = ProcessIntersections(topY);
1132 if (!succeeded) break;
1133 ProcessEdgesAtTopOfScanbeam(topY);
1134 botY = topY;
1135 } while (!m_Scanbeam.empty() || !m_MinimaList.empty());
1136 }
1137 catch(...)
1138 {
1139 succeeded = false;
1140 }
1141
1142 if (succeeded)
1143 {
1144 CLIPPERLIB_PROFILE_BLOCK(Clipper_ExecuteInternal_Fix);
1145
1146 //fix orientations ...
1147 //FIXME Vojtech: Does it not invalidate the loop hierarchy maintained as OutRec::FirstLeft pointers?
1148 //FIXME Vojtech: The area is calculated with floats, it may not be numerically stable!
1149 {
1150 CLIPPERLIB_PROFILE_BLOCK(Clipper_ExecuteInternal_Fix_orientations);
1151 for (OutRec *outRec : m_PolyOuts)
1152 if (outRec->Pts && !outRec->IsOpen && (outRec->IsHole ^ m_ReverseOutput) == (Area(*outRec) > 0))
1153 ReversePolyPtLinks(outRec->Pts);
1154 }
1155
1156 JoinCommonEdges();
1157
1158 //unfortunately FixupOutPolygon() must be done after JoinCommonEdges()
1159 {
1160 CLIPPERLIB_PROFILE_BLOCK(Clipper_ExecuteInternal_Fix_fixup);
1161 for (OutRec *outRec : m_PolyOuts)
1162 if (outRec->Pts) {
1163 if (outRec->IsOpen)
1164 // Removes duplicate points.
1165 FixupOutPolyline(*outRec);
1166 else
1167 // Removes duplicate points and simplifies consecutive parallel edges by removing the middle vertex.
1168 FixupOutPolygon(*outRec);
1169 }
1170 }
1171 // For each polygon, search for exactly duplicate non-successive points.
1172 // If such a point is found, the loop is split into two pieces.
1173 // Search for the duplicate points is O(n^2)!
1174 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/Clipper/Properties/StrictlySimple.htm
1175 if (m_StrictSimple) DoSimplePolygons();
1176 }
1177
1178 m_Joins.clear();
1179 m_GhostJoins.clear();
1180 return succeeded;
1181 }
1182 //------------------------------------------------------------------------------
1183
AllocateOutPt()1184 OutPt* Clipper::AllocateOutPt()
1185 {
1186 OutPt *pt;
1187 if (m_OutPtsFree) {
1188 // Recycle some of the already released points.
1189 pt = m_OutPtsFree;
1190 m_OutPtsFree = pt->Next;
1191 } else if (m_OutPtsChunkLast < m_OutPtsChunkSize) {
1192 // Get a point from the last chunk.
1193 pt = m_OutPts.back() + (m_OutPtsChunkLast ++);
1194 } else {
1195 // The last chunk is full. Allocate a new one.
1196 m_OutPts.push_back(new OutPt[m_OutPtsChunkSize]);
1197 m_OutPtsChunkLast = 1;
1198 pt = m_OutPts.back();
1199 }
1200 return pt;
1201 }
1202
DisposeAllOutRecs()1203 void Clipper::DisposeAllOutRecs()
1204 {
1205 for (OutPt *pts : m_OutPts)
1206 delete[] pts;
1207 for (OutRec *rec : m_PolyOuts)
1208 delete rec;
1209 m_OutPts.clear();
1210 m_OutPtsFree = nullptr;
1211 m_OutPtsChunkLast = m_OutPtsChunkSize;
1212 m_PolyOuts.clear();
1213 }
1214 //------------------------------------------------------------------------------
1215
SetWindingCount(TEdge & edge) const1216 void Clipper::SetWindingCount(TEdge &edge) const
1217 {
1218 TEdge *e = edge.PrevInAEL;
1219 //find the edge of the same polytype that immediately preceeds 'edge' in AEL
1220 while (e && ((e->PolyTyp != edge.PolyTyp) || (e->WindDelta == 0))) e = e->PrevInAEL;
1221 if (!e)
1222 {
1223 edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
1224 edge.WindCnt2 = 0;
1225 e = m_ActiveEdges; //ie get ready to calc WindCnt2
1226 }
1227 else if (edge.WindDelta == 0 && m_ClipType != ctUnion)
1228 {
1229 edge.WindCnt = 1;
1230 edge.WindCnt2 = e->WindCnt2;
1231 e = e->NextInAEL; //ie get ready to calc WindCnt2
1232 }
1233 else if (IsEvenOddFillType(edge))
1234 {
1235 //EvenOdd filling ...
1236 if (edge.WindDelta == 0)
1237 {
1238 //are we inside a subj polygon ...
1239 bool Inside = true;
1240 TEdge *e2 = e->PrevInAEL;
1241 while (e2)
1242 {
1243 if (e2->PolyTyp == e->PolyTyp && e2->WindDelta != 0)
1244 Inside = !Inside;
1245 e2 = e2->PrevInAEL;
1246 }
1247 edge.WindCnt = (Inside ? 0 : 1);
1248 }
1249 else
1250 {
1251 edge.WindCnt = edge.WindDelta;
1252 }
1253 edge.WindCnt2 = e->WindCnt2;
1254 e = e->NextInAEL; //ie get ready to calc WindCnt2
1255 }
1256 else
1257 {
1258 //nonZero, Positive or Negative filling ...
1259 if (e->WindCnt * e->WindDelta < 0)
1260 {
1261 //prev edge is 'decreasing' WindCount (WC) toward zero
1262 //so we're outside the previous polygon ...
1263 if (std::abs(e->WindCnt) > 1)
1264 {
1265 //outside prev poly but still inside another.
1266 //when reversing direction of prev poly use the same WC
1267 if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
1268 //otherwise continue to 'decrease' WC ...
1269 else edge.WindCnt = e->WindCnt + edge.WindDelta;
1270 }
1271 else
1272 //now outside all polys of same polytype so set own WC ...
1273 edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
1274 } else
1275 {
1276 //prev edge is 'increasing' WindCount (WC) away from zero
1277 //so we're inside the previous polygon ...
1278 if (edge.WindDelta == 0)
1279 edge.WindCnt = (e->WindCnt < 0 ? e->WindCnt - 1 : e->WindCnt + 1);
1280 //if wind direction is reversing prev then use same WC
1281 else if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
1282 //otherwise add to WC ...
1283 else edge.WindCnt = e->WindCnt + edge.WindDelta;
1284 }
1285 edge.WindCnt2 = e->WindCnt2;
1286 e = e->NextInAEL; //ie get ready to calc WindCnt2
1287 }
1288
1289 //update WindCnt2 ...
1290 if (IsEvenOddAltFillType(edge))
1291 {
1292 //EvenOdd filling ...
1293 while (e != &edge)
1294 {
1295 if (e->WindDelta != 0)
1296 edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);
1297 e = e->NextInAEL;
1298 }
1299 } else
1300 {
1301 //nonZero, Positive or Negative filling ...
1302 while ( e != &edge )
1303 {
1304 edge.WindCnt2 += e->WindDelta;
1305 e = e->NextInAEL;
1306 }
1307 }
1308 }
1309 //------------------------------------------------------------------------------
1310
IsContributing(const TEdge & edge) const1311 bool Clipper::IsContributing(const TEdge& edge) const
1312 {
1313 PolyFillType pft, pft2;
1314 if (edge.PolyTyp == ptSubject)
1315 {
1316 pft = m_SubjFillType;
1317 pft2 = m_ClipFillType;
1318 } else
1319 {
1320 pft = m_ClipFillType;
1321 pft2 = m_SubjFillType;
1322 }
1323
1324 switch(pft)
1325 {
1326 case pftEvenOdd:
1327 //return false if a subj line has been flagged as inside a subj polygon
1328 if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;
1329 break;
1330 case pftNonZero:
1331 if (std::abs(edge.WindCnt) != 1) return false;
1332 break;
1333 case pftPositive:
1334 if (edge.WindCnt != 1) return false;
1335 break;
1336 default: //pftNegative
1337 if (edge.WindCnt != -1) return false;
1338 }
1339
1340 switch(m_ClipType)
1341 {
1342 case ctIntersection:
1343 switch(pft2)
1344 {
1345 case pftEvenOdd:
1346 case pftNonZero:
1347 return (edge.WindCnt2 != 0);
1348 case pftPositive:
1349 return (edge.WindCnt2 > 0);
1350 default:
1351 return (edge.WindCnt2 < 0);
1352 }
1353 break;
1354 case ctUnion:
1355 switch(pft2)
1356 {
1357 case pftEvenOdd:
1358 case pftNonZero:
1359 return (edge.WindCnt2 == 0);
1360 case pftPositive:
1361 return (edge.WindCnt2 <= 0);
1362 default:
1363 return (edge.WindCnt2 >= 0);
1364 }
1365 break;
1366 case ctDifference:
1367 if (edge.PolyTyp == ptSubject)
1368 switch(pft2)
1369 {
1370 case pftEvenOdd:
1371 case pftNonZero:
1372 return (edge.WindCnt2 == 0);
1373 case pftPositive:
1374 return (edge.WindCnt2 <= 0);
1375 default:
1376 return (edge.WindCnt2 >= 0);
1377 }
1378 else
1379 switch(pft2)
1380 {
1381 case pftEvenOdd:
1382 case pftNonZero:
1383 return (edge.WindCnt2 != 0);
1384 case pftPositive:
1385 return (edge.WindCnt2 > 0);
1386 default:
1387 return (edge.WindCnt2 < 0);
1388 }
1389 break;
1390 case ctXor:
1391 if (edge.WindDelta == 0) //XOr always contributing unless open
1392 switch(pft2)
1393 {
1394 case pftEvenOdd:
1395 case pftNonZero:
1396 return (edge.WindCnt2 == 0);
1397 case pftPositive:
1398 return (edge.WindCnt2 <= 0);
1399 default:
1400 return (edge.WindCnt2 >= 0);
1401 }
1402 else
1403 return true;
1404 break;
1405 default:
1406 return true;
1407 }
1408 }
1409 //------------------------------------------------------------------------------
1410
1411 // Called from Clipper::InsertLocalMinimaIntoAEL() and Clipper::IntersectEdges().
AddLocalMinPoly(TEdge * e1,TEdge * e2,const IntPoint & Pt)1412 OutPt* Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
1413 {
1414 CLIPPERLIB_PROFILE_FUNC();
1415 OutPt* result;
1416 TEdge *e, *prevE;
1417 if (IsHorizontal(*e2) || ( e1->Dx > e2->Dx ))
1418 {
1419 result = AddOutPt(e1, Pt);
1420 e2->OutIdx = e1->OutIdx;
1421 e1->Side = esLeft;
1422 e2->Side = esRight;
1423 e = e1;
1424 if (e->PrevInAEL == e2)
1425 prevE = e2->PrevInAEL;
1426 else
1427 prevE = e->PrevInAEL;
1428 } else
1429 {
1430 result = AddOutPt(e2, Pt);
1431 e1->OutIdx = e2->OutIdx;
1432 e1->Side = esRight;
1433 e2->Side = esLeft;
1434 e = e2;
1435 if (e->PrevInAEL == e1)
1436 prevE = e1->PrevInAEL;
1437 else
1438 prevE = e->PrevInAEL;
1439 }
1440
1441 if (prevE && prevE->OutIdx >= 0 &&
1442 (TopX(*prevE, Pt.Y) == TopX(*e, Pt.Y)) &&
1443 SlopesEqual(*e, *prevE, m_UseFullRange) &&
1444 (e->WindDelta != 0) && (prevE->WindDelta != 0))
1445 {
1446 OutPt* outPt = AddOutPt(prevE, Pt);
1447 m_Joins.emplace_back(Join(result, outPt, e->Top));
1448 }
1449 return result;
1450 }
1451 //------------------------------------------------------------------------------
1452
AddLocalMaxPoly(TEdge * e1,TEdge * e2,const IntPoint & Pt)1453 void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
1454 {
1455 AddOutPt( e1, Pt );
1456 if (e2->WindDelta == 0) AddOutPt(e2, Pt);
1457 if( e1->OutIdx == e2->OutIdx )
1458 {
1459 e1->OutIdx = Unassigned;
1460 e2->OutIdx = Unassigned;
1461 }
1462 else if (e1->OutIdx < e2->OutIdx)
1463 AppendPolygon(e1, e2);
1464 else
1465 AppendPolygon(e2, e1);
1466 }
1467 //------------------------------------------------------------------------------
1468
AddEdgeToSEL(TEdge * edge)1469 void Clipper::AddEdgeToSEL(TEdge *edge)
1470 {
1471 //SEL pointers in PEdge are reused to build a list of horizontal edges.
1472 //However, we don't need to worry about order with horizontal edge processing.
1473 if( !m_SortedEdges )
1474 {
1475 m_SortedEdges = edge;
1476 edge->PrevInSEL = 0;
1477 edge->NextInSEL = 0;
1478 }
1479 else
1480 {
1481 edge->NextInSEL = m_SortedEdges;
1482 edge->PrevInSEL = 0;
1483 m_SortedEdges->PrevInSEL = edge;
1484 m_SortedEdges = edge;
1485 }
1486 }
1487 //------------------------------------------------------------------------------
1488
CopyAELToSEL()1489 void Clipper::CopyAELToSEL()
1490 {
1491 TEdge* e = m_ActiveEdges;
1492 m_SortedEdges = e;
1493 while ( e )
1494 {
1495 e->PrevInSEL = e->PrevInAEL;
1496 e->NextInSEL = e->NextInAEL;
1497 e = e->NextInAEL;
1498 }
1499 }
1500
1501 //------------------------------------------------------------------------------
1502
1503 // Called from Clipper::ExecuteInternal()
InsertLocalMinimaIntoAEL(const cInt botY)1504 void Clipper::InsertLocalMinimaIntoAEL(const cInt botY)
1505 {
1506 CLIPPERLIB_PROFILE_FUNC();
1507 while (!m_MinimaList.empty() && m_MinimaList.back().Y == botY)
1508 {
1509 TEdge* lb = m_MinimaList.back().LeftBound;
1510 TEdge* rb = m_MinimaList.back().RightBound;
1511 m_MinimaList.pop_back();
1512
1513 OutPt *Op1 = 0;
1514 if (!lb)
1515 {
1516 //nb: don't insert LB into either AEL or SEL
1517 InsertEdgeIntoAEL(rb, 0);
1518 SetWindingCount(*rb);
1519 if (IsContributing(*rb))
1520 Op1 = AddOutPt(rb, rb->Bot);
1521 }
1522 else if (!rb)
1523 {
1524 InsertEdgeIntoAEL(lb, 0);
1525 SetWindingCount(*lb);
1526 if (IsContributing(*lb))
1527 Op1 = AddOutPt(lb, lb->Bot);
1528 m_Scanbeam.push(lb->Top.Y);
1529 }
1530 else
1531 {
1532 InsertEdgeIntoAEL(lb, 0);
1533 InsertEdgeIntoAEL(rb, lb);
1534 SetWindingCount( *lb );
1535 rb->WindCnt = lb->WindCnt;
1536 rb->WindCnt2 = lb->WindCnt2;
1537 if (IsContributing(*lb))
1538 Op1 = AddLocalMinPoly(lb, rb, lb->Bot);
1539 m_Scanbeam.push(lb->Top.Y);
1540 }
1541
1542 if (rb)
1543 {
1544 if(IsHorizontal(*rb)) AddEdgeToSEL(rb);
1545 else m_Scanbeam.push(rb->Top.Y);
1546 }
1547
1548 if (!lb || !rb) continue;
1549
1550 //if any output polygons share an edge, they'll need joining later ...
1551 if (Op1 && IsHorizontal(*rb) &&
1552 m_GhostJoins.size() > 0 && (rb->WindDelta != 0))
1553 {
1554 for (Join &jr : m_GhostJoins)
1555 //if the horizontal Rb and a 'ghost' horizontal overlap, then convert
1556 //the 'ghost' join to a real join ready for later ...
1557 if (HorzSegmentsOverlap(jr.OutPt1->Pt.X, jr.OffPt.X, rb->Bot.X, rb->Top.X))
1558 m_Joins.emplace_back(Join(jr.OutPt1, Op1, jr.OffPt));
1559 }
1560
1561 if (lb->OutIdx >= 0 && lb->PrevInAEL &&
1562 lb->PrevInAEL->Curr.X == lb->Bot.X &&
1563 lb->PrevInAEL->OutIdx >= 0 &&
1564 SlopesEqual(*lb->PrevInAEL, *lb, m_UseFullRange) &&
1565 (lb->WindDelta != 0) && (lb->PrevInAEL->WindDelta != 0))
1566 {
1567 OutPt *Op2 = AddOutPt(lb->PrevInAEL, lb->Bot);
1568 m_Joins.emplace_back(Join(Op1, Op2, lb->Top));
1569 }
1570
1571 if(lb->NextInAEL != rb)
1572 {
1573
1574 if (rb->OutIdx >= 0 && rb->PrevInAEL->OutIdx >= 0 &&
1575 SlopesEqual(*rb->PrevInAEL, *rb, m_UseFullRange) &&
1576 (rb->WindDelta != 0) && (rb->PrevInAEL->WindDelta != 0))
1577 {
1578 OutPt *Op2 = AddOutPt(rb->PrevInAEL, rb->Bot);
1579 m_Joins.emplace_back(Join(Op1, Op2, rb->Top));
1580 }
1581
1582 TEdge* e = lb->NextInAEL;
1583 if (e)
1584 {
1585 while( e != rb )
1586 {
1587 //nb: For calculating winding counts etc, IntersectEdges() assumes
1588 //that param1 will be to the Right of param2 ABOVE the intersection ...
1589 IntersectEdges(rb , e , lb->Curr); //order important here
1590 e = e->NextInAEL;
1591 }
1592 }
1593 }
1594
1595 }
1596 }
1597 //------------------------------------------------------------------------------
1598
DeleteFromAEL(TEdge * e)1599 void Clipper::DeleteFromAEL(TEdge *e)
1600 {
1601 TEdge* AelPrev = e->PrevInAEL;
1602 TEdge* AelNext = e->NextInAEL;
1603 if( !AelPrev && !AelNext && (e != m_ActiveEdges) ) return; //already deleted
1604 if( AelPrev ) AelPrev->NextInAEL = AelNext;
1605 else m_ActiveEdges = AelNext;
1606 if( AelNext ) AelNext->PrevInAEL = AelPrev;
1607 e->NextInAEL = 0;
1608 e->PrevInAEL = 0;
1609 }
1610 //------------------------------------------------------------------------------
1611
DeleteFromSEL(TEdge * e)1612 void Clipper::DeleteFromSEL(TEdge *e)
1613 {
1614 TEdge* SelPrev = e->PrevInSEL;
1615 TEdge* SelNext = e->NextInSEL;
1616 if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted
1617 if( SelPrev ) SelPrev->NextInSEL = SelNext;
1618 else m_SortedEdges = SelNext;
1619 if( SelNext ) SelNext->PrevInSEL = SelPrev;
1620 e->NextInSEL = 0;
1621 e->PrevInSEL = 0;
1622 }
1623 //------------------------------------------------------------------------------
1624
1625 #ifdef use_xyz
SetZ(IntPoint & pt,TEdge & e1,TEdge & e2)1626 void Clipper::SetZ(IntPoint& pt, TEdge& e1, TEdge& e2)
1627 {
1628 if (pt.Z != 0 || !m_ZFill) return;
1629 else if (pt == e1.Bot) pt.Z = e1.Bot.Z;
1630 else if (pt == e1.Top) pt.Z = e1.Top.Z;
1631 else if (pt == e2.Bot) pt.Z = e2.Bot.Z;
1632 else if (pt == e2.Top) pt.Z = e2.Top.Z;
1633 else m_ZFill(e1.Bot, e1.Top, e2.Bot, e2.Top, pt);
1634 }
1635 //------------------------------------------------------------------------------
1636 #endif
1637
IntersectEdges(TEdge * e1,TEdge * e2,IntPoint & Pt)1638 void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
1639 {
1640 bool e1Contributing = ( e1->OutIdx >= 0 );
1641 bool e2Contributing = ( e2->OutIdx >= 0 );
1642
1643 #ifdef use_xyz
1644 SetZ(Pt, *e1, *e2);
1645 #endif
1646
1647 #ifdef use_lines
1648 //if either edge is on an OPEN path ...
1649 if (e1->WindDelta == 0 || e2->WindDelta == 0)
1650 {
1651 //ignore subject-subject open path intersections UNLESS they
1652 //are both open paths, AND they are both 'contributing maximas' ...
1653 if (e1->WindDelta == 0 && e2->WindDelta == 0) return;
1654
1655 //if intersecting a subj line with a subj poly ...
1656 else if (e1->PolyTyp == e2->PolyTyp &&
1657 e1->WindDelta != e2->WindDelta && m_ClipType == ctUnion)
1658 {
1659 if (e1->WindDelta == 0)
1660 {
1661 if (e2Contributing)
1662 {
1663 AddOutPt(e1, Pt);
1664 if (e1Contributing) e1->OutIdx = Unassigned;
1665 }
1666 }
1667 else
1668 {
1669 if (e1Contributing)
1670 {
1671 AddOutPt(e2, Pt);
1672 if (e2Contributing) e2->OutIdx = Unassigned;
1673 }
1674 }
1675 }
1676 else if (e1->PolyTyp != e2->PolyTyp)
1677 {
1678 //toggle subj open path OutIdx on/off when Abs(clip.WndCnt) == 1 ...
1679 if ((e1->WindDelta == 0) && std::abs(e2->WindCnt) == 1 &&
1680 (m_ClipType != ctUnion || e2->WindCnt2 == 0))
1681 {
1682 AddOutPt(e1, Pt);
1683 if (e1Contributing) e1->OutIdx = Unassigned;
1684 }
1685 else if ((e2->WindDelta == 0) && (std::abs(e1->WindCnt) == 1) &&
1686 (m_ClipType != ctUnion || e1->WindCnt2 == 0))
1687 {
1688 AddOutPt(e2, Pt);
1689 if (e2Contributing) e2->OutIdx = Unassigned;
1690 }
1691 }
1692 return;
1693 }
1694 #endif
1695
1696 //update winding counts...
1697 //assumes that e1 will be to the Right of e2 ABOVE the intersection
1698 if ( e1->PolyTyp == e2->PolyTyp )
1699 {
1700 if ( IsEvenOddFillType( *e1) )
1701 {
1702 int oldE1WindCnt = e1->WindCnt;
1703 e1->WindCnt = e2->WindCnt;
1704 e2->WindCnt = oldE1WindCnt;
1705 } else
1706 {
1707 if (e1->WindCnt + e2->WindDelta == 0 ) e1->WindCnt = -e1->WindCnt;
1708 else e1->WindCnt += e2->WindDelta;
1709 if ( e2->WindCnt - e1->WindDelta == 0 ) e2->WindCnt = -e2->WindCnt;
1710 else e2->WindCnt -= e1->WindDelta;
1711 }
1712 } else
1713 {
1714 if (!IsEvenOddFillType(*e2)) e1->WindCnt2 += e2->WindDelta;
1715 else e1->WindCnt2 = ( e1->WindCnt2 == 0 ) ? 1 : 0;
1716 if (!IsEvenOddFillType(*e1)) e2->WindCnt2 -= e1->WindDelta;
1717 else e2->WindCnt2 = ( e2->WindCnt2 == 0 ) ? 1 : 0;
1718 }
1719
1720 PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
1721 if (e1->PolyTyp == ptSubject)
1722 {
1723 e1FillType = m_SubjFillType;
1724 e1FillType2 = m_ClipFillType;
1725 } else
1726 {
1727 e1FillType = m_ClipFillType;
1728 e1FillType2 = m_SubjFillType;
1729 }
1730 if (e2->PolyTyp == ptSubject)
1731 {
1732 e2FillType = m_SubjFillType;
1733 e2FillType2 = m_ClipFillType;
1734 } else
1735 {
1736 e2FillType = m_ClipFillType;
1737 e2FillType2 = m_SubjFillType;
1738 }
1739
1740 cInt e1Wc, e2Wc;
1741 switch (e1FillType)
1742 {
1743 case pftPositive: e1Wc = e1->WindCnt; break;
1744 case pftNegative: e1Wc = -e1->WindCnt; break;
1745 default: e1Wc = std::abs(e1->WindCnt);
1746 }
1747 switch(e2FillType)
1748 {
1749 case pftPositive: e2Wc = e2->WindCnt; break;
1750 case pftNegative: e2Wc = -e2->WindCnt; break;
1751 default: e2Wc = std::abs(e2->WindCnt);
1752 }
1753
1754 if ( e1Contributing && e2Contributing )
1755 {
1756 if ((e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
1757 (e1->PolyTyp != e2->PolyTyp && m_ClipType != ctXor) )
1758 {
1759 AddLocalMaxPoly(e1, e2, Pt);
1760 }
1761 else
1762 {
1763 AddOutPt(e1, Pt);
1764 AddOutPt(e2, Pt);
1765 std::swap(e1->Side, e2->Side);
1766 std::swap(e1->OutIdx, e2->OutIdx);
1767 }
1768 }
1769 else if ( e1Contributing )
1770 {
1771 if (e2Wc == 0 || e2Wc == 1)
1772 {
1773 AddOutPt(e1, Pt);
1774 std::swap(e1->Side, e2->Side);
1775 std::swap(e1->OutIdx, e2->OutIdx);
1776 }
1777 }
1778 else if ( e2Contributing )
1779 {
1780 if (e1Wc == 0 || e1Wc == 1)
1781 {
1782 AddOutPt(e2, Pt);
1783 std::swap(e1->Side, e2->Side);
1784 std::swap(e1->OutIdx, e2->OutIdx);
1785 }
1786 }
1787 else if ( (e1Wc == 0 || e1Wc == 1) && (e2Wc == 0 || e2Wc == 1))
1788 {
1789 //neither edge is currently contributing ...
1790
1791 cInt e1Wc2, e2Wc2;
1792 switch (e1FillType2)
1793 {
1794 case pftPositive: e1Wc2 = e1->WindCnt2; break;
1795 case pftNegative : e1Wc2 = -e1->WindCnt2; break;
1796 default: e1Wc2 = std::abs(e1->WindCnt2);
1797 }
1798 switch (e2FillType2)
1799 {
1800 case pftPositive: e2Wc2 = e2->WindCnt2; break;
1801 case pftNegative: e2Wc2 = -e2->WindCnt2; break;
1802 default: e2Wc2 = std::abs(e2->WindCnt2);
1803 }
1804
1805 if (e1->PolyTyp != e2->PolyTyp)
1806 {
1807 AddLocalMinPoly(e1, e2, Pt);
1808 }
1809 else if (e1Wc == 1 && e2Wc == 1)
1810 switch( m_ClipType ) {
1811 case ctIntersection:
1812 if (e1Wc2 > 0 && e2Wc2 > 0)
1813 AddLocalMinPoly(e1, e2, Pt);
1814 break;
1815 case ctUnion:
1816 if ( e1Wc2 <= 0 && e2Wc2 <= 0 )
1817 AddLocalMinPoly(e1, e2, Pt);
1818 break;
1819 case ctDifference:
1820 if (((e1->PolyTyp == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
1821 ((e1->PolyTyp == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
1822 AddLocalMinPoly(e1, e2, Pt);
1823 break;
1824 case ctXor:
1825 AddLocalMinPoly(e1, e2, Pt);
1826 }
1827 else
1828 std::swap(e1->Side, e2->Side);
1829 }
1830 }
1831 //------------------------------------------------------------------------------
1832
SetHoleState(TEdge * e,OutRec * outrec) const1833 void Clipper::SetHoleState(TEdge *e, OutRec *outrec) const
1834 {
1835 bool IsHole = false;
1836 TEdge *e2 = e->PrevInAEL;
1837 while (e2)
1838 {
1839 if (e2->OutIdx >= 0 && e2->WindDelta != 0)
1840 {
1841 IsHole = !IsHole;
1842 if (! outrec->FirstLeft)
1843 outrec->FirstLeft = m_PolyOuts[e2->OutIdx];
1844 }
1845 e2 = e2->PrevInAEL;
1846 }
1847 if (IsHole) outrec->IsHole = true;
1848 }
1849 //------------------------------------------------------------------------------
1850
GetLowermostRec(OutRec * outRec1,OutRec * outRec2)1851 OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2)
1852 {
1853 //work out which polygon fragment has the correct hole state ...
1854 if (!outRec1->BottomPt)
1855 outRec1->BottomPt = GetBottomPt(outRec1->Pts);
1856 if (!outRec2->BottomPt)
1857 outRec2->BottomPt = GetBottomPt(outRec2->Pts);
1858 OutPt *OutPt1 = outRec1->BottomPt;
1859 OutPt *OutPt2 = outRec2->BottomPt;
1860 if (OutPt1->Pt.Y > OutPt2->Pt.Y) return outRec1;
1861 else if (OutPt1->Pt.Y < OutPt2->Pt.Y) return outRec2;
1862 else if (OutPt1->Pt.X < OutPt2->Pt.X) return outRec1;
1863 else if (OutPt1->Pt.X > OutPt2->Pt.X) return outRec2;
1864 else if (OutPt1->Next == OutPt1) return outRec2;
1865 else if (OutPt2->Next == OutPt2) return outRec1;
1866 else if (FirstIsBottomPt(OutPt1, OutPt2)) return outRec1;
1867 else return outRec2;
1868 }
1869 //------------------------------------------------------------------------------
1870
Param1RightOfParam2(OutRec * outRec1,OutRec * outRec2)1871 bool Param1RightOfParam2(OutRec* outRec1, OutRec* outRec2)
1872 {
1873 do
1874 {
1875 outRec1 = outRec1->FirstLeft;
1876 if (outRec1 == outRec2) return true;
1877 } while (outRec1);
1878 return false;
1879 }
1880 //------------------------------------------------------------------------------
1881
GetOutRec(int Idx)1882 OutRec* Clipper::GetOutRec(int Idx)
1883 {
1884 OutRec* outrec = m_PolyOuts[Idx];
1885 while (outrec != m_PolyOuts[outrec->Idx])
1886 outrec = m_PolyOuts[outrec->Idx];
1887 return outrec;
1888 }
1889 //------------------------------------------------------------------------------
1890
AppendPolygon(TEdge * e1,TEdge * e2) const1891 void Clipper::AppendPolygon(TEdge *e1, TEdge *e2) const
1892 {
1893 //get the start and ends of both output polygons ...
1894 OutRec *outRec1 = m_PolyOuts[e1->OutIdx];
1895 OutRec *outRec2 = m_PolyOuts[e2->OutIdx];
1896
1897 OutRec *holeStateRec;
1898 if (Param1RightOfParam2(outRec1, outRec2))
1899 holeStateRec = outRec2;
1900 else if (Param1RightOfParam2(outRec2, outRec1))
1901 holeStateRec = outRec1;
1902 else
1903 holeStateRec = GetLowermostRec(outRec1, outRec2);
1904
1905 //get the start and ends of both output polygons and
1906 //join e2 poly onto e1 poly and delete pointers to e2 ...
1907
1908 OutPt* p1_lft = outRec1->Pts;
1909 OutPt* p1_rt = p1_lft->Prev;
1910 OutPt* p2_lft = outRec2->Pts;
1911 OutPt* p2_rt = p2_lft->Prev;
1912
1913 EdgeSide Side;
1914 //join e2 poly onto e1 poly and delete pointers to e2 ...
1915 if( e1->Side == esLeft )
1916 {
1917 if( e2->Side == esLeft )
1918 {
1919 //z y x a b c
1920 ReversePolyPtLinks(p2_lft);
1921 p2_lft->Next = p1_lft;
1922 p1_lft->Prev = p2_lft;
1923 p1_rt->Next = p2_rt;
1924 p2_rt->Prev = p1_rt;
1925 outRec1->Pts = p2_rt;
1926 } else
1927 {
1928 //x y z a b c
1929 p2_rt->Next = p1_lft;
1930 p1_lft->Prev = p2_rt;
1931 p2_lft->Prev = p1_rt;
1932 p1_rt->Next = p2_lft;
1933 outRec1->Pts = p2_lft;
1934 }
1935 Side = esLeft;
1936 } else
1937 {
1938 if( e2->Side == esRight )
1939 {
1940 //a b c z y x
1941 ReversePolyPtLinks(p2_lft);
1942 p1_rt->Next = p2_rt;
1943 p2_rt->Prev = p1_rt;
1944 p2_lft->Next = p1_lft;
1945 p1_lft->Prev = p2_lft;
1946 } else
1947 {
1948 //a b c x y z
1949 p1_rt->Next = p2_lft;
1950 p2_lft->Prev = p1_rt;
1951 p1_lft->Prev = p2_rt;
1952 p2_rt->Next = p1_lft;
1953 }
1954 Side = esRight;
1955 }
1956
1957 outRec1->BottomPt = 0;
1958 if (holeStateRec == outRec2)
1959 {
1960 if (outRec2->FirstLeft != outRec1)
1961 outRec1->FirstLeft = outRec2->FirstLeft;
1962 outRec1->IsHole = outRec2->IsHole;
1963 }
1964 outRec2->Pts = 0;
1965 outRec2->BottomPt = 0;
1966 outRec2->FirstLeft = outRec1;
1967
1968 int OKIdx = e1->OutIdx;
1969 int ObsoleteIdx = e2->OutIdx;
1970
1971 e1->OutIdx = Unassigned; //nb: safe because we only get here via AddLocalMaxPoly
1972 e2->OutIdx = Unassigned;
1973
1974 TEdge* e = m_ActiveEdges;
1975 while( e )
1976 {
1977 if( e->OutIdx == ObsoleteIdx )
1978 {
1979 e->OutIdx = OKIdx;
1980 e->Side = Side;
1981 break;
1982 }
1983 e = e->NextInAEL;
1984 }
1985
1986 outRec2->Idx = outRec1->Idx;
1987 }
1988 //------------------------------------------------------------------------------
1989
CreateOutRec()1990 OutRec* Clipper::CreateOutRec()
1991 {
1992 OutRec* result = new OutRec;
1993 result->IsHole = false;
1994 result->IsOpen = false;
1995 result->FirstLeft = 0;
1996 result->Pts = 0;
1997 result->BottomPt = 0;
1998 result->PolyNd = 0;
1999 m_PolyOuts.push_back(result);
2000 result->Idx = (int)m_PolyOuts.size()-1;
2001 return result;
2002 }
2003 //------------------------------------------------------------------------------
2004
AddOutPt(TEdge * e,const IntPoint & pt)2005 OutPt* Clipper::AddOutPt(TEdge *e, const IntPoint &pt)
2006 {
2007 if( e->OutIdx < 0 )
2008 {
2009 OutRec *outRec = CreateOutRec();
2010 outRec->IsOpen = (e->WindDelta == 0);
2011 OutPt* newOp = this->AllocateOutPt();
2012 outRec->Pts = newOp;
2013 newOp->Idx = outRec->Idx;
2014 newOp->Pt = pt;
2015 newOp->Next = newOp;
2016 newOp->Prev = newOp;
2017 if (!outRec->IsOpen)
2018 SetHoleState(e, outRec);
2019 e->OutIdx = outRec->Idx;
2020 return newOp;
2021 } else
2022 {
2023 OutRec *outRec = m_PolyOuts[e->OutIdx];
2024 //OutRec.Pts is the 'Left-most' point & OutRec.Pts.Prev is the 'Right-most'
2025 OutPt* op = outRec->Pts;
2026
2027 bool ToFront = (e->Side == esLeft);
2028 if (ToFront && (pt == op->Pt)) return op;
2029 else if (!ToFront && (pt == op->Prev->Pt)) return op->Prev;
2030
2031 OutPt* newOp = this->AllocateOutPt();
2032 newOp->Idx = outRec->Idx;
2033 newOp->Pt = pt;
2034 newOp->Next = op;
2035 newOp->Prev = op->Prev;
2036 newOp->Prev->Next = newOp;
2037 op->Prev = newOp;
2038 if (ToFront) outRec->Pts = newOp;
2039 return newOp;
2040 }
2041 }
2042 //------------------------------------------------------------------------------
2043
GetLastOutPt(TEdge * e)2044 OutPt* Clipper::GetLastOutPt(TEdge *e)
2045 {
2046 OutRec *outRec = m_PolyOuts[e->OutIdx];
2047 if (e->Side == esLeft)
2048 return outRec->Pts;
2049 else
2050 return outRec->Pts->Prev;
2051 }
2052 //------------------------------------------------------------------------------
2053
ProcessHorizontals()2054 void Clipper::ProcessHorizontals()
2055 {
2056 CLIPPERLIB_PROFILE_FUNC();
2057 TEdge* horzEdge = m_SortedEdges;
2058 while(horzEdge)
2059 {
2060 DeleteFromSEL(horzEdge);
2061 ProcessHorizontal(horzEdge);
2062 horzEdge = m_SortedEdges;
2063 }
2064 }
2065 //------------------------------------------------------------------------------
2066
IsMaxima(TEdge * e,const cInt Y)2067 inline bool IsMaxima(TEdge *e, const cInt Y)
2068 {
2069 return e && e->Top.Y == Y && !e->NextInLML;
2070 }
2071 //------------------------------------------------------------------------------
2072
IsIntermediate(TEdge * e,const cInt Y)2073 inline bool IsIntermediate(TEdge *e, const cInt Y)
2074 {
2075 return e->Top.Y == Y && e->NextInLML;
2076 }
2077 //------------------------------------------------------------------------------
2078
GetMaximaPair(TEdge * e)2079 inline TEdge *GetMaximaPair(TEdge *e)
2080 {
2081 TEdge* result = 0;
2082 if ((e->Next->Top == e->Top) && !e->Next->NextInLML)
2083 result = e->Next;
2084 else if ((e->Prev->Top == e->Top) && !e->Prev->NextInLML)
2085 result = e->Prev;
2086
2087 if (result && (result->OutIdx == Skip ||
2088 //result is false if both NextInAEL & PrevInAEL are nil & not horizontal ...
2089 (result->NextInAEL == result->PrevInAEL && !IsHorizontal(*result))))
2090 return 0;
2091 return result;
2092 }
2093 //------------------------------------------------------------------------------
2094
SwapPositionsInAEL(TEdge * Edge1,TEdge * Edge2)2095 void Clipper::SwapPositionsInAEL(TEdge *Edge1, TEdge *Edge2)
2096 {
2097 //check that one or other edge hasn't already been removed from AEL ...
2098 if (Edge1->NextInAEL == Edge1->PrevInAEL ||
2099 Edge2->NextInAEL == Edge2->PrevInAEL) return;
2100
2101 if( Edge1->NextInAEL == Edge2 )
2102 {
2103 TEdge* Next = Edge2->NextInAEL;
2104 if( Next ) Next->PrevInAEL = Edge1;
2105 TEdge* Prev = Edge1->PrevInAEL;
2106 if( Prev ) Prev->NextInAEL = Edge2;
2107 Edge2->PrevInAEL = Prev;
2108 Edge2->NextInAEL = Edge1;
2109 Edge1->PrevInAEL = Edge2;
2110 Edge1->NextInAEL = Next;
2111 }
2112 else if( Edge2->NextInAEL == Edge1 )
2113 {
2114 TEdge* Next = Edge1->NextInAEL;
2115 if( Next ) Next->PrevInAEL = Edge2;
2116 TEdge* Prev = Edge2->PrevInAEL;
2117 if( Prev ) Prev->NextInAEL = Edge1;
2118 Edge1->PrevInAEL = Prev;
2119 Edge1->NextInAEL = Edge2;
2120 Edge2->PrevInAEL = Edge1;
2121 Edge2->NextInAEL = Next;
2122 }
2123 else
2124 {
2125 TEdge* Next = Edge1->NextInAEL;
2126 TEdge* Prev = Edge1->PrevInAEL;
2127 Edge1->NextInAEL = Edge2->NextInAEL;
2128 if( Edge1->NextInAEL ) Edge1->NextInAEL->PrevInAEL = Edge1;
2129 Edge1->PrevInAEL = Edge2->PrevInAEL;
2130 if( Edge1->PrevInAEL ) Edge1->PrevInAEL->NextInAEL = Edge1;
2131 Edge2->NextInAEL = Next;
2132 if( Edge2->NextInAEL ) Edge2->NextInAEL->PrevInAEL = Edge2;
2133 Edge2->PrevInAEL = Prev;
2134 if( Edge2->PrevInAEL ) Edge2->PrevInAEL->NextInAEL = Edge2;
2135 }
2136
2137 if( !Edge1->PrevInAEL ) m_ActiveEdges = Edge1;
2138 else if( !Edge2->PrevInAEL ) m_ActiveEdges = Edge2;
2139 }
2140 //------------------------------------------------------------------------------
2141
SwapPositionsInSEL(TEdge * Edge1,TEdge * Edge2)2142 void Clipper::SwapPositionsInSEL(TEdge *Edge1, TEdge *Edge2)
2143 {
2144 if( !( Edge1->NextInSEL ) && !( Edge1->PrevInSEL ) ) return;
2145 if( !( Edge2->NextInSEL ) && !( Edge2->PrevInSEL ) ) return;
2146
2147 if( Edge1->NextInSEL == Edge2 )
2148 {
2149 TEdge* Next = Edge2->NextInSEL;
2150 if( Next ) Next->PrevInSEL = Edge1;
2151 TEdge* Prev = Edge1->PrevInSEL;
2152 if( Prev ) Prev->NextInSEL = Edge2;
2153 Edge2->PrevInSEL = Prev;
2154 Edge2->NextInSEL = Edge1;
2155 Edge1->PrevInSEL = Edge2;
2156 Edge1->NextInSEL = Next;
2157 }
2158 else if( Edge2->NextInSEL == Edge1 )
2159 {
2160 TEdge* Next = Edge1->NextInSEL;
2161 if( Next ) Next->PrevInSEL = Edge2;
2162 TEdge* Prev = Edge2->PrevInSEL;
2163 if( Prev ) Prev->NextInSEL = Edge1;
2164 Edge1->PrevInSEL = Prev;
2165 Edge1->NextInSEL = Edge2;
2166 Edge2->PrevInSEL = Edge1;
2167 Edge2->NextInSEL = Next;
2168 }
2169 else
2170 {
2171 TEdge* Next = Edge1->NextInSEL;
2172 TEdge* Prev = Edge1->PrevInSEL;
2173 Edge1->NextInSEL = Edge2->NextInSEL;
2174 if( Edge1->NextInSEL ) Edge1->NextInSEL->PrevInSEL = Edge1;
2175 Edge1->PrevInSEL = Edge2->PrevInSEL;
2176 if( Edge1->PrevInSEL ) Edge1->PrevInSEL->NextInSEL = Edge1;
2177 Edge2->NextInSEL = Next;
2178 if( Edge2->NextInSEL ) Edge2->NextInSEL->PrevInSEL = Edge2;
2179 Edge2->PrevInSEL = Prev;
2180 if( Edge2->PrevInSEL ) Edge2->PrevInSEL->NextInSEL = Edge2;
2181 }
2182
2183 if( !Edge1->PrevInSEL ) m_SortedEdges = Edge1;
2184 else if( !Edge2->PrevInSEL ) m_SortedEdges = Edge2;
2185 }
2186 //------------------------------------------------------------------------------
2187
GetHorzDirection(TEdge & HorzEdge,Direction & Dir,cInt & Left,cInt & Right)2188 inline void GetHorzDirection(TEdge& HorzEdge, Direction& Dir, cInt& Left, cInt& Right)
2189 {
2190 if (HorzEdge.Bot.X < HorzEdge.Top.X)
2191 {
2192 Left = HorzEdge.Bot.X;
2193 Right = HorzEdge.Top.X;
2194 Dir = dLeftToRight;
2195 } else
2196 {
2197 Left = HorzEdge.Top.X;
2198 Right = HorzEdge.Bot.X;
2199 Dir = dRightToLeft;
2200 }
2201 }
2202 //------------------------------------------------------------------------
2203
2204 /*******************************************************************************
2205 * Notes: Horizontal edges (HEs) at scanline intersections (ie at the Top or *
2206 * Bottom of a scanbeam) are processed as if layered. The order in which HEs *
2207 * are processed doesn't matter. HEs intersect with other HE Bot.Xs only [#] *
2208 * (or they could intersect with Top.Xs only, ie EITHER Bot.Xs OR Top.Xs), *
2209 * and with other non-horizontal edges [*]. Once these intersections are *
2210 * processed, intermediate HEs then 'promote' the Edge above (NextInLML) into *
2211 * the AEL. These 'promoted' edges may in turn intersect [%] with other HEs. *
2212 *******************************************************************************/
2213
ProcessHorizontal(TEdge * horzEdge)2214 void Clipper::ProcessHorizontal(TEdge *horzEdge)
2215 {
2216 Direction dir;
2217 cInt horzLeft, horzRight;
2218 bool IsOpen = (horzEdge->OutIdx >= 0 && m_PolyOuts[horzEdge->OutIdx]->IsOpen);
2219
2220 GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
2221
2222 TEdge* eLastHorz = horzEdge, *eMaxPair = 0;
2223 while (eLastHorz->NextInLML && IsHorizontal(*eLastHorz->NextInLML))
2224 eLastHorz = eLastHorz->NextInLML;
2225 if (!eLastHorz->NextInLML)
2226 eMaxPair = GetMaximaPair(eLastHorz);
2227
2228 std::vector<cInt>::const_iterator maxIt;
2229 std::vector<cInt>::const_reverse_iterator maxRit;
2230 if (!m_Maxima.empty())
2231 {
2232 //get the first maxima in range (X) ...
2233 if (dir == dLeftToRight)
2234 {
2235 maxIt = m_Maxima.begin();
2236 while (maxIt != m_Maxima.end() && *maxIt <= horzEdge->Bot.X) ++maxIt;
2237 if (maxIt != m_Maxima.end() && *maxIt >= eLastHorz->Top.X)
2238 maxIt = m_Maxima.end();
2239 }
2240 else
2241 {
2242 maxRit = m_Maxima.rbegin();
2243 while (maxRit != m_Maxima.rend() && *maxRit > horzEdge->Bot.X) ++maxRit;
2244 if (maxRit != m_Maxima.rend() && *maxRit <= eLastHorz->Top.X)
2245 maxRit = m_Maxima.rend();
2246 }
2247 }
2248
2249 OutPt* op1 = 0;
2250
2251 for (;;) //loop through consec. horizontal edges
2252 {
2253
2254 bool IsLastHorz = (horzEdge == eLastHorz);
2255 TEdge* e = (dir == dLeftToRight) ? horzEdge->NextInAEL : horzEdge->PrevInAEL;
2256 while(e)
2257 {
2258
2259 //this code block inserts extra coords into horizontal edges (in output
2260 //polygons) whereever maxima touch these horizontal edges. This helps
2261 //'simplifying' polygons (ie if the Simplify property is set).
2262 if (!m_Maxima.empty())
2263 {
2264 if (dir == dLeftToRight)
2265 {
2266 while (maxIt != m_Maxima.end() && *maxIt < e->Curr.X)
2267 {
2268 if (horzEdge->OutIdx >= 0 && !IsOpen)
2269 AddOutPt(horzEdge, IntPoint(*maxIt, horzEdge->Bot.Y));
2270 ++maxIt;
2271 }
2272 }
2273 else
2274 {
2275 while (maxRit != m_Maxima.rend() && *maxRit > e->Curr.X)
2276 {
2277 if (horzEdge->OutIdx >= 0 && !IsOpen)
2278 AddOutPt(horzEdge, IntPoint(*maxRit, horzEdge->Bot.Y));
2279 ++maxRit;
2280 }
2281 }
2282 };
2283
2284 if ((dir == dLeftToRight && e->Curr.X > horzRight) ||
2285 (dir == dRightToLeft && e->Curr.X < horzLeft)) break;
2286
2287 //Also break if we've got to the end of an intermediate horizontal edge ...
2288 //nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
2289 if (e->Curr.X == horzEdge->Top.X && horzEdge->NextInLML &&
2290 e->Dx < horzEdge->NextInLML->Dx) break;
2291
2292 if (horzEdge->OutIdx >= 0 && !IsOpen) //note: may be done multiple times
2293 {
2294 op1 = AddOutPt(horzEdge, e->Curr);
2295 TEdge* eNextHorz = m_SortedEdges;
2296 while (eNextHorz)
2297 {
2298 if (eNextHorz->OutIdx >= 0 &&
2299 HorzSegmentsOverlap(horzEdge->Bot.X,
2300 horzEdge->Top.X, eNextHorz->Bot.X, eNextHorz->Top.X))
2301 {
2302 OutPt* op2 = GetLastOutPt(eNextHorz);
2303 m_Joins.emplace_back(Join(op2, op1, eNextHorz->Top));
2304 }
2305 eNextHorz = eNextHorz->NextInSEL;
2306 }
2307 m_GhostJoins.emplace_back(Join(op1, 0, horzEdge->Bot));
2308 }
2309
2310 //OK, so far we're still in range of the horizontal Edge but make sure
2311 //we're at the last of consec. horizontals when matching with eMaxPair
2312 if(e == eMaxPair && IsLastHorz)
2313 {
2314 if (horzEdge->OutIdx >= 0)
2315 AddLocalMaxPoly(horzEdge, eMaxPair, horzEdge->Top);
2316 DeleteFromAEL(horzEdge);
2317 DeleteFromAEL(eMaxPair);
2318 return;
2319 }
2320
2321 if(dir == dLeftToRight)
2322 {
2323 IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
2324 IntersectEdges(horzEdge, e, Pt);
2325 }
2326 else
2327 {
2328 IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
2329 IntersectEdges( e, horzEdge, Pt);
2330 }
2331 TEdge* eNext = (dir == dLeftToRight) ? e->NextInAEL : e->PrevInAEL;
2332 SwapPositionsInAEL( horzEdge, e );
2333 e = eNext;
2334 } //end while(e)
2335
2336 //Break out of loop if HorzEdge.NextInLML is not also horizontal ...
2337 if (!horzEdge->NextInLML || !IsHorizontal(*horzEdge->NextInLML)) break;
2338
2339 UpdateEdgeIntoAEL(horzEdge);
2340 if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Bot);
2341 GetHorzDirection(*horzEdge, dir, horzLeft, horzRight);
2342
2343 } //end for (;;)
2344
2345 if (horzEdge->OutIdx >= 0 && !op1)
2346 {
2347 op1 = GetLastOutPt(horzEdge);
2348 TEdge* eNextHorz = m_SortedEdges;
2349 while (eNextHorz)
2350 {
2351 if (eNextHorz->OutIdx >= 0 &&
2352 HorzSegmentsOverlap(horzEdge->Bot.X,
2353 horzEdge->Top.X, eNextHorz->Bot.X, eNextHorz->Top.X))
2354 {
2355 OutPt* op2 = GetLastOutPt(eNextHorz);
2356 m_Joins.emplace_back(Join(op2, op1, eNextHorz->Top));
2357 }
2358 eNextHorz = eNextHorz->NextInSEL;
2359 }
2360 m_GhostJoins.emplace_back(Join(op1, 0, horzEdge->Top));
2361 }
2362
2363 if (horzEdge->NextInLML)
2364 {
2365 if(horzEdge->OutIdx >= 0)
2366 {
2367 op1 = AddOutPt( horzEdge, horzEdge->Top);
2368 UpdateEdgeIntoAEL(horzEdge);
2369 if (horzEdge->WindDelta == 0) return;
2370 //nb: HorzEdge is no longer horizontal here
2371 TEdge* ePrev = horzEdge->PrevInAEL;
2372 TEdge* eNext = horzEdge->NextInAEL;
2373 if (ePrev && ePrev->Curr.X == horzEdge->Bot.X &&
2374 ePrev->Curr.Y == horzEdge->Bot.Y && ePrev->WindDelta != 0 &&
2375 (ePrev->OutIdx >= 0 && ePrev->Curr.Y > ePrev->Top.Y &&
2376 SlopesEqual(*horzEdge, *ePrev, m_UseFullRange)))
2377 {
2378 OutPt* op2 = AddOutPt(ePrev, horzEdge->Bot);
2379 m_Joins.emplace_back(Join(op1, op2, horzEdge->Top));
2380 }
2381 else if (eNext && eNext->Curr.X == horzEdge->Bot.X &&
2382 eNext->Curr.Y == horzEdge->Bot.Y && eNext->WindDelta != 0 &&
2383 eNext->OutIdx >= 0 && eNext->Curr.Y > eNext->Top.Y &&
2384 SlopesEqual(*horzEdge, *eNext, m_UseFullRange))
2385 {
2386 OutPt* op2 = AddOutPt(eNext, horzEdge->Bot);
2387 m_Joins.emplace_back(Join(op1, op2, horzEdge->Top));
2388 }
2389 }
2390 else
2391 UpdateEdgeIntoAEL(horzEdge);
2392 }
2393 else
2394 {
2395 if (horzEdge->OutIdx >= 0) AddOutPt(horzEdge, horzEdge->Top);
2396 DeleteFromAEL(horzEdge);
2397 }
2398 }
2399 //------------------------------------------------------------------------------
2400
UpdateEdgeIntoAEL(TEdge * & e)2401 void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
2402 {
2403 if( !e->NextInLML )
2404 throw clipperException("UpdateEdgeIntoAEL: invalid call");
2405
2406 e->NextInLML->OutIdx = e->OutIdx;
2407 TEdge* AelPrev = e->PrevInAEL;
2408 TEdge* AelNext = e->NextInAEL;
2409 if (AelPrev) AelPrev->NextInAEL = e->NextInLML;
2410 else m_ActiveEdges = e->NextInLML;
2411 if (AelNext) AelNext->PrevInAEL = e->NextInLML;
2412 e->NextInLML->Side = e->Side;
2413 e->NextInLML->WindDelta = e->WindDelta;
2414 e->NextInLML->WindCnt = e->WindCnt;
2415 e->NextInLML->WindCnt2 = e->WindCnt2;
2416 e = e->NextInLML;
2417 e->Curr = e->Bot;
2418 e->PrevInAEL = AelPrev;
2419 e->NextInAEL = AelNext;
2420 if (!IsHorizontal(*e))
2421 m_Scanbeam.push(e->Top.Y);
2422 }
2423 //------------------------------------------------------------------------------
2424
ProcessIntersections(const cInt topY)2425 bool Clipper::ProcessIntersections(const cInt topY)
2426 {
2427 CLIPPERLIB_PROFILE_FUNC();
2428 if( !m_ActiveEdges ) return true;
2429 try {
2430 BuildIntersectList(topY);
2431 size_t IlSize = m_IntersectList.size();
2432 if (IlSize == 0) return true;
2433 if (IlSize == 1 || FixupIntersectionOrder()) {
2434 for (IntersectNode &iNode : m_IntersectList) {
2435 IntersectEdges( iNode.Edge1, iNode.Edge2, iNode.Pt);
2436 SwapPositionsInAEL( iNode.Edge1 , iNode.Edge2 );
2437 }
2438 m_IntersectList.clear();
2439 }
2440 else return false;
2441 }
2442 catch(...)
2443 {
2444 m_SortedEdges = 0;
2445 m_IntersectList.clear();
2446 throw clipperException("ProcessIntersections error");
2447 }
2448 m_SortedEdges = 0;
2449 return true;
2450 }
2451 //------------------------------------------------------------------------------
2452
BuildIntersectList(const cInt topY)2453 void Clipper::BuildIntersectList(const cInt topY)
2454 {
2455 if ( !m_ActiveEdges ) return;
2456
2457 //prepare for sorting ...
2458 TEdge* e = m_ActiveEdges;
2459 m_SortedEdges = e;
2460 while( e )
2461 {
2462 e->PrevInSEL = e->PrevInAEL;
2463 e->NextInSEL = e->NextInAEL;
2464 e->Curr.X = TopX( *e, topY );
2465 e = e->NextInAEL;
2466 }
2467
2468 //bubblesort ...
2469 bool isModified;
2470 do
2471 {
2472 isModified = false;
2473 e = m_SortedEdges;
2474 while( e->NextInSEL )
2475 {
2476 TEdge *eNext = e->NextInSEL;
2477 IntPoint Pt;
2478 if(e->Curr.X > eNext->Curr.X)
2479 {
2480 IntersectPoint(*e, *eNext, Pt);
2481 m_IntersectList.emplace_back(IntersectNode(e, eNext, Pt));
2482 SwapPositionsInSEL(e, eNext);
2483 isModified = true;
2484 }
2485 else
2486 e = eNext;
2487 }
2488 if( e->PrevInSEL ) e->PrevInSEL->NextInSEL = 0;
2489 else break;
2490 }
2491 while ( isModified );
2492 m_SortedEdges = 0; //important
2493 }
2494 //------------------------------------------------------------------------------
2495
2496
EdgesAdjacent(const IntersectNode & inode)2497 inline bool EdgesAdjacent(const IntersectNode &inode)
2498 {
2499 return (inode.Edge1->NextInSEL == inode.Edge2) ||
2500 (inode.Edge1->PrevInSEL == inode.Edge2);
2501 }
2502 //------------------------------------------------------------------------------
2503
FixupIntersectionOrder()2504 bool Clipper::FixupIntersectionOrder()
2505 {
2506 //pre-condition: intersections are sorted Bottom-most first.
2507 //Now it's crucial that intersections are made only between adjacent edges,
2508 //so to ensure this the order of intersections may need adjusting ...
2509 CopyAELToSEL();
2510 std::sort(m_IntersectList.begin(), m_IntersectList.end(), [](const IntersectNode &node1, const IntersectNode &node2) { return node2.Pt.Y < node1.Pt.Y; });
2511
2512 size_t cnt = m_IntersectList.size();
2513 for (size_t i = 0; i < cnt; ++i)
2514 {
2515 if (!EdgesAdjacent(m_IntersectList[i]))
2516 {
2517 size_t j = i + 1;
2518 while (j < cnt && !EdgesAdjacent(m_IntersectList[j])) j++;
2519 if (j == cnt) return false;
2520 std::swap(m_IntersectList[i], m_IntersectList[j]);
2521 }
2522 SwapPositionsInSEL(m_IntersectList[i].Edge1, m_IntersectList[i].Edge2);
2523 }
2524 return true;
2525 }
2526 //------------------------------------------------------------------------------
2527
DoMaxima(TEdge * e)2528 void Clipper::DoMaxima(TEdge *e)
2529 {
2530 TEdge* eMaxPair = GetMaximaPair(e);
2531 if (!eMaxPair)
2532 {
2533 if (e->OutIdx >= 0)
2534 AddOutPt(e, e->Top);
2535 DeleteFromAEL(e);
2536 return;
2537 }
2538
2539 TEdge* eNext = e->NextInAEL;
2540 while(eNext && eNext != eMaxPair)
2541 {
2542 IntersectEdges(e, eNext, e->Top);
2543 SwapPositionsInAEL(e, eNext);
2544 eNext = e->NextInAEL;
2545 }
2546
2547 if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned)
2548 {
2549 DeleteFromAEL(e);
2550 DeleteFromAEL(eMaxPair);
2551 }
2552 else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 )
2553 {
2554 if (e->OutIdx >= 0) AddLocalMaxPoly(e, eMaxPair, e->Top);
2555 DeleteFromAEL(e);
2556 DeleteFromAEL(eMaxPair);
2557 }
2558 #ifdef use_lines
2559 else if (e->WindDelta == 0)
2560 {
2561 if (e->OutIdx >= 0)
2562 {
2563 AddOutPt(e, e->Top);
2564 e->OutIdx = Unassigned;
2565 }
2566 DeleteFromAEL(e);
2567
2568 if (eMaxPair->OutIdx >= 0)
2569 {
2570 AddOutPt(eMaxPair, e->Top);
2571 eMaxPair->OutIdx = Unassigned;
2572 }
2573 DeleteFromAEL(eMaxPair);
2574 }
2575 #endif
2576 else throw clipperException("DoMaxima error");
2577 }
2578 //------------------------------------------------------------------------------
2579
ProcessEdgesAtTopOfScanbeam(const cInt topY)2580 void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)
2581 {
2582 CLIPPERLIB_PROFILE_FUNC();
2583 TEdge* e = m_ActiveEdges;
2584 while( e )
2585 {
2586 //1. process maxima, treating them as if they're 'bent' horizontal edges,
2587 // but exclude maxima with horizontal edges. nb: e can't be a horizontal.
2588 bool IsMaximaEdge = IsMaxima(e, topY);
2589
2590 if(IsMaximaEdge)
2591 {
2592 TEdge* eMaxPair = GetMaximaPair(e);
2593 IsMaximaEdge = (!eMaxPair || !IsHorizontal(*eMaxPair));
2594 }
2595
2596 if(IsMaximaEdge)
2597 {
2598 if (m_StrictSimple) m_Maxima.push_back(e->Top.X);
2599 TEdge* ePrev = e->PrevInAEL;
2600 DoMaxima(e);
2601 if( !ePrev ) e = m_ActiveEdges;
2602 else e = ePrev->NextInAEL;
2603 }
2604 else
2605 {
2606 //2. promote horizontal edges, otherwise update Curr.X and Curr.Y ...
2607 if (IsIntermediate(e, topY) && IsHorizontal(*e->NextInLML))
2608 {
2609 UpdateEdgeIntoAEL(e);
2610 if (e->OutIdx >= 0)
2611 AddOutPt(e, e->Bot);
2612 AddEdgeToSEL(e);
2613 }
2614 else
2615 {
2616 e->Curr.X = TopX( *e, topY );
2617 e->Curr.Y = topY;
2618 }
2619
2620 //When StrictlySimple and 'e' is being touched by another edge, then
2621 //make sure both edges have a vertex here ...
2622 if (m_StrictSimple)
2623 {
2624 TEdge* ePrev = e->PrevInAEL;
2625 if ((e->OutIdx >= 0) && (e->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) &&
2626 (ePrev->Curr.X == e->Curr.X) && (ePrev->WindDelta != 0))
2627 {
2628 IntPoint pt = e->Curr;
2629 #ifdef use_xyz
2630 SetZ(pt, *ePrev, *e);
2631 #endif
2632 OutPt* op = AddOutPt(ePrev, pt);
2633 OutPt* op2 = AddOutPt(e, pt);
2634 m_Joins.emplace_back(Join(op, op2, pt)); //StrictlySimple (type-3) join
2635 }
2636 }
2637
2638 e = e->NextInAEL;
2639 }
2640 }
2641
2642 //3. Process horizontals at the Top of the scanbeam ...
2643 std::sort(m_Maxima.begin(), m_Maxima.end());
2644 ProcessHorizontals();
2645 m_Maxima.clear();
2646
2647 //4. Promote intermediate vertices ...
2648 e = m_ActiveEdges;
2649 while(e)
2650 {
2651 if(IsIntermediate(e, topY))
2652 {
2653 OutPt* op = 0;
2654 if( e->OutIdx >= 0 )
2655 op = AddOutPt(e, e->Top);
2656 UpdateEdgeIntoAEL(e);
2657
2658 //if output polygons share an edge, they'll need joining later ...
2659 TEdge* ePrev = e->PrevInAEL;
2660 TEdge* eNext = e->NextInAEL;
2661 if (ePrev && ePrev->Curr.X == e->Bot.X &&
2662 ePrev->Curr.Y == e->Bot.Y && op &&
2663 ePrev->OutIdx >= 0 && ePrev->Curr.Y > ePrev->Top.Y &&
2664 SlopesEqual(*e, *ePrev, m_UseFullRange) &&
2665 (e->WindDelta != 0) && (ePrev->WindDelta != 0))
2666 {
2667 OutPt* op2 = AddOutPt(ePrev, e->Bot);
2668 m_Joins.emplace_back(Join(op, op2, e->Top));
2669 }
2670 else if (eNext && eNext->Curr.X == e->Bot.X &&
2671 eNext->Curr.Y == e->Bot.Y && op &&
2672 eNext->OutIdx >= 0 && eNext->Curr.Y > eNext->Top.Y &&
2673 SlopesEqual(*e, *eNext, m_UseFullRange) &&
2674 (e->WindDelta != 0) && (eNext->WindDelta != 0))
2675 {
2676 OutPt* op2 = AddOutPt(eNext, e->Bot);
2677 m_Joins.emplace_back(Join(op, op2, e->Top));
2678 }
2679 }
2680 e = e->NextInAEL;
2681 }
2682 }
2683 //------------------------------------------------------------------------------
2684
FixupOutPolyline(OutRec & outrec)2685 void Clipper::FixupOutPolyline(OutRec &outrec)
2686 {
2687 OutPt *pp = outrec.Pts;
2688 OutPt *lastPP = pp->Prev;
2689 while (pp != lastPP)
2690 {
2691 pp = pp->Next;
2692 if (pp->Pt == pp->Prev->Pt)
2693 {
2694 if (pp == lastPP) lastPP = pp->Prev;
2695 OutPt *tmpPP = pp->Prev;
2696 tmpPP->Next = pp->Next;
2697 pp->Next->Prev = tmpPP;
2698 this->DisposeOutPt(pp);
2699 pp = tmpPP;
2700 }
2701 }
2702
2703 if (pp == pp->Prev)
2704 {
2705 this->DisposeOutPts(pp);
2706 outrec.Pts = 0;
2707 return;
2708 }
2709 }
2710 //------------------------------------------------------------------------------
2711
FixupOutPolygon(OutRec & outrec)2712 void Clipper::FixupOutPolygon(OutRec &outrec)
2713 {
2714 //FixupOutPolygon() - removes duplicate points and simplifies consecutive
2715 //parallel edges by removing the middle vertex.
2716 OutPt *lastOK = nullptr;
2717 outrec.BottomPt = nullptr;
2718 OutPt *pp = outrec.Pts;
2719 bool preserveCol = m_PreserveCollinear || m_StrictSimple;
2720
2721 for (;;)
2722 {
2723 if (pp->Prev == pp || pp->Prev == pp->Next)
2724 {
2725 // Empty loop or a stick. Release the polygon.
2726 this->DisposeOutPts(pp);
2727 outrec.Pts = nullptr;
2728 return;
2729 }
2730
2731 //test for duplicate points and collinear edges ...
2732 if ((pp->Pt == pp->Next->Pt) || (pp->Pt == pp->Prev->Pt) ||
2733 (SlopesEqual(pp->Prev->Pt, pp->Pt, pp->Next->Pt, m_UseFullRange) &&
2734 (!preserveCol || !Pt2IsBetweenPt1AndPt3(pp->Prev->Pt, pp->Pt, pp->Next->Pt))))
2735 {
2736 lastOK = nullptr;
2737 OutPt *tmp = pp;
2738 pp->Prev->Next = pp->Next;
2739 pp->Next->Prev = pp->Prev;
2740 pp = pp->Prev;
2741 this->DisposeOutPt(tmp);
2742 }
2743 else if (pp == lastOK) break;
2744 else
2745 {
2746 if (!lastOK) lastOK = pp;
2747 pp = pp->Next;
2748 }
2749 }
2750 outrec.Pts = pp;
2751 }
2752 //------------------------------------------------------------------------------
2753
2754 // Count the number of points in a closed linked loop starting with Pts.
PointCount(OutPt * Pts)2755 int PointCount(OutPt *Pts)
2756 {
2757 if (!Pts) return 0;
2758 int result = 0;
2759 OutPt* p = Pts;
2760 do
2761 {
2762 result++;
2763 p = p->Next;
2764 }
2765 while (p != Pts);
2766 return result;
2767 }
2768 //------------------------------------------------------------------------------
2769
BuildResult(Paths & polys)2770 void Clipper::BuildResult(Paths &polys)
2771 {
2772 polys.reserve(m_PolyOuts.size());
2773 for (OutRec* outRec : m_PolyOuts)
2774 {
2775 assert(! outRec->IsOpen);
2776 if (!outRec->Pts) continue;
2777 Path pg;
2778 OutPt* p = outRec->Pts->Prev;
2779 int cnt = PointCount(p);
2780 if (cnt < 2) continue;
2781 pg.reserve(cnt);
2782 for (int i = 0; i < cnt; ++i)
2783 {
2784 pg.emplace_back(p->Pt);
2785 p = p->Prev;
2786 }
2787 polys.emplace_back(std::move(pg));
2788 }
2789 }
2790 //------------------------------------------------------------------------------
2791
BuildResult2(PolyTree & polytree)2792 void Clipper::BuildResult2(PolyTree& polytree)
2793 {
2794 polytree.Clear();
2795 polytree.AllNodes.reserve(m_PolyOuts.size());
2796 //add each output polygon/contour to polytree ...
2797 for (OutRec* outRec : m_PolyOuts)
2798 {
2799 int cnt = PointCount(outRec->Pts);
2800 if ((outRec->IsOpen && cnt < 2) || (!outRec->IsOpen && cnt < 3))
2801 // Ignore an invalid output loop or a polyline.
2802 continue;
2803
2804 //skip OutRecs that (a) contain outermost polygons or
2805 //(b) already have the correct owner/child linkage ...
2806 if (outRec->FirstLeft &&
2807 (outRec->IsHole == outRec->FirstLeft->IsHole || ! outRec->FirstLeft->Pts)) {
2808 OutRec* orfl = outRec->FirstLeft;
2809 while (orfl && ((orfl->IsHole == outRec->IsHole) || !orfl->Pts))
2810 orfl = orfl->FirstLeft;
2811 outRec->FirstLeft = orfl;
2812 }
2813
2814 //nb: polytree takes ownership of all the PolyNodes
2815 polytree.AllNodes.emplace_back(PolyNode());
2816 PolyNode* pn = &polytree.AllNodes.back();
2817 outRec->PolyNd = pn;
2818 pn->Parent = 0;
2819 pn->Index = 0;
2820 pn->Contour.reserve(cnt);
2821 OutPt *op = outRec->Pts->Prev;
2822 for (int j = 0; j < cnt; j++)
2823 {
2824 pn->Contour.emplace_back(op->Pt);
2825 op = op->Prev;
2826 }
2827 }
2828
2829 //fixup PolyNode links etc ...
2830 polytree.Childs.reserve(m_PolyOuts.size());
2831 for (OutRec* outRec : m_PolyOuts)
2832 {
2833 if (!outRec->PolyNd) continue;
2834 if (outRec->IsOpen)
2835 {
2836 outRec->PolyNd->m_IsOpen = true;
2837 polytree.AddChild(*outRec->PolyNd);
2838 }
2839 else if (outRec->FirstLeft && outRec->FirstLeft->PolyNd)
2840 outRec->FirstLeft->PolyNd->AddChild(*outRec->PolyNd);
2841 else
2842 polytree.AddChild(*outRec->PolyNd);
2843 }
2844 }
2845 //------------------------------------------------------------------------------
2846
E2InsertsBeforeE1(TEdge & e1,TEdge & e2)2847 inline bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
2848 {
2849 if (e2.Curr.X == e1.Curr.X)
2850 {
2851 if (e2.Top.Y > e1.Top.Y)
2852 return e2.Top.X < TopX(e1, e2.Top.Y);
2853 else return e1.Top.X > TopX(e2, e1.Top.Y);
2854 }
2855 else return e2.Curr.X < e1.Curr.X;
2856 }
2857 //------------------------------------------------------------------------------
2858
GetOverlap(const cInt a1,const cInt a2,const cInt b1,const cInt b2,cInt & Left,cInt & Right)2859 bool GetOverlap(const cInt a1, const cInt a2, const cInt b1, const cInt b2,
2860 cInt& Left, cInt& Right)
2861 {
2862 if (a1 < a2)
2863 {
2864 if (b1 < b2) {Left = std::max(a1,b1); Right = std::min(a2,b2);}
2865 else {Left = std::max(a1,b2); Right = std::min(a2,b1);}
2866 }
2867 else
2868 {
2869 if (b1 < b2) {Left = std::max(a2,b1); Right = std::min(a1,b2);}
2870 else {Left = std::max(a2,b2); Right = std::min(a1,b1);}
2871 }
2872 return Left < Right;
2873 }
2874 //------------------------------------------------------------------------------
2875
2876 // Make all points of outrec point to outrec.Idx
UpdateOutPtIdxs(OutRec & outrec)2877 inline void UpdateOutPtIdxs(OutRec& outrec)
2878 {
2879 OutPt* op = outrec.Pts;
2880 do
2881 {
2882 op->Idx = outrec.Idx;
2883 op = op->Prev;
2884 }
2885 while(op != outrec.Pts);
2886 }
2887 //------------------------------------------------------------------------------
2888
InsertEdgeIntoAEL(TEdge * edge,TEdge * startEdge)2889 void Clipper::InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge)
2890 {
2891 if(!m_ActiveEdges)
2892 {
2893 edge->PrevInAEL = 0;
2894 edge->NextInAEL = 0;
2895 m_ActiveEdges = edge;
2896 }
2897 else if(!startEdge && E2InsertsBeforeE1(*m_ActiveEdges, *edge))
2898 {
2899 edge->PrevInAEL = 0;
2900 edge->NextInAEL = m_ActiveEdges;
2901 m_ActiveEdges->PrevInAEL = edge;
2902 m_ActiveEdges = edge;
2903 }
2904 else
2905 {
2906 if(!startEdge) startEdge = m_ActiveEdges;
2907 while(startEdge->NextInAEL &&
2908 !E2InsertsBeforeE1(*startEdge->NextInAEL , *edge))
2909 startEdge = startEdge->NextInAEL;
2910 edge->NextInAEL = startEdge->NextInAEL;
2911 if(startEdge->NextInAEL) startEdge->NextInAEL->PrevInAEL = edge;
2912 edge->PrevInAEL = startEdge;
2913 startEdge->NextInAEL = edge;
2914 }
2915 }
2916 //----------------------------------------------------------------------
2917
DupOutPt(OutPt * outPt,bool InsertAfter)2918 OutPt* Clipper::DupOutPt(OutPt* outPt, bool InsertAfter)
2919 {
2920 OutPt* result = this->AllocateOutPt();
2921 result->Pt = outPt->Pt;
2922 result->Idx = outPt->Idx;
2923 if (InsertAfter)
2924 {
2925 result->Next = outPt->Next;
2926 result->Prev = outPt;
2927 outPt->Next->Prev = result;
2928 outPt->Next = result;
2929 }
2930 else
2931 {
2932 result->Prev = outPt->Prev;
2933 result->Next = outPt;
2934 outPt->Prev->Next = result;
2935 outPt->Prev = result;
2936 }
2937 return result;
2938 }
2939 //------------------------------------------------------------------------------
2940
JoinHorz(OutPt * op1,OutPt * op1b,OutPt * op2,OutPt * op2b,const IntPoint & Pt,bool DiscardLeft)2941 bool Clipper::JoinHorz(OutPt* op1, OutPt* op1b, OutPt* op2, OutPt* op2b,
2942 const IntPoint &Pt, bool DiscardLeft)
2943 {
2944 Direction Dir1 = (op1->Pt.X > op1b->Pt.X ? dRightToLeft : dLeftToRight);
2945 Direction Dir2 = (op2->Pt.X > op2b->Pt.X ? dRightToLeft : dLeftToRight);
2946 if (Dir1 == Dir2) return false;
2947
2948 //When DiscardLeft, we want Op1b to be on the Left of Op1, otherwise we
2949 //want Op1b to be on the Right. (And likewise with Op2 and Op2b.)
2950 //So, to facilitate this while inserting Op1b and Op2b ...
2951 //when DiscardLeft, make sure we're AT or RIGHT of Pt before adding Op1b,
2952 //otherwise make sure we're AT or LEFT of Pt. (Likewise with Op2b.)
2953 if (Dir1 == dLeftToRight)
2954 {
2955 while (op1->Next->Pt.X <= Pt.X &&
2956 op1->Next->Pt.X >= op1->Pt.X && op1->Next->Pt.Y == Pt.Y)
2957 op1 = op1->Next;
2958 if (DiscardLeft && (op1->Pt.X != Pt.X)) op1 = op1->Next;
2959 op1b = this->DupOutPt(op1, !DiscardLeft);
2960 if (op1b->Pt != Pt)
2961 {
2962 op1 = op1b;
2963 op1->Pt = Pt;
2964 op1b = this->DupOutPt(op1, !DiscardLeft);
2965 }
2966 }
2967 else
2968 {
2969 while (op1->Next->Pt.X >= Pt.X &&
2970 op1->Next->Pt.X <= op1->Pt.X && op1->Next->Pt.Y == Pt.Y)
2971 op1 = op1->Next;
2972 if (!DiscardLeft && (op1->Pt.X != Pt.X)) op1 = op1->Next;
2973 op1b = this->DupOutPt(op1, DiscardLeft);
2974 if (op1b->Pt != Pt)
2975 {
2976 op1 = op1b;
2977 op1->Pt = Pt;
2978 op1b = this->DupOutPt(op1, DiscardLeft);
2979 }
2980 }
2981
2982 if (Dir2 == dLeftToRight)
2983 {
2984 while (op2->Next->Pt.X <= Pt.X &&
2985 op2->Next->Pt.X >= op2->Pt.X && op2->Next->Pt.Y == Pt.Y)
2986 op2 = op2->Next;
2987 if (DiscardLeft && (op2->Pt.X != Pt.X)) op2 = op2->Next;
2988 op2b = this->DupOutPt(op2, !DiscardLeft);
2989 if (op2b->Pt != Pt)
2990 {
2991 op2 = op2b;
2992 op2->Pt = Pt;
2993 op2b = this->DupOutPt(op2, !DiscardLeft);
2994 };
2995 } else
2996 {
2997 while (op2->Next->Pt.X >= Pt.X &&
2998 op2->Next->Pt.X <= op2->Pt.X && op2->Next->Pt.Y == Pt.Y)
2999 op2 = op2->Next;
3000 if (!DiscardLeft && (op2->Pt.X != Pt.X)) op2 = op2->Next;
3001 op2b = this->DupOutPt(op2, DiscardLeft);
3002 if (op2b->Pt != Pt)
3003 {
3004 op2 = op2b;
3005 op2->Pt = Pt;
3006 op2b = this->DupOutPt(op2, DiscardLeft);
3007 };
3008 };
3009
3010 if ((Dir1 == dLeftToRight) == DiscardLeft)
3011 {
3012 op1->Prev = op2;
3013 op2->Next = op1;
3014 op1b->Next = op2b;
3015 op2b->Prev = op1b;
3016 }
3017 else
3018 {
3019 op1->Next = op2;
3020 op2->Prev = op1;
3021 op1b->Prev = op2b;
3022 op2b->Next = op1b;
3023 }
3024 return true;
3025 }
3026 //------------------------------------------------------------------------------
3027
JoinPoints(Join * j,OutRec * outRec1,OutRec * outRec2)3028 bool Clipper::JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2)
3029 {
3030 OutPt *op1 = j->OutPt1, *op1b;
3031 OutPt *op2 = j->OutPt2, *op2b;
3032
3033 //There are 3 kinds of joins for output polygons ...
3034 //1. Horizontal joins where Join.OutPt1 & Join.OutPt2 are vertices anywhere
3035 //along (horizontal) collinear edges (& Join.OffPt is on the same horizontal).
3036 //2. Non-horizontal joins where Join.OutPt1 & Join.OutPt2 are at the same
3037 //location at the Bottom of the overlapping segment (& Join.OffPt is above).
3038 //3. StrictSimple joins where edges touch but are not collinear and where
3039 //Join.OutPt1, Join.OutPt2 & Join.OffPt all share the same point.
3040 bool isHorizontal = (j->OutPt1->Pt.Y == j->OffPt.Y);
3041
3042 if (isHorizontal && (j->OffPt == j->OutPt1->Pt) &&
3043 (j->OffPt == j->OutPt2->Pt))
3044 {
3045 //Strictly Simple join ...
3046 if (outRec1 != outRec2) return false;
3047 op1b = j->OutPt1->Next;
3048 while (op1b != op1 && (op1b->Pt == j->OffPt))
3049 op1b = op1b->Next;
3050 bool reverse1 = (op1b->Pt.Y > j->OffPt.Y);
3051 op2b = j->OutPt2->Next;
3052 while (op2b != op2 && (op2b->Pt == j->OffPt))
3053 op2b = op2b->Next;
3054 bool reverse2 = (op2b->Pt.Y > j->OffPt.Y);
3055 if (reverse1 == reverse2) return false;
3056 if (reverse1)
3057 {
3058 op1b = this->DupOutPt(op1, false);
3059 op2b = this->DupOutPt(op2, true);
3060 op1->Prev = op2;
3061 op2->Next = op1;
3062 op1b->Next = op2b;
3063 op2b->Prev = op1b;
3064 j->OutPt1 = op1;
3065 j->OutPt2 = op1b;
3066 return true;
3067 } else
3068 {
3069 op1b = this->DupOutPt(op1, true);
3070 op2b = this->DupOutPt(op2, false);
3071 op1->Next = op2;
3072 op2->Prev = op1;
3073 op1b->Prev = op2b;
3074 op2b->Next = op1b;
3075 j->OutPt1 = op1;
3076 j->OutPt2 = op1b;
3077 return true;
3078 }
3079 }
3080 else if (isHorizontal)
3081 {
3082 //treat horizontal joins differently to non-horizontal joins since with
3083 //them we're not yet sure where the overlapping is. OutPt1.Pt & OutPt2.Pt
3084 //may be anywhere along the horizontal edge.
3085 op1b = op1;
3086 while (op1->Prev->Pt.Y == op1->Pt.Y && op1->Prev != op1b && op1->Prev != op2)
3087 op1 = op1->Prev;
3088 while (op1b->Next->Pt.Y == op1b->Pt.Y && op1b->Next != op1 && op1b->Next != op2)
3089 op1b = op1b->Next;
3090 if (op1b->Next == op1 || op1b->Next == op2) return false; //a flat 'polygon'
3091
3092 op2b = op2;
3093 while (op2->Prev->Pt.Y == op2->Pt.Y && op2->Prev != op2b && op2->Prev != op1b)
3094 op2 = op2->Prev;
3095 while (op2b->Next->Pt.Y == op2b->Pt.Y && op2b->Next != op2 && op2b->Next != op1)
3096 op2b = op2b->Next;
3097 if (op2b->Next == op2 || op2b->Next == op1) return false; //a flat 'polygon'
3098
3099 cInt Left, Right;
3100 //Op1 --> Op1b & Op2 --> Op2b are the extremites of the horizontal edges
3101 if (!GetOverlap(op1->Pt.X, op1b->Pt.X, op2->Pt.X, op2b->Pt.X, Left, Right))
3102 return false;
3103
3104 //DiscardLeftSide: when overlapping edges are joined, a spike will created
3105 //which needs to be cleaned up. However, we don't want Op1 or Op2 caught up
3106 //on the discard Side as either may still be needed for other joins ...
3107 IntPoint Pt;
3108 bool DiscardLeftSide;
3109 if (op1->Pt.X >= Left && op1->Pt.X <= Right)
3110 {
3111 Pt = op1->Pt; DiscardLeftSide = (op1->Pt.X > op1b->Pt.X);
3112 }
3113 else if (op2->Pt.X >= Left&& op2->Pt.X <= Right)
3114 {
3115 Pt = op2->Pt; DiscardLeftSide = (op2->Pt.X > op2b->Pt.X);
3116 }
3117 else if (op1b->Pt.X >= Left && op1b->Pt.X <= Right)
3118 {
3119 Pt = op1b->Pt; DiscardLeftSide = op1b->Pt.X > op1->Pt.X;
3120 }
3121 else
3122 {
3123 Pt = op2b->Pt; DiscardLeftSide = (op2b->Pt.X > op2->Pt.X);
3124 }
3125 j->OutPt1 = op1; j->OutPt2 = op2;
3126 return JoinHorz(op1, op1b, op2, op2b, Pt, DiscardLeftSide);
3127 } else
3128 {
3129 //nb: For non-horizontal joins ...
3130 // 1. Jr.OutPt1.Pt.Y == Jr.OutPt2.Pt.Y
3131 // 2. Jr.OutPt1.Pt > Jr.OffPt.Y
3132
3133 //make sure the polygons are correctly oriented ...
3134 op1b = op1->Next;
3135 while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Next;
3136 bool Reverse1 = ((op1b->Pt.Y > op1->Pt.Y) ||
3137 !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange));
3138 if (Reverse1)
3139 {
3140 op1b = op1->Prev;
3141 while ((op1b->Pt == op1->Pt) && (op1b != op1)) op1b = op1b->Prev;
3142 if ((op1b->Pt.Y > op1->Pt.Y) ||
3143 !SlopesEqual(op1->Pt, op1b->Pt, j->OffPt, m_UseFullRange)) return false;
3144 };
3145 op2b = op2->Next;
3146 while ((op2b->Pt == op2->Pt) && (op2b != op2))op2b = op2b->Next;
3147 bool Reverse2 = ((op2b->Pt.Y > op2->Pt.Y) ||
3148 !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange));
3149 if (Reverse2)
3150 {
3151 op2b = op2->Prev;
3152 while ((op2b->Pt == op2->Pt) && (op2b != op2)) op2b = op2b->Prev;
3153 if ((op2b->Pt.Y > op2->Pt.Y) ||
3154 !SlopesEqual(op2->Pt, op2b->Pt, j->OffPt, m_UseFullRange)) return false;
3155 }
3156
3157 if ((op1b == op1) || (op2b == op2) || (op1b == op2b) ||
3158 ((outRec1 == outRec2) && (Reverse1 == Reverse2))) return false;
3159
3160 if (Reverse1)
3161 {
3162 op1b = this->DupOutPt(op1, false);
3163 op2b = this->DupOutPt(op2, true);
3164 op1->Prev = op2;
3165 op2->Next = op1;
3166 op1b->Next = op2b;
3167 op2b->Prev = op1b;
3168 j->OutPt1 = op1;
3169 j->OutPt2 = op1b;
3170 return true;
3171 } else
3172 {
3173 op1b = this->DupOutPt(op1, true);
3174 op2b = this->DupOutPt(op2, false);
3175 op1->Next = op2;
3176 op2->Prev = op1;
3177 op1b->Prev = op2b;
3178 op2b->Next = op1b;
3179 j->OutPt1 = op1;
3180 j->OutPt2 = op1b;
3181 return true;
3182 }
3183 }
3184 }
3185 //----------------------------------------------------------------------
3186
3187 // This is potentially very expensive! O(n^3)!
FixupFirstLefts1(OutRec * OldOutRec,OutRec * NewOutRec) const3188 void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec) const
3189 {
3190 CLIPPERLIB_PROFILE_FUNC();
3191 //tests if NewOutRec contains the polygon before reassigning FirstLeft
3192 for (OutRec *outRec : m_PolyOuts)
3193 {
3194 if (!outRec->Pts || !outRec->FirstLeft) continue;
3195 OutRec* firstLeft = outRec->FirstLeft;
3196 // Skip empty polygons.
3197 while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;
3198 if (firstLeft == OldOutRec && Poly2ContainsPoly1(outRec->Pts, NewOutRec->Pts))
3199 outRec->FirstLeft = NewOutRec;
3200 }
3201 }
3202 //----------------------------------------------------------------------
3203
FixupFirstLefts2(OutRec * OldOutRec,OutRec * NewOutRec) const3204 void Clipper::FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec) const
3205 {
3206 //reassigns FirstLeft WITHOUT testing if NewOutRec contains the polygon
3207 for (OutRec *outRec : m_PolyOuts)
3208 if (outRec->FirstLeft == OldOutRec) outRec->FirstLeft = NewOutRec;
3209 }
3210 //----------------------------------------------------------------------
3211
JoinCommonEdges()3212 void Clipper::JoinCommonEdges()
3213 {
3214 CLIPPERLIB_PROFILE_FUNC();
3215 for (Join &join : m_Joins)
3216 {
3217 OutRec *outRec1 = GetOutRec(join.OutPt1->Idx);
3218 OutRec *outRec2 = GetOutRec(join.OutPt2->Idx);
3219
3220 if (!outRec1->Pts || !outRec2->Pts) continue;
3221 if (outRec1->IsOpen || outRec2->IsOpen) continue;
3222
3223 //get the polygon fragment with the correct hole state (FirstLeft)
3224 //before calling JoinPoints() ...
3225 OutRec *holeStateRec;
3226 if (outRec1 == outRec2) holeStateRec = outRec1;
3227 else if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
3228 else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
3229 else holeStateRec = GetLowermostRec(outRec1, outRec2);
3230
3231 if (!JoinPoints(&join, outRec1, outRec2)) continue;
3232
3233 if (outRec1 == outRec2)
3234 {
3235 //instead of joining two polygons, we've just created a new one by
3236 //splitting one polygon into two.
3237 outRec1->Pts = join.OutPt1;
3238 outRec1->BottomPt = 0;
3239 outRec2 = CreateOutRec();
3240 outRec2->Pts = join.OutPt2;
3241
3242 //update all OutRec2.Pts Idx's ...
3243 UpdateOutPtIdxs(*outRec2);
3244
3245 //We now need to check every OutRec.FirstLeft pointer. If it points
3246 //to OutRec1 it may need to point to OutRec2 instead ...
3247 if (m_UsingPolyTree)
3248 for (size_t j = 0; j < m_PolyOuts.size() - 1; j++)
3249 {
3250 OutRec* oRec = m_PolyOuts[j];
3251 OutRec* firstLeft = oRec->FirstLeft;
3252 while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;
3253 if (!oRec->Pts || firstLeft != outRec1 ||
3254 oRec->IsHole == outRec1->IsHole) continue;
3255 if (Poly2ContainsPoly1(oRec->Pts, join.OutPt2))
3256 oRec->FirstLeft = outRec2;
3257 }
3258
3259 if (Poly2ContainsPoly1(outRec2->Pts, outRec1->Pts))
3260 {
3261 //outRec2 is contained by outRec1 ...
3262 outRec2->IsHole = !outRec1->IsHole;
3263 outRec2->FirstLeft = outRec1;
3264
3265 // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.
3266 if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
3267
3268 if ((outRec2->IsHole ^ m_ReverseOutput) == (Area(*outRec2) > 0))
3269 ReversePolyPtLinks(outRec2->Pts);
3270
3271 } else if (Poly2ContainsPoly1(outRec1->Pts, outRec2->Pts))
3272 {
3273 //outRec1 is contained by outRec2 ...
3274 outRec2->IsHole = outRec1->IsHole;
3275 outRec1->IsHole = !outRec2->IsHole;
3276 outRec2->FirstLeft = outRec1->FirstLeft;
3277 outRec1->FirstLeft = outRec2;
3278
3279 // For each m_PolyOuts, replace FirstLeft from outRec1 to outRec2.
3280 if (m_UsingPolyTree) FixupFirstLefts2(outRec1, outRec2);
3281
3282 if ((outRec1->IsHole ^ m_ReverseOutput) == (Area(*outRec1) > 0))
3283 ReversePolyPtLinks(outRec1->Pts);
3284 }
3285 else
3286 {
3287 //the 2 polygons are completely separate ...
3288 outRec2->IsHole = outRec1->IsHole;
3289 outRec2->FirstLeft = outRec1->FirstLeft;
3290
3291 //fixup FirstLeft pointers that may need reassigning to OutRec2
3292 // For each polygon of m_PolyOuts, replace FirstLeft from outRec1 to outRec2 if the polygon is inside outRec2.
3293 //FIXME This is potentially very expensive! O(n^3)!
3294 if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec2);
3295 }
3296
3297 } else
3298 {
3299 //joined 2 polygons together ...
3300
3301 outRec2->Pts = 0;
3302 outRec2->BottomPt = 0;
3303 outRec2->Idx = outRec1->Idx;
3304
3305 outRec1->IsHole = holeStateRec->IsHole;
3306 if (holeStateRec == outRec2)
3307 outRec1->FirstLeft = outRec2->FirstLeft;
3308 outRec2->FirstLeft = outRec1;
3309
3310 // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.
3311 if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
3312 }
3313 }
3314 }
3315
3316 //------------------------------------------------------------------------------
3317 // ClipperOffset support functions ...
3318 //------------------------------------------------------------------------------
3319
GetUnitNormal(const IntPoint & pt1,const IntPoint & pt2)3320 DoublePoint GetUnitNormal(const IntPoint &pt1, const IntPoint &pt2)
3321 {
3322 if(pt2.X == pt1.X && pt2.Y == pt1.Y)
3323 return DoublePoint(0, 0);
3324
3325 double Dx = (double)(pt2.X - pt1.X);
3326 double dy = (double)(pt2.Y - pt1.Y);
3327 double f = 1 *1.0/ std::sqrt( Dx*Dx + dy*dy );
3328 Dx *= f;
3329 dy *= f;
3330 return DoublePoint(dy, -Dx);
3331 }
3332
3333 //------------------------------------------------------------------------------
3334 // ClipperOffset class
3335 //------------------------------------------------------------------------------
3336
Clear()3337 void ClipperOffset::Clear()
3338 {
3339 for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
3340 delete m_polyNodes.Childs[i];
3341 m_polyNodes.Childs.clear();
3342 m_lowest.X = -1;
3343 }
3344 //------------------------------------------------------------------------------
3345
AddPath(const Path & path,JoinType joinType,EndType endType)3346 void ClipperOffset::AddPath(const Path& path, JoinType joinType, EndType endType)
3347 {
3348 int highI = (int)path.size() - 1;
3349 if (highI < 0) return;
3350 PolyNode* newNode = new PolyNode();
3351 newNode->m_jointype = joinType;
3352 newNode->m_endtype = endType;
3353
3354 //strip duplicate points from path and also get index to the lowest point ...
3355 bool has_shortest_edge_length = ShortestEdgeLength > 0.;
3356 double shortest_edge_length2 = has_shortest_edge_length ? ShortestEdgeLength * ShortestEdgeLength : 0.;
3357 if (endType == etClosedLine || endType == etClosedPolygon)
3358 for (; highI > 0; -- highI) {
3359 bool same = false;
3360 if (has_shortest_edge_length) {
3361 double dx = double(path[highI].X - path[0].X);
3362 double dy = double(path[highI].Y - path[0].Y);
3363 same = dx*dx + dy*dy < shortest_edge_length2;
3364 } else
3365 same = path[0] == path[highI];
3366 if (! same)
3367 break;
3368 }
3369 newNode->Contour.reserve(highI + 1);
3370 newNode->Contour.push_back(path[0]);
3371 int j = 0, k = 0;
3372 for (int i = 1; i <= highI; i++) {
3373 bool same = false;
3374 if (has_shortest_edge_length) {
3375 double dx = double(path[i].X - newNode->Contour[j].X);
3376 double dy = double(path[i].Y - newNode->Contour[j].Y);
3377 same = dx*dx + dy*dy < shortest_edge_length2;
3378 } else
3379 same = newNode->Contour[j] == path[i];
3380 if (same)
3381 continue;
3382 j++;
3383 newNode->Contour.push_back(path[i]);
3384 if (path[i].Y > newNode->Contour[k].Y ||
3385 (path[i].Y == newNode->Contour[k].Y &&
3386 path[i].X < newNode->Contour[k].X)) k = j;
3387 }
3388 if (endType == etClosedPolygon && j < 2)
3389 {
3390 delete newNode;
3391 return;
3392 }
3393 m_polyNodes.AddChild(*newNode);
3394
3395 //if this path's lowest pt is lower than all the others then update m_lowest
3396 if (endType != etClosedPolygon) return;
3397 if (m_lowest.X < 0)
3398 m_lowest = IntPoint(m_polyNodes.ChildCount() - 1, k);
3399 else
3400 {
3401 IntPoint ip = m_polyNodes.Childs[(int)m_lowest.X]->Contour[(int)m_lowest.Y];
3402 if (newNode->Contour[k].Y > ip.Y ||
3403 (newNode->Contour[k].Y == ip.Y &&
3404 newNode->Contour[k].X < ip.X))
3405 m_lowest = IntPoint(m_polyNodes.ChildCount() - 1, k);
3406 }
3407 }
3408 //------------------------------------------------------------------------------
3409
AddPaths(const Paths & paths,JoinType joinType,EndType endType)3410 void ClipperOffset::AddPaths(const Paths& paths, JoinType joinType, EndType endType)
3411 {
3412 for (const Path &path : paths)
3413 AddPath(path, joinType, endType);
3414 }
3415 //------------------------------------------------------------------------------
3416
FixOrientations()3417 void ClipperOffset::FixOrientations()
3418 {
3419 //fixup orientations of all closed paths if the orientation of the
3420 //closed path with the lowermost vertex is wrong ...
3421 if (m_lowest.X >= 0 &&
3422 !Orientation(m_polyNodes.Childs[(int)m_lowest.X]->Contour))
3423 {
3424 for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
3425 {
3426 PolyNode& node = *m_polyNodes.Childs[i];
3427 if (node.m_endtype == etClosedPolygon ||
3428 (node.m_endtype == etClosedLine && Orientation(node.Contour)))
3429 ReversePath(node.Contour);
3430 }
3431 } else
3432 {
3433 for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
3434 {
3435 PolyNode& node = *m_polyNodes.Childs[i];
3436 if (node.m_endtype == etClosedLine && !Orientation(node.Contour))
3437 ReversePath(node.Contour);
3438 }
3439 }
3440 }
3441 //------------------------------------------------------------------------------
3442
Execute(Paths & solution,double delta)3443 void ClipperOffset::Execute(Paths& solution, double delta)
3444 {
3445 solution.clear();
3446 FixOrientations();
3447 DoOffset(delta);
3448
3449 //now clean up 'corners' ...
3450 Clipper clpr;
3451 clpr.AddPaths(m_destPolys, ptSubject, true);
3452 if (delta > 0)
3453 {
3454 clpr.Execute(ctUnion, solution, pftPositive, pftPositive);
3455 }
3456 else
3457 {
3458 IntRect r = clpr.GetBounds();
3459 Path outer(4);
3460 outer[0] = IntPoint(r.left - 10, r.bottom + 10);
3461 outer[1] = IntPoint(r.right + 10, r.bottom + 10);
3462 outer[2] = IntPoint(r.right + 10, r.top - 10);
3463 outer[3] = IntPoint(r.left - 10, r.top - 10);
3464
3465 clpr.AddPath(outer, ptSubject, true);
3466 clpr.ReverseSolution(true);
3467 clpr.Execute(ctUnion, solution, pftNegative, pftNegative);
3468 if (solution.size() > 0) solution.erase(solution.begin());
3469 }
3470 }
3471 //------------------------------------------------------------------------------
3472
Execute(PolyTree & solution,double delta)3473 void ClipperOffset::Execute(PolyTree& solution, double delta)
3474 {
3475 solution.Clear();
3476 FixOrientations();
3477 DoOffset(delta);
3478
3479 //now clean up 'corners' ...
3480 Clipper clpr;
3481 clpr.AddPaths(m_destPolys, ptSubject, true);
3482 if (delta > 0)
3483 {
3484 clpr.Execute(ctUnion, solution, pftPositive, pftPositive);
3485 }
3486 else
3487 {
3488 IntRect r = clpr.GetBounds();
3489 Path outer(4);
3490 outer[0] = IntPoint(r.left - 10, r.bottom + 10);
3491 outer[1] = IntPoint(r.right + 10, r.bottom + 10);
3492 outer[2] = IntPoint(r.right + 10, r.top - 10);
3493 outer[3] = IntPoint(r.left - 10, r.top - 10);
3494
3495 clpr.AddPath(outer, ptSubject, true);
3496 clpr.ReverseSolution(true);
3497 clpr.Execute(ctUnion, solution, pftNegative, pftNegative);
3498 //remove the outer PolyNode rectangle ...
3499 if (solution.ChildCount() == 1 && solution.Childs[0]->ChildCount() > 0)
3500 {
3501 PolyNode* outerNode = solution.Childs[0];
3502 solution.Childs.reserve(outerNode->ChildCount());
3503 solution.Childs[0] = outerNode->Childs[0];
3504 solution.Childs[0]->Parent = outerNode->Parent;
3505 for (int i = 1; i < outerNode->ChildCount(); ++i)
3506 solution.AddChild(*outerNode->Childs[i]);
3507 }
3508 else
3509 solution.Clear();
3510 }
3511 }
3512 //------------------------------------------------------------------------------
3513
DoOffset(double delta)3514 void ClipperOffset::DoOffset(double delta)
3515 {
3516 m_destPolys.clear();
3517 m_delta = delta;
3518
3519 //if Zero offset, just copy any CLOSED polygons to m_p and return ...
3520 if (NEAR_ZERO(delta))
3521 {
3522 m_destPolys.reserve(m_polyNodes.ChildCount());
3523 for (int i = 0; i < m_polyNodes.ChildCount(); i++)
3524 {
3525 PolyNode& node = *m_polyNodes.Childs[i];
3526 if (node.m_endtype == etClosedPolygon)
3527 m_destPolys.push_back(node.Contour);
3528 }
3529 return;
3530 }
3531
3532 //see offset_triginometry3.svg in the documentation folder ...
3533 if (MiterLimit > 2) m_miterLim = 2/(MiterLimit * MiterLimit);
3534 else m_miterLim = 0.5;
3535
3536 double y;
3537 if (ArcTolerance <= 0.0) y = def_arc_tolerance;
3538 else if (ArcTolerance > std::fabs(delta) * def_arc_tolerance)
3539 y = std::fabs(delta) * def_arc_tolerance;
3540 else y = ArcTolerance;
3541 //see offset_triginometry2.svg in the documentation folder ...
3542 double steps = pi / std::acos(1 - y / std::fabs(delta));
3543 if (steps > std::fabs(delta) * pi)
3544 steps = std::fabs(delta) * pi; //ie excessive precision check
3545 m_sin = std::sin(two_pi / steps);
3546 m_cos = std::cos(two_pi / steps);
3547 m_StepsPerRad = steps / two_pi;
3548 if (delta < 0.0) m_sin = -m_sin;
3549
3550 m_destPolys.reserve(m_polyNodes.ChildCount() * 2);
3551 for (int i = 0; i < m_polyNodes.ChildCount(); i++)
3552 {
3553 PolyNode& node = *m_polyNodes.Childs[i];
3554 m_srcPoly = node.Contour;
3555
3556 int len = (int)m_srcPoly.size();
3557 if (len == 0 || (delta <= 0 && (len < 3 || node.m_endtype != etClosedPolygon)))
3558 continue;
3559
3560 m_destPoly.clear();
3561 if (len == 1)
3562 {
3563 if (node.m_jointype == jtRound)
3564 {
3565 double X = 1.0, Y = 0.0;
3566 for (cInt j = 1; j <= steps; j++)
3567 {
3568 m_destPoly.push_back(IntPoint(
3569 Round(m_srcPoly[0].X + X * delta),
3570 Round(m_srcPoly[0].Y + Y * delta)));
3571 double X2 = X;
3572 X = X * m_cos - m_sin * Y;
3573 Y = X2 * m_sin + Y * m_cos;
3574 }
3575 }
3576 else
3577 {
3578 double X = -1.0, Y = -1.0;
3579 for (int j = 0; j < 4; ++j)
3580 {
3581 m_destPoly.push_back(IntPoint(
3582 Round(m_srcPoly[0].X + X * delta),
3583 Round(m_srcPoly[0].Y + Y * delta)));
3584 if (X < 0) X = 1;
3585 else if (Y < 0) Y = 1;
3586 else X = -1;
3587 }
3588 }
3589 m_destPolys.push_back(m_destPoly);
3590 continue;
3591 }
3592 //build m_normals ...
3593 m_normals.clear();
3594 m_normals.reserve(len);
3595 for (int j = 0; j < len - 1; ++j)
3596 m_normals.push_back(GetUnitNormal(m_srcPoly[j], m_srcPoly[j + 1]));
3597 if (node.m_endtype == etClosedLine || node.m_endtype == etClosedPolygon)
3598 m_normals.push_back(GetUnitNormal(m_srcPoly[len - 1], m_srcPoly[0]));
3599 else
3600 m_normals.push_back(DoublePoint(m_normals[len - 2]));
3601
3602 if (node.m_endtype == etClosedPolygon)
3603 {
3604 int k = len - 1;
3605 for (int j = 0; j < len; ++j)
3606 OffsetPoint(j, k, node.m_jointype);
3607 m_destPolys.push_back(m_destPoly);
3608 }
3609 else if (node.m_endtype == etClosedLine)
3610 {
3611 int k = len - 1;
3612 for (int j = 0; j < len; ++j)
3613 OffsetPoint(j, k, node.m_jointype);
3614 m_destPolys.push_back(m_destPoly);
3615 m_destPoly.clear();
3616 //re-build m_normals ...
3617 DoublePoint n = m_normals[len -1];
3618 for (int j = len - 1; j > 0; j--)
3619 m_normals[j] = DoublePoint(-m_normals[j - 1].X, -m_normals[j - 1].Y);
3620 m_normals[0] = DoublePoint(-n.X, -n.Y);
3621 k = 0;
3622 for (int j = len - 1; j >= 0; j--)
3623 OffsetPoint(j, k, node.m_jointype);
3624 m_destPolys.push_back(m_destPoly);
3625 }
3626 else
3627 {
3628 int k = 0;
3629 for (int j = 1; j < len - 1; ++j)
3630 OffsetPoint(j, k, node.m_jointype);
3631
3632 IntPoint pt1;
3633 if (node.m_endtype == etOpenButt)
3634 {
3635 int j = len - 1;
3636 pt1 = IntPoint(Round(m_srcPoly[j].X + m_normals[j].X *
3637 delta), Round(m_srcPoly[j].Y + m_normals[j].Y * delta));
3638 m_destPoly.push_back(pt1);
3639 pt1 = IntPoint(Round(m_srcPoly[j].X - m_normals[j].X *
3640 delta), Round(m_srcPoly[j].Y - m_normals[j].Y * delta));
3641 m_destPoly.push_back(pt1);
3642 }
3643 else
3644 {
3645 int j = len - 1;
3646 k = len - 2;
3647 m_sinA = 0;
3648 m_normals[j] = DoublePoint(-m_normals[j].X, -m_normals[j].Y);
3649 if (node.m_endtype == etOpenSquare)
3650 DoSquare(j, k);
3651 else
3652 DoRound(j, k);
3653 }
3654
3655 //re-build m_normals ...
3656 for (int j = len - 1; j > 0; j--)
3657 m_normals[j] = DoublePoint(-m_normals[j - 1].X, -m_normals[j - 1].Y);
3658 m_normals[0] = DoublePoint(-m_normals[1].X, -m_normals[1].Y);
3659
3660 k = len - 1;
3661 for (int j = k - 1; j > 0; --j) OffsetPoint(j, k, node.m_jointype);
3662
3663 if (node.m_endtype == etOpenButt)
3664 {
3665 pt1 = IntPoint(Round(m_srcPoly[0].X - m_normals[0].X * delta),
3666 Round(m_srcPoly[0].Y - m_normals[0].Y * delta));
3667 m_destPoly.push_back(pt1);
3668 pt1 = IntPoint(Round(m_srcPoly[0].X + m_normals[0].X * delta),
3669 Round(m_srcPoly[0].Y + m_normals[0].Y * delta));
3670 m_destPoly.push_back(pt1);
3671 }
3672 else
3673 {
3674 k = 1;
3675 m_sinA = 0;
3676 if (node.m_endtype == etOpenSquare)
3677 DoSquare(0, 1);
3678 else
3679 DoRound(0, 1);
3680 }
3681 m_destPolys.push_back(m_destPoly);
3682 }
3683 }
3684 }
3685 //------------------------------------------------------------------------------
3686
OffsetPoint(int j,int & k,JoinType jointype)3687 void ClipperOffset::OffsetPoint(int j, int& k, JoinType jointype)
3688 {
3689 //cross product ...
3690 m_sinA = (m_normals[k].X * m_normals[j].Y - m_normals[j].X * m_normals[k].Y);
3691 if (std::fabs(m_sinA * m_delta) < 1.0)
3692 {
3693 //dot product ...
3694 double cosA = (m_normals[k].X * m_normals[j].X + m_normals[j].Y * m_normals[k].Y );
3695 if (cosA > 0) // angle => 0 degrees
3696 {
3697 m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + m_normals[k].X * m_delta),
3698 Round(m_srcPoly[j].Y + m_normals[k].Y * m_delta)));
3699 return;
3700 }
3701 //else angle => 180 degrees
3702 }
3703 else if (m_sinA > 1.0) m_sinA = 1.0;
3704 else if (m_sinA < -1.0) m_sinA = -1.0;
3705
3706 if (m_sinA * m_delta < 0)
3707 {
3708 m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + m_normals[k].X * m_delta),
3709 Round(m_srcPoly[j].Y + m_normals[k].Y * m_delta)));
3710 m_destPoly.push_back(m_srcPoly[j]);
3711 m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + m_normals[j].X * m_delta),
3712 Round(m_srcPoly[j].Y + m_normals[j].Y * m_delta)));
3713 }
3714 else
3715 switch (jointype)
3716 {
3717 case jtMiter:
3718 {
3719 double r = 1 + (m_normals[j].X * m_normals[k].X +
3720 m_normals[j].Y * m_normals[k].Y);
3721 if (r >= m_miterLim) DoMiter(j, k, r); else DoSquare(j, k);
3722 break;
3723 }
3724 case jtSquare: DoSquare(j, k); break;
3725 case jtRound: DoRound(j, k); break;
3726 }
3727 k = j;
3728 }
3729 //------------------------------------------------------------------------------
3730
DoSquare(int j,int k)3731 void ClipperOffset::DoSquare(int j, int k)
3732 {
3733 double dx = std::tan(std::atan2(m_sinA,
3734 m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y) / 4);
3735 m_destPoly.push_back(IntPoint(
3736 Round(m_srcPoly[j].X + m_delta * (m_normals[k].X - m_normals[k].Y * dx)),
3737 Round(m_srcPoly[j].Y + m_delta * (m_normals[k].Y + m_normals[k].X * dx))));
3738 m_destPoly.push_back(IntPoint(
3739 Round(m_srcPoly[j].X + m_delta * (m_normals[j].X + m_normals[j].Y * dx)),
3740 Round(m_srcPoly[j].Y + m_delta * (m_normals[j].Y - m_normals[j].X * dx))));
3741 }
3742 //------------------------------------------------------------------------------
3743
DoMiter(int j,int k,double r)3744 void ClipperOffset::DoMiter(int j, int k, double r)
3745 {
3746 double q = m_delta / r;
3747 m_destPoly.push_back(IntPoint(Round(m_srcPoly[j].X + (m_normals[k].X + m_normals[j].X) * q),
3748 Round(m_srcPoly[j].Y + (m_normals[k].Y + m_normals[j].Y) * q)));
3749 }
3750 //------------------------------------------------------------------------------
3751
DoRound(int j,int k)3752 void ClipperOffset::DoRound(int j, int k)
3753 {
3754 double a = std::atan2(m_sinA,
3755 m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y);
3756 int steps = std::max((int)Round(m_StepsPerRad * std::fabs(a)), 1);
3757
3758 double X = m_normals[k].X, Y = m_normals[k].Y, X2;
3759 for (int i = 0; i < steps; ++i)
3760 {
3761 m_destPoly.push_back(IntPoint(
3762 Round(m_srcPoly[j].X + X * m_delta),
3763 Round(m_srcPoly[j].Y + Y * m_delta)));
3764 X2 = X;
3765 X = X * m_cos - m_sin * Y;
3766 Y = X2 * m_sin + Y * m_cos;
3767 }
3768 m_destPoly.push_back(IntPoint(
3769 Round(m_srcPoly[j].X + m_normals[j].X * m_delta),
3770 Round(m_srcPoly[j].Y + m_normals[j].Y * m_delta)));
3771 }
3772
3773 //------------------------------------------------------------------------------
3774 // Miscellaneous public functions
3775 //------------------------------------------------------------------------------
3776
3777 // Called by Clipper::ExecuteInternal()
3778 // For each polygon, search for exactly duplicate non-successive points.
3779 // If such a point is found, the loop is split into two pieces.
3780 // Search for the duplicate points is O(n^2)!
3781 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/Clipper/Properties/StrictlySimple.htm
DoSimplePolygons()3782 void Clipper::DoSimplePolygons()
3783 {
3784 CLIPPERLIB_PROFILE_FUNC();
3785 size_t i = 0;
3786 while (i < m_PolyOuts.size())
3787 {
3788 OutRec* outrec = m_PolyOuts[i++];
3789 OutPt* op = outrec->Pts;
3790 if (!op || outrec->IsOpen) continue;
3791 do //for each Pt in Polygon until duplicate found do ...
3792 {
3793 OutPt* op2 = op->Next;
3794 while (op2 != outrec->Pts)
3795 {
3796 if ((op->Pt == op2->Pt) && op2->Next != op && op2->Prev != op)
3797 {
3798 //split the polygon into two ...
3799 OutPt* op3 = op->Prev;
3800 OutPt* op4 = op2->Prev;
3801 op->Prev = op4;
3802 op4->Next = op;
3803 op2->Prev = op3;
3804 op3->Next = op2;
3805
3806 outrec->Pts = op;
3807 OutRec* outrec2 = CreateOutRec();
3808 outrec2->Pts = op2;
3809 UpdateOutPtIdxs(*outrec2);
3810 if (Poly2ContainsPoly1(outrec2->Pts, outrec->Pts))
3811 {
3812 //OutRec2 is contained by OutRec1 ...
3813 outrec2->IsHole = !outrec->IsHole;
3814 outrec2->FirstLeft = outrec;
3815 // For each m_PolyOuts, replace FirstLeft from outRec2 to outrec.
3816 if (m_UsingPolyTree) FixupFirstLefts2(outrec2, outrec);
3817 }
3818 else
3819 if (Poly2ContainsPoly1(outrec->Pts, outrec2->Pts))
3820 {
3821 //OutRec1 is contained by OutRec2 ...
3822 outrec2->IsHole = outrec->IsHole;
3823 outrec->IsHole = !outrec2->IsHole;
3824 outrec2->FirstLeft = outrec->FirstLeft;
3825 outrec->FirstLeft = outrec2;
3826 // For each m_PolyOuts, replace FirstLeft from outrec to outrec2.
3827 if (m_UsingPolyTree) FixupFirstLefts2(outrec, outrec2);
3828 }
3829 else
3830 {
3831 //the 2 polygons are separate ...
3832 outrec2->IsHole = outrec->IsHole;
3833 outrec2->FirstLeft = outrec->FirstLeft;
3834 // For each polygon of m_PolyOuts, replace FirstLeft from outrec to outrec2 if the polygon is inside outRec2.
3835 //FIXME This is potentially very expensive! O(n^3)!
3836 if (m_UsingPolyTree) FixupFirstLefts1(outrec, outrec2);
3837 }
3838 op2 = op; //ie get ready for the Next iteration
3839 }
3840 op2 = op2->Next;
3841 }
3842 op = op->Next;
3843 }
3844 while (op != outrec->Pts);
3845 }
3846 }
3847 //------------------------------------------------------------------------------
3848
ReversePath(Path & p)3849 void ReversePath(Path& p)
3850 {
3851 std::reverse(p.begin(), p.end());
3852 }
3853 //------------------------------------------------------------------------------
3854
ReversePaths(Paths & p)3855 void ReversePaths(Paths& p)
3856 {
3857 for (Paths::size_type i = 0; i < p.size(); ++i)
3858 ReversePath(p[i]);
3859 }
3860 //------------------------------------------------------------------------------
3861
SimplifyPolygon(const Path & in_poly,Paths & out_polys,PolyFillType fillType)3862 void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fillType)
3863 {
3864 Clipper c;
3865 c.StrictlySimple(true);
3866 c.AddPath(in_poly, ptSubject, true);
3867 c.Execute(ctUnion, out_polys, fillType, fillType);
3868 }
3869 //------------------------------------------------------------------------------
3870
SimplifyPolygons(const Paths & in_polys,Paths & out_polys,PolyFillType fillType)3871 void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType)
3872 {
3873 Clipper c;
3874 c.StrictlySimple(true);
3875 c.AddPaths(in_polys, ptSubject, true);
3876 c.Execute(ctUnion, out_polys, fillType, fillType);
3877 }
3878 //------------------------------------------------------------------------------
3879
SimplifyPolygons(Paths & polys,PolyFillType fillType)3880 void SimplifyPolygons(Paths &polys, PolyFillType fillType)
3881 {
3882 SimplifyPolygons(polys, polys, fillType);
3883 }
3884 //------------------------------------------------------------------------------
3885
DistanceSqrd(const IntPoint & pt1,const IntPoint & pt2)3886 inline double DistanceSqrd(const IntPoint& pt1, const IntPoint& pt2)
3887 {
3888 double Dx = ((double)pt1.X - pt2.X);
3889 double dy = ((double)pt1.Y - pt2.Y);
3890 return (Dx*Dx + dy*dy);
3891 }
3892 //------------------------------------------------------------------------------
3893
DistanceFromLineSqrd(const IntPoint & pt,const IntPoint & ln1,const IntPoint & ln2)3894 double DistanceFromLineSqrd(
3895 const IntPoint& pt, const IntPoint& ln1, const IntPoint& ln2)
3896 {
3897 //The equation of a line in general form (Ax + By + C = 0)
3898 //given 2 points (x�,y�) & (x�,y�) is ...
3899 //(y� - y�)x + (x� - x�)y + (y� - y�)x� - (x� - x�)y� = 0
3900 //A = (y� - y�); B = (x� - x�); C = (y� - y�)x� - (x� - x�)y�
3901 //perpendicular distance of point (x�,y�) = (Ax� + By� + C)/Sqrt(A� + B�)
3902 //see http://en.wikipedia.org/wiki/Perpendicular_distance
3903 double A = double(ln1.Y - ln2.Y);
3904 double B = double(ln2.X - ln1.X);
3905 double C = A * ln1.X + B * ln1.Y;
3906 C = A * pt.X + B * pt.Y - C;
3907 return (C * C) / (A * A + B * B);
3908 }
3909 //---------------------------------------------------------------------------
3910
SlopesNearCollinear(const IntPoint & pt1,const IntPoint & pt2,const IntPoint & pt3,double distSqrd)3911 bool SlopesNearCollinear(const IntPoint& pt1,
3912 const IntPoint& pt2, const IntPoint& pt3, double distSqrd)
3913 {
3914 //this function is more accurate when the point that's geometrically
3915 //between the other 2 points is the one that's tested for distance.
3916 //ie makes it more likely to pick up 'spikes' ...
3917 if (std::abs(pt1.X - pt2.X) > std::abs(pt1.Y - pt2.Y))
3918 {
3919 if ((pt1.X > pt2.X) == (pt1.X < pt3.X))
3920 return DistanceFromLineSqrd(pt1, pt2, pt3) < distSqrd;
3921 else if ((pt2.X > pt1.X) == (pt2.X < pt3.X))
3922 return DistanceFromLineSqrd(pt2, pt1, pt3) < distSqrd;
3923 else
3924 return DistanceFromLineSqrd(pt3, pt1, pt2) < distSqrd;
3925 }
3926 else
3927 {
3928 if ((pt1.Y > pt2.Y) == (pt1.Y < pt3.Y))
3929 return DistanceFromLineSqrd(pt1, pt2, pt3) < distSqrd;
3930 else if ((pt2.Y > pt1.Y) == (pt2.Y < pt3.Y))
3931 return DistanceFromLineSqrd(pt2, pt1, pt3) < distSqrd;
3932 else
3933 return DistanceFromLineSqrd(pt3, pt1, pt2) < distSqrd;
3934 }
3935 }
3936 //------------------------------------------------------------------------------
3937
PointsAreClose(IntPoint pt1,IntPoint pt2,double distSqrd)3938 bool PointsAreClose(IntPoint pt1, IntPoint pt2, double distSqrd)
3939 {
3940 double Dx = (double)pt1.X - pt2.X;
3941 double dy = (double)pt1.Y - pt2.Y;
3942 return ((Dx * Dx) + (dy * dy) <= distSqrd);
3943 }
3944 //------------------------------------------------------------------------------
3945
ExcludeOp(OutPt * op)3946 OutPt* ExcludeOp(OutPt* op)
3947 {
3948 OutPt* result = op->Prev;
3949 result->Next = op->Next;
3950 op->Next->Prev = result;
3951 result->Idx = 0;
3952 return result;
3953 }
3954 //------------------------------------------------------------------------------
3955
3956 // Simplify a polygon using a linked list of points.
CleanPolygon(const Path & in_poly,Path & out_poly,double distance)3957 void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)
3958 {
3959 //distance = proximity in units/pixels below which vertices
3960 //will be stripped. Default ~= sqrt(2).
3961
3962 size_t size = in_poly.size();
3963
3964 if (size == 0)
3965 {
3966 out_poly.clear();
3967 return;
3968 }
3969
3970 std::vector<OutPt> outPts(size);
3971 for (size_t i = 0; i < size; ++i)
3972 {
3973 outPts[i].Pt = in_poly[i];
3974 outPts[i].Next = &outPts[(i + 1) % size];
3975 outPts[i].Next->Prev = &outPts[i];
3976 outPts[i].Idx = 0;
3977 }
3978
3979 double distSqrd = distance * distance;
3980 OutPt* op = &outPts[0];
3981 while (op->Idx == 0 && op->Next != op->Prev)
3982 {
3983 if (PointsAreClose(op->Pt, op->Prev->Pt, distSqrd))
3984 {
3985 op = ExcludeOp(op);
3986 size--;
3987 }
3988 else if (PointsAreClose(op->Prev->Pt, op->Next->Pt, distSqrd))
3989 {
3990 ExcludeOp(op->Next);
3991 op = ExcludeOp(op);
3992 size -= 2;
3993 }
3994 else if (SlopesNearCollinear(op->Prev->Pt, op->Pt, op->Next->Pt, distSqrd))
3995 {
3996 op = ExcludeOp(op);
3997 size--;
3998 }
3999 else
4000 {
4001 op->Idx = 1;
4002 op = op->Next;
4003 }
4004 }
4005
4006 if (size < 3) size = 0;
4007 out_poly.resize(size);
4008 for (size_t i = 0; i < size; ++i)
4009 {
4010 out_poly[i] = op->Pt;
4011 op = op->Next;
4012 }
4013 }
4014 //------------------------------------------------------------------------------
4015
CleanPolygon(Path & poly,double distance)4016 void CleanPolygon(Path& poly, double distance)
4017 {
4018 CleanPolygon(poly, poly, distance);
4019 }
4020 //------------------------------------------------------------------------------
4021
CleanPolygons(const Paths & in_polys,Paths & out_polys,double distance)4022 void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance)
4023 {
4024 for (Paths::size_type i = 0; i < in_polys.size(); ++i)
4025 CleanPolygon(in_polys[i], out_polys[i], distance);
4026 }
4027 //------------------------------------------------------------------------------
4028
CleanPolygons(Paths & polys,double distance)4029 void CleanPolygons(Paths& polys, double distance)
4030 {
4031 CleanPolygons(polys, polys, distance);
4032 }
4033 //------------------------------------------------------------------------------
4034
Minkowski(const Path & poly,const Path & path,Paths & solution,bool isSum,bool isClosed)4035 void Minkowski(const Path& poly, const Path& path,
4036 Paths& solution, bool isSum, bool isClosed)
4037 {
4038 int delta = (isClosed ? 1 : 0);
4039 size_t polyCnt = poly.size();
4040 size_t pathCnt = path.size();
4041 Paths pp;
4042 pp.reserve(pathCnt);
4043 if (isSum)
4044 for (size_t i = 0; i < pathCnt; ++i)
4045 {
4046 Path p;
4047 p.reserve(polyCnt);
4048 for (size_t j = 0; j < poly.size(); ++j)
4049 p.push_back(IntPoint(path[i].X + poly[j].X, path[i].Y + poly[j].Y));
4050 pp.push_back(p);
4051 }
4052 else
4053 for (size_t i = 0; i < pathCnt; ++i)
4054 {
4055 Path p;
4056 p.reserve(polyCnt);
4057 for (size_t j = 0; j < poly.size(); ++j)
4058 p.push_back(IntPoint(path[i].X - poly[j].X, path[i].Y - poly[j].Y));
4059 pp.push_back(p);
4060 }
4061
4062 solution.clear();
4063 solution.reserve((pathCnt + delta) * (polyCnt + 1));
4064 for (size_t i = 0; i < pathCnt - 1 + delta; ++i)
4065 for (size_t j = 0; j < polyCnt; ++j)
4066 {
4067 Path quad;
4068 quad.reserve(4);
4069 quad.push_back(pp[i % pathCnt][j % polyCnt]);
4070 quad.push_back(pp[(i + 1) % pathCnt][j % polyCnt]);
4071 quad.push_back(pp[(i + 1) % pathCnt][(j + 1) % polyCnt]);
4072 quad.push_back(pp[i % pathCnt][(j + 1) % polyCnt]);
4073 if (!Orientation(quad)) ReversePath(quad);
4074 solution.push_back(quad);
4075 }
4076 }
4077 //------------------------------------------------------------------------------
4078
MinkowskiSum(const Path & pattern,const Path & path,Paths & solution,bool pathIsClosed)4079 void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed)
4080 {
4081 Minkowski(pattern, path, solution, true, pathIsClosed);
4082 Clipper c;
4083 c.AddPaths(solution, ptSubject, true);
4084 c.Execute(ctUnion, solution, pftNonZero, pftNonZero);
4085 }
4086 //------------------------------------------------------------------------------
4087
TranslatePath(const Path & input,Path & output,const IntPoint & delta)4088 void TranslatePath(const Path& input, Path& output, const IntPoint& delta)
4089 {
4090 //precondition: input != output
4091 output.resize(input.size());
4092 for (size_t i = 0; i < input.size(); ++i)
4093 output[i] = IntPoint(input[i].X + delta.X, input[i].Y + delta.Y);
4094 }
4095 //------------------------------------------------------------------------------
4096
MinkowskiSum(const Path & pattern,const Paths & paths,Paths & solution,bool pathIsClosed)4097 void MinkowskiSum(const Path& pattern, const Paths& paths, Paths& solution, bool pathIsClosed)
4098 {
4099 Clipper c;
4100 for (size_t i = 0; i < paths.size(); ++i)
4101 {
4102 Paths tmp;
4103 Minkowski(pattern, paths[i], tmp, true, pathIsClosed);
4104 c.AddPaths(tmp, ptSubject, true);
4105 if (pathIsClosed)
4106 {
4107 Path tmp2;
4108 TranslatePath(paths[i], tmp2, pattern[0]);
4109 c.AddPath(tmp2, ptClip, true);
4110 }
4111 }
4112 c.Execute(ctUnion, solution, pftNonZero, pftNonZero);
4113 }
4114 //------------------------------------------------------------------------------
4115
MinkowskiDiff(const Path & poly1,const Path & poly2,Paths & solution)4116 void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution)
4117 {
4118 Minkowski(poly1, poly2, solution, false, true);
4119 Clipper c;
4120 c.AddPaths(solution, ptSubject, true);
4121 c.Execute(ctUnion, solution, pftNonZero, pftNonZero);
4122 }
4123 //------------------------------------------------------------------------------
4124
4125 enum NodeType {ntAny, ntOpen, ntClosed};
4126
AddPolyNodeToPaths(const PolyNode & polynode,NodeType nodetype,Paths & paths)4127 void AddPolyNodeToPaths(const PolyNode& polynode, NodeType nodetype, Paths& paths)
4128 {
4129 bool match = true;
4130 if (nodetype == ntClosed) match = !polynode.IsOpen();
4131 else if (nodetype == ntOpen) return;
4132
4133 if (!polynode.Contour.empty() && match)
4134 paths.push_back(polynode.Contour);
4135 for (int i = 0; i < polynode.ChildCount(); ++i)
4136 AddPolyNodeToPaths(*polynode.Childs[i], nodetype, paths);
4137 }
4138 //------------------------------------------------------------------------------
4139
PolyTreeToPaths(const PolyTree & polytree,Paths & paths)4140 void PolyTreeToPaths(const PolyTree& polytree, Paths& paths)
4141 {
4142 paths.resize(0);
4143 paths.reserve(polytree.Total());
4144 AddPolyNodeToPaths(polytree, ntAny, paths);
4145 }
4146 //------------------------------------------------------------------------------
4147
ClosedPathsFromPolyTree(const PolyTree & polytree,Paths & paths)4148 void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths)
4149 {
4150 paths.resize(0);
4151 paths.reserve(polytree.Total());
4152 AddPolyNodeToPaths(polytree, ntClosed, paths);
4153 }
4154 //------------------------------------------------------------------------------
4155
OpenPathsFromPolyTree(PolyTree & polytree,Paths & paths)4156 void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths)
4157 {
4158 paths.resize(0);
4159 paths.reserve(polytree.Total());
4160 //Open paths are top level only, so ...
4161 for (int i = 0; i < polytree.ChildCount(); ++i)
4162 if (polytree.Childs[i]->IsOpen())
4163 paths.push_back(polytree.Childs[i]->Contour);
4164 }
4165 //------------------------------------------------------------------------------
4166
operator <<(std::ostream & s,const IntPoint & p)4167 std::ostream& operator <<(std::ostream &s, const IntPoint &p)
4168 {
4169 s << "(" << p.X << "," << p.Y << ")";
4170 return s;
4171 }
4172 //------------------------------------------------------------------------------
4173
operator <<(std::ostream & s,const Path & p)4174 std::ostream& operator <<(std::ostream &s, const Path &p)
4175 {
4176 if (p.empty()) return s;
4177 Path::size_type last = p.size() -1;
4178 for (Path::size_type i = 0; i < last; i++)
4179 s << "(" << p[i].X << "," << p[i].Y << "), ";
4180 s << "(" << p[last].X << "," << p[last].Y << ")\n";
4181 return s;
4182 }
4183 //------------------------------------------------------------------------------
4184
operator <<(std::ostream & s,const Paths & p)4185 std::ostream& operator <<(std::ostream &s, const Paths &p)
4186 {
4187 for (Paths::size_type i = 0; i < p.size(); i++)
4188 s << p[i];
4189 s << "\n";
4190 return s;
4191 }
4192 //------------------------------------------------------------------------------
4193
4194 } //ClipperLib namespace
4195