1 /*******************************************************************************
2 * *
3 * Author : Angus Johnson *
4 * Version : 4.8.8 *
5 * Date : 30 August 2012 *
6 * Website : http://www.angusj.com *
7 * Copyright : Angus Johnson 2010-2012 *
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
50 namespace ClipperLib {
51
52 static long64 const loRange = 0x3FFFFFFF;
53 static long64 const hiRange = 0x3FFFFFFFFFFFFFFFLL;
54 static double const pi = 3.141592653589793238;
55 enum Direction { dRightToLeft, dLeftToRight };
56
57 #define HORIZONTAL (-1.0E+40)
58 #define TOLERANCE (1.0e-20)
59 #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))
60 #define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b))
61
Abs(long64 val)62 inline long64 Abs(long64 val)
63 {
64 return val < 0 ? -val : val;
65 }
66 //------------------------------------------------------------------------------
67
68 //------------------------------------------------------------------------------
69 // Int128 class (enables safe math on signed 64bit integers)
70 // eg Int128 val1((long64)9223372036854775807); //ie 2^63 -1
71 // Int128 val2((long64)9223372036854775807);
72 // Int128 val3 = val1 * val2;
73 // val3.AsString => "85070591730234615847396907784232501249" (8.5e+37)
74 //------------------------------------------------------------------------------
75
76 class Int128
77 {
78 public:
79
Int128(long64 _lo=0)80 Int128(long64 _lo = 0)
81 {
82 lo = _lo;
83 if (lo < 0) hi = -1; else hi = 0;
84 }
85
Int128(const Int128 & val)86 Int128(const Int128 &val): hi(val.hi), lo(val.lo){}
87
operator =(const long64 & val)88 long64 operator = (const long64 &val)
89 {
90 lo = val;
91 if (lo < 0) hi = -1; else hi = 0;
92 return val;
93 }
94
operator ==(const Int128 & val) const95 bool operator == (const Int128 &val) const
96 {return (hi == val.hi && lo == val.lo);}
97
operator !=(const Int128 & val) const98 bool operator != (const Int128 &val) const
99 { return !(*this == val);}
100
operator >(const Int128 & val) const101 bool operator > (const Int128 &val) const
102 {
103 if (hi != val.hi)
104 return hi > val.hi;
105 else
106 return lo > val.lo;
107 }
108
operator <(const Int128 & val) const109 bool operator < (const Int128 &val) const
110 {
111 if (hi != val.hi)
112 return hi < val.hi;
113 else
114 return lo < val.lo;
115 }
116
operator >=(const Int128 & val) const117 bool operator >= (const Int128 &val) const
118 { return !(*this < val);}
119
operator <=(const Int128 & val) const120 bool operator <= (const Int128 &val) const
121 { return !(*this > val);}
122
operator +=(const Int128 & rhs)123 Int128& operator += (const Int128 &rhs)
124 {
125 hi += rhs.hi;
126 lo += rhs.lo;
127 if (ulong64(lo) < ulong64(rhs.lo)) hi++;
128 return *this;
129 }
130
operator +(const Int128 & rhs) const131 Int128 operator + (const Int128 &rhs) const
132 {
133 Int128 result(*this);
134 result+= rhs;
135 return result;
136 }
137
operator -=(const Int128 & rhs)138 Int128& operator -= (const Int128 &rhs)
139 {
140 Int128 tmp(rhs);
141 Negate(tmp);
142 *this += tmp;
143 return *this;
144 }
145
146 //Int128 operator -() const
147 //{
148 // Int128 result(*this);
149 // if (result.lo == 0) {
150 // if (result.hi != 0) result.hi = -1;
151 // }
152 // else {
153 // result.lo = -result.lo;
154 // result.hi = ~result.hi;
155 // }
156 // return result;
157 //}
158
operator -(const Int128 & rhs) const159 Int128 operator - (const Int128 &rhs) const
160 {
161 Int128 result(*this);
162 result -= rhs;
163 return result;
164 }
165
operator *(const Int128 & rhs) const166 Int128 operator * (const Int128 &rhs) const
167 {
168 if ( !(hi == 0 || hi == -1) || !(rhs.hi == 0 || rhs.hi == -1))
169 throw "Int128 operator*: overflow error";
170 bool negate = (hi < 0) != (rhs.hi < 0);
171
172 Int128 tmp(*this);
173 if (tmp.hi < 0) Negate(tmp);
174 ulong64 int1Hi = ulong64(tmp.lo) >> 32;
175 ulong64 int1Lo = ulong64(tmp.lo & 0xFFFFFFFF);
176
177 tmp = rhs;
178 if (tmp.hi < 0) Negate(tmp);
179 ulong64 int2Hi = ulong64(tmp.lo) >> 32;
180 ulong64 int2Lo = ulong64(tmp.lo & 0xFFFFFFFF);
181
182 //nb: see comments in clipper.pas
183 ulong64 a = int1Hi * int2Hi;
184 ulong64 b = int1Lo * int2Lo;
185 ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi;
186
187 tmp.hi = long64(a + (c >> 32));
188 tmp.lo = long64(c << 32);
189 tmp.lo += long64(b);
190 if (ulong64(tmp.lo) < b) tmp.hi++;
191 if (negate) Negate(tmp);
192 return tmp;
193 }
194
operator /(const Int128 & rhs) const195 Int128 operator/ (const Int128 &rhs) const
196 {
197 if (rhs.lo == 0 && rhs.hi == 0)
198 throw "Int128 operator/: divide by zero";
199 bool negate = (rhs.hi < 0) != (hi < 0);
200 Int128 result(*this), denom(rhs);
201 if (result.hi < 0) Negate(result);
202 if (denom.hi < 0) Negate(denom);
203 if (denom > result) return Int128(0); //result is only a fraction of 1
204 Negate(denom);
205
206 Int128 p(0);
207 for (int i = 0; i < 128; ++i)
208 {
209 p.hi = p.hi << 1;
210 if (p.lo < 0) p.hi++;
211 p.lo = long64(p.lo) << 1;
212 if (result.hi < 0) p.lo++;
213 result.hi = result.hi << 1;
214 if (result.lo < 0) result.hi++;
215 result.lo = long64(result.lo) << 1;
216 Int128 p2(p);
217 p += denom;
218 if (p.hi < 0) p = p2;
219 else result.lo++;
220 }
221 if (negate) Negate(result);
222 return result;
223 }
224
AsDouble() const225 double AsDouble() const
226 {
227 const double shift64 = 18446744073709551616.0; //2^64
228 const double bit64 = 9223372036854775808.0;
229 if (hi < 0)
230 {
231 Int128 tmp(*this);
232 Negate(tmp);
233 if (tmp.lo < 0)
234 return (double)tmp.lo - bit64 - tmp.hi * shift64;
235 else
236 return -(double)tmp.lo - tmp.hi * shift64;
237 }
238 else if (lo < 0)
239 return -(double)lo + bit64 + hi * shift64;
240 else
241 return (double)lo + (double)hi * shift64;
242 }
243
244 //for bug testing ...
245 //std::string AsString() const
246 //{
247 // std::string result;
248 // unsigned char r = 0;
249 // Int128 tmp(0), val(*this);
250 // if (hi < 0) Negate(val);
251 // result.resize(50);
252 // std::string::size_type i = result.size() -1;
253 // while (val.hi != 0 || val.lo != 0)
254 // {
255 // Div10(val, tmp, r);
256 // result[i--] = char('0' + r);
257 // val = tmp;
258 // }
259 // if (hi < 0) result[i--] = '-';
260 // result.erase(0,i+1);
261 // if (result.size() == 0) result = "0";
262 // return result;
263 //}
264
265 private:
266 long64 hi;
267 long64 lo;
268
Negate(Int128 & val)269 static void Negate(Int128 &val)
270 {
271 if (val.lo == 0) {
272 if (val.hi != 0) val.hi = -val.hi;;
273 }
274 else {
275 val.lo = -val.lo;
276 val.hi = ~val.hi;
277 }
278 }
279
280 //debugging only ...
281 //void Div10(const Int128 val, Int128& result, unsigned char & remainder) const
282 //{
283 // remainder = 0;
284 // result = 0;
285 // for (int i = 63; i >= 0; --i)
286 // {
287 // if ((val.hi & ((long64)1 << i)) != 0)
288 // remainder = char((remainder * 2) + 1); else
289 // remainder *= char(2);
290 // if (remainder >= 10)
291 // {
292 // result.hi += ((long64)1 << i);
293 // remainder -= char(10);
294 // }
295 // }
296 // for (int i = 63; i >= 0; --i)
297 // {
298 // if ((val.lo & ((long64)1 << i)) != 0)
299 // remainder = char((remainder * 2) + 1); else
300 // remainder *= char(2);
301 // if (remainder >= 10)
302 // {
303 // result.lo += ((long64)1 << i);
304 // remainder -= char(10);
305 // }
306 // }
307 //}
308 };
309
310 //------------------------------------------------------------------------------
311 //------------------------------------------------------------------------------
312
FullRangeNeeded(const Polygon & pts)313 bool FullRangeNeeded(const Polygon &pts)
314 {
315 bool result = false;
316 for (Polygon::size_type i = 0; i < pts.size(); ++i)
317 {
318 if (Abs(pts[i].X) > hiRange || Abs(pts[i].Y) > hiRange)
319 throw "Coordinate exceeds range bounds.";
320 else if (Abs(pts[i].X) > loRange || Abs(pts[i].Y) > loRange)
321 result = true;
322 }
323 return result;
324 }
325 //------------------------------------------------------------------------------
326
Orientation(const Polygon & poly)327 bool Orientation(const Polygon &poly)
328 {
329 int highI = (int)poly.size() -1;
330 if (highI < 2) return false;
331
332 int j = 0, jplus, jminus;
333 for (int i = 0; i <= highI; ++i)
334 {
335 if (poly[i].Y < poly[j].Y) continue;
336 if ((poly[i].Y > poly[j].Y || poly[i].X < poly[j].X)) j = i;
337 };
338 if (j == highI) jplus = 0;
339 else jplus = j +1;
340 if (j == 0) jminus = highI;
341 else jminus = j -1;
342
343 IntPoint vec1, vec2;
344 //get cross product of vectors of the edges adjacent to highest point ...
345 vec1.X = poly[j].X - poly[jminus].X;
346 vec1.Y = poly[j].Y - poly[jminus].Y;
347 vec2.X = poly[jplus].X - poly[j].X;
348 vec2.Y = poly[jplus].Y - poly[j].Y;
349
350 if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange ||
351 Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange)
352 {
353 if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange ||
354 Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange)
355 throw "Coordinate exceeds range bounds.";
356 Int128 cross = Int128(vec1.X) * Int128(vec2.Y) -
357 Int128(vec2.X) * Int128(vec1.Y);
358 return cross >= 0;
359 }
360 else
361 return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0;
362 }
363 //------------------------------------------------------------------------------
364
PointsEqual(const IntPoint & pt1,const IntPoint & pt2)365 inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2)
366 {
367 return ( pt1.X == pt2.X && pt1.Y == pt2.Y );
368 }
369 //------------------------------------------------------------------------------
370
Orientation(OutRec * outRec,bool UseFullInt64Range)371 bool Orientation(OutRec *outRec, bool UseFullInt64Range)
372 {
373 //first make sure bottomPt is correctly assigned ...
374 OutPt *opBottom = outRec->pts, *op = outRec->pts->next;
375 while (op != outRec->pts)
376 {
377 if (op->pt.Y >= opBottom->pt.Y)
378 {
379 if (op->pt.Y > opBottom->pt.Y || op->pt.X < opBottom->pt.X)
380 opBottom = op;
381 }
382 op = op->next;
383 }
384 outRec->bottomPt = opBottom;
385 opBottom->idx = outRec->idx;
386
387 op = opBottom;
388 //find vertices either side of bottomPt (skipping duplicate points) ....
389 OutPt *opPrev = op->prev;
390 OutPt *opNext = op->next;
391 while (op != opPrev && PointsEqual(op->pt, opPrev->pt))
392 opPrev = opPrev->prev;
393 while (op != opNext && PointsEqual(op->pt, opNext->pt))
394 opNext = opNext->next;
395
396 IntPoint ip1, ip2;
397 ip1.X = op->pt.X - opPrev->pt.X;
398 ip1.Y = op->pt.Y - opPrev->pt.Y;
399 ip2.X = opNext->pt.X - op->pt.X;
400 ip2.Y = opNext->pt.Y - op->pt.Y;
401
402 if (UseFullInt64Range)
403 return Int128(ip1.X) * Int128(ip2.Y) - Int128(ip2.X) * Int128(ip1.Y) >= 0;
404 else
405 return (ip1.X * ip2.Y - ip2.X * ip1.Y) >= 0;
406 }
407 //------------------------------------------------------------------------------
408
Area(const Polygon & poly)409 double Area(const Polygon &poly)
410 {
411 int highI = (int)poly.size() -1;
412 if (highI < 2) return 0;
413
414 if (FullRangeNeeded(poly)) {
415 Int128 a;
416 a = (Int128(poly[highI].X) * Int128(poly[0].Y)) -
417 Int128(poly[0].X) * Int128(poly[highI].Y);
418 for (int i = 0; i < highI; ++i)
419 a += Int128(poly[i].X) * Int128(poly[i+1].Y) -
420 Int128(poly[i+1].X) * Int128(poly[i].Y);
421 return a.AsDouble() / 2;
422 }
423 else
424 {
425 double a;
426 a = (double)poly[highI].X * poly[0].Y - (double)poly[0].X * poly[highI].Y;
427 for (int i = 0; i < highI; ++i)
428 a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * poly[i].Y;
429 return a/2;
430 }
431 }
432 //------------------------------------------------------------------------------
433
Area(const OutRec & outRec,bool UseFullInt64Range)434 double Area(const OutRec &outRec, bool UseFullInt64Range)
435 {
436 OutPt *op = outRec.pts;
437 if (UseFullInt64Range) {
438 Int128 a(0);
439 do {
440 a += (Int128(op->prev->pt.X) * Int128(op->pt.Y)) -
441 Int128(op->pt.X) * Int128(op->prev->pt.Y);
442 op = op->next;
443 } while (op != outRec.pts);
444 return a.AsDouble() / 2;
445 }
446 else
447 {
448 double a = 0;
449 do {
450 a += (op->prev->pt.X * op->pt.Y) - (op->pt.X * op->prev->pt.Y);
451 op = op->next;
452 } while (op != outRec.pts);
453 return a/2;
454 }
455 }
456 //------------------------------------------------------------------------------
457
PointIsVertex(const IntPoint & pt,OutPt * pp)458 bool PointIsVertex(const IntPoint &pt, OutPt *pp)
459 {
460 OutPt *pp2 = pp;
461 do
462 {
463 if (PointsEqual(pp2->pt, pt)) return true;
464 pp2 = pp2->next;
465 }
466 while (pp2 != pp);
467 return false;
468 }
469 //------------------------------------------------------------------------------
470
PointInPolygon(const IntPoint & pt,OutPt * pp,bool UseFullInt64Range)471 bool PointInPolygon(const IntPoint &pt, OutPt *pp, bool UseFullInt64Range)
472 {
473 OutPt *pp2 = pp;
474 bool result = false;
475 if (UseFullInt64Range) {
476 do
477 {
478 if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) ||
479 ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) &&
480 Int128(pt.X - pp2->pt.X) < (Int128(pp2->prev->pt.X - pp2->pt.X) *
481 Int128(pt.Y - pp2->pt.Y)) / Int128(pp2->prev->pt.Y - pp2->pt.Y))
482 result = !result;
483 pp2 = pp2->next;
484 }
485 while (pp2 != pp);
486 }
487 else
488 {
489 do
490 {
491 if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) ||
492 ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) &&
493 (pt.X < (pp2->prev->pt.X - pp2->pt.X) * (pt.Y - pp2->pt.Y) /
494 (pp2->prev->pt.Y - pp2->pt.Y) + pp2->pt.X )) result = !result;
495 pp2 = pp2->next;
496 }
497 while (pp2 != pp);
498 }
499 return result;
500 }
501 //------------------------------------------------------------------------------
502
SlopesEqual(TEdge & e1,TEdge & e2,bool UseFullInt64Range)503 bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range)
504 {
505 if (UseFullInt64Range)
506 return Int128(e1.ytop - e1.ybot) * Int128(e2.xtop - e2.xbot) ==
507 Int128(e1.xtop - e1.xbot) * Int128(e2.ytop - e2.ybot);
508 else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) ==
509 (e1.xtop - e1.xbot)*(e2.ytop - e2.ybot);
510 }
511 //------------------------------------------------------------------------------
512
SlopesEqual(const IntPoint pt1,const IntPoint pt2,const IntPoint pt3,bool UseFullInt64Range)513 bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
514 const IntPoint pt3, bool UseFullInt64Range)
515 {
516 if (UseFullInt64Range)
517 return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) ==
518 Int128(pt1.X-pt2.X) * Int128(pt2.Y-pt3.Y);
519 else return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y);
520 }
521 //------------------------------------------------------------------------------
522
SlopesEqual(const IntPoint pt1,const IntPoint pt2,const IntPoint pt3,const IntPoint pt4,bool UseFullInt64Range)523 bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
524 const IntPoint pt3, const IntPoint pt4, bool UseFullInt64Range)
525 {
526 if (UseFullInt64Range)
527 return Int128(pt1.Y-pt2.Y) * Int128(pt3.X-pt4.X) ==
528 Int128(pt1.X-pt2.X) * Int128(pt3.Y-pt4.Y);
529 else return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y);
530 }
531 //------------------------------------------------------------------------------
532
GetDx(const IntPoint pt1,const IntPoint pt2)533 double GetDx(const IntPoint pt1, const IntPoint pt2)
534 {
535 return (pt1.Y == pt2.Y) ?
536 HORIZONTAL : (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y);
537 }
538 //---------------------------------------------------------------------------
539
SetDx(TEdge & e)540 void SetDx(TEdge &e)
541 {
542 if (e.ybot == e.ytop) e.dx = HORIZONTAL;
543 else e.dx = (double)(e.xtop - e.xbot) / (double)(e.ytop - e.ybot);
544 }
545 //---------------------------------------------------------------------------
546
SwapSides(TEdge & edge1,TEdge & edge2)547 void SwapSides(TEdge &edge1, TEdge &edge2)
548 {
549 EdgeSide side = edge1.side;
550 edge1.side = edge2.side;
551 edge2.side = side;
552 }
553 //------------------------------------------------------------------------------
554
SwapPolyIndexes(TEdge & edge1,TEdge & edge2)555 void SwapPolyIndexes(TEdge &edge1, TEdge &edge2)
556 {
557 int outIdx = edge1.outIdx;
558 edge1.outIdx = edge2.outIdx;
559 edge2.outIdx = outIdx;
560 }
561 //------------------------------------------------------------------------------
562
Round(double val)563 inline long64 Round(double val)
564 {
565 return (val < 0) ?
566 static_cast<long64>(val - 0.5) : static_cast<long64>(val + 0.5);
567 }
568 //------------------------------------------------------------------------------
569
TopX(TEdge & edge,const long64 currentY)570 long64 TopX(TEdge &edge, const long64 currentY)
571 {
572 return ( currentY == edge.ytop ) ?
573 edge.xtop : edge.xbot + Round(edge.dx *(currentY - edge.ybot));
574 }
575 //------------------------------------------------------------------------------
576
TopX(const IntPoint pt1,const IntPoint pt2,const long64 currentY)577 long64 TopX(const IntPoint pt1, const IntPoint pt2, const long64 currentY)
578 {
579 //preconditions: pt1.Y <> pt2.Y and pt1.Y > pt2.Y
580 if (currentY >= pt1.Y) return pt1.X;
581 else if (currentY == pt2.Y) return pt2.X;
582 else if (pt1.X == pt2.X) return pt1.X;
583 else
584 {
585 double q = (double)(pt1.X-pt2.X)/(double)(pt1.Y-pt2.Y);
586 return Round(pt1.X + (currentY - pt1.Y) *q);
587 }
588 }
589 //------------------------------------------------------------------------------
590
IntersectPoint(TEdge & edge1,TEdge & edge2,IntPoint & ip,bool UseFullInt64Range)591 bool IntersectPoint(TEdge &edge1, TEdge &edge2,
592 IntPoint &ip, bool UseFullInt64Range)
593 {
594 double b1, b2;
595 if (SlopesEqual(edge1, edge2, UseFullInt64Range)) return false;
596 else if (NEAR_ZERO(edge1.dx))
597 {
598 ip.X = edge1.xbot;
599 if (NEAR_EQUAL(edge2.dx, HORIZONTAL))
600 {
601 ip.Y = edge2.ybot;
602 } else
603 {
604 b2 = edge2.ybot - (edge2.xbot/edge2.dx);
605 ip.Y = Round(ip.X/edge2.dx + b2);
606 }
607 }
608 else if (NEAR_ZERO(edge2.dx))
609 {
610 ip.X = edge2.xbot;
611 if (NEAR_EQUAL(edge1.dx, HORIZONTAL))
612 {
613 ip.Y = edge1.ybot;
614 } else
615 {
616 b1 = edge1.ybot - (edge1.xbot/edge1.dx);
617 ip.Y = Round(ip.X/edge1.dx + b1);
618 }
619 } else
620 {
621 b1 = edge1.xbot - edge1.ybot * edge1.dx;
622 b2 = edge2.xbot - edge2.ybot * edge2.dx;
623 b2 = (b2-b1)/(edge1.dx - edge2.dx);
624 ip.Y = Round(b2);
625 ip.X = Round(edge1.dx * b2 + b1);
626 }
627
628 return
629 //can be *so close* to the top of one edge that the rounded Y equals one ytop ...
630 (ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > edge2.tmpX) ||
631 (ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > edge2.tmpX) ||
632 (ip.Y > edge1.ytop && ip.Y > edge2.ytop);
633 }
634 //------------------------------------------------------------------------------
635
ReversePolyPtLinks(OutPt & pp)636 void ReversePolyPtLinks(OutPt &pp)
637 {
638 OutPt *pp1, *pp2;
639 pp1 = &pp;
640 do {
641 pp2 = pp1->next;
642 pp1->next = pp1->prev;
643 pp1->prev = pp2;
644 pp1 = pp2;
645 } while( pp1 != &pp );
646 }
647 //------------------------------------------------------------------------------
648
DisposeOutPts(OutPt * & pp)649 void DisposeOutPts(OutPt*& pp)
650 {
651 if (pp == 0) return;
652 pp->prev->next = 0;
653 while( pp )
654 {
655 OutPt *tmpPp = pp;
656 pp = pp->next;
657 delete tmpPp ;
658 }
659 }
660 //------------------------------------------------------------------------------
661
InitEdge(TEdge * e,TEdge * eNext,TEdge * ePrev,const IntPoint & pt,PolyType polyType)662 void InitEdge(TEdge *e, TEdge *eNext,
663 TEdge *ePrev, const IntPoint &pt, PolyType polyType)
664 {
665 std::memset( e, 0, sizeof( TEdge ));
666
667 e->next = eNext;
668 e->prev = ePrev;
669 e->xcurr = pt.X;
670 e->ycurr = pt.Y;
671 if (e->ycurr >= e->next->ycurr)
672 {
673 e->xbot = e->xcurr;
674 e->ybot = e->ycurr;
675 e->xtop = e->next->xcurr;
676 e->ytop = e->next->ycurr;
677 e->windDelta = 1;
678 } else
679 {
680 e->xtop = e->xcurr;
681 e->ytop = e->ycurr;
682 e->xbot = e->next->xcurr;
683 e->ybot = e->next->ycurr;
684 e->windDelta = -1;
685 }
686 SetDx(*e);
687 e->polyType = polyType;
688 e->outIdx = -1;
689 }
690 //------------------------------------------------------------------------------
691
SwapX(TEdge & e)692 inline void SwapX(TEdge &e)
693 {
694 //swap horizontal edges' top and bottom x's so they follow the natural
695 //progression of the bounds - ie so their xbots will align with the
696 //adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
697 e.xcurr = e.xtop;
698 e.xtop = e.xbot;
699 e.xbot = e.xcurr;
700 }
701 //------------------------------------------------------------------------------
702
SwapPoints(IntPoint & pt1,IntPoint & pt2)703 void SwapPoints(IntPoint &pt1, IntPoint &pt2)
704 {
705 IntPoint tmp = pt1;
706 pt1 = pt2;
707 pt2 = tmp;
708 }
709 //------------------------------------------------------------------------------
710
GetOverlapSegment(IntPoint pt1a,IntPoint pt1b,IntPoint pt2a,IntPoint pt2b,IntPoint & pt1,IntPoint & pt2)711 bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
712 IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
713 {
714 //precondition: segments are colinear.
715 if ( pt1a.Y == pt1b.Y || Abs((pt1a.X - pt1b.X)/(pt1a.Y - pt1b.Y)) > 1 )
716 {
717 if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b);
718 if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b);
719 if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
720 if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
721 return pt1.X < pt2.X;
722 } else
723 {
724 if (pt1a.Y < pt1b.Y) SwapPoints(pt1a, pt1b);
725 if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b);
726 if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
727 if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
728 return pt1.Y > pt2.Y;
729 }
730 }
731 //------------------------------------------------------------------------------
732
FirstIsBottomPt(const OutPt * btmPt1,const OutPt * btmPt2)733 bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
734 {
735 OutPt *p = btmPt1->prev;
736 while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->prev;
737 double dx1p = std::fabs(GetDx(btmPt1->pt, p->pt));
738 p = btmPt1->next;
739 while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->next;
740 double dx1n = std::fabs(GetDx(btmPt1->pt, p->pt));
741
742 p = btmPt2->prev;
743 while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->prev;
744 double dx2p = std::fabs(GetDx(btmPt2->pt, p->pt));
745 p = btmPt2->next;
746 while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->next;
747 double dx2n = std::fabs(GetDx(btmPt2->pt, p->pt));
748 return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
749 }
750 //------------------------------------------------------------------------------
751
GetBottomPt(OutPt * pp)752 OutPt* GetBottomPt(OutPt *pp)
753 {
754 OutPt* dups = 0;
755 OutPt* p = pp->next;
756 while (p != pp)
757 {
758 if (p->pt.Y > pp->pt.Y)
759 {
760 pp = p;
761 dups = 0;
762 }
763 else if (p->pt.Y == pp->pt.Y && p->pt.X <= pp->pt.X)
764 {
765 if (p->pt.X < pp->pt.X)
766 {
767 dups = 0;
768 pp = p;
769 } else
770 {
771 if (p->next != pp && p->prev != pp) dups = p;
772 }
773 }
774 p = p->next;
775 }
776 if (dups)
777 {
778 //there appears to be at least 2 vertices at bottomPt so ...
779 while (dups != p)
780 {
781 if (!FirstIsBottomPt(p, dups)) pp = dups;
782 dups = dups->next;
783 while (!PointsEqual(dups->pt, pp->pt)) dups = dups->next;
784 }
785 }
786 return pp;
787 }
788 //------------------------------------------------------------------------------
789
FindSegment(OutPt * & pp,IntPoint & pt1,IntPoint & pt2)790 bool FindSegment(OutPt* &pp, IntPoint &pt1, IntPoint &pt2)
791 {
792 //outPt1 & outPt2 => the overlap segment (if the function returns true)
793 if (!pp) return false;
794 OutPt* pp2 = pp;
795 IntPoint pt1a = pt1, pt2a = pt2;
796 do
797 {
798 if (SlopesEqual(pt1a, pt2a, pp->pt, pp->prev->pt, true) &&
799 SlopesEqual(pt1a, pt2a, pp->pt, true) &&
800 GetOverlapSegment(pt1a, pt2a, pp->pt, pp->prev->pt, pt1, pt2))
801 return true;
802 pp = pp->next;
803 }
804 while (pp != pp2);
805 return false;
806 }
807 //------------------------------------------------------------------------------
808
Pt3IsBetweenPt1AndPt2(const IntPoint pt1,const IntPoint pt2,const IntPoint pt3)809 bool Pt3IsBetweenPt1AndPt2(const IntPoint pt1,
810 const IntPoint pt2, const IntPoint pt3)
811 {
812 if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true;
813 else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X);
814 else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.Y);
815 }
816 //------------------------------------------------------------------------------
817
InsertPolyPtBetween(OutPt * p1,OutPt * p2,const IntPoint pt)818 OutPt* InsertPolyPtBetween(OutPt* p1, OutPt* p2, const IntPoint pt)
819 {
820 if (p1 == p2) throw "JoinError";
821 OutPt* result = new OutPt;
822 result->pt = pt;
823 if (p2 == p1->next)
824 {
825 p1->next = result;
826 p2->prev = result;
827 result->next = p2;
828 result->prev = p1;
829 } else
830 {
831 p2->next = result;
832 p1->prev = result;
833 result->next = p1;
834 result->prev = p2;
835 }
836 return result;
837 }
838
839 //------------------------------------------------------------------------------
840 // ClipperBase class methods ...
841 //------------------------------------------------------------------------------
842
ClipperBase()843 ClipperBase::ClipperBase() //constructor
844 {
845 m_MinimaList = 0;
846 m_CurrentLM = 0;
847 m_UseFullRange = true;
848 }
849 //------------------------------------------------------------------------------
850
~ClipperBase()851 ClipperBase::~ClipperBase() //destructor
852 {
853 Clear();
854 }
855 //------------------------------------------------------------------------------
856
AddPolygon(const Polygon & pg,PolyType polyType)857 bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType)
858 {
859 int len = (int)pg.size();
860 if (len < 3) return false;
861 Polygon p(len);
862 p[0] = pg[0];
863 int j = 0;
864
865 long64 maxVal;
866 if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange;
867
868 for (int i = 0; i < len; ++i)
869 {
870 if (Abs(pg[i].X) > maxVal || Abs(pg[i].Y) > maxVal)
871 {
872 if (Abs(pg[i].X) > hiRange || Abs(pg[i].Y) > hiRange)
873 throw "Coordinate exceeds range bounds";
874 maxVal = hiRange;
875 m_UseFullRange = true;
876 }
877
878 if (i == 0 || PointsEqual(p[j], pg[i])) continue;
879 else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i], m_UseFullRange))
880 {
881 if (PointsEqual(p[j-1], pg[i])) j--;
882 } else j++;
883 p[j] = pg[i];
884 }
885 if (j < 2) return false;
886
887 len = j+1;
888 while (len > 2)
889 {
890 //nb: test for point equality before testing slopes ...
891 if (PointsEqual(p[j], p[0])) j--;
892 else if (PointsEqual(p[0], p[1]) ||
893 SlopesEqual(p[j], p[0], p[1], m_UseFullRange))
894 p[0] = p[j--];
895 else if (SlopesEqual(p[j-1], p[j], p[0], m_UseFullRange)) j--;
896 else if (SlopesEqual(p[0], p[1], p[2], m_UseFullRange))
897 {
898 for (int i = 2; i <= j; ++i) p[i-1] = p[i];
899 j--;
900 }
901 else break;
902 len--;
903 }
904 if (len < 3) return false;
905
906 //create a new edge array ...
907 TEdge *edges = new TEdge [len];
908 m_edges.push_back(edges);
909
910 //convert vertices to a double-linked-list of edges and initialize ...
911 edges[0].xcurr = p[0].X;
912 edges[0].ycurr = p[0].Y;
913 InitEdge(&edges[len-1], &edges[0], &edges[len-2], p[len-1], polyType);
914 for (int i = len-2; i > 0; --i)
915 InitEdge(&edges[i], &edges[i+1], &edges[i-1], p[i], polyType);
916 InitEdge(&edges[0], &edges[1], &edges[len-1], p[0], polyType);
917
918 //reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates
919 //increase downward so the 'highest' edge will have the smallest ytop) ...
920 TEdge *e = &edges[0];
921 TEdge *eHighest = e;
922 do
923 {
924 e->xcurr = e->xbot;
925 e->ycurr = e->ybot;
926 if (e->ytop < eHighest->ytop) eHighest = e;
927 e = e->next;
928 }
929 while ( e != &edges[0]);
930
931 //make sure eHighest is positioned so the following loop works safely ...
932 if (eHighest->windDelta > 0) eHighest = eHighest->next;
933 if (NEAR_EQUAL(eHighest->dx, HORIZONTAL)) eHighest = eHighest->next;
934
935 //finally insert each local minima ...
936 e = eHighest;
937 do {
938 e = AddBoundsToLML(e);
939 }
940 while( e != eHighest );
941 return true;
942 }
943 //------------------------------------------------------------------------------
944
InsertLocalMinima(LocalMinima * newLm)945 void ClipperBase::InsertLocalMinima(LocalMinima *newLm)
946 {
947 if( ! m_MinimaList )
948 {
949 m_MinimaList = newLm;
950 }
951 else if( newLm->Y >= m_MinimaList->Y )
952 {
953 newLm->next = m_MinimaList;
954 m_MinimaList = newLm;
955 } else
956 {
957 LocalMinima* tmpLm = m_MinimaList;
958 while( tmpLm->next && ( newLm->Y < tmpLm->next->Y ) )
959 tmpLm = tmpLm->next;
960 newLm->next = tmpLm->next;
961 tmpLm->next = newLm;
962 }
963 }
964 //------------------------------------------------------------------------------
965
AddBoundsToLML(TEdge * e)966 TEdge* ClipperBase::AddBoundsToLML(TEdge *e)
967 {
968 //Starting at the top of one bound we progress to the bottom where there's
969 //a local minima. We then go to the top of the next bound. These two bounds
970 //form the left and right (or right and left) bounds of the local minima.
971 e->nextInLML = 0;
972 e = e->next;
973 for (;;)
974 {
975 if (NEAR_EQUAL(e->dx, HORIZONTAL))
976 {
977 //nb: proceed through horizontals when approaching from their right,
978 // but break on horizontal minima if approaching from their left.
979 // This ensures 'local minima' are always on the left of horizontals.
980 if (e->next->ytop < e->ytop && e->next->xbot > e->prev->xbot) break;
981 if (e->xtop != e->prev->xbot) SwapX(*e);
982 e->nextInLML = e->prev;
983 }
984 else if (e->ycurr == e->prev->ycurr) break;
985 else e->nextInLML = e->prev;
986 e = e->next;
987 }
988
989 //e and e.prev are now at a local minima ...
990 LocalMinima* newLm = new LocalMinima;
991 newLm->next = 0;
992 newLm->Y = e->prev->ybot;
993
994 if ( NEAR_EQUAL(e->dx, HORIZONTAL) ) //horizontal edges never start a left bound
995 {
996 if (e->xbot != e->prev->xbot) SwapX(*e);
997 newLm->leftBound = e->prev;
998 newLm->rightBound = e;
999 } else if (e->dx < e->prev->dx)
1000 {
1001 newLm->leftBound = e->prev;
1002 newLm->rightBound = e;
1003 } else
1004 {
1005 newLm->leftBound = e;
1006 newLm->rightBound = e->prev;
1007 }
1008 newLm->leftBound->side = esLeft;
1009 newLm->rightBound->side = esRight;
1010 InsertLocalMinima( newLm );
1011
1012 for (;;)
1013 {
1014 if ( e->next->ytop == e->ytop && !NEAR_EQUAL(e->next->dx, HORIZONTAL) ) break;
1015 e->nextInLML = e->next;
1016 e = e->next;
1017 if ( NEAR_EQUAL(e->dx, HORIZONTAL) && e->xbot != e->prev->xtop) SwapX(*e);
1018 }
1019 return e->next;
1020 }
1021 //------------------------------------------------------------------------------
1022
AddPolygons(const Polygons & ppg,PolyType polyType)1023 bool ClipperBase::AddPolygons(const Polygons &ppg, PolyType polyType)
1024 {
1025 bool result = false;
1026 for (Polygons::size_type i = 0; i < ppg.size(); ++i)
1027 if (AddPolygon(ppg[i], polyType)) result = true;
1028 return result;
1029 }
1030 //------------------------------------------------------------------------------
1031
Clear()1032 void ClipperBase::Clear()
1033 {
1034 DisposeLocalMinimaList();
1035 for (EdgeList::size_type i = 0; i < m_edges.size(); ++i) delete [] m_edges[i];
1036 m_edges.clear();
1037 m_UseFullRange = false;
1038 }
1039 //------------------------------------------------------------------------------
1040
Reset()1041 void ClipperBase::Reset()
1042 {
1043 m_CurrentLM = m_MinimaList;
1044 if( !m_CurrentLM ) return; //ie nothing to process
1045
1046 //reset all edges ...
1047 LocalMinima* lm = m_MinimaList;
1048 while( lm )
1049 {
1050 TEdge* e = lm->leftBound;
1051 while( e )
1052 {
1053 e->xcurr = e->xbot;
1054 e->ycurr = e->ybot;
1055 e->side = esLeft;
1056 e->outIdx = -1;
1057 e = e->nextInLML;
1058 }
1059 e = lm->rightBound;
1060 while( e )
1061 {
1062 e->xcurr = e->xbot;
1063 e->ycurr = e->ybot;
1064 e->side = esRight;
1065 e->outIdx = -1;
1066 e = e->nextInLML;
1067 }
1068 lm = lm->next;
1069 }
1070 }
1071 //------------------------------------------------------------------------------
1072
DisposeLocalMinimaList()1073 void ClipperBase::DisposeLocalMinimaList()
1074 {
1075 while( m_MinimaList )
1076 {
1077 LocalMinima* tmpLm = m_MinimaList->next;
1078 delete m_MinimaList;
1079 m_MinimaList = tmpLm;
1080 }
1081 m_CurrentLM = 0;
1082 }
1083 //------------------------------------------------------------------------------
1084
PopLocalMinima()1085 void ClipperBase::PopLocalMinima()
1086 {
1087 if( ! m_CurrentLM ) return;
1088 m_CurrentLM = m_CurrentLM->next;
1089 }
1090 //------------------------------------------------------------------------------
1091
GetBounds()1092 IntRect ClipperBase::GetBounds()
1093 {
1094 IntRect result;
1095 LocalMinima* lm = m_MinimaList;
1096 if (!lm)
1097 {
1098 result.left = result.top = result.right = result.bottom = 0;
1099 return result;
1100 }
1101 result.left = lm->leftBound->xbot;
1102 result.top = lm->leftBound->ybot;
1103 result.right = lm->leftBound->xbot;
1104 result.bottom = lm->leftBound->ybot;
1105 while (lm)
1106 {
1107 if (lm->leftBound->ybot > result.bottom)
1108 result.bottom = lm->leftBound->ybot;
1109 TEdge* e = lm->leftBound;
1110 for (;;) {
1111 TEdge* bottomE = e;
1112 while (e->nextInLML)
1113 {
1114 if (e->xbot < result.left) result.left = e->xbot;
1115 if (e->xbot > result.right) result.right = e->xbot;
1116 e = e->nextInLML;
1117 }
1118 if (e->xbot < result.left) result.left = e->xbot;
1119 if (e->xbot > result.right) result.right = e->xbot;
1120 if (e->xtop < result.left) result.left = e->xtop;
1121 if (e->xtop > result.right) result.right = e->xtop;
1122 if (e->ytop < result.top) result.top = e->ytop;
1123
1124 if (bottomE == lm->leftBound) e = lm->rightBound;
1125 else break;
1126 }
1127 lm = lm->next;
1128 }
1129 return result;
1130 }
1131
1132
1133 //------------------------------------------------------------------------------
1134 // TClipper methods ...
1135 //------------------------------------------------------------------------------
1136
Clipper()1137 Clipper::Clipper() : ClipperBase() //constructor
1138 {
1139 m_Scanbeam = 0;
1140 m_ActiveEdges = 0;
1141 m_SortedEdges = 0;
1142 m_IntersectNodes = 0;
1143 m_ExecuteLocked = false;
1144 m_UseFullRange = false;
1145 m_ReverseOutput = false;
1146 }
1147 //------------------------------------------------------------------------------
1148
~Clipper()1149 Clipper::~Clipper() //destructor
1150 {
1151 Clear();
1152 DisposeScanbeamList();
1153 }
1154 //------------------------------------------------------------------------------
1155
Clear()1156 void Clipper::Clear()
1157 {
1158 if (m_edges.size() == 0) return; //avoids problems with ClipperBase destructor
1159 DisposeAllPolyPts();
1160 ClipperBase::Clear();
1161 }
1162 //------------------------------------------------------------------------------
1163
DisposeScanbeamList()1164 void Clipper::DisposeScanbeamList()
1165 {
1166 while ( m_Scanbeam ) {
1167 Scanbeam* sb2 = m_Scanbeam->next;
1168 delete m_Scanbeam;
1169 m_Scanbeam = sb2;
1170 }
1171 }
1172 //------------------------------------------------------------------------------
1173
Reset()1174 void Clipper::Reset()
1175 {
1176 ClipperBase::Reset();
1177 m_Scanbeam = 0;
1178 m_ActiveEdges = 0;
1179 m_SortedEdges = 0;
1180 DisposeAllPolyPts();
1181 LocalMinima* lm = m_MinimaList;
1182 while (lm)
1183 {
1184 InsertScanbeam(lm->Y);
1185 InsertScanbeam(lm->leftBound->ytop);
1186 lm = lm->next;
1187 }
1188 }
1189 //------------------------------------------------------------------------------
1190
Execute(ClipType clipType,Polygons & solution,PolyFillType subjFillType,PolyFillType clipFillType)1191 bool Clipper::Execute(ClipType clipType, Polygons &solution,
1192 PolyFillType subjFillType, PolyFillType clipFillType)
1193 {
1194 if( m_ExecuteLocked ) return false;
1195 m_ExecuteLocked = true;
1196 solution.resize(0);
1197 m_SubjFillType = subjFillType;
1198 m_ClipFillType = clipFillType;
1199 m_ClipType = clipType;
1200 bool succeeded = ExecuteInternal(false);
1201 if (succeeded) BuildResult(solution);
1202 m_ExecuteLocked = false;
1203 return succeeded;
1204 }
1205 //------------------------------------------------------------------------------
1206
Execute(ClipType clipType,ExPolygons & solution,PolyFillType subjFillType,PolyFillType clipFillType)1207 bool Clipper::Execute(ClipType clipType, ExPolygons &solution,
1208 PolyFillType subjFillType, PolyFillType clipFillType)
1209 {
1210 if( m_ExecuteLocked ) return false;
1211 m_ExecuteLocked = true;
1212 solution.resize(0);
1213 m_SubjFillType = subjFillType;
1214 m_ClipFillType = clipFillType;
1215 m_ClipType = clipType;
1216 bool succeeded = ExecuteInternal(true);
1217 if (succeeded) BuildResultEx(solution);
1218 m_ExecuteLocked = false;
1219 return succeeded;
1220 }
1221 //------------------------------------------------------------------------------
1222
PolySort(OutRec * or1,OutRec * or2)1223 bool PolySort(OutRec *or1, OutRec *or2)
1224 {
1225 if (or1 == or2) return false;
1226 if (!or1->pts || !or2->pts)
1227 {
1228 if (or1->pts != or2->pts)
1229 {
1230 return or1->pts ? true : false;
1231 }
1232 else return false;
1233 }
1234 int i1, i2;
1235 if (or1->isHole)
1236 i1 = or1->FirstLeft->idx; else
1237 i1 = or1->idx;
1238 if (or2->isHole)
1239 i2 = or2->FirstLeft->idx; else
1240 i2 = or2->idx;
1241 int result = i1 - i2;
1242 if (result == 0 && (or1->isHole != or2->isHole))
1243 {
1244 return or1->isHole ? false : true;
1245 }
1246 else return result < 0;
1247 }
1248 //------------------------------------------------------------------------------
1249
FindAppendLinkEnd(OutRec * outRec)1250 OutRec* FindAppendLinkEnd(OutRec *outRec)
1251 {
1252 while (outRec->AppendLink) outRec = outRec->AppendLink;
1253 return outRec;
1254 }
1255 //------------------------------------------------------------------------------
1256
FixHoleLinkage(OutRec * outRec)1257 void Clipper::FixHoleLinkage(OutRec *outRec)
1258 {
1259 OutRec *tmp;
1260 if (outRec->bottomPt)
1261 tmp = m_PolyOuts[outRec->bottomPt->idx]->FirstLeft;
1262 else
1263 tmp = outRec->FirstLeft;
1264 if (outRec == tmp) throw clipperException("HoleLinkage error");
1265
1266 if (tmp)
1267 {
1268 if (tmp->AppendLink) tmp = FindAppendLinkEnd(tmp);
1269 if (tmp == outRec) tmp = 0;
1270 else if (tmp->isHole)
1271 {
1272 FixHoleLinkage(tmp);
1273 tmp = tmp->FirstLeft;
1274 }
1275 }
1276 outRec->FirstLeft = tmp;
1277 if (!tmp) outRec->isHole = false;
1278 outRec->AppendLink = 0;
1279 }
1280 //------------------------------------------------------------------------------
1281
ExecuteInternal(bool fixHoleLinkages)1282 bool Clipper::ExecuteInternal(bool fixHoleLinkages)
1283 {
1284 bool succeeded;
1285 try {
1286 Reset();
1287 if (!m_CurrentLM ) return true;
1288 long64 botY = PopScanbeam();
1289 do {
1290 InsertLocalMinimaIntoAEL(botY);
1291 ClearHorzJoins();
1292 ProcessHorizontals();
1293 long64 topY = PopScanbeam();
1294 succeeded = ProcessIntersections(botY, topY);
1295 if (!succeeded) break;
1296 ProcessEdgesAtTopOfScanbeam(topY);
1297 botY = topY;
1298 } while( m_Scanbeam );
1299 }
1300 catch(...) {
1301 succeeded = false;
1302 }
1303
1304 if (succeeded)
1305 {
1306 //tidy up output polygons and fix orientations where necessary ...
1307 for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
1308 {
1309 OutRec *outRec = m_PolyOuts[i];
1310 if (!outRec->pts) continue;
1311 FixupOutPolygon(*outRec);
1312 if (!outRec->pts) continue;
1313 if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec);
1314
1315 if (outRec->bottomPt == outRec->bottomFlag &&
1316 (Orientation(outRec, m_UseFullRange) != (Area(*outRec, m_UseFullRange) > 0)))
1317 DisposeBottomPt(*outRec);
1318
1319 if (outRec->isHole ==
1320 (m_ReverseOutput ^ Orientation(outRec, m_UseFullRange)))
1321 ReversePolyPtLinks(*outRec->pts);
1322 }
1323
1324 JoinCommonEdges(fixHoleLinkages);
1325 if (fixHoleLinkages)
1326 std::sort(m_PolyOuts.begin(), m_PolyOuts.end(), PolySort);
1327 }
1328
1329 ClearJoins();
1330 ClearHorzJoins();
1331 return succeeded;
1332 }
1333 //------------------------------------------------------------------------------
1334
InsertScanbeam(const long64 Y)1335 void Clipper::InsertScanbeam(const long64 Y)
1336 {
1337 if( !m_Scanbeam )
1338 {
1339 m_Scanbeam = new Scanbeam;
1340 m_Scanbeam->next = 0;
1341 m_Scanbeam->Y = Y;
1342 }
1343 else if( Y > m_Scanbeam->Y )
1344 {
1345 Scanbeam* newSb = new Scanbeam;
1346 newSb->Y = Y;
1347 newSb->next = m_Scanbeam;
1348 m_Scanbeam = newSb;
1349 } else
1350 {
1351 Scanbeam* sb2 = m_Scanbeam;
1352 while( sb2->next && ( Y <= sb2->next->Y ) ) sb2 = sb2->next;
1353 if( Y == sb2->Y ) return; //ie ignores duplicates
1354 Scanbeam* newSb = new Scanbeam;
1355 newSb->Y = Y;
1356 newSb->next = sb2->next;
1357 sb2->next = newSb;
1358 }
1359 }
1360 //------------------------------------------------------------------------------
1361
PopScanbeam()1362 long64 Clipper::PopScanbeam()
1363 {
1364 long64 Y = m_Scanbeam->Y;
1365 Scanbeam* sb2 = m_Scanbeam;
1366 m_Scanbeam = m_Scanbeam->next;
1367 delete sb2;
1368 return Y;
1369 }
1370 //------------------------------------------------------------------------------
1371
DisposeAllPolyPts()1372 void Clipper::DisposeAllPolyPts(){
1373 for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
1374 DisposeOutRec(i);
1375 m_PolyOuts.clear();
1376 }
1377 //------------------------------------------------------------------------------
1378
DisposeOutRec(PolyOutList::size_type index)1379 void Clipper::DisposeOutRec(PolyOutList::size_type index)
1380 {
1381 OutRec *outRec = m_PolyOuts[index];
1382 if (outRec->pts) DisposeOutPts(outRec->pts);
1383 delete outRec;
1384 m_PolyOuts[index] = 0;
1385 }
1386 //------------------------------------------------------------------------------
1387
SetWindingCount(TEdge & edge)1388 void Clipper::SetWindingCount(TEdge &edge)
1389 {
1390 TEdge *e = edge.prevInAEL;
1391 //find the edge of the same polytype that immediately preceeds 'edge' in AEL
1392 while ( e && e->polyType != edge.polyType ) e = e->prevInAEL;
1393 if ( !e )
1394 {
1395 edge.windCnt = edge.windDelta;
1396 edge.windCnt2 = 0;
1397 e = m_ActiveEdges; //ie get ready to calc windCnt2
1398 } else if ( IsEvenOddFillType(edge) )
1399 {
1400 //EvenOdd filling ...
1401 edge.windCnt = 1;
1402 edge.windCnt2 = e->windCnt2;
1403 e = e->nextInAEL; //ie get ready to calc windCnt2
1404 } else
1405 {
1406 //nonZero, Positive or Negative filling ...
1407 if ( e->windCnt * e->windDelta < 0 )
1408 {
1409 if (Abs(e->windCnt) > 1)
1410 {
1411 if (e->windDelta * edge.windDelta < 0) edge.windCnt = e->windCnt;
1412 else edge.windCnt = e->windCnt + edge.windDelta;
1413 } else
1414 edge.windCnt = e->windCnt + e->windDelta + edge.windDelta;
1415 } else
1416 {
1417 if ( Abs(e->windCnt) > 1 && e->windDelta * edge.windDelta < 0)
1418 edge.windCnt = e->windCnt;
1419 else if ( e->windCnt + edge.windDelta == 0 )
1420 edge.windCnt = e->windCnt;
1421 else edge.windCnt = e->windCnt + edge.windDelta;
1422 }
1423 edge.windCnt2 = e->windCnt2;
1424 e = e->nextInAEL; //ie get ready to calc windCnt2
1425 }
1426
1427 //update windCnt2 ...
1428 if ( IsEvenOddAltFillType(edge) )
1429 {
1430 //EvenOdd filling ...
1431 while ( e != &edge )
1432 {
1433 edge.windCnt2 = (edge.windCnt2 == 0) ? 1 : 0;
1434 e = e->nextInAEL;
1435 }
1436 } else
1437 {
1438 //nonZero, Positive or Negative filling ...
1439 while ( e != &edge )
1440 {
1441 edge.windCnt2 += e->windDelta;
1442 e = e->nextInAEL;
1443 }
1444 }
1445 }
1446 //------------------------------------------------------------------------------
1447
IsEvenOddFillType(const TEdge & edge) const1448 bool Clipper::IsEvenOddFillType(const TEdge& edge) const
1449 {
1450 if (edge.polyType == ptSubject)
1451 return m_SubjFillType == pftEvenOdd; else
1452 return m_ClipFillType == pftEvenOdd;
1453 }
1454 //------------------------------------------------------------------------------
1455
IsEvenOddAltFillType(const TEdge & edge) const1456 bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const
1457 {
1458 if (edge.polyType == ptSubject)
1459 return m_ClipFillType == pftEvenOdd; else
1460 return m_SubjFillType == pftEvenOdd;
1461 }
1462 //------------------------------------------------------------------------------
1463
IsContributing(const TEdge & edge) const1464 bool Clipper::IsContributing(const TEdge& edge) const
1465 {
1466 PolyFillType pft, pft2;
1467 if (edge.polyType == ptSubject)
1468 {
1469 pft = m_SubjFillType;
1470 pft2 = m_ClipFillType;
1471 } else
1472 {
1473 pft = m_ClipFillType;
1474 pft2 = m_SubjFillType;
1475 }
1476
1477 switch(pft)
1478 {
1479 case pftEvenOdd:
1480 case pftNonZero:
1481 if (Abs(edge.windCnt) != 1) return false;
1482 break;
1483 case pftPositive:
1484 if (edge.windCnt != 1) return false;
1485 break;
1486 default: //pftNegative
1487 if (edge.windCnt != -1) return false;
1488 }
1489
1490 switch(m_ClipType)
1491 {
1492 case ctIntersection:
1493 switch(pft2)
1494 {
1495 case pftEvenOdd:
1496 case pftNonZero:
1497 return (edge.windCnt2 != 0);
1498 case pftPositive:
1499 return (edge.windCnt2 > 0);
1500 default:
1501 return (edge.windCnt2 < 0);
1502 }
1503 case ctUnion:
1504 switch(pft2)
1505 {
1506 case pftEvenOdd:
1507 case pftNonZero:
1508 return (edge.windCnt2 == 0);
1509 case pftPositive:
1510 return (edge.windCnt2 <= 0);
1511 default:
1512 return (edge.windCnt2 >= 0);
1513 }
1514 case ctDifference:
1515 if (edge.polyType == ptSubject)
1516 switch(pft2)
1517 {
1518 case pftEvenOdd:
1519 case pftNonZero:
1520 return (edge.windCnt2 == 0);
1521 case pftPositive:
1522 return (edge.windCnt2 <= 0);
1523 default:
1524 return (edge.windCnt2 >= 0);
1525 }
1526 else
1527 switch(pft2)
1528 {
1529 case pftEvenOdd:
1530 case pftNonZero:
1531 return (edge.windCnt2 != 0);
1532 case pftPositive:
1533 return (edge.windCnt2 > 0);
1534 default:
1535 return (edge.windCnt2 < 0);
1536 }
1537 default:
1538 return true;
1539 }
1540 }
1541 //------------------------------------------------------------------------------
1542
AddLocalMinPoly(TEdge * e1,TEdge * e2,const IntPoint & pt)1543 void Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
1544 {
1545 TEdge *e, *prevE;
1546 if( NEAR_EQUAL(e2->dx, HORIZONTAL) || ( e1->dx > e2->dx ) )
1547 {
1548 AddOutPt( e1, pt );
1549 e2->outIdx = e1->outIdx;
1550 e1->side = esLeft;
1551 e2->side = esRight;
1552 e = e1;
1553 if (e->prevInAEL == e2)
1554 prevE = e2->prevInAEL;
1555 else
1556 prevE = e->prevInAEL;
1557 } else
1558 {
1559 AddOutPt( e2, pt );
1560 e1->outIdx = e2->outIdx;
1561 e1->side = esRight;
1562 e2->side = esLeft;
1563 e = e2;
1564 if (e->prevInAEL == e1)
1565 prevE = e1->prevInAEL;
1566 else
1567 prevE = e->prevInAEL;
1568 }
1569 if (prevE && prevE->outIdx >= 0 &&
1570 (TopX(*prevE, pt.Y) == TopX(*e, pt.Y)) &&
1571 SlopesEqual(*e, *prevE, m_UseFullRange))
1572 AddJoin(e, prevE, -1, -1);
1573 }
1574 //------------------------------------------------------------------------------
1575
AddLocalMaxPoly(TEdge * e1,TEdge * e2,const IntPoint & pt)1576 void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt)
1577 {
1578 AddOutPt( e1, pt );
1579 if( e1->outIdx == e2->outIdx )
1580 {
1581 e1->outIdx = -1;
1582 e2->outIdx = -1;
1583 }
1584 else if (e1->outIdx < e2->outIdx)
1585 AppendPolygon(e1, e2);
1586 else
1587 AppendPolygon(e2, e1);
1588 }
1589 //------------------------------------------------------------------------------
1590
AddEdgeToSEL(TEdge * edge)1591 void Clipper::AddEdgeToSEL(TEdge *edge)
1592 {
1593 //SEL pointers in PEdge are reused to build a list of horizontal edges.
1594 //However, we don't need to worry about order with horizontal edge processing.
1595 if( !m_SortedEdges )
1596 {
1597 m_SortedEdges = edge;
1598 edge->prevInSEL = 0;
1599 edge->nextInSEL = 0;
1600 }
1601 else
1602 {
1603 edge->nextInSEL = m_SortedEdges;
1604 edge->prevInSEL = 0;
1605 m_SortedEdges->prevInSEL = edge;
1606 m_SortedEdges = edge;
1607 }
1608 }
1609 //------------------------------------------------------------------------------
1610
CopyAELToSEL()1611 void Clipper::CopyAELToSEL()
1612 {
1613 TEdge* e = m_ActiveEdges;
1614 m_SortedEdges = e;
1615 if (!m_ActiveEdges) return;
1616 m_SortedEdges->prevInSEL = 0;
1617 e = e->nextInAEL;
1618 while ( e )
1619 {
1620 e->prevInSEL = e->prevInAEL;
1621 e->prevInSEL->nextInSEL = e;
1622 e->nextInSEL = 0;
1623 e = e->nextInAEL;
1624 }
1625 }
1626 //------------------------------------------------------------------------------
1627
AddJoin(TEdge * e1,TEdge * e2,int e1OutIdx,int e2OutIdx)1628 void Clipper::AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx, int e2OutIdx)
1629 {
1630 JoinRec* jr = new JoinRec;
1631 if (e1OutIdx >= 0)
1632 jr->poly1Idx = e1OutIdx; else
1633 jr->poly1Idx = e1->outIdx;
1634 jr->pt1a = IntPoint(e1->xcurr, e1->ycurr);
1635 jr->pt1b = IntPoint(e1->xtop, e1->ytop);
1636 if (e2OutIdx >= 0)
1637 jr->poly2Idx = e2OutIdx; else
1638 jr->poly2Idx = e2->outIdx;
1639 jr->pt2a = IntPoint(e2->xcurr, e2->ycurr);
1640 jr->pt2b = IntPoint(e2->xtop, e2->ytop);
1641 m_Joins.push_back(jr);
1642 }
1643 //------------------------------------------------------------------------------
1644
ClearJoins()1645 void Clipper::ClearJoins()
1646 {
1647 for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
1648 delete m_Joins[i];
1649 m_Joins.resize(0);
1650 }
1651 //------------------------------------------------------------------------------
1652
AddHorzJoin(TEdge * e,int idx)1653 void Clipper::AddHorzJoin(TEdge *e, int idx)
1654 {
1655 HorzJoinRec* hj = new HorzJoinRec;
1656 hj->edge = e;
1657 hj->savedIdx = idx;
1658 m_HorizJoins.push_back(hj);
1659 }
1660 //------------------------------------------------------------------------------
1661
ClearHorzJoins()1662 void Clipper::ClearHorzJoins()
1663 {
1664 for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++)
1665 delete m_HorizJoins[i];
1666 m_HorizJoins.resize(0);
1667 }
1668 //------------------------------------------------------------------------------
1669
InsertLocalMinimaIntoAEL(const long64 botY)1670 void Clipper::InsertLocalMinimaIntoAEL( const long64 botY)
1671 {
1672 while( m_CurrentLM && ( m_CurrentLM->Y == botY ) )
1673 {
1674 TEdge* lb = m_CurrentLM->leftBound;
1675 TEdge* rb = m_CurrentLM->rightBound;
1676
1677 InsertEdgeIntoAEL( lb );
1678 InsertScanbeam( lb->ytop );
1679 InsertEdgeIntoAEL( rb );
1680
1681 if (IsEvenOddFillType(*lb))
1682 {
1683 lb->windDelta = 1;
1684 rb->windDelta = 1;
1685 }
1686 else
1687 {
1688 rb->windDelta = -lb->windDelta;
1689 }
1690 SetWindingCount( *lb );
1691 rb->windCnt = lb->windCnt;
1692 rb->windCnt2 = lb->windCnt2;
1693
1694 if( NEAR_EQUAL(rb->dx, HORIZONTAL) )
1695 {
1696 //nb: only rightbounds can have a horizontal bottom edge
1697 AddEdgeToSEL( rb );
1698 InsertScanbeam( rb->nextInLML->ytop );
1699 }
1700 else
1701 InsertScanbeam( rb->ytop );
1702
1703 if( IsContributing(*lb) )
1704 AddLocalMinPoly( lb, rb, IntPoint(lb->xcurr, m_CurrentLM->Y) );
1705
1706 //if any output polygons share an edge, they'll need joining later ...
1707 if (rb->outIdx >= 0)
1708 {
1709 if (NEAR_EQUAL(rb->dx, HORIZONTAL))
1710 {
1711 for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
1712 {
1713 IntPoint pt, pt2; //returned by GetOverlapSegment() but unused here.
1714 HorzJoinRec* hj = m_HorizJoins[i];
1715 //if horizontals rb and hj.edge overlap, flag for joining later ...
1716 if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot),
1717 IntPoint(hj->edge->xtop, hj->edge->ytop),
1718 IntPoint(rb->xbot, rb->ybot),
1719 IntPoint(rb->xtop, rb->ytop), pt, pt2))
1720 AddJoin(hj->edge, rb, hj->savedIdx);
1721 }
1722 }
1723 }
1724
1725 if( lb->nextInAEL != rb )
1726 {
1727 if (rb->outIdx >= 0 && rb->prevInAEL->outIdx >= 0 &&
1728 SlopesEqual(*rb->prevInAEL, *rb, m_UseFullRange))
1729 AddJoin(rb, rb->prevInAEL);
1730
1731 TEdge* e = lb->nextInAEL;
1732 IntPoint pt = IntPoint(lb->xcurr, lb->ycurr);
1733 while( e != rb )
1734 {
1735 if(!e) throw clipperException("InsertLocalMinimaIntoAEL: missing rightbound!");
1736 //nb: For calculating winding counts etc, IntersectEdges() assumes
1737 //that param1 will be to the right of param2 ABOVE the intersection ...
1738 IntersectEdges( rb , e , pt , ipNone); //order important here
1739 e = e->nextInAEL;
1740 }
1741 }
1742 PopLocalMinima();
1743 }
1744 }
1745 //------------------------------------------------------------------------------
1746
DeleteFromAEL(TEdge * e)1747 void Clipper::DeleteFromAEL(TEdge *e)
1748 {
1749 TEdge* AelPrev = e->prevInAEL;
1750 TEdge* AelNext = e->nextInAEL;
1751 if( !AelPrev && !AelNext && (e != m_ActiveEdges) ) return; //already deleted
1752 if( AelPrev ) AelPrev->nextInAEL = AelNext;
1753 else m_ActiveEdges = AelNext;
1754 if( AelNext ) AelNext->prevInAEL = AelPrev;
1755 e->nextInAEL = 0;
1756 e->prevInAEL = 0;
1757 }
1758 //------------------------------------------------------------------------------
1759
DeleteFromSEL(TEdge * e)1760 void Clipper::DeleteFromSEL(TEdge *e)
1761 {
1762 TEdge* SelPrev = e->prevInSEL;
1763 TEdge* SelNext = e->nextInSEL;
1764 if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted
1765 if( SelPrev ) SelPrev->nextInSEL = SelNext;
1766 else m_SortedEdges = SelNext;
1767 if( SelNext ) SelNext->prevInSEL = SelPrev;
1768 e->nextInSEL = 0;
1769 e->prevInSEL = 0;
1770 }
1771 //------------------------------------------------------------------------------
1772
IntersectEdges(TEdge * e1,TEdge * e2,const IntPoint & pt,IntersectProtects protects)1773 void Clipper::IntersectEdges(TEdge *e1, TEdge *e2,
1774 const IntPoint &pt, IntersectProtects protects)
1775 {
1776 //e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before
1777 //e2 in AEL except when e1 is being inserted at the intersection point ...
1778 bool e1stops = !(ipLeft & protects) && !e1->nextInLML &&
1779 e1->xtop == pt.X && e1->ytop == pt.Y;
1780 bool e2stops = !(ipRight & protects) && !e2->nextInLML &&
1781 e2->xtop == pt.X && e2->ytop == pt.Y;
1782 bool e1Contributing = ( e1->outIdx >= 0 );
1783 bool e2contributing = ( e2->outIdx >= 0 );
1784
1785 //update winding counts...
1786 //assumes that e1 will be to the right of e2 ABOVE the intersection
1787 if ( e1->polyType == e2->polyType )
1788 {
1789 if ( IsEvenOddFillType( *e1) )
1790 {
1791 int oldE1WindCnt = e1->windCnt;
1792 e1->windCnt = e2->windCnt;
1793 e2->windCnt = oldE1WindCnt;
1794 } else
1795 {
1796 if (e1->windCnt + e2->windDelta == 0 ) e1->windCnt = -e1->windCnt;
1797 else e1->windCnt += e2->windDelta;
1798 if ( e2->windCnt - e1->windDelta == 0 ) e2->windCnt = -e2->windCnt;
1799 else e2->windCnt -= e1->windDelta;
1800 }
1801 } else
1802 {
1803 if (!IsEvenOddFillType(*e2)) e1->windCnt2 += e2->windDelta;
1804 else e1->windCnt2 = ( e1->windCnt2 == 0 ) ? 1 : 0;
1805 if (!IsEvenOddFillType(*e1)) e2->windCnt2 -= e1->windDelta;
1806 else e2->windCnt2 = ( e2->windCnt2 == 0 ) ? 1 : 0;
1807 }
1808
1809 PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
1810 if (e1->polyType == ptSubject)
1811 {
1812 e1FillType = m_SubjFillType;
1813 e1FillType2 = m_ClipFillType;
1814 } else
1815 {
1816 e1FillType = m_ClipFillType;
1817 e1FillType2 = m_SubjFillType;
1818 }
1819 if (e2->polyType == ptSubject)
1820 {
1821 e2FillType = m_SubjFillType;
1822 e2FillType2 = m_ClipFillType;
1823 } else
1824 {
1825 e2FillType = m_ClipFillType;
1826 e2FillType2 = m_SubjFillType;
1827 }
1828
1829 long64 e1Wc, e2Wc;
1830 switch (e1FillType)
1831 {
1832 case pftPositive: e1Wc = e1->windCnt; break;
1833 case pftNegative: e1Wc = -e1->windCnt; break;
1834 default: e1Wc = Abs(e1->windCnt);
1835 }
1836 switch(e2FillType)
1837 {
1838 case pftPositive: e2Wc = e2->windCnt; break;
1839 case pftNegative: e2Wc = -e2->windCnt; break;
1840 default: e2Wc = Abs(e2->windCnt);
1841 }
1842
1843 if ( e1Contributing && e2contributing )
1844 {
1845 if ( e1stops || e2stops ||
1846 (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
1847 (e1->polyType != e2->polyType && m_ClipType != ctXor) )
1848 AddLocalMaxPoly(e1, e2, pt);
1849 else
1850 DoBothEdges( e1, e2, pt );
1851 }
1852 else if ( e1Contributing )
1853 {
1854 if ((e2Wc == 0 || e2Wc == 1) &&
1855 (m_ClipType != ctIntersection ||
1856 e2->polyType == ptSubject || (e2->windCnt2 != 0)))
1857 DoEdge1(e1, e2, pt);
1858 }
1859 else if ( e2contributing )
1860 {
1861 if ((e1Wc == 0 || e1Wc == 1) &&
1862 (m_ClipType != ctIntersection ||
1863 e1->polyType == ptSubject || (e1->windCnt2 != 0)))
1864 DoEdge2(e1, e2, pt);
1865 }
1866 else if ( (e1Wc == 0 || e1Wc == 1) &&
1867 (e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops )
1868 {
1869 //neither edge is currently contributing ...
1870
1871 long64 e1Wc2, e2Wc2;
1872 switch (e1FillType2)
1873 {
1874 case pftPositive: e1Wc2 = e1->windCnt2; break;
1875 case pftNegative : e1Wc2 = -e1->windCnt2; break;
1876 default: e1Wc2 = Abs(e1->windCnt2);
1877 }
1878 switch (e2FillType2)
1879 {
1880 case pftPositive: e2Wc2 = e2->windCnt2; break;
1881 case pftNegative: e2Wc2 = -e2->windCnt2; break;
1882 default: e2Wc2 = Abs(e2->windCnt2);
1883 }
1884
1885 if (e1->polyType != e2->polyType)
1886 AddLocalMinPoly(e1, e2, pt);
1887 else if (e1Wc == 1 && e2Wc == 1)
1888 switch( m_ClipType ) {
1889 case ctIntersection:
1890 if (e1Wc2 > 0 && e2Wc2 > 0)
1891 AddLocalMinPoly(e1, e2, pt);
1892 break;
1893 case ctUnion:
1894 if ( e1Wc2 <= 0 && e2Wc2 <= 0 )
1895 AddLocalMinPoly(e1, e2, pt);
1896 break;
1897 case ctDifference:
1898 if (((e1->polyType == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
1899 ((e1->polyType == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
1900 AddLocalMinPoly(e1, e2, pt);
1901 break;
1902 case ctXor:
1903 AddLocalMinPoly(e1, e2, pt);
1904 }
1905 else
1906 SwapSides( *e1, *e2 );
1907 }
1908
1909 if( (e1stops != e2stops) &&
1910 ( (e1stops && (e1->outIdx >= 0)) || (e2stops && (e2->outIdx >= 0)) ) )
1911 {
1912 SwapSides( *e1, *e2 );
1913 SwapPolyIndexes( *e1, *e2 );
1914 }
1915
1916 //finally, delete any non-contributing maxima edges ...
1917 if( e1stops ) DeleteFromAEL( e1 );
1918 if( e2stops ) DeleteFromAEL( e2 );
1919 }
1920 //------------------------------------------------------------------------------
1921
SetHoleState(TEdge * e,OutRec * outRec)1922 void Clipper::SetHoleState(TEdge *e, OutRec *outRec)
1923 {
1924 bool isHole = false;
1925 TEdge *e2 = e->prevInAEL;
1926 while (e2)
1927 {
1928 if (e2->outIdx >= 0)
1929 {
1930 isHole = !isHole;
1931 if (! outRec->FirstLeft)
1932 outRec->FirstLeft = m_PolyOuts[e2->outIdx];
1933 }
1934 e2 = e2->prevInAEL;
1935 }
1936 if (isHole) outRec->isHole = true;
1937 }
1938 //------------------------------------------------------------------------------
1939
GetLowermostRec(OutRec * outRec1,OutRec * outRec2)1940 OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2)
1941 {
1942 //work out which polygon fragment has the correct hole state ...
1943 OutPt *outPt1 = outRec1->bottomPt;
1944 OutPt *outPt2 = outRec2->bottomPt;
1945 if (outPt1->pt.Y > outPt2->pt.Y) return outRec1;
1946 else if (outPt1->pt.Y < outPt2->pt.Y) return outRec2;
1947 else if (outPt1->pt.X < outPt2->pt.X) return outRec1;
1948 else if (outPt1->pt.X > outPt2->pt.X) return outRec2;
1949 else if (outPt1->next == outPt1) return outRec2;
1950 else if (outPt2->next == outPt2) return outRec1;
1951 else if (FirstIsBottomPt(outPt1, outPt2)) return outRec1;
1952 else return outRec2;
1953 }
1954 //------------------------------------------------------------------------------
1955
Param1RightOfParam2(OutRec * outRec1,OutRec * outRec2)1956 bool Param1RightOfParam2(OutRec* outRec1, OutRec* outRec2)
1957 {
1958 do
1959 {
1960 outRec1 = outRec1->FirstLeft;
1961 if (outRec1 == outRec2) return true;
1962 } while (outRec1);
1963 return false;
1964 }
1965 //------------------------------------------------------------------------------
1966
AppendPolygon(TEdge * e1,TEdge * e2)1967 void Clipper::AppendPolygon(TEdge *e1, TEdge *e2)
1968 {
1969 //get the start and ends of both output polygons ...
1970 OutRec *outRec1 = m_PolyOuts[e1->outIdx];
1971 OutRec *outRec2 = m_PolyOuts[e2->outIdx];
1972
1973 OutRec *holeStateRec;
1974 if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
1975 else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
1976 else holeStateRec = GetLowermostRec(outRec1, outRec2);
1977
1978 OutPt* p1_lft = outRec1->pts;
1979 OutPt* p1_rt = p1_lft->prev;
1980 OutPt* p2_lft = outRec2->pts;
1981 OutPt* p2_rt = p2_lft->prev;
1982
1983 EdgeSide side;
1984 //join e2 poly onto e1 poly and delete pointers to e2 ...
1985 if( e1->side == esLeft )
1986 {
1987 if( e2->side == esLeft )
1988 {
1989 //z y x a b c
1990 ReversePolyPtLinks(*p2_lft);
1991 p2_lft->next = p1_lft;
1992 p1_lft->prev = p2_lft;
1993 p1_rt->next = p2_rt;
1994 p2_rt->prev = p1_rt;
1995 outRec1->pts = p2_rt;
1996 } else
1997 {
1998 //x y z a b c
1999 p2_rt->next = p1_lft;
2000 p1_lft->prev = p2_rt;
2001 p2_lft->prev = p1_rt;
2002 p1_rt->next = p2_lft;
2003 outRec1->pts = p2_lft;
2004 }
2005 side = esLeft;
2006 } else
2007 {
2008 if( e2->side == esRight )
2009 {
2010 //a b c z y x
2011 ReversePolyPtLinks( *p2_lft );
2012 p1_rt->next = p2_rt;
2013 p2_rt->prev = p1_rt;
2014 p2_lft->next = p1_lft;
2015 p1_lft->prev = p2_lft;
2016 } else
2017 {
2018 //a b c x y z
2019 p1_rt->next = p2_lft;
2020 p2_lft->prev = p1_rt;
2021 p1_lft->prev = p2_rt;
2022 p2_rt->next = p1_lft;
2023 }
2024 side = esRight;
2025 }
2026
2027 if (holeStateRec == outRec2)
2028 {
2029 outRec1->bottomPt = outRec2->bottomPt;
2030 outRec1->bottomPt->idx = outRec1->idx;
2031 if (outRec2->FirstLeft != outRec1)
2032 outRec1->FirstLeft = outRec2->FirstLeft;
2033 outRec1->isHole = outRec2->isHole;
2034 }
2035 outRec2->pts = 0;
2036 outRec2->bottomPt = 0;
2037 outRec2->AppendLink = outRec1;
2038 int OKIdx = e1->outIdx;
2039 int ObsoleteIdx = e2->outIdx;
2040
2041 e1->outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly
2042 e2->outIdx = -1;
2043
2044 TEdge* e = m_ActiveEdges;
2045 while( e )
2046 {
2047 if( e->outIdx == ObsoleteIdx )
2048 {
2049 e->outIdx = OKIdx;
2050 e->side = side;
2051 break;
2052 }
2053 e = e->nextInAEL;
2054 }
2055
2056 for (JoinList::size_type i = 0; i < m_Joins.size(); ++i)
2057 {
2058 if (m_Joins[i]->poly1Idx == ObsoleteIdx) m_Joins[i]->poly1Idx = OKIdx;
2059 if (m_Joins[i]->poly2Idx == ObsoleteIdx) m_Joins[i]->poly2Idx = OKIdx;
2060 }
2061
2062 for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
2063 {
2064 if (m_HorizJoins[i]->savedIdx == ObsoleteIdx)
2065 m_HorizJoins[i]->savedIdx = OKIdx;
2066 }
2067
2068 }
2069 //------------------------------------------------------------------------------
2070
CreateOutRec()2071 OutRec* Clipper::CreateOutRec()
2072 {
2073 OutRec* result = new OutRec;
2074 result->isHole = false;
2075 result->FirstLeft = 0;
2076 result->AppendLink = 0;
2077 result->pts = 0;
2078 result->bottomPt = 0;
2079 result->sides = esNeither;
2080 result->bottomFlag = 0;
2081
2082 return result;
2083 }
2084 //------------------------------------------------------------------------------
2085
DisposeBottomPt(OutRec & outRec)2086 void Clipper::DisposeBottomPt(OutRec &outRec)
2087 {
2088 OutPt* next = outRec.bottomPt->next;
2089 OutPt* prev = outRec.bottomPt->prev;
2090 if (outRec.pts == outRec.bottomPt) outRec.pts = next;
2091 delete outRec.bottomPt;
2092 next->prev = prev;
2093 prev->next = next;
2094 outRec.bottomPt = next;
2095 FixupOutPolygon(outRec);
2096 }
2097 //------------------------------------------------------------------------------
2098
AddOutPt(TEdge * e,const IntPoint & pt)2099 void Clipper::AddOutPt(TEdge *e, const IntPoint &pt)
2100 {
2101 bool ToFront = (e->side == esLeft);
2102 if( e->outIdx < 0 )
2103 {
2104 OutRec *outRec = CreateOutRec();
2105 m_PolyOuts.push_back(outRec);
2106 outRec->idx = (int)m_PolyOuts.size()-1;
2107 e->outIdx = outRec->idx;
2108 OutPt* op = new OutPt;
2109 outRec->pts = op;
2110 outRec->bottomPt = op;
2111 op->pt = pt;
2112 op->idx = outRec->idx;
2113 op->next = op;
2114 op->prev = op;
2115 SetHoleState(e, outRec);
2116 } else
2117 {
2118 OutRec *outRec = m_PolyOuts[e->outIdx];
2119 OutPt* op = outRec->pts;
2120 if ((ToFront && PointsEqual(pt, op->pt)) ||
2121 (!ToFront && PointsEqual(pt, op->prev->pt))) return;
2122
2123 if ((e->side | outRec->sides) != outRec->sides)
2124 {
2125 //check for 'rounding' artefacts ...
2126 if (outRec->sides == esNeither && pt.Y == op->pt.Y)
2127 {
2128 if (ToFront)
2129 {
2130 if (pt.X == op->pt.X +1) return; //ie wrong side of bottomPt
2131 }
2132 else if (pt.X == op->pt.X -1) return; //ie wrong side of bottomPt
2133 }
2134
2135 outRec->sides = (EdgeSide)(outRec->sides | e->side);
2136 if (outRec->sides == esBoth)
2137 {
2138 //A vertex from each side has now been added.
2139 //Vertices of one side of an output polygon are quite commonly close to
2140 //or even 'touching' edges of the other side of the output polygon.
2141 //Very occasionally vertices from one side can 'cross' an edge on the
2142 //the other side. The distance 'crossed' is always less that a unit
2143 //and is purely an artefact of coordinate rounding. Nevertheless, this
2144 //results in very tiny self-intersections. Because of the way
2145 //orientation is calculated, even tiny self-intersections can cause
2146 //the Orientation function to return the wrong result. Therefore, it's
2147 //important to ensure that any self-intersections close to BottomPt are
2148 //detected and removed before orientation is assigned.
2149
2150 OutPt *opBot, *op2;
2151 if (ToFront)
2152 {
2153 opBot = outRec->pts;
2154 op2 = opBot->next; //op2 == right side
2155 if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y &&
2156 ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) <
2157 (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y)))
2158 outRec->bottomFlag = opBot;
2159 } else
2160 {
2161 opBot = outRec->pts->prev;
2162 op2 = opBot->prev; //op2 == left side
2163 if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y &&
2164 ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) >
2165 (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y)))
2166 outRec->bottomFlag = opBot;
2167 }
2168 }
2169 }
2170
2171 OutPt* op2 = new OutPt;
2172 op2->pt = pt;
2173 op2->idx = outRec->idx;
2174 if (op2->pt.Y == outRec->bottomPt->pt.Y &&
2175 op2->pt.X < outRec->bottomPt->pt.X)
2176 outRec->bottomPt = op2;
2177 op2->next = op;
2178 op2->prev = op->prev;
2179 op2->prev->next = op2;
2180 op->prev = op2;
2181 if (ToFront) outRec->pts = op2;
2182 }
2183 }
2184 //------------------------------------------------------------------------------
2185
ProcessHorizontals()2186 void Clipper::ProcessHorizontals()
2187 {
2188 TEdge* horzEdge = m_SortedEdges;
2189 while( horzEdge )
2190 {
2191 DeleteFromSEL( horzEdge );
2192 ProcessHorizontal( horzEdge );
2193 horzEdge = m_SortedEdges;
2194 }
2195 }
2196 //------------------------------------------------------------------------------
2197
IsTopHorz(const long64 XPos)2198 bool Clipper::IsTopHorz(const long64 XPos)
2199 {
2200 TEdge* e = m_SortedEdges;
2201 while( e )
2202 {
2203 if( ( XPos >= std::min(e->xcurr, e->xtop) ) &&
2204 ( XPos <= std::max(e->xcurr, e->xtop) ) ) return false;
2205 e = e->nextInSEL;
2206 }
2207 return true;
2208 }
2209 //------------------------------------------------------------------------------
2210
IsMinima(TEdge * e)2211 bool IsMinima(TEdge *e)
2212 {
2213 return e && (e->prev->nextInLML != e) && (e->next->nextInLML != e);
2214 }
2215 //------------------------------------------------------------------------------
2216
IsMaxima(TEdge * e,const long64 Y)2217 bool IsMaxima(TEdge *e, const long64 Y)
2218 {
2219 return e && e->ytop == Y && !e->nextInLML;
2220 }
2221 //------------------------------------------------------------------------------
2222
IsIntermediate(TEdge * e,const long64 Y)2223 bool IsIntermediate(TEdge *e, const long64 Y)
2224 {
2225 return e->ytop == Y && e->nextInLML;
2226 }
2227 //------------------------------------------------------------------------------
2228
GetMaximaPair(TEdge * e)2229 TEdge *GetMaximaPair(TEdge *e)
2230 {
2231 if( !IsMaxima(e->next, e->ytop) || e->next->xtop != e->xtop )
2232 return e->prev; else
2233 return e->next;
2234 }
2235 //------------------------------------------------------------------------------
2236
SwapPositionsInAEL(TEdge * edge1,TEdge * edge2)2237 void Clipper::SwapPositionsInAEL(TEdge *edge1, TEdge *edge2)
2238 {
2239 if( !edge1->nextInAEL && !edge1->prevInAEL ) return;
2240 if( !edge2->nextInAEL && !edge2->prevInAEL ) return;
2241
2242 if( edge1->nextInAEL == edge2 )
2243 {
2244 TEdge* next = edge2->nextInAEL;
2245 if( next ) next->prevInAEL = edge1;
2246 TEdge* prev = edge1->prevInAEL;
2247 if( prev ) prev->nextInAEL = edge2;
2248 edge2->prevInAEL = prev;
2249 edge2->nextInAEL = edge1;
2250 edge1->prevInAEL = edge2;
2251 edge1->nextInAEL = next;
2252 }
2253 else if( edge2->nextInAEL == edge1 )
2254 {
2255 TEdge* next = edge1->nextInAEL;
2256 if( next ) next->prevInAEL = edge2;
2257 TEdge* prev = edge2->prevInAEL;
2258 if( prev ) prev->nextInAEL = edge1;
2259 edge1->prevInAEL = prev;
2260 edge1->nextInAEL = edge2;
2261 edge2->prevInAEL = edge1;
2262 edge2->nextInAEL = next;
2263 }
2264 else
2265 {
2266 TEdge* next = edge1->nextInAEL;
2267 TEdge* prev = edge1->prevInAEL;
2268 edge1->nextInAEL = edge2->nextInAEL;
2269 if( edge1->nextInAEL ) edge1->nextInAEL->prevInAEL = edge1;
2270 edge1->prevInAEL = edge2->prevInAEL;
2271 if( edge1->prevInAEL ) edge1->prevInAEL->nextInAEL = edge1;
2272 edge2->nextInAEL = next;
2273 if( edge2->nextInAEL ) edge2->nextInAEL->prevInAEL = edge2;
2274 edge2->prevInAEL = prev;
2275 if( edge2->prevInAEL ) edge2->prevInAEL->nextInAEL = edge2;
2276 }
2277
2278 if( !edge1->prevInAEL ) m_ActiveEdges = edge1;
2279 else if( !edge2->prevInAEL ) m_ActiveEdges = edge2;
2280 }
2281 //------------------------------------------------------------------------------
2282
SwapPositionsInSEL(TEdge * edge1,TEdge * edge2)2283 void Clipper::SwapPositionsInSEL(TEdge *edge1, TEdge *edge2)
2284 {
2285 if( !( edge1->nextInSEL ) && !( edge1->prevInSEL ) ) return;
2286 if( !( edge2->nextInSEL ) && !( edge2->prevInSEL ) ) return;
2287
2288 if( edge1->nextInSEL == edge2 )
2289 {
2290 TEdge* next = edge2->nextInSEL;
2291 if( next ) next->prevInSEL = edge1;
2292 TEdge* prev = edge1->prevInSEL;
2293 if( prev ) prev->nextInSEL = edge2;
2294 edge2->prevInSEL = prev;
2295 edge2->nextInSEL = edge1;
2296 edge1->prevInSEL = edge2;
2297 edge1->nextInSEL = next;
2298 }
2299 else if( edge2->nextInSEL == edge1 )
2300 {
2301 TEdge* next = edge1->nextInSEL;
2302 if( next ) next->prevInSEL = edge2;
2303 TEdge* prev = edge2->prevInSEL;
2304 if( prev ) prev->nextInSEL = edge1;
2305 edge1->prevInSEL = prev;
2306 edge1->nextInSEL = edge2;
2307 edge2->prevInSEL = edge1;
2308 edge2->nextInSEL = next;
2309 }
2310 else
2311 {
2312 TEdge* next = edge1->nextInSEL;
2313 TEdge* prev = edge1->prevInSEL;
2314 edge1->nextInSEL = edge2->nextInSEL;
2315 if( edge1->nextInSEL ) edge1->nextInSEL->prevInSEL = edge1;
2316 edge1->prevInSEL = edge2->prevInSEL;
2317 if( edge1->prevInSEL ) edge1->prevInSEL->nextInSEL = edge1;
2318 edge2->nextInSEL = next;
2319 if( edge2->nextInSEL ) edge2->nextInSEL->prevInSEL = edge2;
2320 edge2->prevInSEL = prev;
2321 if( edge2->prevInSEL ) edge2->prevInSEL->nextInSEL = edge2;
2322 }
2323
2324 if( !edge1->prevInSEL ) m_SortedEdges = edge1;
2325 else if( !edge2->prevInSEL ) m_SortedEdges = edge2;
2326 }
2327 //------------------------------------------------------------------------------
2328
GetNextInAEL(TEdge * e,Direction dir)2329 TEdge* GetNextInAEL(TEdge *e, Direction dir)
2330 {
2331 return dir == dLeftToRight ? e->nextInAEL : e->prevInAEL;
2332 }
2333 //------------------------------------------------------------------------------
2334
ProcessHorizontal(TEdge * horzEdge)2335 void Clipper::ProcessHorizontal(TEdge *horzEdge)
2336 {
2337 Direction dir;
2338 long64 horzLeft, horzRight;
2339
2340 if( horzEdge->xcurr < horzEdge->xtop )
2341 {
2342 horzLeft = horzEdge->xcurr;
2343 horzRight = horzEdge->xtop;
2344 dir = dLeftToRight;
2345 } else
2346 {
2347 horzLeft = horzEdge->xtop;
2348 horzRight = horzEdge->xcurr;
2349 dir = dRightToLeft;
2350 }
2351
2352 TEdge* eMaxPair;
2353 if( horzEdge->nextInLML ) eMaxPair = 0;
2354 else eMaxPair = GetMaximaPair(horzEdge);
2355
2356 TEdge* e = GetNextInAEL( horzEdge , dir );
2357 while( e )
2358 {
2359 TEdge* eNext = GetNextInAEL( e, dir );
2360
2361 if (eMaxPair ||
2362 ((dir == dLeftToRight) && (e->xcurr <= horzRight)) ||
2363 ((dir == dRightToLeft) && (e->xcurr >= horzLeft)))
2364 {
2365 //ok, so far it looks like we're still in range of the horizontal edge
2366 if ( e->xcurr == horzEdge->xtop && !eMaxPair )
2367 {
2368 if (SlopesEqual(*e, *horzEdge->nextInLML, m_UseFullRange))
2369 {
2370 //if output polygons share an edge, they'll need joining later ...
2371 if (horzEdge->outIdx >= 0 && e->outIdx >= 0)
2372 AddJoin(horzEdge->nextInLML, e, horzEdge->outIdx);
2373 break; //we've reached the end of the horizontal line
2374 }
2375 else if (e->dx < horzEdge->nextInLML->dx)
2376 //we really have got to the end of the intermediate horz edge so quit.
2377 //nb: More -ve slopes follow more +ve slopes ABOVE the horizontal.
2378 break;
2379 }
2380
2381 if( e == eMaxPair )
2382 {
2383 //horzEdge is evidently a maxima horizontal and we've arrived at its end.
2384 if (dir == dLeftToRight)
2385 IntersectEdges(horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
2386 else
2387 IntersectEdges(e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), ipNone);
2388 if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error");
2389 return;
2390 }
2391 else if( NEAR_EQUAL(e->dx, HORIZONTAL) && !IsMinima(e) && !(e->xcurr > e->xtop) )
2392 {
2393 //An overlapping horizontal edge. Overlapping horizontal edges are
2394 //processed as if layered with the current horizontal edge (horizEdge)
2395 //being infinitesimally lower that the next (e). Therfore, we
2396 //intersect with e only if e.xcurr is within the bounds of horzEdge ...
2397 if( dir == dLeftToRight )
2398 IntersectEdges( horzEdge , e, IntPoint(e->xcurr, horzEdge->ycurr),
2399 (IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
2400 else
2401 IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
2402 (IsTopHorz( e->xcurr ))? ipRight : ipBoth );
2403 }
2404 else if( dir == dLeftToRight )
2405 {
2406 IntersectEdges( horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr),
2407 (IsTopHorz( e->xcurr ))? ipLeft : ipBoth );
2408 }
2409 else
2410 {
2411 IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr),
2412 (IsTopHorz( e->xcurr ))? ipRight : ipBoth );
2413 }
2414 SwapPositionsInAEL( horzEdge, e );
2415 }
2416 else if( (dir == dLeftToRight && e->xcurr > horzRight && m_SortedEdges) ||
2417 (dir == dRightToLeft && e->xcurr < horzLeft && m_SortedEdges) ) break;
2418 e = eNext;
2419 } //end while
2420
2421 if( horzEdge->nextInLML )
2422 {
2423 if( horzEdge->outIdx >= 0 )
2424 AddOutPt( horzEdge, IntPoint(horzEdge->xtop, horzEdge->ytop));
2425 UpdateEdgeIntoAEL( horzEdge );
2426 }
2427 else
2428 {
2429 if ( horzEdge->outIdx >= 0 )
2430 IntersectEdges( horzEdge, eMaxPair,
2431 IntPoint(horzEdge->xtop, horzEdge->ycurr), ipBoth);
2432 if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error");
2433 DeleteFromAEL(eMaxPair);
2434 DeleteFromAEL(horzEdge);
2435 }
2436 }
2437 //------------------------------------------------------------------------------
2438
UpdateEdgeIntoAEL(TEdge * & e)2439 void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
2440 {
2441 if( !e->nextInLML ) throw
2442 clipperException("UpdateEdgeIntoAEL: invalid call");
2443 TEdge* AelPrev = e->prevInAEL;
2444 TEdge* AelNext = e->nextInAEL;
2445 e->nextInLML->outIdx = e->outIdx;
2446 if( AelPrev ) AelPrev->nextInAEL = e->nextInLML;
2447 else m_ActiveEdges = e->nextInLML;
2448 if( AelNext ) AelNext->prevInAEL = e->nextInLML;
2449 e->nextInLML->side = e->side;
2450 e->nextInLML->windDelta = e->windDelta;
2451 e->nextInLML->windCnt = e->windCnt;
2452 e->nextInLML->windCnt2 = e->windCnt2;
2453 e = e->nextInLML;
2454 e->prevInAEL = AelPrev;
2455 e->nextInAEL = AelNext;
2456 if( !NEAR_EQUAL(e->dx, HORIZONTAL) ) InsertScanbeam( e->ytop );
2457 }
2458 //------------------------------------------------------------------------------
2459
ProcessIntersections(const long64 botY,const long64 topY)2460 bool Clipper::ProcessIntersections(const long64 botY, const long64 topY)
2461 {
2462 if( !m_ActiveEdges ) return true;
2463 try {
2464 BuildIntersectList(botY, topY);
2465 if ( !m_IntersectNodes) return true;
2466 if ( FixupIntersections() ) ProcessIntersectList();
2467 else return false;
2468 }
2469 catch(...) {
2470 m_SortedEdges = 0;
2471 DisposeIntersectNodes();
2472 throw clipperException("ProcessIntersections error");
2473 }
2474 return true;
2475 }
2476 //------------------------------------------------------------------------------
2477
DisposeIntersectNodes()2478 void Clipper::DisposeIntersectNodes()
2479 {
2480 while ( m_IntersectNodes )
2481 {
2482 IntersectNode* iNode = m_IntersectNodes->next;
2483 delete m_IntersectNodes;
2484 m_IntersectNodes = iNode;
2485 }
2486 }
2487 //------------------------------------------------------------------------------
2488
BuildIntersectList(const long64 botY,const long64 topY)2489 void Clipper::BuildIntersectList(const long64 botY, const long64 topY)
2490 {
2491 if ( !m_ActiveEdges ) return;
2492
2493 //prepare for sorting ...
2494 TEdge* e = m_ActiveEdges;
2495 e->tmpX = TopX( *e, topY );
2496 m_SortedEdges = e;
2497 m_SortedEdges->prevInSEL = 0;
2498 e = e->nextInAEL;
2499 while( e )
2500 {
2501 e->prevInSEL = e->prevInAEL;
2502 e->prevInSEL->nextInSEL = e;
2503 e->nextInSEL = 0;
2504 e->tmpX = TopX( *e, topY );
2505 e = e->nextInAEL;
2506 }
2507
2508 //bubblesort ...
2509 bool isModified = true;
2510 while( isModified && m_SortedEdges )
2511 {
2512 isModified = false;
2513 e = m_SortedEdges;
2514 while( e->nextInSEL )
2515 {
2516 TEdge *eNext = e->nextInSEL;
2517 IntPoint pt;
2518 if(e->tmpX > eNext->tmpX &&
2519 IntersectPoint(*e, *eNext, pt, m_UseFullRange))
2520 {
2521 if (pt.Y > botY)
2522 {
2523 pt.Y = botY;
2524 pt.X = TopX(*e, pt.Y);
2525 }
2526 AddIntersectNode( e, eNext, pt );
2527 SwapPositionsInSEL(e, eNext);
2528 isModified = true;
2529 }
2530 else
2531 e = eNext;
2532 }
2533 if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0;
2534 else break;
2535 }
2536 m_SortedEdges = 0;
2537 }
2538 //------------------------------------------------------------------------------
2539
ProcessParam1BeforeParam2(IntersectNode & node1,IntersectNode & node2)2540 bool ProcessParam1BeforeParam2(IntersectNode &node1, IntersectNode &node2)
2541 {
2542 bool result;
2543 if (node1.pt.Y == node2.pt.Y)
2544 {
2545 if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1)
2546 {
2547 result = node2.pt.X > node1.pt.X;
2548 return node2.edge1->dx > 0 ? !result : result;
2549 }
2550 else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2)
2551 {
2552 result = node2.pt.X > node1.pt.X;
2553 return node2.edge2->dx > 0 ? !result : result;
2554 }
2555 else return node2.pt.X > node1.pt.X;
2556 }
2557 else return node1.pt.Y > node2.pt.Y;
2558 }
2559 //------------------------------------------------------------------------------
2560
AddIntersectNode(TEdge * e1,TEdge * e2,const IntPoint & pt)2561 void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt)
2562 {
2563 IntersectNode* newNode = new IntersectNode;
2564 newNode->edge1 = e1;
2565 newNode->edge2 = e2;
2566 newNode->pt = pt;
2567 newNode->next = 0;
2568 if( !m_IntersectNodes ) m_IntersectNodes = newNode;
2569 else if( ProcessParam1BeforeParam2(*newNode, *m_IntersectNodes) )
2570 {
2571 newNode->next = m_IntersectNodes;
2572 m_IntersectNodes = newNode;
2573 }
2574 else
2575 {
2576 IntersectNode* iNode = m_IntersectNodes;
2577 while( iNode->next && ProcessParam1BeforeParam2(*iNode->next, *newNode) )
2578 iNode = iNode->next;
2579 newNode->next = iNode->next;
2580 iNode->next = newNode;
2581 }
2582 }
2583 //------------------------------------------------------------------------------
2584
ProcessIntersectList()2585 void Clipper::ProcessIntersectList()
2586 {
2587 while( m_IntersectNodes )
2588 {
2589 IntersectNode* iNode = m_IntersectNodes->next;
2590 {
2591 IntersectEdges( m_IntersectNodes->edge1 ,
2592 m_IntersectNodes->edge2 , m_IntersectNodes->pt, ipBoth );
2593 SwapPositionsInAEL( m_IntersectNodes->edge1 , m_IntersectNodes->edge2 );
2594 }
2595 delete m_IntersectNodes;
2596 m_IntersectNodes = iNode;
2597 }
2598 }
2599 //------------------------------------------------------------------------------
2600
DoMaxima(TEdge * e,long64 topY)2601 void Clipper::DoMaxima(TEdge *e, long64 topY)
2602 {
2603 TEdge* eMaxPair = GetMaximaPair(e);
2604 long64 X = e->xtop;
2605 TEdge* eNext = e->nextInAEL;
2606 while( eNext != eMaxPair )
2607 {
2608 if (!eNext) throw clipperException("DoMaxima error");
2609 IntersectEdges( e, eNext, IntPoint(X, topY), ipBoth );
2610 eNext = eNext->nextInAEL;
2611 }
2612 if( e->outIdx < 0 && eMaxPair->outIdx < 0 )
2613 {
2614 DeleteFromAEL( e );
2615 DeleteFromAEL( eMaxPair );
2616 }
2617 else if( e->outIdx >= 0 && eMaxPair->outIdx >= 0 )
2618 {
2619 IntersectEdges( e, eMaxPair, IntPoint(X, topY), ipNone );
2620 }
2621 else throw clipperException("DoMaxima error");
2622 }
2623 //------------------------------------------------------------------------------
2624
ProcessEdgesAtTopOfScanbeam(const long64 topY)2625 void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY)
2626 {
2627 TEdge* e = m_ActiveEdges;
2628 while( e )
2629 {
2630 //1. process maxima, treating them as if they're 'bent' horizontal edges,
2631 // but exclude maxima with horizontal edges. nb: e can't be a horizontal.
2632 if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, HORIZONTAL) )
2633 {
2634 //'e' might be removed from AEL, as may any following edges so ...
2635 TEdge* ePrior = e->prevInAEL;
2636 DoMaxima(e, topY);
2637 if( !ePrior ) e = m_ActiveEdges;
2638 else e = ePrior->nextInAEL;
2639 }
2640 else
2641 {
2642 //2. promote horizontal edges, otherwise update xcurr and ycurr ...
2643 if( IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, HORIZONTAL) )
2644 {
2645 if (e->outIdx >= 0)
2646 {
2647 AddOutPt(e, IntPoint(e->xtop, e->ytop));
2648
2649 for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i)
2650 {
2651 IntPoint pt, pt2;
2652 HorzJoinRec* hj = m_HorizJoins[i];
2653 if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot),
2654 IntPoint(hj->edge->xtop, hj->edge->ytop),
2655 IntPoint(e->nextInLML->xbot, e->nextInLML->ybot),
2656 IntPoint(e->nextInLML->xtop, e->nextInLML->ytop), pt, pt2))
2657 AddJoin(hj->edge, e->nextInLML, hj->savedIdx, e->outIdx);
2658 }
2659
2660 AddHorzJoin(e->nextInLML, e->outIdx);
2661 }
2662 UpdateEdgeIntoAEL(e);
2663 AddEdgeToSEL(e);
2664 } else
2665 {
2666 //this just simplifies horizontal processing ...
2667 e->xcurr = TopX( *e, topY );
2668 e->ycurr = topY;
2669 }
2670 e = e->nextInAEL;
2671 }
2672 }
2673
2674 //3. Process horizontals at the top of the scanbeam ...
2675 ProcessHorizontals();
2676
2677 //4. Promote intermediate vertices ...
2678 e = m_ActiveEdges;
2679 while( e )
2680 {
2681 if( IsIntermediate( e, topY ) )
2682 {
2683 if( e->outIdx >= 0 ) AddOutPt(e, IntPoint(e->xtop,e->ytop));
2684 UpdateEdgeIntoAEL(e);
2685
2686 //if output polygons share an edge, they'll need joining later ...
2687 if (e->outIdx >= 0 && e->prevInAEL && e->prevInAEL->outIdx >= 0 &&
2688 e->prevInAEL->xcurr == e->xbot && e->prevInAEL->ycurr == e->ybot &&
2689 SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop),
2690 IntPoint(e->xbot,e->ybot),
2691 IntPoint(e->prevInAEL->xtop, e->prevInAEL->ytop), m_UseFullRange))
2692 {
2693 AddOutPt(e->prevInAEL, IntPoint(e->xbot, e->ybot));
2694 AddJoin(e, e->prevInAEL);
2695 }
2696 else if (e->outIdx >= 0 && e->nextInAEL && e->nextInAEL->outIdx >= 0 &&
2697 e->nextInAEL->ycurr > e->nextInAEL->ytop &&
2698 e->nextInAEL->ycurr <= e->nextInAEL->ybot &&
2699 e->nextInAEL->xcurr == e->xbot && e->nextInAEL->ycurr == e->ybot &&
2700 SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop),
2701 IntPoint(e->xbot,e->ybot),
2702 IntPoint(e->nextInAEL->xtop, e->nextInAEL->ytop), m_UseFullRange))
2703 {
2704 AddOutPt(e->nextInAEL, IntPoint(e->xbot, e->ybot));
2705 AddJoin(e, e->nextInAEL);
2706 }
2707 }
2708 e = e->nextInAEL;
2709 }
2710 }
2711 //------------------------------------------------------------------------------
2712
FixupOutPolygon(OutRec & outRec)2713 void Clipper::FixupOutPolygon(OutRec &outRec)
2714 {
2715 //FixupOutPolygon() - removes duplicate points and simplifies consecutive
2716 //parallel edges by removing the middle vertex.
2717 OutPt *lastOK = 0;
2718 outRec.pts = outRec.bottomPt;
2719 OutPt *pp = outRec.bottomPt;
2720
2721 for (;;)
2722 {
2723 if (pp->prev == pp || pp->prev == pp->next )
2724 {
2725 DisposeOutPts(pp);
2726 outRec.pts = 0;
2727 outRec.bottomPt = 0;
2728 return;
2729 }
2730 //test for duplicate points and for same slope (cross-product) ...
2731 if ( PointsEqual(pp->pt, pp->next->pt) ||
2732 SlopesEqual(pp->prev->pt, pp->pt, pp->next->pt, m_UseFullRange) )
2733 {
2734 lastOK = 0;
2735 OutPt *tmp = pp;
2736 if (pp == outRec.bottomPt)
2737 outRec.bottomPt = 0; //flags need for updating
2738 pp->prev->next = pp->next;
2739 pp->next->prev = pp->prev;
2740 pp = pp->prev;
2741 delete tmp;
2742 }
2743 else if (pp == lastOK) break;
2744 else
2745 {
2746 if (!lastOK) lastOK = pp;
2747 pp = pp->next;
2748 }
2749 }
2750 if (!outRec.bottomPt) {
2751 outRec.bottomPt = GetBottomPt(pp);
2752 outRec.bottomPt->idx = outRec.idx;
2753 outRec.pts = outRec.bottomPt;
2754 }
2755 }
2756 //------------------------------------------------------------------------------
2757
BuildResult(Polygons & polys)2758 void Clipper::BuildResult(Polygons &polys)
2759 {
2760 int k = 0;
2761 polys.resize(m_PolyOuts.size());
2762 for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
2763 {
2764 if (m_PolyOuts[i]->pts)
2765 {
2766 Polygon* pg = &polys[k];
2767 pg->clear();
2768 OutPt* p = m_PolyOuts[i]->pts;
2769 do
2770 {
2771 pg->push_back(p->pt);
2772 p = p->next;
2773 } while (p != m_PolyOuts[i]->pts);
2774 //make sure each polygon has at least 3 vertices ...
2775 if (pg->size() < 3) pg->clear(); else k++;
2776 }
2777 }
2778 polys.resize(k);
2779 }
2780 //------------------------------------------------------------------------------
2781
BuildResultEx(ExPolygons & polys)2782 void Clipper::BuildResultEx(ExPolygons &polys)
2783 {
2784 PolyOutList::size_type i = 0;
2785 int k = 0;
2786 polys.resize(0);
2787 polys.reserve(m_PolyOuts.size());
2788 while (i < m_PolyOuts.size() && m_PolyOuts[i]->pts)
2789 {
2790 ExPolygon epg;
2791 OutPt* p = m_PolyOuts[i]->pts;
2792 do {
2793 epg.outer.push_back(p->pt);
2794 p = p->next;
2795 } while (p != m_PolyOuts[i]->pts);
2796 i++;
2797 //make sure polygons have at least 3 vertices ...
2798 if (epg.outer.size() < 3) continue;
2799 while (i < m_PolyOuts.size()
2800 && m_PolyOuts[i]->pts && m_PolyOuts[i]->isHole)
2801 {
2802 Polygon pg;
2803 p = m_PolyOuts[i]->pts;
2804 do {
2805 pg.push_back(p->pt);
2806 p = p->next;
2807 } while (p != m_PolyOuts[i]->pts);
2808 epg.holes.push_back(pg);
2809 i++;
2810 }
2811 polys.push_back(epg);
2812 k++;
2813 }
2814 polys.resize(k);
2815 }
2816 //------------------------------------------------------------------------------
2817
SwapIntersectNodes(IntersectNode & int1,IntersectNode & int2)2818 void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)
2819 {
2820 TEdge *e1 = int1.edge1;
2821 TEdge *e2 = int1.edge2;
2822 IntPoint p = int1.pt;
2823
2824 int1.edge1 = int2.edge1;
2825 int1.edge2 = int2.edge2;
2826 int1.pt = int2.pt;
2827
2828 int2.edge1 = e1;
2829 int2.edge2 = e2;
2830 int2.pt = p;
2831 }
2832 //------------------------------------------------------------------------------
2833
FixupIntersections()2834 bool Clipper::FixupIntersections()
2835 {
2836 if ( !m_IntersectNodes->next ) return true;
2837
2838 CopyAELToSEL();
2839 IntersectNode *int1 = m_IntersectNodes;
2840 IntersectNode *int2 = m_IntersectNodes->next;
2841 while (int2)
2842 {
2843 TEdge *e1 = int1->edge1;
2844 TEdge *e2;
2845 if (e1->prevInSEL == int1->edge2) e2 = e1->prevInSEL;
2846 else if (e1->nextInSEL == int1->edge2) e2 = e1->nextInSEL;
2847 else
2848 {
2849 //The current intersection is out of order, so try and swap it with
2850 //a subsequent intersection ...
2851 while (int2)
2852 {
2853 if (int2->edge1->nextInSEL == int2->edge2 ||
2854 int2->edge1->prevInSEL == int2->edge2) break;
2855 else int2 = int2->next;
2856 }
2857 if ( !int2 ) return false; //oops!!!
2858
2859 //found an intersect node that can be swapped ...
2860 SwapIntersectNodes(*int1, *int2);
2861 e1 = int1->edge1;
2862 e2 = int1->edge2;
2863 }
2864 SwapPositionsInSEL(e1, e2);
2865 int1 = int1->next;
2866 int2 = int1->next;
2867 }
2868
2869 m_SortedEdges = 0;
2870
2871 //finally, check the last intersection too ...
2872 return (int1->edge1->prevInSEL == int1->edge2 ||
2873 int1->edge1->nextInSEL == int1->edge2);
2874 }
2875 //------------------------------------------------------------------------------
2876
E2InsertsBeforeE1(TEdge & e1,TEdge & e2)2877 bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
2878 {
2879 return e2.xcurr == e1.xcurr ? e2.dx > e1.dx : e2.xcurr < e1.xcurr;
2880 }
2881 //------------------------------------------------------------------------------
2882
InsertEdgeIntoAEL(TEdge * edge)2883 void Clipper::InsertEdgeIntoAEL(TEdge *edge)
2884 {
2885 edge->prevInAEL = 0;
2886 edge->nextInAEL = 0;
2887 if( !m_ActiveEdges )
2888 {
2889 m_ActiveEdges = edge;
2890 }
2891 else if( E2InsertsBeforeE1(*m_ActiveEdges, *edge) )
2892 {
2893 edge->nextInAEL = m_ActiveEdges;
2894 m_ActiveEdges->prevInAEL = edge;
2895 m_ActiveEdges = edge;
2896 } else
2897 {
2898 TEdge* e = m_ActiveEdges;
2899 while( e->nextInAEL && !E2InsertsBeforeE1(*e->nextInAEL , *edge) )
2900 e = e->nextInAEL;
2901 edge->nextInAEL = e->nextInAEL;
2902 if( e->nextInAEL ) e->nextInAEL->prevInAEL = edge;
2903 edge->prevInAEL = e;
2904 e->nextInAEL = edge;
2905 }
2906 }
2907 //----------------------------------------------------------------------
2908
DoEdge1(TEdge * edge1,TEdge * edge2,const IntPoint & pt)2909 void Clipper::DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2910 {
2911 AddOutPt(edge1, pt);
2912 SwapSides(*edge1, *edge2);
2913 SwapPolyIndexes(*edge1, *edge2);
2914 }
2915 //----------------------------------------------------------------------
2916
DoEdge2(TEdge * edge1,TEdge * edge2,const IntPoint & pt)2917 void Clipper::DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2918 {
2919 AddOutPt(edge2, pt);
2920 SwapSides(*edge1, *edge2);
2921 SwapPolyIndexes(*edge1, *edge2);
2922 }
2923 //----------------------------------------------------------------------
2924
DoBothEdges(TEdge * edge1,TEdge * edge2,const IntPoint & pt)2925 void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt)
2926 {
2927 AddOutPt(edge1, pt);
2928 AddOutPt(edge2, pt);
2929 SwapSides( *edge1 , *edge2 );
2930 SwapPolyIndexes( *edge1 , *edge2 );
2931 }
2932 //----------------------------------------------------------------------
2933
CheckHoleLinkages1(OutRec * outRec1,OutRec * outRec2)2934 void Clipper::CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2)
2935 {
2936 //when a polygon is split into 2 polygons, make sure any holes the original
2937 //polygon contained link to the correct polygon ...
2938 for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
2939 {
2940 OutRec *orec = m_PolyOuts[i];
2941 if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec1 &&
2942 !PointInPolygon(orec->bottomPt->pt, outRec1->pts, m_UseFullRange))
2943 orec->FirstLeft = outRec2;
2944 }
2945 }
2946 //----------------------------------------------------------------------
2947
CheckHoleLinkages2(OutRec * outRec1,OutRec * outRec2)2948 void Clipper::CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2)
2949 {
2950 //if a hole is owned by outRec2 then make it owned by outRec1 ...
2951 for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
2952 if (m_PolyOuts[i]->isHole && m_PolyOuts[i]->bottomPt &&
2953 m_PolyOuts[i]->FirstLeft == outRec2)
2954 m_PolyOuts[i]->FirstLeft = outRec1;
2955 }
2956 //----------------------------------------------------------------------
2957
JoinCommonEdges(bool fixHoleLinkages)2958 void Clipper::JoinCommonEdges(bool fixHoleLinkages)
2959 {
2960 for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
2961 {
2962 JoinRec* j = m_Joins[i];
2963 OutRec *outRec1 = m_PolyOuts[j->poly1Idx];
2964 OutPt *pp1a = outRec1->pts;
2965 OutRec *outRec2 = m_PolyOuts[j->poly2Idx];
2966 OutPt *pp2a = outRec2->pts;
2967 IntPoint pt1 = j->pt2a, pt2 = j->pt2b;
2968 IntPoint pt3 = j->pt1a, pt4 = j->pt1b;
2969 if (!FindSegment(pp1a, pt1, pt2)) continue;
2970 if (j->poly1Idx == j->poly2Idx)
2971 {
2972 //we're searching the same polygon for overlapping segments so
2973 //segment 2 mustn't be the same as segment 1 ...
2974 pp2a = pp1a->next;
2975 if (!FindSegment(pp2a, pt3, pt4) || (pp2a == pp1a)) continue;
2976 }
2977 else if (!FindSegment(pp2a, pt3, pt4)) continue;
2978
2979 if (!GetOverlapSegment(pt1, pt2, pt3, pt4, pt1, pt2)) continue;
2980
2981 OutPt *p1, *p2, *p3, *p4;
2982 OutPt *prev = pp1a->prev;
2983 //get p1 & p2 polypts - the overlap start & endpoints on poly1
2984 if (PointsEqual(pp1a->pt, pt1)) p1 = pp1a;
2985 else if (PointsEqual(prev->pt, pt1)) p1 = prev;
2986 else p1 = InsertPolyPtBetween(pp1a, prev, pt1);
2987
2988 if (PointsEqual(pp1a->pt, pt2)) p2 = pp1a;
2989 else if (PointsEqual(prev->pt, pt2)) p2 = prev;
2990 else if ((p1 == pp1a) || (p1 == prev))
2991 p2 = InsertPolyPtBetween(pp1a, prev, pt2);
2992 else if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2))
2993 p2 = InsertPolyPtBetween(pp1a, p1, pt2); else
2994 p2 = InsertPolyPtBetween(p1, prev, pt2);
2995
2996 //get p3 & p4 polypts - the overlap start & endpoints on poly2
2997 prev = pp2a->prev;
2998 if (PointsEqual(pp2a->pt, pt1)) p3 = pp2a;
2999 else if (PointsEqual(prev->pt, pt1)) p3 = prev;
3000 else p3 = InsertPolyPtBetween(pp2a, prev, pt1);
3001
3002 if (PointsEqual(pp2a->pt, pt2)) p4 = pp2a;
3003 else if (PointsEqual(prev->pt, pt2)) p4 = prev;
3004 else if ((p3 == pp2a) || (p3 == prev))
3005 p4 = InsertPolyPtBetween(pp2a, prev, pt2);
3006 else if (Pt3IsBetweenPt1AndPt2(pp2a->pt, p3->pt, pt2))
3007 p4 = InsertPolyPtBetween(pp2a, p3, pt2); else
3008 p4 = InsertPolyPtBetween(p3, prev, pt2);
3009
3010 //p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ...
3011 if (p1->next == p2 && p3->prev == p4)
3012 {
3013 p1->next = p3;
3014 p3->prev = p1;
3015 p2->prev = p4;
3016 p4->next = p2;
3017 }
3018 else if (p1->prev == p2 && p3->next == p4)
3019 {
3020 p1->prev = p3;
3021 p3->next = p1;
3022 p2->next = p4;
3023 p4->prev = p2;
3024 }
3025 else
3026 continue; //an orientation is probably wrong
3027
3028 if (j->poly2Idx == j->poly1Idx)
3029 {
3030 //instead of joining two polygons, we've just created a new one by
3031 //splitting one polygon into two.
3032 outRec1->pts = GetBottomPt(p1);
3033 outRec1->bottomPt = outRec1->pts;
3034 outRec1->bottomPt->idx = outRec1->idx;
3035 outRec2 = CreateOutRec();
3036 m_PolyOuts.push_back(outRec2);
3037 outRec2->idx = (int)m_PolyOuts.size()-1;
3038 j->poly2Idx = outRec2->idx;
3039 outRec2->pts = GetBottomPt(p2);
3040 outRec2->bottomPt = outRec2->pts;
3041 outRec2->bottomPt->idx = outRec2->idx;
3042
3043 if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange))
3044 {
3045 //outRec2 is contained by outRec1 ...
3046 outRec2->isHole = !outRec1->isHole;
3047 outRec2->FirstLeft = outRec1;
3048 if (outRec2->isHole ==
3049 (m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange)))
3050 ReversePolyPtLinks(*outRec2->pts);
3051 } else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRange))
3052 {
3053 //outRec1 is contained by outRec2 ...
3054 outRec2->isHole = outRec1->isHole;
3055 outRec1->isHole = !outRec2->isHole;
3056 outRec2->FirstLeft = outRec1->FirstLeft;
3057 outRec1->FirstLeft = outRec2;
3058 if (outRec1->isHole ==
3059 (m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange)))
3060 ReversePolyPtLinks(*outRec1->pts);
3061 //make sure any contained holes now link to the correct polygon ...
3062 if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2);
3063 } else
3064 {
3065 outRec2->isHole = outRec1->isHole;
3066 outRec2->FirstLeft = outRec1->FirstLeft;
3067 //make sure any contained holes now link to the correct polygon ...
3068 if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2);
3069 }
3070
3071 //now fixup any subsequent joins that match this polygon
3072 for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
3073 {
3074 JoinRec* j2 = m_Joins[k];
3075 if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2))
3076 j2->poly1Idx = j->poly2Idx;
3077 if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2))
3078 j2->poly2Idx = j->poly2Idx;
3079 }
3080
3081 //now cleanup redundant edges too ...
3082 FixupOutPolygon(*outRec1);
3083 FixupOutPolygon(*outRec2);
3084
3085 if (Orientation(outRec1, m_UseFullRange) != (Area(*outRec1, m_UseFullRange) > 0))
3086 DisposeBottomPt(*outRec1);
3087 if (Orientation(outRec2, m_UseFullRange) != (Area(*outRec2, m_UseFullRange) > 0))
3088 DisposeBottomPt(*outRec2);
3089
3090 } else
3091 {
3092 //joined 2 polygons together ...
3093
3094 //make sure any holes contained by outRec2 now link to outRec1 ...
3095 if (fixHoleLinkages) CheckHoleLinkages2(outRec1, outRec2);
3096
3097 //now cleanup redundant edges too ...
3098 FixupOutPolygon(*outRec1);
3099
3100 if (outRec1->pts)
3101 {
3102 outRec1->isHole = !Orientation(outRec1, m_UseFullRange);
3103 if (outRec1->isHole && !outRec1->FirstLeft)
3104 outRec1->FirstLeft = outRec2->FirstLeft;
3105 }
3106
3107 //delete the obsolete pointer ...
3108 int OKIdx = outRec1->idx;
3109 int ObsoleteIdx = outRec2->idx;
3110 outRec2->pts = 0;
3111 outRec2->bottomPt = 0;
3112 outRec2->AppendLink = outRec1;
3113
3114 //now fixup any subsequent Joins that match this polygon
3115 for (JoinList::size_type k = i+1; k < m_Joins.size(); k++)
3116 {
3117 JoinRec* j2 = m_Joins[k];
3118 if (j2->poly1Idx == ObsoleteIdx) j2->poly1Idx = OKIdx;
3119 if (j2->poly2Idx == ObsoleteIdx) j2->poly2Idx = OKIdx;
3120 }
3121 }
3122 }
3123 }
3124 //------------------------------------------------------------------------------
3125
ReversePolygon(Polygon & p)3126 void ReversePolygon(Polygon& p)
3127 {
3128 std::reverse(p.begin(), p.end());
3129 }
3130 //------------------------------------------------------------------------------
3131
ReversePolygons(Polygons & p)3132 void ReversePolygons(Polygons& p)
3133 {
3134 for (Polygons::size_type i = 0; i < p.size(); ++i)
3135 ReversePolygon(p[i]);
3136 }
3137
3138 //------------------------------------------------------------------------------
3139 // OffsetPolygon functions ...
3140 //------------------------------------------------------------------------------
3141
3142 struct DoublePoint
3143 {
3144 double X;
3145 double Y;
DoublePointClipperLib::DoublePoint3146 DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {}
3147 };
3148 //------------------------------------------------------------------------------
3149
BuildArc(const IntPoint & pt,const double a1,const double a2,const double r)3150 Polygon BuildArc(const IntPoint &pt,
3151 const double a1, const double a2, const double r)
3152 {
3153 long64 steps = std::max(6, int(std::sqrt(std::fabs(r)) * std::fabs(a2 - a1)));
3154 if (steps > 0x100000) steps = 0x100000;
3155 int n = (unsigned)steps;
3156 Polygon result(n);
3157 double da = (a2 - a1) / (n -1);
3158 double a = a1;
3159 for (int i = 0; i < n; ++i)
3160 {
3161 result[i].X = pt.X + Round(std::cos(a)*r);
3162 result[i].Y = pt.Y + Round(std::sin(a)*r);
3163 a += da;
3164 }
3165 return result;
3166 }
3167 //------------------------------------------------------------------------------
3168
GetUnitNormal(const IntPoint & pt1,const IntPoint & pt2)3169 DoublePoint GetUnitNormal( const IntPoint &pt1, const IntPoint &pt2)
3170 {
3171 if(pt2.X == pt1.X && pt2.Y == pt1.Y)
3172 return DoublePoint(0, 0);
3173
3174 double dx = (double)(pt2.X - pt1.X);
3175 double dy = (double)(pt2.Y - pt1.Y);
3176 double f = 1 *1.0/ std::sqrt( dx*dx + dy*dy );
3177 dx *= f;
3178 dy *= f;
3179 return DoublePoint(dy, -dx);
3180 }
3181
3182 //------------------------------------------------------------------------------
3183 //------------------------------------------------------------------------------
3184
3185 class PolyOffsetBuilder
3186 {
3187 private:
3188 Polygons m_p;
3189 Polygon* m_curr_poly;
3190 std::vector<DoublePoint> normals;
3191 double m_delta, m_RMin, m_R;
3192 size_t m_i, m_j, m_k;
3193 static const int buffLength = 128;
3194 JoinType m_jointype;
3195
3196 public:
3197
PolyOffsetBuilder(const Polygons & in_polys,Polygons & out_polys,double delta,JoinType jointype,double MiterLimit)3198 PolyOffsetBuilder(const Polygons& in_polys, Polygons& out_polys,
3199 double delta, JoinType jointype, double MiterLimit)
3200 {
3201 //nb precondition - out_polys != ptsin_polys
3202 if (NEAR_ZERO(delta))
3203 {
3204 out_polys = in_polys;
3205 return;
3206 }
3207
3208 this->m_p = in_polys;
3209 this->m_delta = delta;
3210 this->m_jointype = jointype;
3211 if (MiterLimit <= 1) MiterLimit = 1;
3212 m_RMin = 2/(MiterLimit*MiterLimit);
3213
3214 double deltaSq = delta*delta;
3215 out_polys.clear();
3216 out_polys.resize(in_polys.size());
3217 for (m_i = 0; m_i < in_polys.size(); m_i++)
3218 {
3219 m_curr_poly = &out_polys[m_i];
3220 size_t len = in_polys[m_i].size();
3221 if (len > 1 && m_p[m_i][0].X == m_p[m_i][len - 1].X &&
3222 m_p[m_i][0].Y == m_p[m_i][len-1].Y) len--;
3223
3224 //when 'shrinking' polygons - to minimize artefacts
3225 //strip those polygons that have an area < pi * delta^2 ...
3226 double a1 = Area(in_polys[m_i]);
3227 if (delta < 0) { if (a1 > 0 && a1 < deltaSq *pi) len = 0; }
3228 else if (a1 < 0 && -a1 < deltaSq *pi) len = 0; //holes have neg. area
3229
3230 if (len == 0 || (len < 3 && delta <= 0))
3231 continue;
3232 else if (len == 1)
3233 {
3234 Polygon arc;
3235 arc = BuildArc(in_polys[m_i][len-1], 0, 2 * pi, delta);
3236 out_polys[m_i] = arc;
3237 continue;
3238 }
3239
3240 //build normals ...
3241 normals.clear();
3242 normals.resize(len);
3243 normals[len-1] = GetUnitNormal(in_polys[m_i][len-1], in_polys[m_i][0]);
3244 for (m_j = 0; m_j < len -1; ++m_j)
3245 normals[m_j] = GetUnitNormal(in_polys[m_i][m_j], in_polys[m_i][m_j+1]);
3246
3247 m_k = len -1;
3248 for (m_j = 0; m_j < len; ++m_j)
3249 {
3250 switch (jointype)
3251 {
3252 case jtMiter:
3253 {
3254 m_R = 1 + (normals[m_j].X*normals[m_k].X +
3255 normals[m_j].Y*normals[m_k].Y);
3256 if (m_R >= m_RMin) DoMiter(); else DoSquare(MiterLimit);
3257 break;
3258 }
3259 case jtSquare: DoSquare(); break;
3260 case jtRound: DoRound(); break;
3261 }
3262 m_k = m_j;
3263 }
3264 }
3265
3266 //finally, clean up untidy corners using Clipper ...
3267 Clipper clpr;
3268 clpr.AddPolygons(out_polys, ptSubject);
3269 if (delta > 0)
3270 {
3271 if (!clpr.Execute(ctUnion, out_polys, pftPositive, pftPositive))
3272 out_polys.clear();
3273 }
3274 else
3275 {
3276 IntRect r = clpr.GetBounds();
3277 Polygon outer(4);
3278 outer[0] = IntPoint(r.left - 10, r.bottom + 10);
3279 outer[1] = IntPoint(r.right + 10, r.bottom + 10);
3280 outer[2] = IntPoint(r.right + 10, r.top - 10);
3281 outer[3] = IntPoint(r.left - 10, r.top - 10);
3282
3283 clpr.AddPolygon(outer, ptSubject);
3284 if (clpr.Execute(ctUnion, out_polys, pftNegative, pftNegative))
3285 {
3286 out_polys.erase(out_polys.begin());
3287 ReversePolygons(out_polys);
3288
3289 } else
3290 out_polys.clear();
3291 }
3292 }
3293 //------------------------------------------------------------------------------
3294
3295 private:
3296
AddPoint(const IntPoint & pt)3297 void AddPoint(const IntPoint& pt)
3298 {
3299 Polygon::size_type len = m_curr_poly->size();
3300 if (len == m_curr_poly->capacity())
3301 m_curr_poly->reserve(len + buffLength);
3302 m_curr_poly->push_back(pt);
3303 }
3304 //------------------------------------------------------------------------------
3305
DoSquare(double mul=1.0)3306 void DoSquare(double mul = 1.0)
3307 {
3308 IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
3309 (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
3310 IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
3311 (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
3312 if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
3313 {
3314 double a1 = std::atan2(normals[m_k].Y, normals[m_k].X);
3315 double a2 = std::atan2(-normals[m_j].Y, -normals[m_j].X);
3316 a1 = std::fabs(a2 - a1);
3317 if (a1 > pi) a1 = pi * 2 - a1;
3318 double dx = std::tan((pi - a1)/4) * std::fabs(m_delta * mul);
3319 pt1 = IntPoint((long64)(pt1.X -normals[m_k].Y * dx),
3320 (long64)(pt1.Y + normals[m_k].X * dx));
3321 AddPoint(pt1);
3322 pt2 = IntPoint((long64)(pt2.X + normals[m_j].Y * dx),
3323 (long64)(pt2.Y -normals[m_j].X * dx));
3324 AddPoint(pt2);
3325 }
3326 else
3327 {
3328 AddPoint(pt1);
3329 AddPoint(m_p[m_i][m_j]);
3330 AddPoint(pt2);
3331 }
3332 }
3333 //------------------------------------------------------------------------------
3334
DoMiter()3335 void DoMiter()
3336 {
3337 if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
3338 {
3339 double q = m_delta / m_R;
3340 AddPoint(IntPoint((long64)Round(m_p[m_i][m_j].X +
3341 (normals[m_k].X + normals[m_j].X) * q),
3342 (long64)Round(m_p[m_i][m_j].Y + (normals[m_k].Y + normals[m_j].Y) * q)));
3343 }
3344 else
3345 {
3346 IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X *
3347 m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
3348 IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X *
3349 m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
3350 AddPoint(pt1);
3351 AddPoint(m_p[m_i][m_j]);
3352 AddPoint(pt2);
3353 }
3354 }
3355 //------------------------------------------------------------------------------
3356
DoRound()3357 void DoRound()
3358 {
3359 IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
3360 (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
3361 IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
3362 (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
3363 AddPoint(pt1);
3364 //round off reflex angles (ie > 180 deg) unless almost flat (ie < ~10deg).
3365 if ((normals[m_k].X*normals[m_j].Y - normals[m_j].X*normals[m_k].Y) * m_delta >= 0)
3366 {
3367 if (normals[m_j].X * normals[m_k].X + normals[m_j].Y * normals[m_k].Y < 0.985)
3368 {
3369 double a1 = std::atan2(normals[m_k].Y, normals[m_k].X);
3370 double a2 = std::atan2(normals[m_j].Y, normals[m_j].X);
3371 if (m_delta > 0 && a2 < a1) a2 += pi *2;
3372 else if (m_delta < 0 && a2 > a1) a2 -= pi *2;
3373 Polygon arc = BuildArc(m_p[m_i][m_j], a1, a2, m_delta);
3374 for (Polygon::size_type m = 0; m < arc.size(); m++)
3375 AddPoint(arc[m]);
3376 }
3377 }
3378 else
3379 AddPoint(m_p[m_i][m_j]);
3380 AddPoint(pt2);
3381 }
3382 //--------------------------------------------------------------------------
3383
3384 }; //end PolyOffsetBuilder
3385
3386 //------------------------------------------------------------------------------
3387 //------------------------------------------------------------------------------
3388
OffsetPolygons(const Polygons & in_polys,Polygons & out_polys,double delta,JoinType jointype,double MiterLimit)3389 void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys,
3390 double delta, JoinType jointype, double MiterLimit)
3391 {
3392 if (&out_polys == &in_polys)
3393 {
3394 Polygons poly2(in_polys);
3395 PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit);
3396 }
3397 else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit);
3398 }
3399 //------------------------------------------------------------------------------
3400
SimplifyPolygon(const Polygon & in_poly,Polygons & out_polys,PolyFillType fillType)3401 void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType)
3402 {
3403 Clipper c;
3404 c.AddPolygon(in_poly, ptSubject);
3405 c.Execute(ctUnion, out_polys, fillType, fillType);
3406 }
3407 //------------------------------------------------------------------------------
3408
SimplifyPolygons(const Polygons & in_polys,Polygons & out_polys,PolyFillType fillType)3409 void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType)
3410 {
3411 Clipper c;
3412 c.AddPolygons(in_polys, ptSubject);
3413 c.Execute(ctUnion, out_polys, fillType, fillType);
3414 }
3415 //------------------------------------------------------------------------------
3416
SimplifyPolygons(Polygons & polys,PolyFillType fillType)3417 void SimplifyPolygons(Polygons &polys, PolyFillType fillType)
3418 {
3419 SimplifyPolygons(polys, polys, fillType);
3420 }
3421 //------------------------------------------------------------------------------
3422
operator <<(std::ostream & s,IntPoint & p)3423 std::ostream& operator <<(std::ostream &s, IntPoint& p)
3424 {
3425 s << p.X << ' ' << p.Y << "\n";
3426 return s;
3427 }
3428 //------------------------------------------------------------------------------
3429
operator <<(std::ostream & s,Polygon & p)3430 std::ostream& operator <<(std::ostream &s, Polygon &p)
3431 {
3432 for (Polygon::size_type i = 0; i < p.size(); i++)
3433 s << p[i];
3434 s << "\n";
3435 return s;
3436 }
3437 //------------------------------------------------------------------------------
3438
operator <<(std::ostream & s,Polygons & p)3439 std::ostream& operator <<(std::ostream &s, Polygons &p)
3440 {
3441 for (Polygons::size_type i = 0; i < p.size(); i++)
3442 s << p[i];
3443 s << "\n";
3444 return s;
3445 }
3446 //------------------------------------------------------------------------------
3447
3448 } //ClipperLib namespace
3449