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