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