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