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