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.h"
42	#include <cmath>
43	#include <vector>
44	#include <algorithm>
45	#include <stdexcept>
46	#include <cstring>
47	#include <cstdlib>
48	#include <ostream>
49	#include <functional>
50
51	namespace QtClipperLib {
52
53	static double const pi = 3.141592653589793238;
54	static double const two_pi = pi *2;
55	static double const def_arc_tolerance = 0.25;
56
57	enum Direction { dRightToLeft, dLeftToRight };
58
59	static int const Unassigned = -1; //edge not currently 'owning' a solution
60	static int const Skip = -2; //edge that would otherwise close a path
61
62	#define HORIZONTAL (-1.0E+40)
63	#define TOLERANCE (1.0e-20)
64	#define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))
65
66	struct TEdge {
67	IntPoint Bot;
68	IntPoint Curr; //current (updated for every new scanbeam)
69	IntPoint Top;
70	double Dx;
71	PolyType PolyTyp;
72	EdgeSide Side; //side only refers to current side of solution poly
73	int WindDelta; //1 or -1 depending on winding direction
74	int WindCnt;
75	int WindCnt2; //winding count of the opposite polytype
76	int OutIdx;
77	TEdge *Next;
78	TEdge *Prev;
79	TEdge *NextInLML;
80	TEdge *NextInAEL;
81	TEdge *PrevInAEL;
82	TEdge *NextInSEL;
83	TEdge *PrevInSEL;
84	};
85
86	struct IntersectNode {
87	TEdge *Edge1;
88	TEdge *Edge2;
89	IntPoint Pt;
90	};
91
92	struct LocalMinimum {
93	cInt Y;
94	TEdge *LeftBound;
95	TEdge *RightBound;
96	};
97
98	struct OutPt;
99
100	//OutRec: contains a path in the clipping solution. Edges in the AEL will
101	//carry a pointer to an OutRec when they are part of the clipping solution.
102	struct OutRec {
103	int Idx;
104	bool IsHole;
105	bool IsOpen;
106	OutRec *FirstLeft; //see comments in clipper.pas
107	PolyNode *PolyNd;
108	OutPt *Pts;
109	OutPt *BottomPt;
110	};
111
112	struct OutPt {
113	int Idx;
114	IntPoint Pt;
115	OutPt *Next;
116	OutPt *Prev;
117	};
118
119	struct Join {
120	OutPt *OutPt1;
121	OutPt *OutPt2;
122	IntPoint OffPt;
123	};
124
125	struct LocMinSorter
126	{
127	inline bool operator()(const LocalMinimum& locMin1, const LocalMinimum& locMin2)
128	{
129	return locMin2.Y < locMin1.Y;
130	}
131	};
132
133	//------------------------------------------------------------------------------
134	//------------------------------------------------------------------------------
135
136	inline cInt Round(double val)
137	{
138	if ((val < 0)) return static_cast<cInt>(val - 0.5);
139	else return static_cast<cInt>(val + 0.5);
140	}
141	//------------------------------------------------------------------------------
142
143	inline cInt Abs(cInt val)
144	{
145	return val < 0 ? -val : val;
146	}
147
148	//------------------------------------------------------------------------------
149	// PolyTree methods ...
150	//------------------------------------------------------------------------------
151
152	void PolyTree::Clear()
153	{
154	for (PolyNodes::size_type i = 0; i < AllNodes.size(); ++i)
155	delete AllNodes[i];
156	AllNodes.resize(new_size: 0);
157	Childs.resize(new_size: 0);
158	}
159	//------------------------------------------------------------------------------
160
161	PolyNode* PolyTree::GetFirst() const
162	{
163	if (!Childs.empty())
164	return Childs[0];
165	else
166	return 0;
167	}
168	//------------------------------------------------------------------------------
169
170	int PolyTree::Total() const
171	{
172	int result = (int)AllNodes.size();
173	//with negative offsets, ignore the hidden outer polygon ...
174	if (result > 0 && Childs[0] != AllNodes[0]) result--;
175	return result;
176	}
177
178	//------------------------------------------------------------------------------
179	// PolyNode methods ...
180	//------------------------------------------------------------------------------
181
182	PolyNode::PolyNode(): Childs(), Parent(0), Index(0), m_IsOpen(false)
183	{
184	}
185	//------------------------------------------------------------------------------
186
187	int PolyNode::ChildCount() const
188	{
189	return (int)Childs.size();
190	}
191	//------------------------------------------------------------------------------
192
193	void PolyNode::AddChild(PolyNode& child)
194	{
195	unsigned cnt = (unsigned)Childs.size();
196	Childs.push_back(x: &child);
197	child.Parent = this;
198	child.Index = cnt;
199	}
200	//------------------------------------------------------------------------------
201
202	PolyNode* PolyNode::GetNext() const
203	{
204	if (!Childs.empty())
205	return Childs[0];
206	else
207	return GetNextSiblingUp();
208	}
209	//------------------------------------------------------------------------------
210
211	PolyNode* PolyNode::GetNextSiblingUp() const
212	{
213	if (!Parent) //protects against PolyTree.GetNextSiblingUp()
214	return 0;
215	else if (Index == Parent->Childs.size() - 1)
216	return Parent->GetNextSiblingUp();
217	else
218	return Parent->Childs[Index + 1];
219	}
220	//------------------------------------------------------------------------------
221
222	bool PolyNode::IsHole() const
223	{
224	bool result = true;
225	PolyNode* node = Parent;
226	while (node)
227	{
228	result = !result;
229	node = node->Parent;
230	}
231	return result;
232	}
233	//------------------------------------------------------------------------------
234
235	bool PolyNode::IsOpen() const
236	{
237	return m_IsOpen;
238	}
239	//------------------------------------------------------------------------------
240
241	#ifndef use_int32
242
243	//------------------------------------------------------------------------------
244	// Int128 class (enables safe math on signed 64bit integers)
245	// eg Int128 val1((long64)9223372036854775807); //ie 2^63 -1
246	// Int128 val2((long64)9223372036854775807);
247	// Int128 val3 = val1 * val2;
248	// val3.AsString => "85070591730234615847396907784232501249" (8.5e+37)
249	//------------------------------------------------------------------------------
250
251	class Int128
252	{
253	public:
254	ulong64 lo;
255	long64 hi;
256
257	Int128(long64 _lo = 0)
258	{
259	lo = (ulong64)_lo;
260	if (_lo < 0) hi = -1; else hi = 0;
261	}
262
263
264	Int128(const Int128 &val): lo(val.lo), hi(val.hi){}
265
266	Int128(const long64& _hi, const ulong64& _lo): lo(_lo), hi(_hi){}
267
268	Int128& operator = (const long64 &val)
269	{
270	lo = (ulong64)val;
271	if (val < 0) hi = -1; else hi = 0;
272	return *this;
273	}
274
275	bool operator == (const Int128 &val) const
276	{return (hi == val.hi && lo == val.lo);}
277
278	bool operator != (const Int128 &val) const
279	{ return !(*this == val);}
280
281	bool operator > (const Int128 &val) const
282	{
283	if (hi != val.hi)
284	return hi > val.hi;
285	else
286	return lo > val.lo;
287	}
288
289	bool operator < (const Int128 &val) const
290	{
291	if (hi != val.hi)
292	return hi < val.hi;
293	else
294	return lo < val.lo;
295	}
296
297	bool operator >= (const Int128 &val) const
298	{ return !(*this < val);}
299
300	bool operator <= (const Int128 &val) const
301	{ return !(*this > val);}
302
303	Int128& operator += (const Int128 &rhs)
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
318	Int128& operator -= (const Int128 &rhs)
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
354	Int128 Int128Mul (long64 lhs, long64 rhs)
355	{
356	bool negate = (lhs < 0) != (rhs < 0);
357
358	if (lhs < 0) lhs = -lhs;
359	ulong64 int1Hi = ulong64(lhs) >> 32;
360	ulong64 int1Lo = ulong64(lhs & 0xFFFFFFFF);
361
362	if (rhs < 0) rhs = -rhs;
363	ulong64 int2Hi = ulong64(rhs) >> 32;
364	ulong64 int2Lo = ulong64(rhs & 0xFFFFFFFF);
365
366	//nb: see comments in clipper.pas
367	ulong64 a = int1Hi * int2Hi;
368	ulong64 b = int1Lo * int2Lo;
369	ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi;
370
371	Int128 tmp;
372	tmp.hi = long64(a + (c >> 32));
373	tmp.lo = long64(c << 32);
374	tmp.lo += long64(b);
375	if (tmp.lo < b) tmp.hi++;
376	if (negate) tmp = -tmp;
377	return tmp;
378	};
379	#endif
380
381	//------------------------------------------------------------------------------
382	// Miscellaneous global functions
383	//------------------------------------------------------------------------------
384
385	bool Orientation(const Path &poly)
386	{
387	return Area(poly) >= 0;
388	}
389	//------------------------------------------------------------------------------
390
391	double Area(const Path &poly)
392	{
393	int size = (int)poly.size();
394	if (size < 3) return 0;
395
396	double a = 0;
397	for (int i = 0, j = size -1; i < size; ++i)
398	{
399	a += ((double)poly[j].X + poly[i].X) * ((double)poly[j].Y - poly[i].Y);
400	j = i;
401	}
402	return -a * 0.5;
403	}
404	//------------------------------------------------------------------------------
405
406	double Area(const OutPt *op)
407	{
408	const OutPt *startOp = op;
409	if (!op) return 0;
410	double a = 0;
411	do {
412	a += (double)(op->Prev->Pt.X + op->Pt.X) * (double)(op->Prev->Pt.Y - op->Pt.Y);
413	op = op->Next;
414	} while (op != startOp);
415	return a * 0.5;
416	}
417	//------------------------------------------------------------------------------
418
419	double Area(const OutRec &outRec)
420	{
421	return Area(op: outRec.Pts);
422	}
423	//------------------------------------------------------------------------------
424
425	bool PointIsVertex(const IntPoint &Pt, OutPt *pp)
426	{
427	OutPt *pp2 = pp;
428	do
429	{
430	if (pp2->Pt == Pt) return true;
431	pp2 = pp2->Next;
432	}
433	while (pp2 != pp);
434	return false;
435	}
436	//------------------------------------------------------------------------------
437
438	//See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
439	//http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
440	int PointInPolygon(const IntPoint &pt, const Path &path)
441	{
442	//returns 0 if false, +1 if true, -1 if pt ON polygon boundary
443	int result = 0;
444	size_t cnt = path.size();
445	if (cnt < 3) return 0;
446	IntPoint ip = path[0];
447	for(size_t i = 1; i <= cnt; ++i)
448	{
449	IntPoint ipNext = (i == cnt ? path[0] : path[i]);
450	if (ipNext.Y == pt.Y)
451	{
452	if ((ipNext.X == pt.X) || (ip.Y == pt.Y &&
453	((ipNext.X > pt.X) == (ip.X < pt.X)))) return -1;
454	}
455	if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
456	{
457	if (ip.X >= pt.X)
458	{
459	if (ipNext.X > pt.X) result = 1 - result;
460	else
461	{
462	double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
463	(double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
464	if (!d) return -1;
465	if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
466	}
467	} else
468	{
469	if (ipNext.X > pt.X)
470	{
471	double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
472	(double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
473	if (!d) return -1;
474	if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result;
475	}
476	}
477	}
478	ip = ipNext;
479	}
480	return result;
481	}
482	//------------------------------------------------------------------------------
483
484	int PointInPolygon (const IntPoint &pt, OutPt *op)
485	{
486	//returns 0 if false, +1 if true, -1 if pt ON polygon boundary
487	int result = 0;
488	OutPt* startOp = op;
489	for(;;)
490	{
491	if (op->Next->Pt.Y == pt.Y)
492	{
493	if ((op->Next->Pt.X == pt.X) || (op->Pt.Y == pt.Y &&
494	((op->Next->Pt.X > pt.X) == (op->Pt.X < pt.X)))) return -1;
495	}
496	if ((op->Pt.Y < pt.Y) != (op->Next->Pt.Y < pt.Y))
497	{
498	if (op->Pt.X >= pt.X)
499	{
500	if (op->Next->Pt.X > pt.X) result = 1 - result;
501	else
502	{
503	double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) -
504	(double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
505	if (!d) return -1;
506	if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
507	}
508	} else
509	{
510	if (op->Next->Pt.X > pt.X)
511	{
512	double d = (double)(op->Pt.X - pt.X) * (op->Next->Pt.Y - pt.Y) -
513	(double)(op->Next->Pt.X - pt.X) * (op->Pt.Y - pt.Y);
514	if (!d) return -1;
515	if ((d > 0) == (op->Next->Pt.Y > op->Pt.Y)) result = 1 - result;
516	}
517	}
518	}
519	op = op->Next;
520	if (startOp == op) break;
521	}
522	return result;
523	}
524	//------------------------------------------------------------------------------
525
526	bool Poly2ContainsPoly1(OutPt *OutPt1, OutPt *OutPt2)
527	{
528	OutPt* op = OutPt1;
529	do
530	{
531	//nb: PointInPolygon returns 0 if false, +1 if true, -1 if pt on polygon
532	int res = PointInPolygon(pt: op->Pt, op: OutPt2);
533	if (res >= 0) return res > 0;
534	op = op->Next;
535	}
536	while (op != OutPt1);
537	return true;
538	}
539	//----------------------------------------------------------------------
540
541	bool SlopesEqual(const TEdge &e1, const TEdge &e2, bool UseFullInt64Range)
542	{
543	#ifndef use_int32
544	if (UseFullInt64Range)
545	return Int128Mul(lhs: e1.Top.Y - e1.Bot.Y, rhs: e2.Top.X - e2.Bot.X) ==
546	Int128Mul(lhs: e1.Top.X - e1.Bot.X, rhs: e2.Top.Y - e2.Bot.Y);
547	else
548	#endif
549	return (e1.Top.Y - e1.Bot.Y) * (e2.Top.X - e2.Bot.X) ==
550	(e1.Top.X - e1.Bot.X) * (e2.Top.Y - e2.Bot.Y);
551	}
552	//------------------------------------------------------------------------------
553
554	bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
555	const IntPoint pt3, bool UseFullInt64Range)
556	{
557	#ifndef use_int32
558	if (UseFullInt64Range)
559	return Int128Mul(lhs: pt1.Y-pt2.Y, rhs: pt2.X-pt3.X) == Int128Mul(lhs: pt1.X-pt2.X, rhs: pt2.Y-pt3.Y);
560	else
561	#endif
562	return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y);
563	}
564	//------------------------------------------------------------------------------
565
566	bool SlopesEqual(const IntPoint pt1, const IntPoint pt2,
567	const IntPoint pt3, const IntPoint pt4, bool UseFullInt64Range)
568	{
569	#ifndef use_int32
570	if (UseFullInt64Range)
571	return Int128Mul(lhs: pt1.Y-pt2.Y, rhs: pt3.X-pt4.X) == Int128Mul(lhs: pt1.X-pt2.X, rhs: pt3.Y-pt4.Y);
572	else
573	#endif
574	return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y);
575	}
576	//------------------------------------------------------------------------------
577
578	inline bool IsHorizontal(TEdge &e)
579	{
580	return e.Dx == HORIZONTAL;
581	}
582	//------------------------------------------------------------------------------
583
584	inline double GetDx(const IntPoint pt1, const IntPoint pt2)
585	{
586	return (pt1.Y == pt2.Y) ?
587	HORIZONTAL : (double)(pt2.X - pt1.X) / (pt2.Y - pt1.Y);
588	}
589	//---------------------------------------------------------------------------
590
591	inline void SetDx(TEdge &e)
592	{
593	cInt dy = (e.Top.Y - e.Bot.Y);
594	if (dy == 0) e.Dx = HORIZONTAL;
595	else e.Dx = (double)(e.Top.X - e.Bot.X) / dy;
596	}
597	//---------------------------------------------------------------------------
598
599	inline void SwapSides(TEdge &Edge1, TEdge &Edge2)
600	{
601	EdgeSide Side = Edge1.Side;
602	Edge1.Side = Edge2.Side;
603	Edge2.Side = Side;
604	}
605	//------------------------------------------------------------------------------
606
607	inline void SwapPolyIndexes(TEdge &Edge1, TEdge &Edge2)
608	{
609	int OutIdx = Edge1.OutIdx;
610	Edge1.OutIdx = Edge2.OutIdx;
611	Edge2.OutIdx = OutIdx;
612	}
613	//------------------------------------------------------------------------------
614
615	inline cInt TopX(TEdge &edge, const cInt currentY)
616	{
617	return ( currentY == edge.Top.Y ) ?
618	edge.Top.X : edge.Bot.X + Round(val: edge.Dx *(currentY - edge.Bot.Y));
619	}
620	//------------------------------------------------------------------------------
621
622	void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip)
623	{
624	#ifdef use_xyz
625	ip.Z = 0;
626	#endif
627
628	double b1, b2;
629	if (Edge1.Dx == Edge2.Dx)
630	{
631	ip.Y = Edge1.Curr.Y;
632	ip.X = TopX(edge&: Edge1, currentY: ip.Y);
633	return;
634	}
635	else if (Edge1.Dx == 0)
636	{
637	ip.X = Edge1.Bot.X;
638	if (IsHorizontal(e&: Edge2))
639	ip.Y = Edge2.Bot.Y;
640	else
641	{
642	b2 = Edge2.Bot.Y - (Edge2.Bot.X / Edge2.Dx);
643	ip.Y = Round(val: ip.X / Edge2.Dx + b2);
644	}
645	}
646	else if (Edge2.Dx == 0)
647	{
648	ip.X = Edge2.Bot.X;
649	if (IsHorizontal(e&: Edge1))
650	ip.Y = Edge1.Bot.Y;
651	else
652	{
653	b1 = Edge1.Bot.Y - (Edge1.Bot.X / Edge1.Dx);
654	ip.Y = Round(val: 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(val: q);
663	if (std::fabs(x: Edge1.Dx) < std::fabs(x: Edge2.Dx))
664	ip.X = Round(val: Edge1.Dx * q + b1);
665	else
666	ip.X = Round(val: 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(x: Edge1.Dx) < std::fabs(x: Edge2.Dx))
676	ip.X = TopX(edge&: Edge1, currentY: ip.Y);
677	else
678	ip.X = TopX(edge&: Edge2, currentY: 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(x: Edge1.Dx) > std::fabs(x: Edge2.Dx))
686	ip.X = TopX(edge&: Edge2, currentY: ip.Y); else
687	ip.X = TopX(edge&: Edge1, currentY: ip.Y);
688	}
689	}
690	//------------------------------------------------------------------------------
691
692	void ReversePolyPtLinks(OutPt *pp)
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
706	void DisposeOutPts(OutPt*& pp)
707	{
708	if (pp == 0) return;
709	pp->Prev->Next = 0;
710	while( pp )
711	{
712	OutPt *tmpPp = pp;
713	pp = pp->Next;
714	delete tmpPp;
715	}
716	}
717	//------------------------------------------------------------------------------
718
719	inline void InitEdge(TEdge* e, TEdge* eNext, TEdge* ePrev, const IntPoint& Pt)
720	{
721	std::memset(s: e, c: 0, n: sizeof(TEdge));
722	e->Next = eNext;
723	e->Prev = ePrev;
724	e->Curr = Pt;
725	e->OutIdx = Unassigned;
726	}
727	//------------------------------------------------------------------------------
728
729	void InitEdge2(TEdge& e, PolyType Pt)
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
745	TEdge* RemoveEdge(TEdge* e)
746	{
747	//removes e from double_linked_list (but without removing from memory)
748	e->Prev->Next = e->Next;
749	e->Next->Prev = e->Prev;
750	TEdge* result = e->Next;
751	e->Prev = 0; //flag as removed (see ClipperBase.Clear)
752	return result;
753	}
754	//------------------------------------------------------------------------------
755
756	inline void ReverseHorizontal(TEdge &e)
757	{
758	//swap horizontal edges' Top and Bottom x's so they follow the natural
759	//progression of the bounds - ie so their xbots will align with the
760	//adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
761	std::swap(a&: e.Top.X, b&: e.Bot.X);
762	#ifdef use_xyz
763	std::swap(e.Top.Z, e.Bot.Z);
764	#endif
765	}
766	//------------------------------------------------------------------------------
767
768	void SwapPoints(IntPoint &pt1, IntPoint &pt2)
769	{
770	IntPoint tmp = pt1;
771	pt1 = pt2;
772	pt2 = tmp;
773	}
774	//------------------------------------------------------------------------------
775
776	bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
777	IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)
778	{
779	//precondition: segments are Collinear.
780	if (Abs(val: pt1a.X - pt1b.X) > Abs(val: pt1a.Y - pt1b.Y))
781	{
782	if (pt1a.X > pt1b.X) SwapPoints(pt1&: pt1a, pt2&: pt1b);
783	if (pt2a.X > pt2b.X) SwapPoints(pt1&: pt2a, pt2&: 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(pt1&: pt1a, pt2&: pt1b);
790	if (pt2a.Y < pt2b.Y) SwapPoints(pt1&: pt2a, pt2&: pt2b);
791	if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
792	if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
793	return pt1.Y > pt2.Y;
794	}
795	}
796	//------------------------------------------------------------------------------
797
798	bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
799	{
800	OutPt *p = btmPt1->Prev;
801	while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Prev;
802	double dx1p = std::fabs(x: GetDx(pt1: btmPt1->Pt, pt2: p->Pt));
803	p = btmPt1->Next;
804	while ((p->Pt == btmPt1->Pt) && (p != btmPt1)) p = p->Next;
805	double dx1n = std::fabs(x: GetDx(pt1: btmPt1->Pt, pt2: p->Pt));
806
807	p = btmPt2->Prev;
808	while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Prev;
809	double dx2p = std::fabs(x: GetDx(pt1: btmPt2->Pt, pt2: p->Pt));
810	p = btmPt2->Next;
811	while ((p->Pt == btmPt2->Pt) && (p != btmPt2)) p = p->Next;
812	double dx2n = std::fabs(x: GetDx(pt1: btmPt2->Pt, pt2: p->Pt));
813
814	if (std::max(a: dx1p, b: dx1n) == std::max(a: dx2p, b: dx2n) &&
815	std::min(a: dx1p, b: dx1n) == std::min(a: dx2p, b: dx2n))
816	return Area(op: btmPt1) > 0; //if otherwise identical use orientation
817	else
818	return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
819	}
820	//------------------------------------------------------------------------------
821
822	OutPt* GetBottomPt(OutPt *pp)
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(btmPt1: p, btmPt2: dups)) pp = dups;
852	dups = dups->Next;
853	while (dups->Pt != pp->Pt) dups = dups->Next;
854	}
855	}
856	return pp;
857	}
858	//------------------------------------------------------------------------------
859
860	bool Pt2IsBetweenPt1AndPt3(const IntPoint pt1,
861	const IntPoint pt2, const IntPoint pt3)
862	{
863	if ((pt1 == pt3) || (pt1 == pt2) || (pt3 == pt2))
864	return false;
865	else if (pt1.X != pt3.X)
866	return (pt2.X > pt1.X) == (pt2.X < pt3.X);
867	else
868	return (pt2.Y > pt1.Y) == (pt2.Y < pt3.Y);
869	}
870	//------------------------------------------------------------------------------
871
872	bool HorzSegmentsOverlap(cInt seg1a, cInt seg1b, cInt seg2a, cInt seg2b)
873	{
874	if (seg1a > seg1b) std::swap(a&: seg1a, b&: seg1b);
875	if (seg2a > seg2b) std::swap(a&: seg2a, b&: seg2b);
876	return (seg1a < seg2b) && (seg2a < seg1b);
877	}
878
879	//------------------------------------------------------------------------------
880	// ClipperBase class methods ...
881	//------------------------------------------------------------------------------
882
883	ClipperBase::ClipperBase() //constructor
884	{
885	m_CurrentLM = m_MinimaList.begin(); //begin() == end() here
886	m_UseFullRange = false;
887	}
888	//------------------------------------------------------------------------------
889
890	ClipperBase::~ClipperBase() //destructor
891	{
892	Clear();
893	}
894	//------------------------------------------------------------------------------
895
896	void RangeTest(const IntPoint& Pt, bool& useFullRange)
897	{
898	if (useFullRange)
899	{
900	if (Pt.X > hiRange || Pt.Y > hiRange || -Pt.X > hiRange || -Pt.Y > hiRange)
901	throw clipperException("Coordinate outside allowed range");
902	}
903	else if (Pt.X > loRange|| Pt.Y > loRange || -Pt.X > loRange || -Pt.Y > loRange)
904	{
905	useFullRange = true;
906	RangeTest(Pt, useFullRange);
907	}
908	}
909	//------------------------------------------------------------------------------
910
911	TEdge* FindNextLocMin(TEdge* E)
912	{
913	for (;;)
914	{
915	while (E->Bot != E->Prev->Bot || E->Curr == E->Top) E = E->Next;
916	if (!IsHorizontal(e&: *E) && !IsHorizontal(e&: *E->Prev)) break;
917	while (IsHorizontal(e&: *E->Prev)) E = E->Prev;
918	TEdge* E2 = E;
919	while (IsHorizontal(e&: *E)) E = E->Next;
920	if (E->Top.Y == E->Prev->Bot.Y) continue; //ie just an intermediate horz.
921	if (E2->Prev->Bot.X < E->Bot.X) E = E2;
922	break;
923	}
924	return E;
925	}
926	//------------------------------------------------------------------------------
927
928	TEdge* ClipperBase::ProcessBound(TEdge* E, bool NextIsForward)
929	{
930	TEdge *Result = E;
931	TEdge *Horz = 0;
932
933	if (E->OutIdx == Skip)
934	{
935	//if edges still remain in the current bound beyond the skip edge then
936	//create another LocMin and call ProcessBound once more
937	if (NextIsForward)
938	{
939	while (E->Top.Y == E->Next->Bot.Y) E = E->Next;
940	//don't include top horizontals when parsing a bound a second time,
941	//they will be contained in the opposite bound ...
942	while (E != Result && IsHorizontal(e&: *E)) E = 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 = 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(x: locMin);
969	}
970	return Result;
971	}
972
973	TEdge *EStart;
974
975	if (IsHorizontal(e&: *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(e&: *EStart)) //ie an adjoining horizontal skip edge
985	{
986	if (EStart->Bot.X != E->Bot.X && EStart->Top.X != E->Bot.X)
987	ReverseHorizontal(e&: *E);
988	}
989	else if (EStart->Bot.X != E->Bot.X)
990	ReverseHorizontal(e&: *E);
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(e&: *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(e&: *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) && E != EStart &&
1011	E->Bot.X != E->Prev->Top.X) ReverseHorizontal(e&: *E);
1012	E = E->Next;
1013	}
1014	if (IsHorizontal(e&: *E) && E != EStart && E->Bot.X != E->Prev->Top.X)
1015	ReverseHorizontal(e&: *E);
1016	Result = Result->Next; //move to the edge just beyond current bound
1017	} else
1018	{
1019	while (Result->Top.Y == Result->Prev->Bot.Y && Result->Prev->OutIdx != Skip)
1020	Result = Result->Prev;
1021	if (IsHorizontal(e&: *Result) && Result->Prev->OutIdx != Skip)
1022	{
1023	Horz = Result;
1024	while (IsHorizontal(e&: *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) && E != EStart && E->Bot.X != E->Next->Top.X)
1033	ReverseHorizontal(e&: *E);
1034	E = E->Prev;
1035	}
1036	if (IsHorizontal(e&: *E) && E != EStart && E->Bot.X != E->Next->Top.X)
1037	ReverseHorizontal(e&: *E);
1038	Result = Result->Prev; //move to the edge just beyond current bound
1039	}
1040
1041	return Result;
1042	}
1043	//------------------------------------------------------------------------------
1044
1045	bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
1046	{
1047	#ifdef use_lines
1048	if (!Closed && PolyTyp == ptClip)
1049	throw clipperException("AddPath: Open paths must be subject.");
1050	#else
1051	if (!Closed)
1052	throw clipperException("AddPath: Open paths have been disabled.");
1053	#endif
1054
1055	int highI = (int)pg.size() -1;
1056	if (Closed) while (highI > 0 && (pg[highI] == pg[0])) --highI;
1057	while (highI > 0 && (pg[highI] == pg[highI -1])) --highI;
1058	if ((Closed && highI < 2) || (!Closed && highI < 1)) return false;
1059
1060	//create a new edge array ...
1061	TEdge *edges = new TEdge [highI +1];
1062
1063	bool IsFlat = true;
1064	//1. Basic (first) edge initialization ...
1065	try
1066	{
1067	edges[1].Curr = pg[1];
1068	RangeTest(Pt: pg[0], useFullRange&: m_UseFullRange);
1069	RangeTest(Pt: pg[highI], useFullRange&: m_UseFullRange);
1070	InitEdge(e: &edges[0], eNext: &edges[1], ePrev: &edges[highI], Pt: pg[0]);
1071	InitEdge(e: &edges[highI], eNext: &edges[0], ePrev: &edges[highI-1], Pt: pg[highI]);
1072	for (int i = highI - 1; i >= 1; --i)
1073	{
1074	RangeTest(Pt: pg[i], useFullRange&: m_UseFullRange);
1075	InitEdge(e: &edges[i], eNext: &edges[i+1], ePrev: &edges[i-1], Pt: 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: E);
1095	eLoopStop = E;
1096	continue;
1097	}
1098	if (E->Prev == E->Next)
1099	break; //only two vertices
1100	else if (Closed &&
1101	SlopesEqual(pt1: E->Prev->Curr, pt2: E->Curr, pt3: E->Next->Curr, UseFullInt64Range: m_UseFullRange) &&
1102	(!m_PreserveCollinear ||
1103	!Pt2IsBetweenPt1AndPt3(pt1: E->Prev->Curr, pt2: E->Curr, pt3: 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: 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&: *E, Pt: 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&: *E);
1162	if (E->Next->OutIdx == Skip) break;
1163	E->NextInLML = E->Next;
1164	E = E->Next;
1165	}
1166	m_MinimaList.push_back(x: locMin);
1167	m_edges.push_back(x: edges);
1168	return true;
1169	}
1170
1171	m_edges.push_back(x: 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(E: locMin.LeftBound, NextIsForward: leftBoundIsForward);
1208	if (E->OutIdx == Skip) E = ProcessBound(E, NextIsForward: leftBoundIsForward);
1209
1210	TEdge* E2 = ProcessBound(E: locMin.RightBound, NextIsForward: !leftBoundIsForward);
1211	if (E2->OutIdx == Skip) E2 = ProcessBound(E: E2, NextIsForward: !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(x: locMin);
1218	if (!leftBoundIsForward) E = E2;
1219	}
1220	return true;
1221	}
1222	//------------------------------------------------------------------------------
1223
1224	bool ClipperBase::AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed)
1225	{
1226	bool result = false;
1227	for (Paths::size_type i = 0; i < ppg.size(); ++i)
1228	if (AddPath(pg: ppg[i], PolyTyp, Closed)) result = true;
1229	return result;
1230	}
1231	//------------------------------------------------------------------------------
1232
1233	void ClipperBase::Clear()
1234	{
1235	DisposeLocalMinimaList();
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
1247	void ClipperBase::Reset()
1248	{
1249	m_CurrentLM = m_MinimaList.begin();
1250	if (m_CurrentLM == m_MinimaList.end()) return; //ie nothing to process
1251	std::sort(first: m_MinimaList.begin(), last: m_MinimaList.end(), comp: 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(Y: 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
1279	void ClipperBase::DisposeLocalMinimaList()
1280	{
1281	m_MinimaList.clear();
1282	m_CurrentLM = m_MinimaList.begin();
1283	}
1284	//------------------------------------------------------------------------------
1285
1286	bool ClipperBase::PopLocalMinima(cInt Y, const LocalMinimum *&locMin)
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
1295	IntRect ClipperBase::GetBounds()
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(a: result.bottom, b: 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(a: result.left, b: e->Bot.X);
1322	result.right = std::max(a: result.right, b: e->Bot.X);
1323	result.left = std::min(a: result.left, b: e->Top.X);
1324	result.right = std::max(a: result.right, b: e->Top.X);
1325	result.top = std::min(a: result.top, b: e->Top.Y);
1326	if (bottomE == lm->LeftBound) e = lm->RightBound;
1327	else break;
1328	}
1329	++lm;
1330	}
1331	return result;
1332	}
1333	//------------------------------------------------------------------------------
1334
1335	void ClipperBase::InsertScanbeam(const cInt Y)
1336	{
1337	m_Scanbeam.push(x: Y);
1338	}
1339	//------------------------------------------------------------------------------
1340
1341	bool ClipperBase::PopScanbeam(cInt &Y)
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
1351	void ClipperBase::DisposeAllOutRecs(){
1352	for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
1353	DisposeOutRec(index: i);
1354	m_PolyOuts.clear();
1355	}
1356	//------------------------------------------------------------------------------
1357
1358	void ClipperBase::DisposeOutRec(PolyOutList::size_type index)
1359	{
1360	OutRec *outRec = m_PolyOuts[index];
1361	if (outRec->Pts) DisposeOutPts(pp&: outRec->Pts);
1362	delete outRec;
1363	m_PolyOuts[index] = 0;
1364	}
1365	//------------------------------------------------------------------------------
1366
1367	void ClipperBase::DeleteFromAEL(TEdge *e)
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
1380	OutRec* ClipperBase::CreateOutRec()
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(x: result);
1390	result->Idx = (int)m_PolyOuts.size() - 1;
1391	return result;
1392	}
1393	//------------------------------------------------------------------------------
1394
1395	void ClipperBase::SwapPositionsInAEL(TEdge *Edge1, TEdge *Edge2)
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
1442	void ClipperBase::UpdateEdgeIntoAEL(TEdge *&e)
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&: *e)) InsertScanbeam(Y: e->Top.Y);
1462	}
1463	//------------------------------------------------------------------------------
1464
1465	bool ClipperBase::LocalMinimaPending()
1466	{
1467	return (m_CurrentLM != m_MinimaList.end());
1468	}
1469
1470	//------------------------------------------------------------------------------
1471	// TClipper methods ...
1472	//------------------------------------------------------------------------------
1473
1474	Clipper::Clipper(int initOptions) : ClipperBase() //constructor
1475	{
1476	m_ExecuteLocked = false;
1477	m_UseFullRange = false;
1478	m_ReverseOutput = ((initOptions & ioReverseSolution) != 0);
1479	m_StrictSimple = ((initOptions & ioStrictlySimple) != 0);
1480	m_PreserveCollinear = ((initOptions & ioPreserveCollinear) != 0);
1481	m_HasOpenPaths = false;
1482	#ifdef use_xyz
1483	m_ZFill = 0;
1484	#endif
1485	}
1486	//------------------------------------------------------------------------------
1487
1488	#ifdef use_xyz
1489	void Clipper::ZFillFunction(ZFillCallback zFillFunc)
1490	{
1491	m_ZFill = zFillFunc;
1492	}
1493	//------------------------------------------------------------------------------
1494	#endif
1495
1496	bool Clipper::Execute(ClipType clipType, Paths &solution, PolyFillType fillType)
1497	{
1498	return Execute(clipType, solution, subjFillType: fillType, clipFillType: fillType);
1499	}
1500	//------------------------------------------------------------------------------
1501
1502	bool Clipper::Execute(ClipType clipType, PolyTree &polytree, PolyFillType fillType)
1503	{
1504	return Execute(clipType, polytree, subjFillType: fillType, clipFillType: fillType);
1505	}
1506	//------------------------------------------------------------------------------
1507
1508	bool Clipper::Execute(ClipType clipType, Paths &solution,
1509	PolyFillType subjFillType, PolyFillType clipFillType)
1510	{
1511	if( m_ExecuteLocked ) return false;
1512	if (m_HasOpenPaths)
1513	throw clipperException("Error: PolyTree struct is needed for open path clipping.");
1514	m_ExecuteLocked = true;
1515	solution.resize(new_size: 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(polys&: solution);
1522	DisposeAllOutRecs();
1523	m_ExecuteLocked = false;
1524	return succeeded;
1525	}
1526	//------------------------------------------------------------------------------
1527
1528	bool Clipper::Execute(ClipType clipType, PolyTree& polytree,
1529	PolyFillType subjFillType, PolyFillType clipFillType)
1530	{
1531	if( m_ExecuteLocked ) return false;
1532	m_ExecuteLocked = true;
1533	m_SubjFillType = subjFillType;
1534	m_ClipFillType = clipFillType;
1535	m_ClipType = clipType;
1536	m_UsingPolyTree = true;
1537	bool succeeded = ExecuteInternal();
1538	if (succeeded) BuildResult2(polytree);
1539	DisposeAllOutRecs();
1540	m_ExecuteLocked = false;
1541	return succeeded;
1542	}
1543	//------------------------------------------------------------------------------
1544
1545	void Clipper::FixHoleLinkage(OutRec &outrec)
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
1560	bool Clipper::ExecuteInternal()
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(Y&: botY)) return false;
1571	InsertLocalMinimaIntoAEL(botY);
1572	while (PopScanbeam(Y&: topY) || LocalMinimaPending())
1573	{
1574	ProcessHorizontals();
1575	ClearGhostJoins();
1576	if (!ProcessIntersections(topY))
1577	{
1578	succeeded = false;
1579	break;
1580	}
1581	ProcessEdgesAtTopOfScanbeam(topY);
1582	botY = topY;
1583	InsertLocalMinimaIntoAEL(botY);
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: *outRec) > 0))
1599	ReversePolyPtLinks(pp: 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&: *outRec);
1611	else
1612	FixupOutPolygon(outrec&: *outRec);
1613	}
1614
1615	if (m_StrictSimple) DoSimplePolygons();
1616	}
1617
1618	ClearJoins();
1619	ClearGhostJoins();
1620	return succeeded;
1621	}
1622	//------------------------------------------------------------------------------
1623
1624	void Clipper::SetWindingCount(TEdge &edge)
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	{
1633	PolyFillType pft = (edge.PolyTyp == ptSubject ? m_SubjFillType : m_ClipFillType);
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(val: e->WindCnt) > 1)
1678	{
1679	//outside prev poly but still inside another.
1680	//when reversing direction of prev poly use the same WC
1681	if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
1682	//otherwise continue to 'decrease' WC ...
1683	else edge.WindCnt = e->WindCnt + edge.WindDelta;
1684	}
1685	else
1686	//now outside all polys of same polytype so set own WC ...
1687	edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
1688	} else
1689	{
1690	//prev edge is 'increasing' WindCount (WC) away from zero
1691	//so we're inside the previous polygon ...
1692	if (edge.WindDelta == 0)
1693	edge.WindCnt = (e->WindCnt < 0 ? e->WindCnt - 1 : e->WindCnt + 1);
1694	//if wind direction is reversing prev then use same WC
1695	else if (e->WindDelta * edge.WindDelta < 0) edge.WindCnt = e->WindCnt;
1696	//otherwise add to WC ...
1697	else edge.WindCnt = e->WindCnt + edge.WindDelta;
1698	}
1699	edge.WindCnt2 = e->WindCnt2;
1700	e = e->NextInAEL; //ie get ready to calc WindCnt2
1701	}
1702
1703	//update WindCnt2 ...
1704	if (IsEvenOddAltFillType(edge))
1705	{
1706	//EvenOdd filling ...
1707	while (e != &edge)
1708	{
1709	if (e->WindDelta != 0)
1710	edge.WindCnt2 = (edge.WindCnt2 == 0 ? 1 : 0);
1711	e = e->NextInAEL;
1712	}
1713	} else
1714	{
1715	//nonZero, Positive or Negative filling ...
1716	while ( e != &edge )
1717	{
1718	edge.WindCnt2 += e->WindDelta;
1719	e = e->NextInAEL;
1720	}
1721	}
1722	}
1723	//------------------------------------------------------------------------------
1724
1725	bool Clipper::IsEvenOddFillType(const TEdge& edge) const
1726	{
1727	if (edge.PolyTyp == ptSubject)
1728	return m_SubjFillType == pftEvenOdd; else
1729	return m_ClipFillType == pftEvenOdd;
1730	}
1731	//------------------------------------------------------------------------------
1732
1733	bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const
1734	{
1735	if (edge.PolyTyp == ptSubject)
1736	return m_ClipFillType == pftEvenOdd; else
1737	return m_SubjFillType == pftEvenOdd;
1738	}
1739	//------------------------------------------------------------------------------
1740
1741	bool Clipper::IsContributing(const TEdge& edge) const
1742	{
1743	PolyFillType pft, pft2;
1744	if (edge.PolyTyp == ptSubject)
1745	{
1746	pft = m_SubjFillType;
1747	pft2 = m_ClipFillType;
1748	} else
1749	{
1750	pft = m_ClipFillType;
1751	pft2 = m_SubjFillType;
1752	}
1753
1754	switch(pft)
1755	{
1756	case pftEvenOdd:
1757	//return false if a subj line has been flagged as inside a subj polygon
1758	if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;
1759	break;
1760	case pftNonZero:
1761	if (Abs(val: 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
1841	OutPt* Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
1842	{
1843	OutPt* result;
1844	TEdge *e, *prevE;
1845	if (IsHorizontal(e&: *e2) || ( e1->Dx > e2->Dx ))
1846	{
1847	result = AddOutPt(e: e1, pt: 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(e: e2, pt: 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(edge&: *prevE, currentY: Pt.Y);
1872	cInt xE = TopX(edge&: *e, currentY: Pt.Y);
1873	if (xPrev == xE && (e->WindDelta != 0) && (prevE->WindDelta != 0) &&
1874	SlopesEqual(pt1: IntPoint(xPrev, Pt.Y), pt2: prevE->Top, pt3: IntPoint(xE, Pt.Y), pt4: e->Top, UseFullInt64Range: m_UseFullRange))
1875	{
1876	OutPt* outPt = AddOutPt(e: prevE, pt: Pt);
1877	AddJoin(op1: result, op2: outPt, offPt: e->Top);
1878	}
1879	}
1880	return result;
1881	}
1882	//------------------------------------------------------------------------------
1883
1884	void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)
1885	{
1886	AddOutPt( e: e1, pt: Pt );
1887	if (e2->WindDelta == 0) AddOutPt(e: e2, pt: 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(e1: e2, e2: e1);
1897	}
1898	//------------------------------------------------------------------------------
1899
1900	void Clipper::AddEdgeToSEL(TEdge *edge)
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
1920	bool Clipper::PopEdgeFromSEL(TEdge *&edge)
1921	{
1922	if (!m_SortedEdges) return false;
1923	edge = m_SortedEdges;
1924	DeleteFromSEL(e: m_SortedEdges);
1925	return true;
1926	}
1927	//------------------------------------------------------------------------------
1928
1929	void Clipper::CopyAELToSEL()
1930	{
1931	TEdge* e = m_ActiveEdges;
1932	m_SortedEdges = e;
1933	while ( e )
1934	{
1935	e->PrevInSEL = e->PrevInAEL;
1936	e->NextInSEL = e->NextInAEL;
1937	e = e->NextInAEL;
1938	}
1939	}
1940	//------------------------------------------------------------------------------
1941
1942	void Clipper::AddJoin(OutPt *op1, OutPt *op2, const IntPoint OffPt)
1943	{
1944	Join* j = new Join;
1945	j->OutPt1 = op1;
1946	j->OutPt2 = op2;
1947	j->OffPt = OffPt;
1948	m_Joins.push_back(x: j);
1949	}
1950	//------------------------------------------------------------------------------
1951
1952	void Clipper::ClearJoins()
1953	{
1954	for (JoinList::size_type i = 0; i < m_Joins.size(); i++)
1955	delete m_Joins[i];
1956	m_Joins.resize(new_size: 0);
1957	}
1958	//------------------------------------------------------------------------------
1959
1960	void Clipper::ClearGhostJoins()
1961	{
1962	for (JoinList::size_type i = 0; i < m_GhostJoins.size(); i++)
1963	delete m_GhostJoins[i];
1964	m_GhostJoins.resize(new_size: 0);
1965	}
1966	//------------------------------------------------------------------------------
1967
1968	void Clipper::AddGhostJoin(OutPt *op, const IntPoint OffPt)
1969	{
1970	Join* j = new Join;
1971	j->OutPt1 = op;
1972	j->OutPt2 = 0;
1973	j->OffPt = OffPt;
1974	m_GhostJoins.push_back(x: j);
1975	}
1976	//------------------------------------------------------------------------------
1977
1978	void Clipper::InsertLocalMinimaIntoAEL(const cInt botY)
1979	{
1980	const LocalMinimum *lm;
1981	while (PopLocalMinima(Y: botY, locMin&: 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(edge: rb, startEdge: 0);
1991	SetWindingCount(*rb);
1992	if (IsContributing(edge: *rb))
1993	Op1 = AddOutPt(e: rb, pt: rb->Bot);
1994	}
1995	else if (!rb)
1996	{
1997	InsertEdgeIntoAEL(edge: lb, startEdge: 0);
1998	SetWindingCount(*lb);
1999	if (IsContributing(edge: *lb))
2000	Op1 = AddOutPt(e: lb, pt: lb->Bot);
2001	InsertScanbeam(Y: lb->Top.Y);
2002	}
2003	else
2004	{
2005	InsertEdgeIntoAEL(edge: lb, startEdge: 0);
2006	InsertEdgeIntoAEL(edge: rb, startEdge: lb);
2007	SetWindingCount( *lb );
2008	rb->WindCnt = lb->WindCnt;
2009	rb->WindCnt2 = lb->WindCnt2;
2010	if (IsContributing(edge: *lb))
2011	Op1 = AddLocalMinPoly(e1: lb, e2: rb, Pt: lb->Bot);
2012	InsertScanbeam(Y: lb->Top.Y);
2013	}
2014
2015	if (rb)
2016	{
2017	if (IsHorizontal(e&: *rb))
2018	{
2019	AddEdgeToSEL(edge: rb);
2020	if (rb->NextInLML)
2021	InsertScanbeam(Y: rb->NextInLML->Top.Y);
2022	}
2023	else InsertScanbeam( Y: 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(e&: *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(seg1a: jr->OutPt1->Pt.X, seg1b: jr->OffPt.X, seg2a: rb->Bot.X, seg2b: rb->Top.X))
2038	AddJoin(op1: jr->OutPt1, op2: Op1, OffPt: 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(pt1: lb->PrevInAEL->Bot, pt2: lb->PrevInAEL->Top, pt3: lb->Curr, pt4: lb->Top, UseFullInt64Range: m_UseFullRange) &&
2046	(lb->WindDelta != 0) && (lb->PrevInAEL->WindDelta != 0))
2047	{
2048	OutPt *Op2 = AddOutPt(e: lb->PrevInAEL, pt: lb->Bot);
2049	AddJoin(op1: Op1, op2: Op2, OffPt: lb->Top);
2050	}
2051
2052	if(lb->NextInAEL != rb)
2053	{
2054
2055	if (rb->OutIdx >= 0 && rb->PrevInAEL->OutIdx >= 0 &&
2056	SlopesEqual(pt1: rb->PrevInAEL->Curr, pt2: rb->PrevInAEL->Top, pt3: rb->Curr, pt4: rb->Top, UseFullInt64Range: m_UseFullRange) &&
2057	(rb->WindDelta != 0) && (rb->PrevInAEL->WindDelta != 0))
2058	{
2059	OutPt *Op2 = AddOutPt(e: rb->PrevInAEL, pt: rb->Bot);
2060	AddJoin(op1: Op1, op2: Op2, OffPt: 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(e1: rb , e2: e , pt&: lb->Curr); //order important here
2071	e = e->NextInAEL;
2072	}
2073	}
2074	}
2075
2076	}
2077	}
2078	//------------------------------------------------------------------------------
2079
2080	void Clipper::DeleteFromSEL(TEdge *e)
2081	{
2082	TEdge* SelPrev = e->PrevInSEL;
2083	TEdge* SelNext = e->NextInSEL;
2084	if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted
2085	if( SelPrev ) SelPrev->NextInSEL = SelNext;
2086	else m_SortedEdges = SelNext;
2087	if( SelNext ) SelNext->PrevInSEL = SelPrev;
2088	e->NextInSEL = 0;
2089	e->PrevInSEL = 0;
2090	}
2091	//------------------------------------------------------------------------------
2092
2093	#ifdef use_xyz
2094	void Clipper::SetZ(IntPoint& pt, TEdge& e1, TEdge& e2)
2095	{
2096	if (pt.Z != 0 || !m_ZFill) return;
2097	else if (pt == e1.Bot) pt.Z = e1.Bot.Z;
2098	else if (pt == e1.Top) pt.Z = e1.Top.Z;
2099	else if (pt == e2.Bot) pt.Z = e2.Bot.Z;
2100	else if (pt == e2.Top) pt.Z = e2.Top.Z;
2101	else (*m_ZFill)(e1.Bot, e1.Top, e2.Bot, e2.Top, pt);
2102	}
2103	//------------------------------------------------------------------------------
2104	#endif
2105
2106	void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
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(e: e1, pt: Pt);
2132	if (e1Contributing) e1->OutIdx = Unassigned;
2133	}
2134	}
2135	else
2136	{
2137	if (e1Contributing)
2138	{
2139	AddOutPt(e: e2, pt: 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(x: e2->WindCnt) == 1 &&
2148	(m_ClipType != ctUnion || e2->WindCnt2 == 0))
2149	{
2150	AddOutPt(e: e1, pt: Pt);
2151	if (e1Contributing) e1->OutIdx = Unassigned;
2152	}
2153	else if ((e2->WindDelta == 0) && (abs(x: e1->WindCnt) == 1) &&
2154	(m_ClipType != ctUnion || e1->WindCnt2 == 0))
2155	{
2156	AddOutPt(e: e2, pt: 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( edge: *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(edge: *e2)) e1->WindCnt2 += e2->WindDelta;
2183	else e1->WindCnt2 = ( e1->WindCnt2 == 0 ) ? 1 : 0;
2184	if (!IsEvenOddFillType(edge: *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(val: 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(val: 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(e: e1, pt: Pt);
2232	AddOutPt(e: e2, pt: Pt);
2233	SwapSides( Edge1&: *e1 , Edge2&: *e2 );
2234	SwapPolyIndexes( Edge1&: *e1 , Edge2&: *e2 );
2235	}
2236	}
2237	else if ( e1Contributing )
2238	{
2239	if (e2Wc == 0 || e2Wc == 1)
2240	{
2241	AddOutPt(e: e1, pt: Pt);
2242	SwapSides(Edge1&: *e1, Edge2&: *e2);
2243	SwapPolyIndexes(Edge1&: *e1, Edge2&: *e2);
2244	}
2245	}
2246	else if ( e2Contributing )
2247	{
2248	if (e1Wc == 0 || e1Wc == 1)
2249	{
2250	AddOutPt(e: e2, pt: Pt);
2251	SwapSides(Edge1&: *e1, Edge2&: *e2);
2252	SwapPolyIndexes(Edge1&: *e1, Edge2&: *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(val: 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(val: 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( Edge1&: *e1, Edge2&: *e2 );
2297	}
2298	}
2299	//------------------------------------------------------------------------------
2300
2301	void Clipper::SetHoleState(TEdge *e, OutRec *outrec)
2302	{
2303	TEdge *e2 = e->PrevInAEL;
2304	TEdge *eTmp = 0;
2305	while (e2)
2306	{
2307	if (e2->OutIdx >= 0 && e2->WindDelta != 0)
2308	{
2309	if (!eTmp) eTmp = e2;
2310	else if (eTmp->OutIdx == e2->OutIdx) eTmp = 0;
2311	}
2312	e2 = e2->PrevInAEL;
2313	}
2314	if (!eTmp)
2315	{
2316	outrec->FirstLeft = 0;
2317	outrec->IsHole = false;
2318	}
2319	else
2320	{
2321	outrec->FirstLeft = m_PolyOuts[eTmp->OutIdx];
2322	outrec->IsHole = !outrec->FirstLeft->IsHole;
2323	}
2324	}
2325	//------------------------------------------------------------------------------
2326
2327	OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2)
2328	{
2329	//work out which polygon fragment has the correct hole state ...
2330	if (!outRec1->BottomPt)
2331	outRec1->BottomPt = GetBottomPt(pp: outRec1->Pts);
2332	if (!outRec2->BottomPt)
2333	outRec2->BottomPt = GetBottomPt(pp: 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(btmPt1: OutPt1, btmPt2: OutPt2)) return outRec1;
2343	else return outRec2;
2344	}
2345	//------------------------------------------------------------------------------
2346
2347	bool OutRec1RightOfOutRec2(OutRec* outRec1, OutRec* outRec2)
2348	{
2349	do
2350	{
2351	outRec1 = outRec1->FirstLeft;
2352	if (outRec1 == outRec2) return true;
2353	} while (outRec1);
2354	return false;
2355	}
2356	//------------------------------------------------------------------------------
2357
2358	OutRec* Clipper::GetOutRec(int Idx)
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
2367	void Clipper::AppendPolygon(TEdge *e1, TEdge *e2)
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(outRec1: outRec2, 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(pp: 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(pp: 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
2463	OutPt* Clipper::AddOutPt(TEdge *e, const IntPoint &pt)
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: 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
2502	OutPt* Clipper::GetLastOutPt(TEdge *e)
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
2512	void Clipper::ProcessHorizontals()
2513	{
2514	TEdge* horzEdge;
2515	while (PopEdgeFromSEL(edge&: horzEdge))
2516	ProcessHorizontal(horzEdge);
2517	}
2518	//------------------------------------------------------------------------------
2519
2520	inline bool IsMinima(TEdge *e)
2521	{
2522	return e && (e->Prev->NextInLML != e) && (e->Next->NextInLML != e);
2523	}
2524	//------------------------------------------------------------------------------
2525
2526	inline bool IsMaxima(TEdge *e, const cInt Y)
2527	{
2528	return e && e->Top.Y == Y && !e->NextInLML;
2529	}
2530	//------------------------------------------------------------------------------
2531
2532	inline bool IsIntermediate(TEdge *e, const cInt Y)
2533	{
2534	return e->Top.Y == Y && e->NextInLML;
2535	}
2536	//------------------------------------------------------------------------------
2537
2538	TEdge *GetMaximaPair(TEdge *e)
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
2548	TEdge *GetMaximaPairEx(TEdge *e)
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(e&: *result)))) return 0;
2554	return result;
2555	}
2556	//------------------------------------------------------------------------------
2557
2558	void Clipper::SwapPositionsInSEL(TEdge *Edge1, TEdge *Edge2)
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
2604	TEdge* GetNextInAEL(TEdge *e, Direction dir)
2605	{
2606	return dir == dLeftToRight ? e->NextInAEL : e->PrevInAEL;
2607	}
2608	//------------------------------------------------------------------------------
2609
2610	void GetHorzDirection(TEdge& HorzEdge, Direction& Dir, cInt& Left, cInt& Right)
2611	{
2612	if (HorzEdge.Bot.X < HorzEdge.Top.X)
2613	{
2614	Left = HorzEdge.Bot.X;
2615	Right = HorzEdge.Top.X;
2616	Dir = dLeftToRight;
2617	} else
2618	{
2619	Left = HorzEdge.Top.X;
2620	Right = HorzEdge.Bot.X;
2621	Dir = dRightToLeft;
2622	}
2623	}
2624	//------------------------------------------------------------------------
2625
2626	/*******************************************************************************
2627	* Notes: Horizontal edges (HEs) at scanline intersections (ie at the Top or *
2628	* Bottom of a scanbeam) are processed as if layered. The order in which HEs *
2629	* are processed doesn't matter. HEs intersect with other HE Bot.Xs only [#] *
2630	* (or they could intersect with Top.Xs only, ie EITHER Bot.Xs OR Top.Xs), *
2631	* and with other non-horizontal edges [*]. Once these intersections are *
2632	* processed, intermediate HEs then 'promote' the Edge above (NextInLML) into *
2633	* the AEL. These 'promoted' edges may in turn intersect [%] with other HEs. *
2634	*******************************************************************************/
2635
2636	void Clipper::ProcessHorizontal(TEdge *horzEdge)
2637	{
2638	Direction dir;
2639	cInt horzLeft, horzRight;
2640	bool IsOpen = (horzEdge->WindDelta == 0);
2641
2642	GetHorzDirection(HorzEdge&: *horzEdge, Dir&: dir, Left&: horzLeft, Right&: horzRight);
2643
2644	TEdge* eLastHorz = horzEdge, *eMaxPair = 0;
2645	while (eLastHorz->NextInLML && IsHorizontal(e&: *eLastHorz->NextInLML))
2646	eLastHorz = eLastHorz->NextInLML;
2647	if (!eLastHorz->NextInLML)
2648	eMaxPair = GetMaximaPair(e: 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(e: 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(e: horzEdge, pt: 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(e: horzEdge, pt: 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(e: horzEdge, pt: e->Curr);
2717	TEdge* eNextHorz = m_SortedEdges;
2718	while (eNextHorz)
2719	{
2720	if (eNextHorz->OutIdx >= 0 &&
2721	HorzSegmentsOverlap(seg1a: horzEdge->Bot.X,
2722	seg1b: horzEdge->Top.X, seg2a: eNextHorz->Bot.X, seg2b: eNextHorz->Top.X))
2723	{
2724	OutPt* op2 = GetLastOutPt(e: eNextHorz);
2725	AddJoin(op1: op2, op2: op1, OffPt: eNextHorz->Top);
2726	}
2727	eNextHorz = eNextHorz->NextInSEL;
2728	}
2729	AddGhostJoin(op: op1, OffPt: 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(e1: horzEdge, e2: eMaxPair, Pt: horzEdge->Top);
2738	DeleteFromAEL(e: horzEdge);
2739	DeleteFromAEL(e: eMaxPair);
2740	return;
2741	}
2742
2743	if(dir == dLeftToRight)
2744	{
2745	IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
2746	IntersectEdges(e1: horzEdge, e2: e, Pt);
2747	}
2748	else
2749	{
2750	IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);
2751	IntersectEdges( e1: e, e2: horzEdge, Pt);
2752	}
2753	TEdge* eNext = GetNextInAEL(e, dir);
2754	SwapPositionsInAEL( Edge1: horzEdge, Edge2: 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(e&: *horzEdge->NextInLML)) break;
2760
2761	UpdateEdgeIntoAEL(e&: horzEdge);
2762	if (horzEdge->OutIdx >= 0) AddOutPt(e: horzEdge, pt: horzEdge->Bot);
2763	GetHorzDirection(HorzEdge&: *horzEdge, Dir&: dir, Left&: horzLeft, Right&: horzRight);
2764
2765	} //end for (;;)
2766
2767	if (horzEdge->OutIdx >= 0 && !op1)
2768	{
2769	op1 = GetLastOutPt(e: horzEdge);
2770	TEdge* eNextHorz = m_SortedEdges;
2771	while (eNextHorz)
2772	{
2773	if (eNextHorz->OutIdx >= 0 &&
2774	HorzSegmentsOverlap(seg1a: horzEdge->Bot.X,
2775	seg1b: horzEdge->Top.X, seg2a: eNextHorz->Bot.X, seg2b: eNextHorz->Top.X))
2776	{
2777	OutPt* op2 = GetLastOutPt(e: eNextHorz);
2778	AddJoin(op1: op2, op2: op1, OffPt: eNextHorz->Top);
2779	}
2780	eNextHorz = eNextHorz->NextInSEL;
2781	}
2782	AddGhostJoin(op: op1, OffPt: horzEdge->Top);
2783	}
2784
2785	if (horzEdge->NextInLML)
2786	{
2787	if(horzEdge->OutIdx >= 0)
2788	{
2789	op1 = AddOutPt( e: horzEdge, pt: horzEdge->Top);
2790	UpdateEdgeIntoAEL(e&: 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(e1: *horzEdge, e2: *ePrev, UseFullInt64Range: m_UseFullRange)))
2799	{
2800	OutPt* op2 = AddOutPt(e: ePrev, pt: horzEdge->Bot);
2801	AddJoin(op1, op2, OffPt: 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(e1: *horzEdge, e2: *eNext, UseFullInt64Range: m_UseFullRange))
2807	{
2808	OutPt* op2 = AddOutPt(e: eNext, pt: horzEdge->Bot);
2809	AddJoin(op1, op2, OffPt: horzEdge->Top);
2810	}
2811	}
2812	else
2813	UpdateEdgeIntoAEL(e&: horzEdge);
2814	}
2815	else
2816	{
2817	if (horzEdge->OutIdx >= 0) AddOutPt(e: horzEdge, pt: horzEdge->Top);
2818	DeleteFromAEL(e: horzEdge);
2819	}
2820	}
2821	//------------------------------------------------------------------------------
2822
2823	bool Clipper::ProcessIntersections(const cInt topY)
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;
2836	DisposeIntersectNodes();
2837	throw clipperException("ProcessIntersections error");
2838	}
2839	m_SortedEdges = 0;
2840	return true;
2841	}
2842	//------------------------------------------------------------------------------
2843
2844	void Clipper::DisposeIntersectNodes()
2845	{
2846	for (size_t i = 0; i < m_IntersectList.size(); ++i )
2847	delete m_IntersectList[i];
2848	m_IntersectList.clear();
2849	}
2850	//------------------------------------------------------------------------------
2851
2852	void Clipper::BuildIntersectList(const cInt topY)
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( edge&: *e, currentY: 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(Edge1&: *e, Edge2&: *eNext, ip&: Pt);
2880	if (Pt.Y < topY) Pt = IntPoint(TopX(edge&: *e, currentY: topY), topY);
2881	IntersectNode * newNode = new IntersectNode;
2882	newNode->Edge1 = e;
2883	newNode->Edge2 = eNext;
2884	newNode->Pt = Pt;
2885	m_IntersectList.push_back(x: newNode);
2886
2887	SwapPositionsInSEL(Edge1: e, Edge2: 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
2902	void Clipper::ProcessIntersectList()
2903	{
2904	for (size_t i = 0; i < m_IntersectList.size(); ++i)
2905	{
2906	IntersectNode* iNode = m_IntersectList[i];
2907	{
2908	IntersectEdges( e1: iNode->Edge1, e2: iNode->Edge2, Pt&: iNode->Pt);
2909	SwapPositionsInAEL( Edge1: iNode->Edge1 , Edge2: iNode->Edge2 );
2910	}
2911	delete iNode;
2912	}
2913	m_IntersectList.clear();
2914	}
2915	//------------------------------------------------------------------------------
2916
2917	bool IntersectListSort(IntersectNode* node1, IntersectNode* node2)
2918	{
2919	return node2->Pt.Y < node1->Pt.Y;
2920	}
2921	//------------------------------------------------------------------------------
2922
2923	inline bool EdgesAdjacent(const IntersectNode &inode)
2924	{
2925	return (inode.Edge1->NextInSEL == inode.Edge2) ||
2926	(inode.Edge1->PrevInSEL == inode.Edge2);
2927	}
2928	//------------------------------------------------------------------------------
2929
2930	bool Clipper::FixupIntersectionOrder()
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(first: m_IntersectList.begin(), last: m_IntersectList.end(), comp: IntersectListSort);
2937	size_t cnt = m_IntersectList.size();
2938	for (size_t i = 0; i < cnt; ++i)
2939	{
2940	if (!EdgesAdjacent(inode: *m_IntersectList[i]))
2941	{
2942	size_t j = i + 1;
2943	while (j < cnt && !EdgesAdjacent(inode: *m_IntersectList[j])) j++;
2944	if (j == cnt) return false;
2945	std::swap(a&: m_IntersectList[i], b&: m_IntersectList[j]);
2946	}
2947	SwapPositionsInSEL(Edge1: m_IntersectList[i]->Edge1, Edge2: m_IntersectList[i]->Edge2);
2948	}
2949	return true;
2950	}
2951	//------------------------------------------------------------------------------
2952
2953	void Clipper::DoMaxima(TEdge *e)
2954	{
2955	TEdge* eMaxPair = GetMaximaPairEx(e);
2956	if (!eMaxPair)
2957	{
2958	if (e->OutIdx >= 0)
2959	AddOutPt(e, pt: e->Top);
2960	DeleteFromAEL(e);
2961	return;
2962	}
2963
2964	TEdge* eNext = e->NextInAEL;
2965	while(eNext && eNext != eMaxPair)
2966	{
2967	IntersectEdges(e1: e, e2: eNext, Pt&: e->Top);
2968	SwapPositionsInAEL(Edge1: e, Edge2: eNext);
2969	eNext = e->NextInAEL;
2970	}
2971
2972	if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned)
2973	{
2974	DeleteFromAEL(e);
2975	DeleteFromAEL(e: eMaxPair);
2976	}
2977	else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 )
2978	{
2979	if (e->OutIdx >= 0) AddLocalMaxPoly(e1: e, e2: eMaxPair, Pt: e->Top);
2980	DeleteFromAEL(e);
2981	DeleteFromAEL(e: eMaxPair);
2982	}
2983	#ifdef use_lines
2984	else if (e->WindDelta == 0)
2985	{
2986	if (e->OutIdx >= 0)
2987	{
2988	AddOutPt(e, pt: e->Top);
2989	e->OutIdx = Unassigned;
2990	}
2991	DeleteFromAEL(e);
2992
2993	if (eMaxPair->OutIdx >= 0)
2994	{
2995	AddOutPt(e: eMaxPair, pt: e->Top);
2996	eMaxPair->OutIdx = Unassigned;
2997	}
2998	DeleteFromAEL(e: eMaxPair);
2999	}
3000	#endif
3001	else throw clipperException("DoMaxima error");
3002	}
3003	//------------------------------------------------------------------------------
3004
3005	void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)
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, Y: topY);
3013
3014	if(IsMaximaEdge)
3015	{
3016	TEdge* eMaxPair = GetMaximaPairEx(e);
3017	IsMaximaEdge = (!eMaxPair || !IsHorizontal(e&: *eMaxPair));
3018	}
3019
3020	if(IsMaximaEdge)
3021	{
3022	if (m_StrictSimple) m_Maxima.push_back(x: 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, Y: topY) && IsHorizontal(e&: *e->NextInLML))
3032	{
3033	UpdateEdgeIntoAEL(e);
3034	if (e->OutIdx >= 0)
3035	AddOutPt(e, pt: e->Bot);
3036	AddEdgeToSEL(edge: e);
3037	}
3038	else
3039	{
3040	e->Curr.X = TopX( edge&: *e, currentY: 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(e: ePrev, pt);
3057	OutPt* op2 = AddOutPt(e, pt);
3058	AddJoin(op1: op, op2, OffPt: 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();
3068	ProcessHorizontals();
3069	m_Maxima.clear();
3070
3071	//4. Promote intermediate vertices ...
3072	e = m_ActiveEdges;
3073	while(e)
3074	{
3075	if(IsIntermediate(e, Y: topY))
3076	{
3077	OutPt* op = 0;
3078	if( e->OutIdx >= 0 )
3079	op = AddOutPt(e, pt: e->Top);
3080	UpdateEdgeIntoAEL(e);
3081
3082	//if output polygons share an edge, they'll need joining later ...
3083	TEdge* ePrev = e->PrevInAEL;
3084	TEdge* eNext = e->NextInAEL;
3085	if (ePrev && ePrev->Curr.X == e->Bot.X &&
3086	ePrev->Curr.Y == e->Bot.Y && op &&
3087	ePrev->OutIdx >= 0 && ePrev->Curr.Y > ePrev->Top.Y &&
3088	SlopesEqual(pt1: e->Curr, pt2: e->Top, pt3: ePrev->Curr, pt4: ePrev->Top, UseFullInt64Range: m_UseFullRange) &&
3089	(e->WindDelta != 0) && (ePrev->WindDelta != 0))
3090	{
3091	OutPt* op2 = AddOutPt(e: ePrev, pt: e->Bot);
3092	AddJoin(op1: op, op2, OffPt: 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(pt1: e->Curr, pt2: e->Top, pt3: eNext->Curr, pt4: eNext->Top, UseFullInt64Range: m_UseFullRange) &&
3098	(e->WindDelta != 0) && (eNext->WindDelta != 0))
3099	{
3100	OutPt* op2 = AddOutPt(e: eNext, pt: e->Bot);
3101	AddJoin(op1: op, op2, OffPt: e->Top);
3102	}
3103	}
3104	e = e->NextInAEL;
3105	}
3106	}
3107	//------------------------------------------------------------------------------
3108
3109	void Clipper::FixupOutPolyline(OutRec &outrec)
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
3136	void Clipper::FixupOutPolygon(OutRec &outrec)
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(pt1: pp->Prev->Pt, pt2: pp->Pt, pt3: pp->Next->Pt, UseFullInt64Range: m_UseFullRange) &&
3157	(!preserveCol || !Pt2IsBetweenPt1AndPt3(pt1: pp->Prev->Pt, pt2: pp->Pt, pt3: 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
3177	int PointCount(OutPt *Pts)
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
3192	void Clipper::BuildResult(Paths &polys)
3193	{
3194	polys.reserve(n: 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(Pts: p);
3201	if (cnt < 2) continue;
3202	pg.reserve(n: cnt);
3203	for (int i = 0; i < cnt; ++i)
3204	{
3205	pg.push_back(x: p->Pt);
3206	p = p->Prev;
3207	}
3208	polys.push_back(x: pg);
3209	}
3210	}
3211	//------------------------------------------------------------------------------
3212
3213	void Clipper::BuildResult2(PolyTree& polytree)
3214	{
3215	polytree.Clear();
3216	polytree.AllNodes.reserve(n: 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(Pts: outRec->Pts);
3222	if ((outRec->IsOpen && cnt < 2) || (!outRec->IsOpen && cnt < 3)) continue;
3223	FixHoleLinkage(outrec&: *outRec);
3224	PolyNode* pn = new PolyNode();
3225	//nb: polytree takes ownership of all the PolyNodes
3226	polytree.AllNodes.push_back(x: pn);
3227	outRec->PolyNd = pn;
3228	pn->Parent = 0;
3229	pn->Index = 0;
3230	pn->Contour.reserve(n: cnt);
3231	OutPt *op = outRec->Pts->Prev;
3232	for (int j = 0; j < cnt; j++)
3233	{
3234	pn->Contour.push_back(x: op->Pt);
3235	op = op->Prev;
3236	}
3237	}
3238
3239	//fixup PolyNode links etc ...
3240	polytree.Childs.reserve(n: 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(child&: *outRec->PolyNd);
3249	}
3250	else if (outRec->FirstLeft && outRec->FirstLeft->PolyNd)
3251	outRec->FirstLeft->PolyNd->AddChild(child&: *outRec->PolyNd);
3252	else
3253	polytree.AddChild(child&: *outRec->PolyNd);
3254	}
3255	}
3256	//------------------------------------------------------------------------------
3257
3258	void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)
3259	{
3260	//just swap the contents (because fIntersectNodes is a single-linked-list)
3261	IntersectNode inode = int1; //gets a copy of Int1
3262	int1.Edge1 = int2.Edge1;
3263	int1.Edge2 = int2.Edge2;
3264	int1.Pt = int2.Pt;
3265	int2.Edge1 = inode.Edge1;
3266	int2.Edge2 = inode.Edge2;
3267	int2.Pt = inode.Pt;
3268	}
3269	//------------------------------------------------------------------------------
3270
3271	inline bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)
3272	{
3273	if (e2.Curr.X == e1.Curr.X)
3274	{
3275	if (e2.Top.Y > e1.Top.Y)
3276	return e2.Top.X < TopX(edge&: e1, currentY: e2.Top.Y);
3277	else return e1.Top.X > TopX(edge&: e2, currentY: e1.Top.Y);
3278	}
3279	else return e2.Curr.X < e1.Curr.X;
3280	}
3281	//------------------------------------------------------------------------------
3282
3283	bool GetOverlap(const cInt a1, const cInt a2, const cInt b1, const cInt b2,
3284	cInt& Left, cInt& Right)
3285	{
3286	if (a1 < a2)
3287	{
3288	if (b1 < b2) {Left = std::max(a: a1,b: b1); Right = std::min(a: a2,b: b2);}
3289	else {Left = std::max(a: a1,b: b2); Right = std::min(a: a2,b: b1);}
3290	}
3291	else
3292	{
3293	if (b1 < b2) {Left = std::max(a: a2,b: b1); Right = std::min(a: a1,b: b2);}
3294	else {Left = std::max(a: a2,b: b2); Right = std::min(a: a1,b: b1);}
3295	}
3296	return Left < Right;
3297	}
3298	//------------------------------------------------------------------------------
3299
3300	inline void UpdateOutPtIdxs(OutRec& outrec)
3301	{
3302	OutPt* op = outrec.Pts;
3303	do
3304	{
3305	op->Idx = outrec.Idx;
3306	op = op->Prev;
3307	}
3308	while(op != outrec.Pts);
3309	}
3310	//------------------------------------------------------------------------------
3311
3312	void Clipper::InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge)
3313	{
3314	if(!m_ActiveEdges)
3315	{
3316	edge->PrevInAEL = 0;
3317	edge->NextInAEL = 0;
3318	m_ActiveEdges = edge;
3319	}
3320	else if(!startEdge && E2InsertsBeforeE1(e1&: *m_ActiveEdges, e2&: *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(e1&: *startEdge->NextInAEL , e2&: *edge))
3332	startEdge = startEdge->NextInAEL;
3333	edge->NextInAEL = startEdge->NextInAEL;
3334	if(startEdge->NextInAEL) startEdge->NextInAEL->PrevInAEL = edge;
3335	edge->PrevInAEL = startEdge;
3336	startEdge->NextInAEL = edge;
3337	}
3338	}
3339	//----------------------------------------------------------------------
3340
3341	OutPt* DupOutPt(OutPt* outPt, bool InsertAfter)
3342	{
3343	OutPt* result = new OutPt;
3344	result->Pt = outPt->Pt;
3345	result->Idx = outPt->Idx;
3346	if (InsertAfter)
3347	{
3348	result->Next = outPt->Next;
3349	result->Prev = outPt;
3350	outPt->Next->Prev = result;
3351	outPt->Next = result;
3352	}
3353	else
3354	{
3355	result->Prev = outPt->Prev;
3356	result->Next = outPt;
3357	outPt->Prev->Next = result;
3358	outPt->Prev = result;
3359	}
3360	return result;
3361	}
3362	//------------------------------------------------------------------------------
3363
3364	bool JoinHorz(OutPt* op1, OutPt* op1b, OutPt* op2, OutPt* op2b,
3365	const IntPoint Pt, bool DiscardLeft)
3366	{
3367	Direction Dir1 = (op1->Pt.X > op1b->Pt.X ? dRightToLeft : dLeftToRight);
3368	Direction Dir2 = (op2->Pt.X > op2b->Pt.X ? dRightToLeft : dLeftToRight);
3369	if (Dir1 == Dir2) return false;
3370
3371	//When DiscardLeft, we want Op1b to be on the Left of Op1, otherwise we
3372	//want Op1b to be on the Right. (And likewise with Op2 and Op2b.)
3373	//So, to facilitate this while inserting Op1b and Op2b ...
3374	//when DiscardLeft, make sure we're AT or RIGHT of Pt before adding Op1b,
3375	//otherwise make sure we're AT or LEFT of Pt. (Likewise with Op2b.)
3376	if (Dir1 == dLeftToRight)
3377	{
3378	while (op1->Next->Pt.X <= Pt.X &&
3379	op1->Next->Pt.X >= op1->Pt.X && op1->Next->Pt.Y == Pt.Y)
3380	op1 = op1->Next;
3381	if (DiscardLeft && (op1->Pt.X != Pt.X)) op1 = op1->Next;
3382	op1b = DupOutPt(outPt: op1, InsertAfter: !DiscardLeft);
3383	if (op1b->Pt != Pt)
3384	{
3385	op1 = op1b;
3386	op1->Pt = Pt;
3387	op1b = DupOutPt(outPt: op1, InsertAfter: !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(outPt: op1, InsertAfter: DiscardLeft);
3397	if (op1b->Pt != Pt)
3398	{
3399	op1 = op1b;
3400	op1->Pt = Pt;
3401	op1b = DupOutPt(outPt: op1, InsertAfter: 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(outPt: op2, InsertAfter: !DiscardLeft);
3412	if (op2b->Pt != Pt)
3413	{
3414	op2 = op2b;
3415	op2->Pt = Pt;
3416	op2b = DupOutPt(outPt: op2, InsertAfter: !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(outPt: op2, InsertAfter: DiscardLeft);
3425	if (op2b->Pt != Pt)
3426	{
3427	op2 = op2b;
3428	op2->Pt = Pt;
3429	op2b = DupOutPt(outPt: op2, InsertAfter: DiscardLeft);
3430	};
3431	};
3432
3433	if ((Dir1 == dLeftToRight) == DiscardLeft)
3434	{
3435	op1->Prev = op2;
3436	op2->Next = op1;
3437	op1b->Next = op2b;
3438	op2b->Prev = op1b;
3439	}
3440	else
3441	{
3442	op1->Next = op2;
3443	op2->Prev = op1;
3444	op1b->Prev = op2b;
3445	op2b->Next = op1b;
3446	}
3447	return true;
3448	}
3449	//------------------------------------------------------------------------------
3450
3451	bool Clipper::JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2)
3452	{
3453	OutPt *op1 = j->OutPt1, *op1b;
3454	OutPt *op2 = j->OutPt2, *op2b;
3455
3456	//There are 3 kinds of joins for output polygons ...
3457	//1. Horizontal joins where Join.OutPt1 & Join.OutPt2 are vertices anywhere
3458	//along (horizontal) collinear edges (& Join.OffPt is on the same horizontal).
3459	//2. Non-horizontal joins where Join.OutPt1 & Join.OutPt2 are at the same
3460	//location at the Bottom of the overlapping segment (& Join.OffPt is above).
3461	//3. StrictSimple joins where edges touch but are not collinear and where
3462	//Join.OutPt1, Join.OutPt2 & Join.OffPt all share the same point.
3463	bool isHorizontal = (j->OutPt1->Pt.Y == j->OffPt.Y);
3464
3465	if (isHorizontal && (j->OffPt == j->OutPt1->Pt) &&
3466	(j->OffPt == j->OutPt2->Pt))
3467	{
3468	//Strictly Simple join ...
3469	if (outRec1 != outRec2) return false;
3470	op1b = j->OutPt1->Next;
3471	while (op1b != op1 && (op1b->Pt == j->OffPt))
3472	op1b = op1b->Next;
3473	bool reverse1 = (op1b->Pt.Y > j->OffPt.Y);
3474	op2b = j->OutPt2->Next;
3475	while (op2b != op2 && (op2b->Pt == j->OffPt))
3476	op2b = op2b->Next;
3477	bool reverse2 = (op2b->Pt.Y > j->OffPt.Y);
3478	if (reverse1 == reverse2) return false;
3479	if (reverse1)
3480	{
3481	op1b = DupOutPt(outPt: op1, InsertAfter: false);
3482	op2b = DupOutPt(outPt: op2, InsertAfter: 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(outPt: op1, InsertAfter: true);
3493	op2b = DupOutPt(outPt: op2, InsertAfter: 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(a1: op1->Pt.X, a2: op1b->Pt.X, b1: op2->Pt.X, b2: 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, DiscardLeft: 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(pt1: op1->Pt, pt2: op1b->Pt, pt3: j->OffPt, UseFullInt64Range: 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(pt1: op1->Pt, pt2: op1b->Pt, pt3: j->OffPt, UseFullInt64Range: 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(pt1: op2->Pt, pt2: op2b->Pt, pt3: j->OffPt, UseFullInt64Range: 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(pt1: op2->Pt, pt2: op2b->Pt, pt3: j->OffPt, UseFullInt64Range: 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(outPt: op1, InsertAfter: false);
3586	op2b = DupOutPt(outPt: op2, InsertAfter: 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(outPt: op1, InsertAfter: true);
3597	op2b = DupOutPt(outPt: op2, InsertAfter: false);
3598	op1->Next = op2;
3599	op2->Prev = op1;
3600	op1b->Prev = op2b;
3601	op2b->Next = op1b;
3602	j->OutPt1 = op1;
3603	j->OutPt2 = op1b;
3604	return true;
3605	}
3606	}
3607	}
3608	//----------------------------------------------------------------------
3609
3610	static OutRec* ParseFirstLeft(OutRec* FirstLeft)
3611	{
3612	while (FirstLeft && !FirstLeft->Pts)
3613	FirstLeft = FirstLeft->FirstLeft;
3614	return FirstLeft;
3615	}
3616	//------------------------------------------------------------------------------
3617
3618	void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec)
3619	{
3620	//tests if NewOutRec contains the polygon before reassigning FirstLeft
3621	for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
3622	{
3623	OutRec* outRec = m_PolyOuts[i];
3624	OutRec* firstLeft = ParseFirstLeft(FirstLeft: outRec->FirstLeft);
3625	if (outRec->Pts && firstLeft == OldOutRec)
3626	{
3627	if (Poly2ContainsPoly1(OutPt1: outRec->Pts, OutPt2: NewOutRec->Pts))
3628	outRec->FirstLeft = NewOutRec;
3629	}
3630	}
3631	}
3632	//----------------------------------------------------------------------
3633
3634	void Clipper::FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec)
3635	{
3636	//A polygon has split into two such that one is now the inner of the other.
3637	//It's possible that these polygons now wrap around other polygons, so check
3638	//every polygon that's also contained by OuterOutRec's FirstLeft container
3639	//(including 0) to see if they've become inner to the new inner polygon ...
3640	OutRec* orfl = OuterOutRec->FirstLeft;
3641	for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
3642	{
3643	OutRec* outRec = m_PolyOuts[i];
3644
3645	if (!outRec->Pts || outRec == OuterOutRec || outRec == InnerOutRec)
3646	continue;
3647	OutRec* firstLeft = ParseFirstLeft(FirstLeft: outRec->FirstLeft);
3648	if (firstLeft != orfl && firstLeft != InnerOutRec && firstLeft != OuterOutRec)
3649	continue;
3650	if (Poly2ContainsPoly1(OutPt1: outRec->Pts, OutPt2: InnerOutRec->Pts))
3651	outRec->FirstLeft = InnerOutRec;
3652	else if (Poly2ContainsPoly1(OutPt1: outRec->Pts, OutPt2: OuterOutRec->Pts))
3653	outRec->FirstLeft = OuterOutRec;
3654	else if (outRec->FirstLeft == InnerOutRec || outRec->FirstLeft == OuterOutRec)
3655	outRec->FirstLeft = orfl;
3656	}
3657	}
3658	//----------------------------------------------------------------------
3659	void Clipper::FixupFirstLefts3(OutRec* OldOutRec, OutRec* NewOutRec)
3660	{
3661	//reassigns FirstLeft WITHOUT testing if NewOutRec contains the polygon
3662	for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
3663	{
3664	OutRec* outRec = m_PolyOuts[i];
3665	OutRec* firstLeft = ParseFirstLeft(FirstLeft: outRec->FirstLeft);
3666	if (outRec->Pts && outRec->FirstLeft == OldOutRec)
3667	outRec->FirstLeft = NewOutRec;
3668	}
3669	}
3670	//----------------------------------------------------------------------
3671
3672	void Clipper::JoinCommonEdges()
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(Idx: join->OutPt1->Idx);
3679	OutRec *outRec2 = GetOutRec(Idx: 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(outRec1: outRec2, outRec2: outRec1)) holeStateRec = outRec1;
3690	else holeStateRec = GetLowermostRec(outRec1, outRec2);
3691
3692	if (!JoinPoints(j: 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(outrec&: *outRec2);
3705
3706	if (Poly2ContainsPoly1(OutPt1: outRec2->Pts, OutPt2: outRec1->Pts))
3707	{
3708	//outRec1 contains outRec2 ...
3709	outRec2->IsHole = !outRec1->IsHole;
3710	outRec2->FirstLeft = outRec1;
3711
3712	if (m_UsingPolyTree) FixupFirstLefts2(InnerOutRec: outRec2, OuterOutRec: outRec1);
3713
3714	if ((outRec2->IsHole ^ m_ReverseOutput) == (Area(outRec: *outRec2) > 0))
3715	ReversePolyPtLinks(pp: outRec2->Pts);
3716
3717	} else if (Poly2ContainsPoly1(OutPt1: outRec1->Pts, OutPt2: 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(InnerOutRec: outRec1, OuterOutRec: outRec2);
3726
3727	if ((outRec1->IsHole ^ m_ReverseOutput) == (Area(outRec: *outRec1) > 0))
3728	ReversePolyPtLinks(pp: 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(OldOutRec: outRec1, NewOutRec: 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(OldOutRec: outRec2, NewOutRec: outRec1);
3754	}
3755	}
3756	}
3757
3758	//------------------------------------------------------------------------------
3759	// ClipperOffset support functions ...
3760	//------------------------------------------------------------------------------
3761
3762	DoublePoint GetUnitNormal(const IntPoint &pt1, const IntPoint &pt2)
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( x: Dx*Dx + dy*dy );
3770	Dx *= f;
3771	dy *= f;
3772	return DoublePoint(dy, -Dx);
3773	}
3774
3775	//------------------------------------------------------------------------------
3776	// ClipperOffset class
3777	//------------------------------------------------------------------------------
3778
3779	ClipperOffset::ClipperOffset(double miterLimit, double arcTolerance)
3780	{
3781	this->MiterLimit = miterLimit;
3782	this->ArcTolerance = arcTolerance;
3783	m_lowest.X = -1;
3784	}
3785	//------------------------------------------------------------------------------
3786
3787	ClipperOffset::~ClipperOffset()
3788	{
3789	Clear();
3790	}
3791	//------------------------------------------------------------------------------
3792
3793	void ClipperOffset::Clear()
3794	{
3795	for (int i = 0; i < m_polyNodes.ChildCount(); ++i)
3796	delete m_polyNodes.Childs[i];
3797	m_polyNodes.Childs.clear();
3798	m_lowest.X = -1;
3799	}
3800	//------------------------------------------------------------------------------
3801
3802	void ClipperOffset::AddPath(const Path& path, JoinType joinType, EndType endType)
3803	{
3804	int highI = (int)path.size() - 1;
3805	if (highI < 0) return;
3806	PolyNode* newNode = new PolyNode();
3807	newNode->m_jointype = joinType;
3808	newNode->m_endtype = endType;
3809
3810	//strip duplicate points from path and also get index to the lowest point ...
3811	if (endType == etClosedLine || endType == etClosedPolygon)
3812	while (highI > 0 && path[0] == path[highI]) highI--;
3813	newNode->Contour.reserve(n: highI + 1);
3814	newNode->Contour.push_back(x: 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(x: 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(child&: *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)
3835	m_lowest = IntPoint(m_polyNodes.ChildCount() - 1, k);
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))
3842	m_lowest = IntPoint(m_polyNodes.ChildCount() - 1, k);
3843	}
3844	}
3845	//------------------------------------------------------------------------------
3846
3847	void ClipperOffset::AddPaths(const Paths& paths, JoinType joinType, EndType endType)
3848	{
3849	for (Paths::size_type i = 0; i < paths.size(); ++i)
3850	AddPath(path: paths[i], joinType, endType);
3851	}
3852	//------------------------------------------------------------------------------
3853
3854	void ClipperOffset::FixOrientations()
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(poly: 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(poly: node.Contour)))
3866	ReversePath(p&: 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(poly: node.Contour))
3874	ReversePath(p&: node.Contour);
3875	}
3876	}
3877	}
3878	//------------------------------------------------------------------------------
3879
3880	void ClipperOffset::Execute(Paths& solution, double delta)
3881	{
3882	solution.clear();
3883	FixOrientations();
3884	DoOffset(delta);
3885
3886	//now clean up 'corners' ...
3887	Clipper clpr;
3888	clpr.AddPaths(ppg: m_destPolys, PolyTyp: ptSubject, Closed: true);
3889	if (delta > 0)
3890	{
3891	clpr.Execute(clipType: ctUnion, solution, subjFillType: pftPositive, clipFillType: 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(pg: outer, PolyTyp: ptSubject, Closed: true);
3903	clpr.ReverseSolution(value: true);
3904	clpr.Execute(clipType: ctUnion, solution, subjFillType: pftNegative, clipFillType: pftNegative);
3905	if (solution.size() > 0) solution.erase(position: solution.begin());
3906	}
3907	}
3908	//------------------------------------------------------------------------------
3909
3910	void ClipperOffset::Execute(PolyTree& solution, double delta)
3911	{
3912	solution.Clear();
3913	FixOrientations();
3914	DoOffset(delta);
3915
3916	//now clean up 'corners' ...
3917	Clipper clpr;
3918	clpr.AddPaths(ppg: m_destPolys, PolyTyp: ptSubject, Closed: true);
3919	if (delta > 0)
3920	{
3921	clpr.Execute(clipType: ctUnion, polytree&: solution, subjFillType: pftPositive, clipFillType: 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(pg: outer, PolyTyp: ptSubject, Closed: true);
3933	clpr.ReverseSolution(value: true);
3934	clpr.Execute(clipType: ctUnion, polytree&: solution, subjFillType: pftNegative, clipFillType: 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(n: 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(child&: *outerNode->Childs[i]);
3944	}
3945	else
3946	solution.Clear();
3947	}
3948	}
3949	//------------------------------------------------------------------------------
3950
3951	void ClipperOffset::DoOffset(double delta)
3952	{
3953	m_destPolys.clear();
3954	m_delta = delta;
3955
3956	//if Zero offset, just copy any CLOSED polygons to m_p and return ...
3957	if (NEAR_ZERO(delta))
3958	{
3959	m_destPolys.reserve(n: m_polyNodes.ChildCount());
3960	for (int i = 0; i < m_polyNodes.ChildCount(); i++)
3961	{
3962	PolyNode& node = *m_polyNodes.Childs[i];
3963	if (node.m_endtype == etClosedPolygon)
3964	m_destPolys.push_back(x: 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(x: delta) * def_arc_tolerance)
3976	y = std::fabs(x: delta) * def_arc_tolerance;
3977	else y = ArcTolerance;
3978	//see offset_triginometry2.svg in the documentation folder ...
3979	double steps = pi / std::acos(x: 1 - y / std::fabs(x: delta));
3980	if (steps > std::fabs(x: delta) * pi)
3981	steps = std::fabs(x: delta) * pi; //ie excessive precision check
3982	m_sin = std::sin(x: two_pi / steps);
3983	m_cos = std::cos(x: two_pi / steps);
3984	m_StepsPerRad = steps / two_pi;
3985	if (delta < 0.0) m_sin = -m_sin;
3986
3987	m_destPolys.reserve(n: 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(x: IntPoint(
4006	Round(val: m_srcPoly[0].X + X * delta),
4007	Round(val: 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(x: IntPoint(
4019	Round(val: m_srcPoly[0].X + X * delta),
4020	Round(val: 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(x: m_destPoly);
4027	continue;
4028	}
4029	//build m_normals ...
4030	m_normals.clear();
4031	m_normals.reserve(n: len);
4032	for (int j = 0; j < len - 1; ++j)
4033	m_normals.push_back(x: GetUnitNormal(pt1: m_srcPoly[j], pt2: m_srcPoly[j + 1]));
4034	if (node.m_endtype == etClosedLine || node.m_endtype == etClosedPolygon)
4035	m_normals.push_back(x: GetUnitNormal(pt1: m_srcPoly[len - 1], pt2: m_srcPoly[0]));
4036	else
4037	m_normals.push_back(x: 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, jointype: node.m_jointype);
4044	m_destPolys.push_back(x: 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, jointype: node.m_jointype);
4051	m_destPolys.push_back(x: 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, jointype: node.m_jointype);
4061	m_destPolys.push_back(x: m_destPoly);
4062	}
4063	else
4064	{
4065	int k = 0;
4066	for (int j = 1; j < len - 1; ++j)
4067	OffsetPoint(j, k, jointype: node.m_jointype);
4068
4069	IntPoint pt1;
4070	if (node.m_endtype == etOpenButt)
4071	{
4072	int j = len - 1;
4073	pt1 = IntPoint((cInt)Round(val: m_srcPoly[j].X + m_normals[j].X *
4074	delta), (cInt)Round(val: m_srcPoly[j].Y + m_normals[j].Y * delta));
4075	m_destPoly.push_back(x: pt1);
4076	pt1 = IntPoint((cInt)Round(val: m_srcPoly[j].X - m_normals[j].X *
4077	delta), (cInt)Round(val: m_srcPoly[j].Y - m_normals[j].Y * delta));
4078	m_destPoly.push_back(x: pt1);
4079	}
4080	else
4081	{
4082	int j = len - 1;
4083	k = len - 2;
4084	m_sinA = 0;
4085	m_normals[j] = DoublePoint(-m_normals[j].X, -m_normals[j].Y);
4086	if (node.m_endtype == etOpenSquare)
4087	DoSquare(j, k);
4088	else
4089	DoRound(j, k);
4090	}
4091
4092	//re-build m_normals ...
4093	for (int j = len - 1; j > 0; j--)
4094	m_normals[j] = DoublePoint(-m_normals[j - 1].X, -m_normals[j - 1].Y);
4095	m_normals[0] = DoublePoint(-m_normals[1].X, -m_normals[1].Y);
4096
4097	k = len - 1;
4098	for (int j = k - 1; j > 0; --j) OffsetPoint(j, k, jointype: node.m_jointype);
4099
4100	if (node.m_endtype == etOpenButt)
4101	{
4102	pt1 = IntPoint((cInt)Round(val: m_srcPoly[0].X - m_normals[0].X * delta),
4103	(cInt)Round(val: m_srcPoly[0].Y - m_normals[0].Y * delta));
4104	m_destPoly.push_back(x: pt1);
4105	pt1 = IntPoint((cInt)Round(val: m_srcPoly[0].X + m_normals[0].X * delta),
4106	(cInt)Round(val: m_srcPoly[0].Y + m_normals[0].Y * delta));
4107	m_destPoly.push_back(x: pt1);
4108	}
4109	else
4110	{
4111	k = 1;
4112	m_sinA = 0;
4113	if (node.m_endtype == etOpenSquare)
4114	DoSquare(j: 0, k: 1);
4115	else
4116	DoRound(j: 0, k: 1);
4117	}
4118	m_destPolys.push_back(x: m_destPoly);
4119	}
4120	}
4121	}
4122	//------------------------------------------------------------------------------
4123
4124	void ClipperOffset::OffsetPoint(int j, int& k, JoinType jointype)
4125	{
4126	//cross product ...
4127	m_sinA = (m_normals[k].X * m_normals[j].Y - m_normals[j].X * m_normals[k].Y);
4128	if (std::fabs(x: 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(x: IntPoint(Round(val: m_srcPoly[j].X + m_normals[k].X * m_delta),
4135	Round(val: 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(x: IntPoint(Round(val: m_srcPoly[j].X + m_normals[k].X * m_delta),
4146	Round(val: m_srcPoly[j].Y + m_normals[k].Y * m_delta)));
4147	m_destPoly.push_back(x: m_srcPoly[j]);
4148	m_destPoly.push_back(x: IntPoint(Round(val: m_srcPoly[j].X + m_normals[j].X * m_delta),
4149	Round(val: 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
4168	void ClipperOffset::DoSquare(int j, int k)
4169	{
4170	double dx = std::tan(x: std::atan2(y: m_sinA,
4171	x: m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y) / 4);
4172	m_destPoly.push_back(x: IntPoint(
4173	Round(val: m_srcPoly[j].X + m_delta * (m_normals[k].X - m_normals[k].Y * dx)),
4174	Round(val: m_srcPoly[j].Y + m_delta * (m_normals[k].Y + m_normals[k].X * dx))));
4175	m_destPoly.push_back(x: IntPoint(
4176	Round(val: m_srcPoly[j].X + m_delta * (m_normals[j].X + m_normals[j].Y * dx)),
4177	Round(val: m_srcPoly[j].Y + m_delta * (m_normals[j].Y - m_normals[j].X * dx))));
4178	}
4179	//------------------------------------------------------------------------------
4180
4181	void ClipperOffset::DoMiter(int j, int k, double r)
4182	{
4183	double q = m_delta / r;
4184	m_destPoly.push_back(x: IntPoint(Round(val: m_srcPoly[j].X + (m_normals[k].X + m_normals[j].X) * q),
4185	Round(val: m_srcPoly[j].Y + (m_normals[k].Y + m_normals[j].Y) * q)));
4186	}
4187	//------------------------------------------------------------------------------
4188
4189	void ClipperOffset::DoRound(int j, int k)
4190	{
4191	double a = std::atan2(y: m_sinA,
4192	x: m_normals[k].X * m_normals[j].X + m_normals[k].Y * m_normals[j].Y);
4193	int steps = std::max(a: (int)Round(val: m_StepsPerRad * std::fabs(x: a)), b: 1);
4194
4195	double X = m_normals[k].X, Y = m_normals[k].Y, X2;
4196	for (int i = 0; i < steps; ++i)
4197	{
4198	m_destPoly.push_back(x: IntPoint(
4199	Round(val: m_srcPoly[j].X + X * m_delta),
4200	Round(val: m_srcPoly[j].Y + Y * m_delta)));
4201	X2 = X;
4202	X = X * m_cos - m_sin * Y;
4203	Y = X2 * m_sin + Y * m_cos;
4204	}
4205	m_destPoly.push_back(x: IntPoint(
4206	Round(val: m_srcPoly[j].X + m_normals[j].X * m_delta),
4207	Round(val: m_srcPoly[j].Y + m_normals[j].Y * m_delta)));
4208	}
4209
4210	//------------------------------------------------------------------------------
4211	// Miscellaneous public functions
4212	//------------------------------------------------------------------------------
4213
4214	void Clipper::DoSimplePolygons()
4215	{
4216	PolyOutList::size_type i = 0;
4217	while (i < m_PolyOuts.size())
4218	{
4219	OutRec* outrec = m_PolyOuts[i++];
4220	OutPt* op = outrec->Pts;
4221	if (!op || outrec->IsOpen) continue;
4222	do //for each Pt in Polygon until duplicate found do ...
4223	{
4224	OutPt* op2 = op->Next;
4225	while (op2 != outrec->Pts)
4226	{
4227	if ((op->Pt == op2->Pt) && op2->Next != op && op2->Prev != op)
4228	{
4229	//split the polygon into two ...
4230	OutPt* op3 = op->Prev;
4231	OutPt* op4 = op2->Prev;
4232	op->Prev = op4;
4233	op4->Next = op;
4234	op2->Prev = op3;
4235	op3->Next = op2;
4236
4237	outrec->Pts = op;
4238	OutRec* outrec2 = CreateOutRec();
4239	outrec2->Pts = op2;
4240	UpdateOutPtIdxs(outrec&: *outrec2);
4241	if (Poly2ContainsPoly1(OutPt1: outrec2->Pts, OutPt2: outrec->Pts))
4242	{
4243	//OutRec2 is contained by OutRec1 ...
4244	outrec2->IsHole = !outrec->IsHole;
4245	outrec2->FirstLeft = outrec;
4246	if (m_UsingPolyTree) FixupFirstLefts2(InnerOutRec: outrec2, OuterOutRec: outrec);
4247	}
4248	else
4249	if (Poly2ContainsPoly1(OutPt1: outrec->Pts, OutPt2: outrec2->Pts))
4250	{
4251	//OutRec1 is contained by OutRec2 ...
4252	outrec2->IsHole = outrec->IsHole;
4253	outrec->IsHole = !outrec2->IsHole;
4254	outrec2->FirstLeft = outrec->FirstLeft;
4255	outrec->FirstLeft = outrec2;
4256	if (m_UsingPolyTree) FixupFirstLefts2(InnerOutRec: outrec, OuterOutRec: outrec2);
4257	}
4258	else
4259	{
4260	//the 2 polygons are separate ...
4261	outrec2->IsHole = outrec->IsHole;
4262	outrec2->FirstLeft = outrec->FirstLeft;
4263	if (m_UsingPolyTree) FixupFirstLefts1(OldOutRec: outrec, NewOutRec: outrec2);
4264	}
4265	op2 = op; //ie get ready for the Next iteration
4266	}
4267	op2 = op2->Next;
4268	}
4269	op = op->Next;
4270	}
4271	while (op != outrec->Pts);
4272	}
4273	}
4274	//------------------------------------------------------------------------------
4275
4276	void ReversePath(Path& p)
4277	{
4278	std::reverse(first: p.begin(), last: p.end());
4279	}
4280	//------------------------------------------------------------------------------
4281
4282	void ReversePaths(Paths& p)
4283	{
4284	for (Paths::size_type i = 0; i < p.size(); ++i)
4285	ReversePath(p&: p[i]);
4286	}
4287	//------------------------------------------------------------------------------
4288
4289	void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fillType)
4290	{
4291	Clipper c;
4292	c.StrictlySimple(value: true);
4293	c.AddPath(pg: in_poly, PolyTyp: ptSubject, Closed: true);
4294	c.Execute(clipType: ctUnion, solution&: out_polys, subjFillType: fillType, clipFillType: fillType);
4295	}
4296	//------------------------------------------------------------------------------
4297
4298	void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType)
4299	{
4300	Clipper c;
4301	c.StrictlySimple(value: true);
4302	c.AddPaths(ppg: in_polys, PolyTyp: ptSubject, Closed: true);
4303	c.Execute(clipType: ctUnion, solution&: out_polys, subjFillType: fillType, clipFillType: fillType);
4304	}
4305	//------------------------------------------------------------------------------
4306
4307	void SimplifyPolygons(Paths &polys, PolyFillType fillType)
4308	{
4309	SimplifyPolygons(in_polys: polys, out_polys&: polys, fillType);
4310	}
4311	//------------------------------------------------------------------------------
4312
4313	inline double DistanceSqrd(const IntPoint& pt1, const IntPoint& pt2)
4314	{
4315	double Dx = ((double)pt1.X - pt2.X);
4316	double dy = ((double)pt1.Y - pt2.Y);
4317	return (Dx*Dx + dy*dy);
4318	}
4319	//------------------------------------------------------------------------------
4320
4321	double DistanceFromLineSqrd(
4322	const IntPoint& pt, const IntPoint& ln1, const IntPoint& ln2)
4323	{
4324	//The equation of a line in general form (Ax + By + C = 0)
4325	//given 2 points (x¹,y¹) & (x²,y²) is ...
4326	//(y¹ - y²)x + (x² - x¹)y + (y² - y¹)x¹ - (x² - x¹)y¹ = 0
4327	//A = (y¹ - y²); B = (x² - x¹); C = (y² - y¹)x¹ - (x² - x¹)y¹
4328	//perpendicular distance of point (x³,y³) = (Ax³ + By³ + C)/Sqrt(A² + B²)
4329	//see http://en.wikipedia.org/wiki/Perpendicular_distance
4330	double A = double(ln1.Y - ln2.Y);
4331	double B = double(ln2.X - ln1.X);
4332	double C = A * ln1.X + B * ln1.Y;
4333	C = A * pt.X + B * pt.Y - C;
4334	return (C * C) / (A * A + B * B);
4335	}
4336	//---------------------------------------------------------------------------
4337
4338	bool SlopesNearCollinear(const IntPoint& pt1,
4339	const IntPoint& pt2, const IntPoint& pt3, double distSqrd)
4340	{
4341	//this function is more accurate when the point that's geometrically
4342	//between the other 2 points is the one that's tested for distance.
4343	//ie makes it more likely to pick up 'spikes' ...
4344	if (Abs(val: pt1.X - pt2.X) > Abs(val: pt1.Y - pt2.Y))
4345	{
4346	if ((pt1.X > pt2.X) == (pt1.X < pt3.X))
4347	return DistanceFromLineSqrd(pt: pt1, ln1: pt2, ln2: pt3) < distSqrd;
4348	else if ((pt2.X > pt1.X) == (pt2.X < pt3.X))
4349	return DistanceFromLineSqrd(pt: pt2, ln1: pt1, ln2: pt3) < distSqrd;
4350	else
4351	return DistanceFromLineSqrd(pt: pt3, ln1: pt1, ln2: pt2) < distSqrd;
4352	}
4353	else
4354	{
4355	if ((pt1.Y > pt2.Y) == (pt1.Y < pt3.Y))
4356	return DistanceFromLineSqrd(pt: pt1, ln1: pt2, ln2: pt3) < distSqrd;
4357	else if ((pt2.Y > pt1.Y) == (pt2.Y < pt3.Y))
4358	return DistanceFromLineSqrd(pt: pt2, ln1: pt1, ln2: pt3) < distSqrd;
4359	else
4360	return DistanceFromLineSqrd(pt: pt3, ln1: pt1, ln2: pt2) < distSqrd;
4361	}
4362	}
4363	//------------------------------------------------------------------------------
4364
4365	bool PointsAreClose(IntPoint pt1, IntPoint pt2, double distSqrd)
4366	{
4367	double Dx = (double)pt1.X - pt2.X;
4368	double dy = (double)pt1.Y - pt2.Y;
4369	return ((Dx * Dx) + (dy * dy) <= distSqrd);
4370	}
4371	//------------------------------------------------------------------------------
4372
4373	OutPt* ExcludeOp(OutPt* op)
4374	{
4375	OutPt* result = op->Prev;
4376	result->Next = op->Next;
4377	op->Next->Prev = result;
4378	result->Idx = 0;
4379	return result;
4380	}
4381	//------------------------------------------------------------------------------
4382
4383	void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)
4384	{
4385	//distance = proximity in units/pixels below which vertices
4386	//will be stripped. Default ~= sqrt(2).
4387
4388	size_t size = in_poly.size();
4389
4390	if (size == 0)
4391	{
4392	out_poly.clear();
4393	return;
4394	}
4395
4396	OutPt* outPts = new OutPt[size];
4397	for (size_t i = 0; i < size; ++i)
4398	{
4399	outPts[i].Pt = in_poly[i];
4400	outPts[i].Next = &outPts[(i + 1) % size];
4401	outPts[i].Next->Prev = &outPts[i];
4402	outPts[i].Idx = 0;
4403	}
4404
4405	double distSqrd = distance * distance;
4406	OutPt* op = &outPts[0];
4407	while (op->Idx == 0 && op->Next != op->Prev)
4408	{
4409	if (PointsAreClose(pt1: op->Pt, pt2: op->Prev->Pt, distSqrd))
4410	{
4411	op = ExcludeOp(op);
4412	size--;
4413	}
4414	else if (PointsAreClose(pt1: op->Prev->Pt, pt2: op->Next->Pt, distSqrd))
4415	{
4416	ExcludeOp(op: op->Next);
4417	op = ExcludeOp(op);
4418	size -= 2;
4419	}
4420	else if (SlopesNearCollinear(pt1: op->Prev->Pt, pt2: op->Pt, pt3: op->Next->Pt, distSqrd))
4421	{
4422	op = ExcludeOp(op);
4423	size--;
4424	}
4425	else
4426	{
4427	op->Idx = 1;
4428	op = op->Next;
4429	}
4430	}
4431
4432	if (size < 3) size = 0;
4433	out_poly.resize(new_size: size);
4434	for (size_t i = 0; i < size; ++i)
4435	{
4436	out_poly[i] = op->Pt;
4437	op = op->Next;
4438	}
4439	delete [] outPts;
4440	}
4441	//------------------------------------------------------------------------------
4442
4443	void CleanPolygon(Path& poly, double distance)
4444	{
4445	CleanPolygon(in_poly: poly, out_poly&: poly, distance);
4446	}
4447	//------------------------------------------------------------------------------
4448
4449	void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance)
4450	{
4451	out_polys.resize(new_size: in_polys.size());
4452	for (Paths::size_type i = 0; i < in_polys.size(); ++i)
4453	CleanPolygon(in_poly: in_polys[i], out_poly&: out_polys[i], distance);
4454	}
4455	//------------------------------------------------------------------------------
4456
4457	void CleanPolygons(Paths& polys, double distance)
4458	{
4459	CleanPolygons(in_polys: polys, out_polys&: polys, distance);
4460	}
4461	//------------------------------------------------------------------------------
4462
4463	void Minkowski(const Path& poly, const Path& path,
4464	Paths& solution, bool isSum, bool isClosed)
4465	{
4466	int delta = (isClosed ? 1 : 0);
4467	size_t polyCnt = poly.size();
4468	size_t pathCnt = path.size();
4469	Paths pp;
4470	pp.reserve(n: pathCnt);
4471	if (isSum)
4472	for (size_t i = 0; i < pathCnt; ++i)
4473	{
4474	Path p;
4475	p.reserve(n: polyCnt);
4476	for (size_t j = 0; j < poly.size(); ++j)
4477	p.push_back(x: IntPoint(path[i].X + poly[j].X, path[i].Y + poly[j].Y));
4478	pp.push_back(x: p);
4479	}
4480	else
4481	for (size_t i = 0; i < pathCnt; ++i)
4482	{
4483	Path p;
4484	p.reserve(n: polyCnt);
4485	for (size_t j = 0; j < poly.size(); ++j)
4486	p.push_back(x: IntPoint(path[i].X - poly[j].X, path[i].Y - poly[j].Y));
4487	pp.push_back(x: p);
4488	}
4489
4490	solution.clear();
4491	solution.reserve(n: (pathCnt + delta) * (polyCnt + 1));
4492	for (size_t i = 0; i < pathCnt - 1 + delta; ++i)
4493	for (size_t j = 0; j < polyCnt; ++j)
4494	{
4495	Path quad;
4496	quad.reserve(n: 4);
4497	quad.push_back(x: pp[i % pathCnt][j % polyCnt]);
4498	quad.push_back(x: pp[(i + 1) % pathCnt][j % polyCnt]);
4499	quad.push_back(x: pp[(i + 1) % pathCnt][(j + 1) % polyCnt]);
4500	quad.push_back(x: pp[i % pathCnt][(j + 1) % polyCnt]);
4501	if (!Orientation(poly: quad)) ReversePath(p&: quad);
4502	solution.push_back(x: quad);
4503	}
4504	}
4505	//------------------------------------------------------------------------------
4506
4507	void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed)
4508	{
4509	Minkowski(poly: pattern, path, solution, isSum: true, isClosed: pathIsClosed);
4510	Clipper c;
4511	c.AddPaths(ppg: solution, PolyTyp: ptSubject, Closed: true);
4512	c.Execute(clipType: ctUnion, solution, subjFillType: pftNonZero, clipFillType: pftNonZero);
4513	}
4514	//------------------------------------------------------------------------------
4515
4516	void TranslatePath(const Path& input, Path& output, const IntPoint delta)
4517	{
4518	//precondition: input != output
4519	output.resize(new_size: input.size());
4520	for (size_t i = 0; i < input.size(); ++i)
4521	output[i] = IntPoint(input[i].X + delta.X, input[i].Y + delta.Y);
4522	}
4523	//------------------------------------------------------------------------------
4524
4525	void MinkowskiSum(const Path& pattern, const Paths& paths, Paths& solution, bool pathIsClosed)
4526	{
4527	Clipper c;
4528	for (size_t i = 0; i < paths.size(); ++i)
4529	{
4530	Paths tmp;
4531	Minkowski(poly: pattern, path: paths[i], solution&: tmp, isSum: true, isClosed: pathIsClosed);
4532	c.AddPaths(ppg: tmp, PolyTyp: ptSubject, Closed: true);
4533	if (pathIsClosed)
4534	{
4535	Path tmp2;
4536	TranslatePath(input: paths[i], output&: tmp2, delta: pattern[0]);
4537	c.AddPath(pg: tmp2, PolyTyp: ptClip, Closed: true);
4538	}
4539	}
4540	c.Execute(clipType: ctUnion, solution, subjFillType: pftNonZero, clipFillType: pftNonZero);
4541	}
4542	//------------------------------------------------------------------------------
4543
4544	void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution)
4545	{
4546	Minkowski(poly: poly1, path: poly2, solution, isSum: false, isClosed: true);
4547	Clipper c;
4548	c.AddPaths(ppg: solution, PolyTyp: ptSubject, Closed: true);
4549	c.Execute(clipType: ctUnion, solution, subjFillType: pftNonZero, clipFillType: pftNonZero);
4550	}
4551	//------------------------------------------------------------------------------
4552
4553	enum NodeType {ntAny, ntOpen, ntClosed};
4554
4555	void AddPolyNodeToPaths(const PolyNode& polynode, NodeType nodetype, Paths& paths)
4556	{
4557	bool match = true;
4558	if (nodetype == ntClosed) match = !polynode.IsOpen();
4559	else if (nodetype == ntOpen) return;
4560
4561	if (!polynode.Contour.empty() && match)
4562	paths.push_back(x: polynode.Contour);
4563	for (int i = 0; i < polynode.ChildCount(); ++i)
4564	AddPolyNodeToPaths(polynode: *polynode.Childs[i], nodetype, paths);
4565	}
4566	//------------------------------------------------------------------------------
4567
4568	void PolyTreeToPaths(const PolyTree& polytree, Paths& paths)
4569	{
4570	paths.resize(new_size: 0);
4571	paths.reserve(n: polytree.Total());
4572	AddPolyNodeToPaths(polynode: polytree, nodetype: ntAny, paths);
4573	}
4574	//------------------------------------------------------------------------------
4575
4576	void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths)
4577	{
4578	paths.resize(new_size: 0);
4579	paths.reserve(n: polytree.Total());
4580	AddPolyNodeToPaths(polynode: polytree, nodetype: ntClosed, paths);
4581	}
4582	//------------------------------------------------------------------------------
4583
4584	void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths)
4585	{
4586	paths.resize(new_size: 0);
4587	paths.reserve(n: polytree.Total());
4588	//Open paths are top level only, so ...
4589	for (int i = 0; i < polytree.ChildCount(); ++i)
4590	if (polytree.Childs[i]->IsOpen())
4591	paths.push_back(x: polytree.Childs[i]->Contour);
4592	}
4593	//------------------------------------------------------------------------------
4594
4595	std::ostream& operator <<(std::ostream &s, const IntPoint &p)
4596	{
4597	s << "(" << p.X << "," << p.Y << ")";
4598	return s;
4599	}
4600	//------------------------------------------------------------------------------
4601
4602	std::ostream& operator <<(std::ostream &s, const Path &p)
4603	{
4604	if (p.empty()) return s;
4605	Path::size_type last = p.size() -1;
4606	for (Path::size_type i = 0; i < last; i++)
4607	s << "(" << p[i].X << "," << p[i].Y << "), ";
4608	s << "(" << p[last].X << "," << p[last].Y << ")\n";
4609	return s;
4610	}
4611	//------------------------------------------------------------------------------
4612
4613	std::ostream& operator <<(std::ostream &s, const Paths &p)
4614	{
4615	for (Paths::size_type i = 0; i < p.size(); i++)
4616	s << p[i];
4617	s << "\n";
4618	return s;
4619	}
4620	//------------------------------------------------------------------------------
4621
4622	} //QtClipperLib namespace
4623