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