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