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