Loading files
This file is pinned to the selected release. Download the original to open it in your design tool.
5203ce801This file is pinned to the selected release. Download the original to open it in your design tool.
/*******************************************************************************
* *
* Author : Angus Johnson *
* Version : 5.1.6 *
* Date : 23 May 2013 *
* Website : http://www.angusj.com *
* Copyright : Angus Johnson 2010-2013 *
* *
* License: *
* Use, modification & distribution is subject to Boost Software License Ver 1. *
* http://www.boost.org/LICENSE_1_0.txt *
* *
* Attributions: *
* The code in this library is an extension of Bala Vatti's clipping algorithm: *
* "A generic solution to polygon clipping" *
* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. *
* http://portal.acm.org/citation.cfm?id=129906 *
* *
* Computer graphics and geometric modeling: implementation and algorithms *
* By Max K. Agoston *
* Springer; 1 edition (January 4, 2005) *
* http://books.google.com/books?q=vatti+clipping+agoston *
* *
* See also: *
* "Polygon Offsetting by Computing Winding Numbers" *
* Paper no. DETC2005-85513 pp. 565-575 *
* ASME 2005 International Design Engineering Technical Conferences *
* and Computers and Information in Engineering Conference (IDETC/CIE2005) *
* September 24-28, 2005 , Long Beach, California, USA *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf *
* *
*******************************************************************************/
/*******************************************************************************
* *
* This is a translation of the Delphi Clipper library and the naming style *
* used has retained a Delphi flavour. *
* *
*******************************************************************************/
using System;
using System.Collections.Generic;
//using System.Text; //for Int128.AsString() & StringBuilder
//using System.IO; //streamReader & StreamWriter
namespace ClipperLib
{
using Polygon = List<IntPoint>;
using Polygons = List<List<IntPoint>>;
//------------------------------------------------------------------------------
// PolyTree & PolyNode classes
//------------------------------------------------------------------------------
public class PolyTree : PolyNode
{
internal List<PolyNode> m_AllPolys = new List<PolyNode>();
~PolyTree()
{
Clear();
}
public void Clear()
{
for (int i = 0; i < m_AllPolys.Count; i++)
m_AllPolys[i] = null;
m_AllPolys.Clear();
m_Childs.Clear();
}
public PolyNode GetFirst()
{
if (m_Childs.Count > 0)
return m_Childs[0];
else
return null;
}
public int Total
{
get { return m_AllPolys.Count; }
}
}
public class PolyNode
{
internal PolyNode m_Parent;
internal Polygon m_polygon = new Polygon();
internal int m_Index;
internal List<PolyNode> m_Childs = new List<PolyNode>();
private bool IsHoleNode()
{
bool result = true;
PolyNode node = m_Parent;
while (node != null)
{
result = !result;
node = node.m_Parent;
}
return result;
}
public int ChildCount
{
get { return m_Childs.Count; }
}
public Polygon Contour
{
get { return m_polygon; }
}
internal void AddChild(PolyNode Child)
{
int cnt = m_Childs.Count;
m_Childs.Add(Child);
Child.m_Parent = this;
Child.m_Index = cnt;
}
public PolyNode GetNext()
{
if (m_Childs.Count > 0)
return m_Childs[0];
else
return GetNextSiblingUp();
}
internal PolyNode GetNextSiblingUp()
{
if (m_Parent == null)
return null;
else if (m_Index == m_Parent.m_Childs.Count - 1)
return m_Parent.GetNextSiblingUp();
else
return m_Parent.m_Childs[m_Index + 1];
}
public List<PolyNode> Childs
{
get { return m_Childs; }
}
public PolyNode Parent
{
get { return m_Parent; }
}
public bool IsHole
{
get { return IsHoleNode(); }
}
}
//------------------------------------------------------------------------------
// Int128 struct (enables safe math on signed 64bit integers)
// eg Int128 val1((Int64)9223372036854775807); //ie 2^63 -1
// Int128 val2((Int64)9223372036854775807);
// Int128 val3 = val1 * val2;
// val3.ToString => "85070591730234615847396907784232501249" (8.5e+37)
//------------------------------------------------------------------------------
internal struct Int128
{
private Int64 hi;
private UInt64 lo;
public Int128(Int64 _lo)
{
lo = (UInt64)_lo;
if (_lo < 0) hi = -1;
else hi = 0;
}
public Int128(Int64 _hi, UInt64 _lo)
{
lo = _lo;
hi = _hi;
}
public Int128(Int128 val)
{
hi = val.hi;
lo = val.lo;
}
public bool IsNegative()
{
return hi < 0;
}
public static bool operator ==(Int128 val1, Int128 val2)
{
if ((object)val1 == (object)val2) return true;
else if ((object)val1 == null || (object)val2 == null) return false;
return (val1.hi == val2.hi && val1.lo == val2.lo);
}
public static bool operator!= (Int128 val1, Int128 val2)
{
return !(val1 == val2);
}
public override bool Equals(System.Object obj)
{
if (obj == null || !(obj is Int128))
return false;
Int128 i128 = (Int128)obj;
return (i128.hi == hi && i128.lo == lo);
}
public override int GetHashCode()
{
return hi.GetHashCode() ^ lo.GetHashCode();
}
public static bool operator> (Int128 val1, Int128 val2)
{
if (val1.hi != val2.hi)
return val1.hi > val2.hi;
else
return val1.lo > val2.lo;
}
public static bool operator< (Int128 val1, Int128 val2)
{
if (val1.hi != val2.hi)
return val1.hi < val2.hi;
else
return val1.lo < val2.lo;
}
public static Int128 operator+ (Int128 lhs, Int128 rhs)
{
lhs.hi += rhs.hi;
lhs.lo += rhs.lo;
if (lhs.lo < rhs.lo) lhs.hi++;
return lhs;
}
public static Int128 operator- (Int128 lhs, Int128 rhs)
{
return lhs + -rhs;
}
public static Int128 operator -(Int128 val)
{
if (val.lo == 0)
return new Int128(-val.hi, 0);
else
return new Int128(~val.hi, ~val.lo +1);
}
//nb: Constructing two new Int128 objects every time we want to multiply longs
//is slow. So, although calling the Int128Mul method doesn't look as clean, the
//code runs significantly faster than if we'd used the * operator.
public static Int128 Int128Mul(Int64 lhs, Int64 rhs)
{
bool negate = (lhs < 0) != (rhs < 0);
if (lhs < 0) lhs = -lhs;
if (rhs < 0) rhs = -rhs;
UInt64 int1Hi = (UInt64)lhs >> 32;
UInt64 int1Lo = (UInt64)lhs & 0xFFFFFFFF;
UInt64 int2Hi = (UInt64)rhs >> 32;
UInt64 int2Lo = (UInt64)rhs & 0xFFFFFFFF;
//nb: see comments in clipper.pas
UInt64 a = int1Hi * int2Hi;
UInt64 b = int1Lo * int2Lo;
UInt64 c = int1Hi * int2Lo + int1Lo * int2Hi;
UInt64 lo;
Int64 hi;
hi = (Int64)(a + (c >> 32));
unchecked { lo = (c << 32) + b; }
if (lo < b) hi++;
Int128 result = new Int128(hi, lo);
return negate ? -result : result;
}
public static Int128 operator /(Int128 lhs, Int128 rhs)
{
if (rhs.lo == 0 && rhs.hi == 0)
throw new ClipperException("Int128: divide by zero");
bool negate = (rhs.hi < 0) != (lhs.hi < 0);
if (lhs.hi < 0) lhs = -lhs;
if (rhs.hi < 0) rhs = -rhs;
if (rhs < lhs)
{
Int128 result = new Int128(0);
Int128 cntr = new Int128(1);
while (rhs.hi >= 0 && !(rhs > lhs))
{
rhs.hi <<= 1;
if ((Int64)rhs.lo < 0) rhs.hi++;
rhs.lo <<= 1;
cntr.hi <<= 1;
if ((Int64)cntr.lo < 0) cntr.hi++;
cntr.lo <<= 1;
}
rhs.lo >>= 1;
if ((rhs.hi & 1) == 1)
rhs.lo |= 0x8000000000000000;
rhs.hi = (Int64)((UInt64)rhs.hi >> 1);
cntr.lo >>= 1;
if ((cntr.hi & 1) == 1)
cntr.lo |= 0x8000000000000000;
cntr.hi >>= 1;
while (cntr.hi != 0 || cntr.lo != 0)
{
if (!(lhs < rhs))
{
lhs -= rhs;
result.hi |= cntr.hi;
result.lo |= cntr.lo;
}
rhs.lo >>= 1;
if ((rhs.hi & 1) == 1)
rhs.lo |= 0x8000000000000000;
rhs.hi >>= 1;
cntr.lo >>= 1;
if ((cntr.hi & 1) == 1)
cntr.lo |= 0x8000000000000000;
cntr.hi >>= 1;
}
return negate ? -result : result;
}
else if (rhs == lhs)
return new Int128(1);
else
return new Int128(0);
}
public double ToDouble()
{
const double shift64 = 18446744073709551616.0; //2^64
if (hi < 0)
{
if (lo == 0)
return (double)hi * shift64;
else
return -(double)(~lo + ~hi * shift64);
}
else
return (double)(lo + hi * shift64);
}
};
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
public struct IntPoint
{
public Int64 X;
public Int64 Y;
public IntPoint(Int64 X, Int64 Y)
{
this.X = X; this.Y = Y;
}
public IntPoint(IntPoint pt)
{
this.X = pt.X; this.Y = pt.Y;
}
}
public struct IntRect
{
public Int64 left;
public Int64 top;
public Int64 right;
public Int64 bottom;
public IntRect(Int64 l, Int64 t, Int64 r, Int64 b)
{
this.left = l; this.top = t;
this.right = r; this.bottom = b;
}
}
public enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor };
public enum PolyType { ptSubject, ptClip };
//By far the most widely used winding rules for polygon filling are
//EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32)
//Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL)
//see http://glprogramming.com/red/chapter11.html
public enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative };
public enum JoinType { jtSquare, jtRound, jtMiter };
public enum EndType { etClosed, etButt, etSquare, etRound};
[Flags]
internal enum EdgeSide { esLeft = 1, esRight = 2 };
[Flags]
internal enum Protects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 };
internal enum Direction { dRightToLeft, dLeftToRight };
internal class TEdge {
public Int64 xbot;
public Int64 ybot;
public Int64 xcurr;
public Int64 ycurr;
public Int64 xtop;
public Int64 ytop;
public double dx;
public Int64 deltaX;
public Int64 deltaY;
public PolyType polyType;
public EdgeSide side;
public int windDelta; //1 or -1 depending on winding direction
public int windCnt;
public int windCnt2; //winding count of the opposite polytype
public int outIdx;
public TEdge next;
public TEdge prev;
public TEdge nextInLML;
public TEdge nextInAEL;
public TEdge prevInAEL;
public TEdge nextInSEL;
public TEdge prevInSEL;
};
internal class IntersectNode
{
public TEdge edge1;
public TEdge edge2;
public IntPoint pt;
public IntersectNode next;
};
internal class LocalMinima
{
public Int64 Y;
public TEdge leftBound;
public TEdge rightBound;
public LocalMinima next;
};
internal class Scanbeam
{
public Int64 Y;
public Scanbeam next;
};
internal class OutRec
{
public int idx;
public bool isHole;
public OutRec FirstLeft; //see comments in clipper.pas
public OutPt pts;
public OutPt bottomPt;
public PolyNode polyNode;
};
internal class OutPt
{
public int idx;
public IntPoint pt;
public OutPt next;
public OutPt prev;
};
internal class JoinRec
{
public IntPoint pt1a;
public IntPoint pt1b;
public int poly1Idx;
public IntPoint pt2a;
public IntPoint pt2b;
public int poly2Idx;
};
internal class HorzJoinRec
{
public TEdge edge;
public int savedIdx;
};
public class ClipperBase
{
protected const double horizontal = -3.4E+38;
internal const Int64 loRange = 0x3FFFFFFF;
internal const Int64 hiRange = 0x3FFFFFFFFFFFFFFFL;
internal LocalMinima m_MinimaList;
internal LocalMinima m_CurrentLM;
internal List<List<TEdge>> m_edges = new List<List<TEdge>>();
internal bool m_UseFullRange;
//------------------------------------------------------------------------------
protected static bool PointsEqual(IntPoint pt1, IntPoint pt2)
{
return ( pt1.X == pt2.X && pt1.Y == pt2.Y );
}
//------------------------------------------------------------------------------
internal bool PointIsVertex(IntPoint pt, OutPt pp)
{
OutPt pp2 = pp;
do
{
if (PointsEqual(pp2.pt, pt)) return true;
pp2 = pp2.next;
}
while (pp2 != pp);
return false;
}
//------------------------------------------------------------------------------
internal bool PointOnLineSegment(IntPoint pt,
IntPoint linePt1, IntPoint linePt2, bool UseFullInt64Range)
{
if (UseFullInt64Range)
return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) ||
((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) ||
(((pt.X > linePt1.X) == (pt.X < linePt2.X)) &&
((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) &&
((Int128.Int128Mul((pt.X - linePt1.X), (linePt2.Y - linePt1.Y)) ==
Int128.Int128Mul((linePt2.X - linePt1.X), (pt.Y - linePt1.Y)))));
else
return ((pt.X == linePt1.X) && (pt.Y == linePt1.Y)) ||
((pt.X == linePt2.X) && (pt.Y == linePt2.Y)) ||
(((pt.X > linePt1.X) == (pt.X < linePt2.X)) &&
((pt.Y > linePt1.Y) == (pt.Y < linePt2.Y)) &&
((pt.X - linePt1.X) * (linePt2.Y - linePt1.Y) ==
(linePt2.X - linePt1.X) * (pt.Y - linePt1.Y)));
}
//------------------------------------------------------------------------------
internal bool PointOnPolygon(IntPoint pt, OutPt pp, bool UseFullInt64Range)
{
OutPt pp2 = pp;
while (true)
{
if (PointOnLineSegment(pt, pp2.pt, pp2.next.pt, UseFullInt64Range))
return true;
pp2 = pp2.next;
if (pp2 == pp) break;
}
return false;
}
//------------------------------------------------------------------------------
internal bool PointInPolygon(IntPoint pt, OutPt pp, bool UseFulllongRange)
{
OutPt pp2 = pp;
bool result = false;
if (UseFulllongRange)
{
do
{
if ((((pp2.pt.Y <= pt.Y) && (pt.Y < pp2.prev.pt.Y)) ||
((pp2.prev.pt.Y <= pt.Y) && (pt.Y < pp2.pt.Y))) &&
new Int128(pt.X - pp2.pt.X) <
Int128.Int128Mul(pp2.prev.pt.X - pp2.pt.X, pt.Y - pp2.pt.Y) /
new Int128(pp2.prev.pt.Y - pp2.pt.Y))
result = !result;
pp2 = pp2.next;
}
while (pp2 != pp);
}
else
{
do
{
if ((((pp2.pt.Y <= pt.Y) && (pt.Y < pp2.prev.pt.Y)) ||
((pp2.prev.pt.Y <= pt.Y) && (pt.Y < pp2.pt.Y))) &&
(pt.X - pp2.pt.X < (pp2.prev.pt.X - pp2.pt.X) * (pt.Y - pp2.pt.Y) /
(pp2.prev.pt.Y - pp2.pt.Y))) result = !result;
pp2 = pp2.next;
}
while (pp2 != pp);
}
return result;
}
//------------------------------------------------------------------------------
internal static bool SlopesEqual(TEdge e1, TEdge e2, bool UseFullRange)
{
if (UseFullRange)
return Int128.Int128Mul(e1.deltaY, e2.deltaX) ==
Int128.Int128Mul(e1.deltaX, e2.deltaY);
else return (Int64)(e1.deltaY) * (e2.deltaX) ==
(Int64)(e1.deltaX) * (e2.deltaY);
}
//------------------------------------------------------------------------------
protected static bool SlopesEqual(IntPoint pt1, IntPoint pt2,
IntPoint pt3, bool UseFullRange)
{
if (UseFullRange)
return Int128.Int128Mul(pt1.Y - pt2.Y, pt2.X - pt3.X) ==
Int128.Int128Mul(pt1.X - pt2.X, pt2.Y - pt3.Y);
else return
(Int64)(pt1.Y - pt2.Y) * (pt2.X - pt3.X) - (Int64)(pt1.X - pt2.X) * (pt2.Y - pt3.Y) == 0;
}
//------------------------------------------------------------------------------
protected static bool SlopesEqual(IntPoint pt1, IntPoint pt2,
IntPoint pt3, IntPoint pt4, bool UseFullRange)
{
if (UseFullRange)
return Int128.Int128Mul(pt1.Y - pt2.Y, pt3.X - pt4.X) ==
Int128.Int128Mul(pt1.X - pt2.X, pt3.Y - pt4.Y);
else return
(Int64)(pt1.Y - pt2.Y) * (pt3.X - pt4.X) - (Int64)(pt1.X - pt2.X) * (pt3.Y - pt4.Y) == 0;
}
//------------------------------------------------------------------------------
internal ClipperBase() //constructor (nb: no external instantiation)
{
m_MinimaList = null;
m_CurrentLM = null;
m_UseFullRange = false;
}
//------------------------------------------------------------------------------
//destructor - commented out since I gather this impedes the GC
//~ClipperBase()
//{
// Clear();
//}
//------------------------------------------------------------------------------
public virtual void Clear()
{
DisposeLocalMinimaList();
for (int i = 0; i < m_edges.Count; ++i)
{
for (int j = 0; j < m_edges[i].Count; ++j) m_edges[i][j] = null;
m_edges[i].Clear();
}
m_edges.Clear();
m_UseFullRange = false;
}
//------------------------------------------------------------------------------
private void DisposeLocalMinimaList()
{
while( m_MinimaList != null )
{
LocalMinima tmpLm = m_MinimaList.next;
m_MinimaList = null;
m_MinimaList = tmpLm;
}
m_CurrentLM = null;
}
//------------------------------------------------------------------------------
public bool AddPolygons(Polygons ppg, PolyType polyType)
{
bool result = false;
for (int i = 0; i < ppg.Count; ++i)
if (AddPolygon(ppg[i], polyType)) result = true;
return result;
}
//------------------------------------------------------------------------------
void RangeTest(IntPoint pt, ref Int64 maxrange)
{
if (pt.X > maxrange)
{
if (pt.X > hiRange)
throw new ClipperException("Coordinate exceeds range bounds");
else maxrange = hiRange;
}
if (pt.Y > maxrange)
{
if (pt.Y > hiRange)
throw new ClipperException("Coordinate exceeds range bounds");
else maxrange = hiRange;
}
}
//------------------------------------------------------------------------------
public bool AddPolygon(Polygon pg, PolyType polyType)
{
int len = pg.Count;
if (len < 3) return false;
Int64 maxVal;
if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange;
RangeTest(pg[0], ref maxVal);
Polygon p = new Polygon(len);
p.Add(new IntPoint(pg[0].X, pg[0].Y));
int j = 0;
for (int i = 1; i < len; ++i)
{
RangeTest(pg[i], ref maxVal);
if (PointsEqual(p[j], pg[i])) continue;
else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i], maxVal == hiRange))
{
if (PointsEqual(p[j-1], pg[i])) j--;
} else j++;
if (j < p.Count)
p[j] = pg[i]; else
p.Add(new IntPoint(pg[i].X, pg[i].Y));
}
if (j < 2) return false;
m_UseFullRange = maxVal == hiRange;
len = j+1;
while (len > 2)
{
//nb: test for point equality before testing slopes ...
if (PointsEqual(p[j], p[0])) j--;
else if (PointsEqual(p[0], p[1]) || SlopesEqual(p[j], p[0], p[1], m_UseFullRange))
p[0] = p[j--];
else if (SlopesEqual(p[j - 1], p[j], p[0], m_UseFullRange)) j--;
else if (SlopesEqual(p[0], p[1], p[2], m_UseFullRange))
{
for (int i = 2; i <= j; ++i) p[i - 1] = p[i];
j--;
}
else break;
len--;
}
if (len < 3) return false;
//create a new edge array ...
List<TEdge> edges = new List<TEdge>(len);
for (int i = 0; i < len; i++) edges.Add(new TEdge());
m_edges.Add(edges);
//convert vertices to a double-linked-list of edges and initialize ...
edges[0].xcurr = p[0].X;
edges[0].ycurr = p[0].Y;
InitEdge(edges[len-1], edges[0], edges[len-2], p[len-1], polyType);
for (int i = len-2; i > 0; --i)
InitEdge(edges[i], edges[i+1], edges[i-1], p[i], polyType);
InitEdge(edges[0], edges[1], edges[len-1], p[0], polyType);
//reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates
//increase downward so the 'highest' edge will have the smallest ytop) ...
TEdge e = edges[0];
TEdge eHighest = e;
do
{
e.xcurr = e.xbot;
e.ycurr = e.ybot;
if (e.ytop < eHighest.ytop) eHighest = e;
e = e.next;
}
while ( e != edges[0]);
//make sure eHighest is positioned so the following loop works safely ...
if (eHighest.windDelta > 0) eHighest = eHighest.next;
if (eHighest.dx == horizontal) eHighest = eHighest.next;
//finally insert each local minima ...
e = eHighest;
do {
e = AddBoundsToLML(e);
}
while( e != eHighest );
return true;
}
//------------------------------------------------------------------------------
private void InitEdge(TEdge e, TEdge eNext,
TEdge ePrev, IntPoint pt, PolyType polyType)
{
e.next = eNext;
e.prev = ePrev;
e.xcurr = pt.X;
e.ycurr = pt.Y;
if (e.ycurr >= e.next.ycurr)
{
e.xbot = e.xcurr;
e.ybot = e.ycurr;
e.xtop = e.next.xcurr;
e.ytop = e.next.ycurr;
e.windDelta = 1;
} else
{
e.xtop = e.xcurr;
e.ytop = e.ycurr;
e.xbot = e.next.xcurr;
e.ybot = e.next.ycurr;
e.windDelta = -1;
}
SetDx(e);
e.polyType = polyType;
e.outIdx = -1;
}
//------------------------------------------------------------------------------
private void SetDx(TEdge e)
{
e.deltaX = (e.xtop - e.xbot);
e.deltaY = (e.ytop - e.ybot);
if (e.deltaY == 0) e.dx = horizontal;
else e.dx = (double)(e.deltaX) / (e.deltaY);
}
//---------------------------------------------------------------------------
TEdge AddBoundsToLML(TEdge e)
{
//Starting at the top of one bound we progress to the bottom where there's
//a local minima. We then go to the top of the next bound. These two bounds
//form the left and right (or right and left) bounds of the local minima.
e.nextInLML = null;
e = e.next;
for (;;)
{
if ( e.dx == horizontal )
{
//nb: proceed through horizontals when approaching from their right,
// but break on horizontal minima if approaching from their left.
// This ensures 'local minima' are always on the left of horizontals.
if (e.next.ytop < e.ytop && e.next.xbot > e.prev.xbot) break;
if (e.xtop != e.prev.xbot) SwapX(e);
e.nextInLML = e.prev;
}
else if (e.ycurr == e.prev.ycurr) break;
else e.nextInLML = e.prev;
e = e.next;
}
//e and e.prev are now at a local minima ...
LocalMinima newLm = new LocalMinima();
newLm.next = null;
newLm.Y = e.prev.ybot;
if ( e.dx == horizontal ) //horizontal edges never start a left bound
{
if (e.xbot != e.prev.xbot) SwapX(e);
newLm.leftBound = e.prev;
newLm.rightBound = e;
} else if (e.dx < e.prev.dx)
{
newLm.leftBound = e.prev;
newLm.rightBound = e;
} else
{
newLm.leftBound = e;
newLm.rightBound = e.prev;
}
newLm.leftBound.side = EdgeSide.esLeft;
newLm.rightBound.side = EdgeSide.esRight;
InsertLocalMinima( newLm );
for (;;)
{
if ( e.next.ytop == e.ytop && e.next.dx != horizontal ) break;
e.nextInLML = e.next;
e = e.next;
if ( e.dx == horizontal && e.xbot != e.prev.xtop) SwapX(e);
}
return e.next;
}
//------------------------------------------------------------------------------
private void InsertLocalMinima(LocalMinima newLm)
{
if( m_MinimaList == null )
{
m_MinimaList = newLm;
}
else if( newLm.Y >= m_MinimaList.Y )
{
newLm.next = m_MinimaList;
m_MinimaList = newLm;
} else
{
LocalMinima tmpLm = m_MinimaList;
while( tmpLm.next != null && ( newLm.Y < tmpLm.next.Y ) )
tmpLm = tmpLm.next;
newLm.next = tmpLm.next;
tmpLm.next = newLm;
}
}
//------------------------------------------------------------------------------
protected void PopLocalMinima()
{
if (m_CurrentLM == null) return;
m_CurrentLM = m_CurrentLM.next;
}
//------------------------------------------------------------------------------
private void SwapX(TEdge e)
{
//swap horizontal edges' top and bottom x's so they follow the natural
//progression of the bounds - ie so their xbots will align with the
//adjoining lower edge. [Helpful in the ProcessHorizontal() method.]
e.xcurr = e.xtop;
e.xtop = e.xbot;
e.xbot = e.xcurr;
}
//------------------------------------------------------------------------------
protected virtual void Reset()
{
m_CurrentLM = m_MinimaList;
//reset all edges ...
LocalMinima lm = m_MinimaList;
while (lm != null)
{
TEdge e = lm.leftBound;
while (e != null)
{
e.xcurr = e.xbot;
e.ycurr = e.ybot;
e.side = EdgeSide.esLeft;
e.outIdx = -1;
e = e.nextInLML;
}
e = lm.rightBound;
while (e != null)
{
e.xcurr = e.xbot;
e.ycurr = e.ybot;
e.side = EdgeSide.esRight;
e.outIdx = -1;
e = e.nextInLML;
}
lm = lm.next;
}
return;
}
//------------------------------------------------------------------------------
public IntRect GetBounds()
{
IntRect result = new IntRect();
LocalMinima lm = m_MinimaList;
if (lm == null) return result;
result.left = lm.leftBound.xbot;
result.top = lm.leftBound.ybot;
result.right = lm.leftBound.xbot;
result.bottom = lm.leftBound.ybot;
while (lm != null)
{
if (lm.leftBound.ybot > result.bottom)
result.bottom = lm.leftBound.ybot;
TEdge e = lm.leftBound;
for (; ; )
{
TEdge bottomE = e;
while (e.nextInLML != null)
{
if (e.xbot < result.left) result.left = e.xbot;
if (e.xbot > result.right) result.right = e.xbot;
e = e.nextInLML;
}
if (e.xbot < result.left) result.left = e.xbot;
if (e.xbot > result.right) result.right = e.xbot;
if (e.xtop < result.left) result.left = e.xtop;
if (e.xtop > result.right) result.right = e.xtop;
if (e.ytop < result.top) result.top = e.ytop;
if (bottomE == lm.leftBound) e = lm.rightBound;
else break;
}
lm = lm.next;
}
return result;
}
} //ClipperBase
public class Clipper : ClipperBase
{
private List<OutRec> m_PolyOuts;
private ClipType m_ClipType;
private Scanbeam m_Scanbeam;
private TEdge m_ActiveEdges;
private TEdge m_SortedEdges;
private IntersectNode m_IntersectNodes;
private bool m_ExecuteLocked;
private PolyFillType m_ClipFillType;
private PolyFillType m_SubjFillType;
private List<JoinRec> m_Joins;
private List<HorzJoinRec> m_HorizJoins;
private bool m_ReverseOutput;
private bool m_ForceSimple;
private bool m_UsingPolyTree;
public Clipper()
{
m_Scanbeam = null;
m_ActiveEdges = null;
m_SortedEdges = null;
m_IntersectNodes = null;
m_ExecuteLocked = false;
m_UsingPolyTree = false;
m_PolyOuts = new List<OutRec>();
m_Joins = new List<JoinRec>();
m_HorizJoins = new List<HorzJoinRec>();
m_ReverseOutput = false;
m_ForceSimple = false;
}
//------------------------------------------------------------------------------
//destructor - commented out since I gather this impedes the GC
//~Clipper() //destructor
//{
// Clear();
// DisposeScanbeamList();
//}
//------------------------------------------------------------------------------
public override void Clear()
{
if (m_edges.Count == 0) return; //avoids problems with ClipperBase destructor
DisposeAllPolyPts();
base.Clear();
}
//------------------------------------------------------------------------------
void DisposeScanbeamList()
{
while ( m_Scanbeam != null ) {
Scanbeam sb2 = m_Scanbeam.next;
m_Scanbeam = null;
m_Scanbeam = sb2;
}
}
//------------------------------------------------------------------------------
protected override void Reset()
{
base.Reset();
m_Scanbeam = null;
m_ActiveEdges = null;
m_SortedEdges = null;
DisposeAllPolyPts();
LocalMinima lm = m_MinimaList;
while (lm != null)
{
InsertScanbeam(lm.Y);
lm = lm.next;
}
}
//------------------------------------------------------------------------------
public bool ReverseSolution
{
get { return m_ReverseOutput; }
set { m_ReverseOutput = value; }
}
//------------------------------------------------------------------------------
public bool ForceSimple
{
get { return m_ForceSimple; }
set { m_ForceSimple = value; }
}
//------------------------------------------------------------------------------
private void InsertScanbeam(Int64 Y)
{
if( m_Scanbeam == null )
{
m_Scanbeam = new Scanbeam();
m_Scanbeam.next = null;
m_Scanbeam.Y = Y;
}
else if( Y > m_Scanbeam.Y )
{
Scanbeam newSb = new Scanbeam();
newSb.Y = Y;
newSb.next = m_Scanbeam;
m_Scanbeam = newSb;
} else
{
Scanbeam sb2 = m_Scanbeam;
while( sb2.next != null && ( Y <= sb2.next.Y ) ) sb2 = sb2.next;
if( Y == sb2.Y ) return; //ie ignores duplicates
Scanbeam newSb = new Scanbeam();
newSb.Y = Y;
newSb.next = sb2.next;
sb2.next = newSb;
}
}
//------------------------------------------------------------------------------
public bool Execute(ClipType clipType, Polygons solution,
PolyFillType subjFillType, PolyFillType clipFillType)
{
if (m_ExecuteLocked) return false;
m_ExecuteLocked = true;
solution.Clear();
m_SubjFillType = subjFillType;
m_ClipFillType = clipFillType;
m_ClipType = clipType;
m_UsingPolyTree = false;
bool succeeded = ExecuteInternal();
//build the return polygons ...
if (succeeded) BuildResult(solution);
m_ExecuteLocked = false;
return succeeded;
}
//------------------------------------------------------------------------------
public bool Execute(ClipType clipType, PolyTree polytree,
PolyFillType subjFillType, PolyFillType clipFillType)
{
if (m_ExecuteLocked) return false;
m_ExecuteLocked = true;
m_SubjFillType = subjFillType;
m_ClipFillType = clipFillType;
m_ClipType = clipType;
m_UsingPolyTree = true;
bool succeeded = ExecuteInternal();
//build the return polygons ...
if (succeeded) BuildResult2(polytree);
m_ExecuteLocked = false;
return succeeded;
}
//------------------------------------------------------------------------------
public bool Execute(ClipType clipType, Polygons solution)
{
return Execute(clipType, solution,
PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);
}
//------------------------------------------------------------------------------
public bool Execute(ClipType clipType, PolyTree polytree)
{
return Execute(clipType, polytree,
PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);
}
//------------------------------------------------------------------------------
internal void FixHoleLinkage(OutRec outRec)
{
//skip if an outermost polygon or
//already already points to the correct FirstLeft ...
if (outRec.FirstLeft == null ||
(outRec.isHole != outRec.FirstLeft.isHole &&
outRec.FirstLeft.pts != null)) return;
OutRec orfl = outRec.FirstLeft;
while (orfl != null && ((orfl.isHole == outRec.isHole) || orfl.pts == null))
orfl = orfl.FirstLeft;
outRec.FirstLeft = orfl;
}
//------------------------------------------------------------------------------
private bool ExecuteInternal()
{
bool succeeded;
try
{
Reset();
if (m_CurrentLM == null) return true;
Int64 botY = PopScanbeam();
do
{
InsertLocalMinimaIntoAEL(botY);
m_HorizJoins.Clear();
ProcessHorizontals();
Int64 topY = PopScanbeam();
succeeded = ProcessIntersections(botY, topY);
if (!succeeded) break;
ProcessEdgesAtTopOfScanbeam(topY);
botY = topY;
} while (m_Scanbeam != null || m_CurrentLM != null);
}
catch { succeeded = false; }
if (succeeded)
{
//tidy up output polygons and fix orientations where necessary ...
for (int i = 0; i < m_PolyOuts.Count; i++)
{
OutRec outRec = m_PolyOuts[i];
if (outRec.pts == null) continue;
FixupOutPolygon(outRec);
if (outRec.pts == null) continue;
if ((outRec.isHole ^ m_ReverseOutput) == (Area(outRec, m_UseFullRange) > 0))
ReversePolyPtLinks(outRec.pts);
}
JoinCommonEdges();
if (m_ForceSimple) DoSimplePolygons();
}
m_Joins.Clear();
m_HorizJoins.Clear();
return succeeded;
}
//------------------------------------------------------------------------------
private Int64 PopScanbeam()
{
Int64 Y = m_Scanbeam.Y;
Scanbeam sb2 = m_Scanbeam;
m_Scanbeam = m_Scanbeam.next;
sb2 = null;
return Y;
}
//------------------------------------------------------------------------------
private void DisposeAllPolyPts(){
for (int i = 0; i < m_PolyOuts.Count; ++i) DisposeOutRec(i);
m_PolyOuts.Clear();
}
//------------------------------------------------------------------------------
void DisposeOutRec(int index)
{
OutRec outRec = m_PolyOuts[index];
if (outRec.pts != null) DisposeOutPts(outRec.pts);
outRec = null;
m_PolyOuts[index] = null;
}
//------------------------------------------------------------------------------
private void DisposeOutPts(OutPt pp)
{
if (pp == null) return;
OutPt tmpPp = null;
pp.prev.next = null;
while (pp != null)
{
tmpPp = pp;
pp = pp.next;
tmpPp = null;
}
}
//------------------------------------------------------------------------------
private void AddJoin(TEdge e1, TEdge e2, int e1OutIdx, int e2OutIdx)
{
JoinRec jr = new JoinRec();
if (e1OutIdx >= 0)
jr.poly1Idx = e1OutIdx; else
jr.poly1Idx = e1.outIdx;
jr.pt1a = new IntPoint(e1.xcurr, e1.ycurr);
jr.pt1b = new IntPoint(e1.xtop, e1.ytop);
if (e2OutIdx >= 0)
jr.poly2Idx = e2OutIdx; else
jr.poly2Idx = e2.outIdx;
jr.pt2a = new IntPoint(e2.xcurr, e2.ycurr);
jr.pt2b = new IntPoint(e2.xtop, e2.ytop);
m_Joins.Add(jr);
}
//------------------------------------------------------------------------------
private void AddHorzJoin(TEdge e, int idx)
{
HorzJoinRec hj = new HorzJoinRec();
hj.edge = e;
hj.savedIdx = idx;
m_HorizJoins.Add(hj);
}
//------------------------------------------------------------------------------
private void InsertLocalMinimaIntoAEL(Int64 botY)
{
while( m_CurrentLM != null && ( m_CurrentLM.Y == botY ) )
{
TEdge lb = m_CurrentLM.leftBound;
TEdge rb = m_CurrentLM.rightBound;
InsertEdgeIntoAEL( lb );
InsertScanbeam( lb.ytop );
InsertEdgeIntoAEL( rb );
if (IsEvenOddFillType(lb))
{
lb.windDelta = 1;
rb.windDelta = 1;
}
else
{
rb.windDelta = -lb.windDelta;
}
SetWindingCount(lb);
rb.windCnt = lb.windCnt;
rb.windCnt2 = lb.windCnt2;
if( rb.dx == horizontal )
{
//nb: only rightbounds can have a horizontal bottom edge
AddEdgeToSEL( rb );
InsertScanbeam( rb.nextInLML.ytop );
}
else
InsertScanbeam( rb.ytop );
if( IsContributing(lb) )
AddLocalMinPoly(lb, rb, new IntPoint(lb.xcurr, m_CurrentLM.Y));
//if any output polygons share an edge, they'll need joining later ...
if (rb.outIdx >= 0 && rb.dx == horizontal)
{
for (int i = 0; i < m_HorizJoins.Count; i++)
{
IntPoint pt = new IntPoint(), pt2 = new IntPoint(); //used as dummy params.
HorzJoinRec hj = m_HorizJoins[i];
//if horizontals rb and hj.edge overlap, flag for joining later ...
if (GetOverlapSegment(new IntPoint(hj.edge.xbot, hj.edge.ybot),
new IntPoint(hj.edge.xtop, hj.edge.ytop),
new IntPoint(rb.xbot, rb.ybot),
new IntPoint(rb.xtop, rb.ytop),
ref pt, ref pt2))
AddJoin(hj.edge, rb, hj.savedIdx, -1);
}
}
if( lb.nextInAEL != rb )
{
if (rb.outIdx >= 0 && rb.prevInAEL.outIdx >= 0 &&
SlopesEqual(rb.prevInAEL, rb, m_UseFullRange))
AddJoin(rb, rb.prevInAEL, -1, -1);
TEdge e = lb.nextInAEL;
IntPoint pt = new IntPoint(lb.xcurr, lb.ycurr);
while( e != rb )
{
if(e == null)
throw new ClipperException("InsertLocalMinimaIntoAEL: missing rightbound!");
//nb: For calculating winding counts etc, IntersectEdges() assumes
//that param1 will be to the right of param2 ABOVE the intersection ...
IntersectEdges( rb , e , pt , Protects.ipNone); //order important here
e = e.nextInAEL;
}
}
PopLocalMinima();
}
}
//------------------------------------------------------------------------------
private void InsertEdgeIntoAEL(TEdge edge)
{
edge.prevInAEL = null;
edge.nextInAEL = null;
if (m_ActiveEdges == null)
{
m_ActiveEdges = edge;
}
else if( E2InsertsBeforeE1(m_ActiveEdges, edge) )
{
edge.nextInAEL = m_ActiveEdges;
m_ActiveEdges.prevInAEL = edge;
m_ActiveEdges = edge;
} else
{
TEdge e = m_ActiveEdges;
while (e.nextInAEL != null && !E2InsertsBeforeE1(e.nextInAEL, edge))
e = e.nextInAEL;
edge.nextInAEL = e.nextInAEL;
if (e.nextInAEL != null) e.nextInAEL.prevInAEL = edge;
edge.prevInAEL = e;
e.nextInAEL = edge;
}
}
//----------------------------------------------------------------------
private bool E2InsertsBeforeE1(TEdge e1, TEdge e2)
{
if (e2.xcurr == e1.xcurr)
{
if (e2.ytop > e1.ytop)
return e2.xtop < TopX(e1, e2.ytop);
else return e1.xtop > TopX(e2, e1.ytop);
}
else return e2.xcurr < e1.xcurr;
}
//------------------------------------------------------------------------------
private bool IsEvenOddFillType(TEdge edge)
{
if (edge.polyType == PolyType.ptSubject)
return m_SubjFillType == PolyFillType.pftEvenOdd;
else
return m_ClipFillType == PolyFillType.pftEvenOdd;
}
//------------------------------------------------------------------------------
private bool IsEvenOddAltFillType(TEdge edge)
{
if (edge.polyType == PolyType.ptSubject)
return m_ClipFillType == PolyFillType.pftEvenOdd;
else
return m_SubjFillType == PolyFillType.pftEvenOdd;
}
//------------------------------------------------------------------------------
private bool IsContributing(TEdge edge)
{
PolyFillType pft, pft2;
if (edge.polyType == PolyType.ptSubject)
{
pft = m_SubjFillType;
pft2 = m_ClipFillType;
}
else
{
pft = m_ClipFillType;
pft2 = m_SubjFillType;
}
switch (pft)
{
case PolyFillType.pftEvenOdd:
case PolyFillType.pftNonZero:
if (Math.Abs(edge.windCnt) != 1) return false;
break;
case PolyFillType.pftPositive:
if (edge.windCnt != 1) return false;
break;
default: //PolyFillType.pftNegative
if (edge.windCnt != -1) return false;
break;
}
switch (m_ClipType)
{
case ClipType.ctIntersection:
switch (pft2)
{
case PolyFillType.pftEvenOdd:
case PolyFillType.pftNonZero:
return (edge.windCnt2 != 0);
case PolyFillType.pftPositive:
return (edge.windCnt2 > 0);
default:
return (edge.windCnt2 < 0);
}
case ClipType.ctUnion:
switch (pft2)
{
case PolyFillType.pftEvenOdd:
case PolyFillType.pftNonZero:
return (edge.windCnt2 == 0);
case PolyFillType.pftPositive:
return (edge.windCnt2 <= 0);
default:
return (edge.windCnt2 >= 0);
}
case ClipType.ctDifference:
if (edge.polyType == PolyType.ptSubject)
switch (pft2)
{
case PolyFillType.pftEvenOdd:
case PolyFillType.pftNonZero:
return (edge.windCnt2 == 0);
case PolyFillType.pftPositive:
return (edge.windCnt2 <= 0);
default:
return (edge.windCnt2 >= 0);
}
else
switch (pft2)
{
case PolyFillType.pftEvenOdd:
case PolyFillType.pftNonZero:
return (edge.windCnt2 != 0);
case PolyFillType.pftPositive:
return (edge.windCnt2 > 0);
default:
return (edge.windCnt2 < 0);
}
}
return true;
}
//------------------------------------------------------------------------------
private void SetWindingCount(TEdge edge)
{
TEdge e = edge.prevInAEL;
//find the edge of the same polytype that immediately preceeds 'edge' in AEL
while (e != null && e.polyType != edge.polyType)
e = e.prevInAEL;
if (e == null)
{
edge.windCnt = edge.windDelta;
edge.windCnt2 = 0;
e = m_ActiveEdges; //ie get ready to calc windCnt2
}
else if (IsEvenOddFillType(edge))
{
//even-odd filling ...
edge.windCnt = 1;
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; //ie get ready to calc windCnt2
}
else
{
//nonZero filling ...
if (e.windCnt * e.windDelta < 0)
{
if (Math.Abs(e.windCnt) > 1)
{
if (e.windDelta * edge.windDelta < 0)
edge.windCnt = e.windCnt;
else
edge.windCnt = e.windCnt + edge.windDelta;
}
else
edge.windCnt = e.windCnt + e.windDelta + edge.windDelta;
}
else
{
if (Math.Abs(e.windCnt) > 1 && e.windDelta * edge.windDelta < 0)
edge.windCnt = e.windCnt;
else if (e.windCnt + edge.windDelta == 0)
edge.windCnt = e.windCnt;
else
edge.windCnt = e.windCnt + edge.windDelta;
}
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; //ie get ready to calc windCnt2
}
//update windCnt2 ...
if (IsEvenOddAltFillType(edge))
{
//even-odd filling ...
while (e != edge)
{
edge.windCnt2 = (edge.windCnt2 == 0) ? 1 : 0;
e = e.nextInAEL;
}
}
else
{
//nonZero filling ...
while (e != edge)
{
edge.windCnt2 += e.windDelta;
e = e.nextInAEL;
}
}
}
//------------------------------------------------------------------------------
private void AddEdgeToSEL(TEdge edge)
{
//SEL pointers in PEdge are reused to build a list of horizontal edges.
//However, we don't need to worry about order with horizontal edge processing.
if (m_SortedEdges == null)
{
m_SortedEdges = edge;
edge.prevInSEL = null;
edge.nextInSEL = null;
}
else
{
edge.nextInSEL = m_SortedEdges;
edge.prevInSEL = null;
m_SortedEdges.prevInSEL = edge;
m_SortedEdges = edge;
}
}
//------------------------------------------------------------------------------
private void CopyAELToSEL()
{
TEdge e = m_ActiveEdges;
m_SortedEdges = e;
while (e != null)
{
e.prevInSEL = e.prevInAEL;
e.nextInSEL = e.nextInAEL;
e = e.nextInAEL;
}
}
//------------------------------------------------------------------------------
private void SwapPositionsInAEL(TEdge edge1, TEdge edge2)
{
if (edge1.nextInAEL == edge2)
{
TEdge next = edge2.nextInAEL;
if (next != null)
next.prevInAEL = edge1;
TEdge prev = edge1.prevInAEL;
if (prev != null)
prev.nextInAEL = edge2;
edge2.prevInAEL = prev;
edge2.nextInAEL = edge1;
edge1.prevInAEL = edge2;
edge1.nextInAEL = next;
}
else if (edge2.nextInAEL == edge1)
{
TEdge next = edge1.nextInAEL;
if (next != null)
next.prevInAEL = edge2;
TEdge prev = edge2.prevInAEL;
if (prev != null)
prev.nextInAEL = edge1;
edge1.prevInAEL = prev;
edge1.nextInAEL = edge2;
edge2.prevInAEL = edge1;
edge2.nextInAEL = next;
}
else
{
TEdge next = edge1.nextInAEL;
TEdge prev = edge1.prevInAEL;
edge1.nextInAEL = edge2.nextInAEL;
if (edge1.nextInAEL != null)
edge1.nextInAEL.prevInAEL = edge1;
edge1.prevInAEL = edge2.prevInAEL;
if (edge1.prevInAEL != null)
edge1.prevInAEL.nextInAEL = edge1;
edge2.nextInAEL = next;
if (edge2.nextInAEL != null)
edge2.nextInAEL.prevInAEL = edge2;
edge2.prevInAEL = prev;
if (edge2.prevInAEL != null)
edge2.prevInAEL.nextInAEL = edge2;
}
if (edge1.prevInAEL == null)
m_ActiveEdges = edge1;
else if (edge2.prevInAEL == null)
m_ActiveEdges = edge2;
}
//------------------------------------------------------------------------------
private void SwapPositionsInSEL(TEdge edge1, TEdge edge2)
{
if (edge1.nextInSEL == null && edge1.prevInSEL == null)
return;
if (edge2.nextInSEL == null && edge2.prevInSEL == null)
return;
if (edge1.nextInSEL == edge2)
{
TEdge next = edge2.nextInSEL;
if (next != null)
next.prevInSEL = edge1;
TEdge prev = edge1.prevInSEL;
if (prev != null)
prev.nextInSEL = edge2;
edge2.prevInSEL = prev;
edge2.nextInSEL = edge1;
edge1.prevInSEL = edge2;
edge1.nextInSEL = next;
}
else if (edge2.nextInSEL == edge1)
{
TEdge next = edge1.nextInSEL;
if (next != null)
next.prevInSEL = edge2;
TEdge prev = edge2.prevInSEL;
if (prev != null)
prev.nextInSEL = edge1;
edge1.prevInSEL = prev;
edge1.nextInSEL = edge2;
edge2.prevInSEL = edge1;
edge2.nextInSEL = next;
}
else
{
TEdge next = edge1.nextInSEL;
TEdge prev = edge1.prevInSEL;
edge1.nextInSEL = edge2.nextInSEL;
if (edge1.nextInSEL != null)
edge1.nextInSEL.prevInSEL = edge1;
edge1.prevInSEL = edge2.prevInSEL;
if (edge1.prevInSEL != null)
edge1.prevInSEL.nextInSEL = edge1;
edge2.nextInSEL = next;
if (edge2.nextInSEL != null)
edge2.nextInSEL.prevInSEL = edge2;
edge2.prevInSEL = prev;
if (edge2.prevInSEL != null)
edge2.prevInSEL.nextInSEL = edge2;
}
if (edge1.prevInSEL == null)
m_SortedEdges = edge1;
else if (edge2.prevInSEL == null)
m_SortedEdges = edge2;
}
//------------------------------------------------------------------------------
private void AddLocalMaxPoly(TEdge e1, TEdge e2, IntPoint pt)
{
AddOutPt(e1, pt);
if (e1.outIdx == e2.outIdx)
{
e1.outIdx = -1;
e2.outIdx = -1;
}
else if (e1.outIdx < e2.outIdx)
AppendPolygon(e1, e2);
else
AppendPolygon(e2, e1);
}
//------------------------------------------------------------------------------
private void AddLocalMinPoly(TEdge e1, TEdge e2, IntPoint pt)
{
TEdge e, prevE;
if (e2.dx == horizontal || (e1.dx > e2.dx))
{
AddOutPt(e1, pt);
e2.outIdx = e1.outIdx;
e1.side = EdgeSide.esLeft;
e2.side = EdgeSide.esRight;
e = e1;
if (e.prevInAEL == e2)
prevE = e2.prevInAEL;
else
prevE = e.prevInAEL;
}
else
{
AddOutPt(e2, pt);
e1.outIdx = e2.outIdx;
e1.side = EdgeSide.esRight;
e2.side = EdgeSide.esLeft;
e = e2;
if (e.prevInAEL == e1)
prevE = e1.prevInAEL;
else
prevE = e.prevInAEL;
}
if (prevE != null && prevE.outIdx >= 0 &&
(TopX(prevE, pt.Y) == TopX(e, pt.Y)) &&
SlopesEqual(e, prevE, m_UseFullRange))
AddJoin(e, prevE, -1, -1);
}
//------------------------------------------------------------------------------
private OutRec CreateOutRec()
{
OutRec result = new OutRec();
result.idx = -1;
result.isHole = false;
result.FirstLeft = null;
result.pts = null;
result.bottomPt = null;
result.polyNode = null;
m_PolyOuts.Add(result);
result.idx = m_PolyOuts.Count - 1;
return result;
}
//------------------------------------------------------------------------------
private void AddOutPt(TEdge e, IntPoint pt)
{
bool ToFront = (e.side == EdgeSide.esLeft);
if( e.outIdx < 0 )
{
OutRec outRec = CreateOutRec();
e.outIdx = outRec.idx;
OutPt op = new OutPt();
outRec.pts = op;
op.pt = pt;
op.idx = outRec.idx;
op.next = op;
op.prev = op;
SetHoleState(e, outRec);
} else
{
OutRec outRec = m_PolyOuts[e.outIdx];
OutPt op = outRec.pts, op2;
if (ToFront && PointsEqual(pt, op.pt) ||
(!ToFront && PointsEqual(pt, op.prev.pt))) return;
op2 = new OutPt();
op2.pt = pt;
op2.idx = outRec.idx;
op2.next = op;
op2.prev = op.prev;
op2.prev.next = op2;
op.prev = op2;
if (ToFront) outRec.pts = op2;
}
}
//------------------------------------------------------------------------------
internal void SwapPoints(ref IntPoint pt1, ref IntPoint pt2)
{
IntPoint tmp = pt1;
pt1 = pt2;
pt2 = tmp;
}
//------------------------------------------------------------------------------
private bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,
IntPoint pt2b, ref IntPoint pt1, ref IntPoint pt2)
{
//precondition: segments are colinear.
if (Math.Abs(pt1a.X - pt1b.X) > Math.Abs(pt1a.Y - pt1b.Y))
{
if (pt1a.X > pt1b.X) SwapPoints(ref pt1a, ref pt1b);
if (pt2a.X > pt2b.X) SwapPoints(ref pt2a, ref pt2b);
if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a;
if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b;
return pt1.X < pt2.X;
} else
{
if (pt1a.Y < pt1b.Y) SwapPoints(ref pt1a, ref pt1b);
if (pt2a.Y < pt2b.Y) SwapPoints(ref pt2a, ref pt2b);
if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a;
if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b;
return pt1.Y > pt2.Y;
}
}
//------------------------------------------------------------------------------
private bool FindSegment(ref OutPt pp, bool UseFullInt64Range,
ref IntPoint pt1, ref IntPoint pt2)
{
if (pp == null) return false;
OutPt pp2 = pp;
IntPoint pt1a = new IntPoint(pt1);
IntPoint pt2a = new IntPoint(pt2);
do
{
if (SlopesEqual(pt1a, pt2a, pp.pt, pp.prev.pt, UseFullInt64Range) &&
SlopesEqual(pt1a, pt2a, pp.pt, UseFullInt64Range) &&
GetOverlapSegment(pt1a, pt2a, pp.pt, pp.prev.pt, ref pt1, ref pt2))
return true;
pp = pp.next;
}
while (pp != pp2);
return false;
}
//------------------------------------------------------------------------------
internal bool Pt3IsBetweenPt1AndPt2(IntPoint pt1, IntPoint pt2, IntPoint pt3)
{
if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true;
else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X);
else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.Y);
}
//------------------------------------------------------------------------------
private OutPt InsertPolyPtBetween(OutPt p1, OutPt p2, IntPoint pt)
{
OutPt result = new OutPt();
result.pt = pt;
if (p2 == p1.next)
{
p1.next = result;
p2.prev = result;
result.next = p2;
result.prev = p1;
} else
{
p2.next = result;
p1.prev = result;
result.next = p1;
result.prev = p2;
}
return result;
}
//------------------------------------------------------------------------------
private void SetHoleState(TEdge e, OutRec outRec)
{
bool isHole = false;
TEdge e2 = e.prevInAEL;
while (e2 != null)
{
if (e2.outIdx >= 0)
{
isHole = !isHole;
if (outRec.FirstLeft == null)
outRec.FirstLeft = m_PolyOuts[e2.outIdx];
}
e2 = e2.prevInAEL;
}
if (isHole) outRec.isHole = true;
}
//------------------------------------------------------------------------------
private double GetDx(IntPoint pt1, IntPoint pt2)
{
if (pt1.Y == pt2.Y) return horizontal;
else return (double)(pt2.X - pt1.X) / (pt2.Y - pt1.Y);
}
//---------------------------------------------------------------------------
private bool FirstIsBottomPt(OutPt btmPt1, OutPt btmPt2)
{
OutPt p = btmPt1.prev;
while (PointsEqual(p.pt, btmPt1.pt) && (p != btmPt1)) p = p.prev;
double dx1p = Math.Abs(GetDx(btmPt1.pt, p.pt));
p = btmPt1.next;
while (PointsEqual(p.pt, btmPt1.pt) && (p != btmPt1)) p = p.next;
double dx1n = Math.Abs(GetDx(btmPt1.pt, p.pt));
p = btmPt2.prev;
while (PointsEqual(p.pt, btmPt2.pt) && (p != btmPt2)) p = p.prev;
double dx2p = Math.Abs(GetDx(btmPt2.pt, p.pt));
p = btmPt2.next;
while (PointsEqual(p.pt, btmPt2.pt) && (p != btmPt2)) p = p.next;
double dx2n = Math.Abs(GetDx(btmPt2.pt, p.pt));
return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n);
}
//------------------------------------------------------------------------------
private OutPt GetBottomPt(OutPt pp)
{
OutPt dups = null;
OutPt p = pp.next;
while (p != pp)
{
if (p.pt.Y > pp.pt.Y)
{
pp = p;
dups = null;
}
else if (p.pt.Y == pp.pt.Y && p.pt.X <= pp.pt.X)
{
if (p.pt.X < pp.pt.X)
{
dups = null;
pp = p;
} else
{
if (p.next != pp && p.prev != pp) dups = p;
}
}
p = p.next;
}
if (dups != null)
{
//there appears to be at least 2 vertices at bottomPt so ...
while (dups != p)
{
if (!FirstIsBottomPt(p, dups)) pp = dups;
dups = dups.next;
while (!PointsEqual(dups.pt, pp.pt)) dups = dups.next;
}
}
return pp;
}
//------------------------------------------------------------------------------
private OutRec GetLowermostRec(OutRec outRec1, OutRec outRec2)
{
//work out which polygon fragment has the correct hole state ...
if (outRec1.bottomPt == null)
outRec1.bottomPt = GetBottomPt(outRec1.pts);
if (outRec2.bottomPt == null)
outRec2.bottomPt = GetBottomPt(outRec2.pts);
OutPt bPt1 = outRec1.bottomPt;
OutPt bPt2 = outRec2.bottomPt;
if (bPt1.pt.Y > bPt2.pt.Y) return outRec1;
else if (bPt1.pt.Y < bPt2.pt.Y) return outRec2;
else if (bPt1.pt.X < bPt2.pt.X) return outRec1;
else if (bPt1.pt.X > bPt2.pt.X) return outRec2;
else if (bPt1.next == bPt1) return outRec2;
else if (bPt2.next == bPt2) return outRec1;
else if (FirstIsBottomPt(bPt1, bPt2)) return outRec1;
else return outRec2;
}
//------------------------------------------------------------------------------
bool Param1RightOfParam2(OutRec outRec1, OutRec outRec2)
{
do
{
outRec1 = outRec1.FirstLeft;
if (outRec1 == outRec2) return true;
} while (outRec1 != null);
return false;
}
//------------------------------------------------------------------------------
private OutRec GetOutRec(int idx)
{
OutRec outrec = m_PolyOuts[idx];
while (outrec != m_PolyOuts[outrec.idx])
outrec = m_PolyOuts[outrec.idx];
return outrec;
}
//------------------------------------------------------------------------------
private void AppendPolygon(TEdge e1, TEdge e2)
{
//get the start and ends of both output polygons ...
OutRec outRec1 = m_PolyOuts[e1.outIdx];
OutRec outRec2 = m_PolyOuts[e2.outIdx];
OutRec holeStateRec;
if (Param1RightOfParam2(outRec1, outRec2))
holeStateRec = outRec2;
else if (Param1RightOfParam2(outRec2, outRec1))
holeStateRec = outRec1;
else
holeStateRec = GetLowermostRec(outRec1, outRec2);
OutPt p1_lft = outRec1.pts;
OutPt p1_rt = p1_lft.prev;
OutPt p2_lft = outRec2.pts;
OutPt p2_rt = p2_lft.prev;
EdgeSide side;
//join e2 poly onto e1 poly and delete pointers to e2 ...
if( e1.side == EdgeSide.esLeft )
{
if (e2.side == EdgeSide.esLeft)
{
//z y x a b c
ReversePolyPtLinks(p2_lft);
p2_lft.next = p1_lft;
p1_lft.prev = p2_lft;
p1_rt.next = p2_rt;
p2_rt.prev = p1_rt;
outRec1.pts = p2_rt;
} else
{
//x y z a b c
p2_rt.next = p1_lft;
p1_lft.prev = p2_rt;
p2_lft.prev = p1_rt;
p1_rt.next = p2_lft;
outRec1.pts = p2_lft;
}
side = EdgeSide.esLeft;
} else
{
if (e2.side == EdgeSide.esRight)
{
//a b c z y x
ReversePolyPtLinks( p2_lft );
p1_rt.next = p2_rt;
p2_rt.prev = p1_rt;
p2_lft.next = p1_lft;
p1_lft.prev = p2_lft;
} else
{
//a b c x y z
p1_rt.next = p2_lft;
p2_lft.prev = p1_rt;
p1_lft.prev = p2_rt;
p2_rt.next = p1_lft;
}
side = EdgeSide.esRight;
}
outRec1.bottomPt = null;
if (holeStateRec == outRec2)
{
if (outRec2.FirstLeft != outRec1)
outRec1.FirstLeft = outRec2.FirstLeft;
outRec1.isHole = outRec2.isHole;
}
outRec2.pts = null;
outRec2.bottomPt = null;
outRec2.FirstLeft = outRec1;
int OKIdx = e1.outIdx;
int ObsoleteIdx = e2.outIdx;
e1.outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly
e2.outIdx = -1;
TEdge e = m_ActiveEdges;
while( e != null )
{
if( e.outIdx == ObsoleteIdx )
{
e.outIdx = OKIdx;
e.side = side;
break;
}
e = e.nextInAEL;
}
outRec2.idx = outRec1.idx;
}
//------------------------------------------------------------------------------
private void ReversePolyPtLinks(OutPt pp)
{
if (pp == null) return;
OutPt pp1;
OutPt pp2;
pp1 = pp;
do
{
pp2 = pp1.next;
pp1.next = pp1.prev;
pp1.prev = pp2;
pp1 = pp2;
} while (pp1 != pp);
}
//------------------------------------------------------------------------------
private static void SwapSides(TEdge edge1, TEdge edge2)
{
EdgeSide side = edge1.side;
edge1.side = edge2.side;
edge2.side = side;
}
//------------------------------------------------------------------------------
private static void SwapPolyIndexes(TEdge edge1, TEdge edge2)
{
int outIdx = edge1.outIdx;
edge1.outIdx = edge2.outIdx;
edge2.outIdx = outIdx;
}
//------------------------------------------------------------------------------
private void IntersectEdges(TEdge e1, TEdge e2, IntPoint pt, Protects protects)
{
//e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before
//e2 in AEL except when e1 is being inserted at the intersection point ...
bool e1stops = (Protects.ipLeft & protects) == 0 && e1.nextInLML == null &&
e1.xtop == pt.X && e1.ytop == pt.Y;
bool e2stops = (Protects.ipRight & protects) == 0 && e2.nextInLML == null &&
e2.xtop == pt.X && e2.ytop == pt.Y;
bool e1Contributing = (e1.outIdx >= 0);
bool e2contributing = (e2.outIdx >= 0);
//update winding counts...
//assumes that e1 will be to the right of e2 ABOVE the intersection
if (e1.polyType == e2.polyType)
{
if (IsEvenOddFillType(e1))
{
int oldE1WindCnt = e1.windCnt;
e1.windCnt = e2.windCnt;
e2.windCnt = oldE1WindCnt;
}
else
{
if (e1.windCnt + e2.windDelta == 0) e1.windCnt = -e1.windCnt;
else e1.windCnt += e2.windDelta;
if (e2.windCnt - e1.windDelta == 0) e2.windCnt = -e2.windCnt;
else e2.windCnt -= e1.windDelta;
}
}
else
{
if (!IsEvenOddFillType(e2)) e1.windCnt2 += e2.windDelta;
else e1.windCnt2 = (e1.windCnt2 == 0) ? 1 : 0;
if (!IsEvenOddFillType(e1)) e2.windCnt2 -= e1.windDelta;
else e2.windCnt2 = (e2.windCnt2 == 0) ? 1 : 0;
}
PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
if (e1.polyType == PolyType.ptSubject)
{
e1FillType = m_SubjFillType;
e1FillType2 = m_ClipFillType;
}
else
{
e1FillType = m_ClipFillType;
e1FillType2 = m_SubjFillType;
}
if (e2.polyType == PolyType.ptSubject)
{
e2FillType = m_SubjFillType;
e2FillType2 = m_ClipFillType;
}
else
{
e2FillType = m_ClipFillType;
e2FillType2 = m_SubjFillType;
}
int e1Wc, e2Wc;
switch (e1FillType)
{
case PolyFillType.pftPositive: e1Wc = e1.windCnt; break;
case PolyFillType.pftNegative: e1Wc = -e1.windCnt; break;
default: e1Wc = Math.Abs(e1.windCnt); break;
}
switch (e2FillType)
{
case PolyFillType.pftPositive: e2Wc = e2.windCnt; break;
case PolyFillType.pftNegative: e2Wc = -e2.windCnt; break;
default: e2Wc = Math.Abs(e2.windCnt); break;
}
if (e1Contributing && e2contributing)
{
if ( e1stops || e2stops ||
(e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
(e1.polyType != e2.polyType && m_ClipType != ClipType.ctXor))
AddLocalMaxPoly(e1, e2, pt);
else
{
AddOutPt(e1, pt);
AddOutPt(e2, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if (e1Contributing)
{
if (e2Wc == 0 || e2Wc == 1)
{
AddOutPt(e1, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if (e2contributing)
{
if (e1Wc == 0 || e1Wc == 1)
{
AddOutPt(e2, pt);
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
}
else if ( (e1Wc == 0 || e1Wc == 1) &&
(e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops )
{
//neither edge is currently contributing ...
Int64 e1Wc2, e2Wc2;
switch (e1FillType2)
{
case PolyFillType.pftPositive: e1Wc2 = e1.windCnt2; break;
case PolyFillType.pftNegative: e1Wc2 = -e1.windCnt2; break;
default: e1Wc2 = Math.Abs(e1.windCnt2); break;
}
switch (e2FillType2)
{
case PolyFillType.pftPositive: e2Wc2 = e2.windCnt2; break;
case PolyFillType.pftNegative: e2Wc2 = -e2.windCnt2; break;
default: e2Wc2 = Math.Abs(e2.windCnt2); break;
}
if (e1.polyType != e2.polyType)
AddLocalMinPoly(e1, e2, pt);
else if (e1Wc == 1 && e2Wc == 1)
switch (m_ClipType)
{
case ClipType.ctIntersection:
if (e1Wc2 > 0 && e2Wc2 > 0)
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctUnion:
if (e1Wc2 <= 0 && e2Wc2 <= 0)
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctDifference:
if (((e1.polyType == PolyType.ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) ||
((e1.polyType == PolyType.ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0)))
AddLocalMinPoly(e1, e2, pt);
break;
case ClipType.ctXor:
AddLocalMinPoly(e1, e2, pt);
break;
}
else
SwapSides(e1, e2);
}
if ((e1stops != e2stops) &&
((e1stops && (e1.outIdx >= 0)) || (e2stops && (e2.outIdx >= 0))))
{
SwapSides(e1, e2);
SwapPolyIndexes(e1, e2);
}
//finally, delete any non-contributing maxima edges ...
if (e1stops) DeleteFromAEL(e1);
if (e2stops) DeleteFromAEL(e2);
}
//------------------------------------------------------------------------------
private void DeleteFromAEL(TEdge e)
{
TEdge AelPrev = e.prevInAEL;
TEdge AelNext = e.nextInAEL;
if (AelPrev == null && AelNext == null && (e != m_ActiveEdges))
return; //already deleted
if (AelPrev != null)
AelPrev.nextInAEL = AelNext;
else m_ActiveEdges = AelNext;
if (AelNext != null)
AelNext.prevInAEL = AelPrev;
e.nextInAEL = null;
e.prevInAEL = null;
}
//------------------------------------------------------------------------------
private void DeleteFromSEL(TEdge e)
{
TEdge SelPrev = e.prevInSEL;
TEdge SelNext = e.nextInSEL;
if (SelPrev == null && SelNext == null && (e != m_SortedEdges))
return; //already deleted
if (SelPrev != null)
SelPrev.nextInSEL = SelNext;
else m_SortedEdges = SelNext;
if (SelNext != null)
SelNext.prevInSEL = SelPrev;
e.nextInSEL = null;
e.prevInSEL = null;
}
//------------------------------------------------------------------------------
private void UpdateEdgeIntoAEL(ref TEdge e)
{
if (e.nextInLML == null)
throw new ClipperException("UpdateEdgeIntoAEL: invalid call");
TEdge AelPrev = e.prevInAEL;
TEdge AelNext = e.nextInAEL;
e.nextInLML.outIdx = e.outIdx;
if (AelPrev != null)
AelPrev.nextInAEL = e.nextInLML;
else m_ActiveEdges = e.nextInLML;
if (AelNext != null)
AelNext.prevInAEL = e.nextInLML;
e.nextInLML.side = e.side;
e.nextInLML.windDelta = e.windDelta;
e.nextInLML.windCnt = e.windCnt;
e.nextInLML.windCnt2 = e.windCnt2;
e = e.nextInLML;
e.prevInAEL = AelPrev;
e.nextInAEL = AelNext;
if (e.dx != horizontal) InsertScanbeam(e.ytop);
}
//------------------------------------------------------------------------------
private void ProcessHorizontals()
{
TEdge horzEdge = m_SortedEdges;
while (horzEdge != null)
{
DeleteFromSEL(horzEdge);
ProcessHorizontal(horzEdge);
horzEdge = m_SortedEdges;
}
}
//------------------------------------------------------------------------------
private void ProcessHorizontal(TEdge horzEdge)
{
Direction Direction;
Int64 horzLeft, horzRight;
if (horzEdge.xcurr < horzEdge.xtop)
{
horzLeft = horzEdge.xcurr;
horzRight = horzEdge.xtop;
Direction = Direction.dLeftToRight;
}
else
{
horzLeft = horzEdge.xtop;
horzRight = horzEdge.xcurr;
Direction = Direction.dRightToLeft;
}
TEdge eMaxPair;
if (horzEdge.nextInLML != null)
eMaxPair = null;
else
eMaxPair = GetMaximaPair(horzEdge);
TEdge e = GetNextInAEL(horzEdge, Direction);
while (e != null)
{
if (e.xcurr == horzEdge.xtop && eMaxPair == null)
{
if (SlopesEqual(e, horzEdge.nextInLML, m_UseFullRange))
{
//if output polygons share an edge, they'll need joining later ...
if (horzEdge.outIdx >= 0 && e.outIdx >= 0)
AddJoin(horzEdge.nextInLML, e, horzEdge.outIdx, -1);
break; //we've reached the end of the horizontal line
}
else if (e.dx < horzEdge.nextInLML.dx)
//we really have got to the end of the intermediate horz edge so quit.
//nb: More -ve slopes follow more +ve slopes ABOVE the horizontal.
break;
}
TEdge eNext = GetNextInAEL(e, Direction);
if (eMaxPair != null ||
((Direction == Direction.dLeftToRight) && (e.xcurr < horzRight)) ||
((Direction == Direction.dRightToLeft) && (e.xcurr > horzLeft)))
{
//so far we're still in range of the horizontal edge
if (e == eMaxPair)
{
//horzEdge is evidently a maxima horizontal and we've arrived at its end.
if (Direction == Direction.dLeftToRight)
IntersectEdges(horzEdge, e, new IntPoint(e.xcurr, horzEdge.ycurr), 0);
else
IntersectEdges(e, horzEdge, new IntPoint(e.xcurr, horzEdge.ycurr), 0);
if (eMaxPair.outIdx >= 0) throw new ClipperException("ProcessHorizontal error");
return;
}
else if (e.dx == horizontal && !IsMinima(e) && !(e.xcurr > e.xtop))
{
if (Direction == Direction.dLeftToRight)
IntersectEdges(horzEdge, e, new IntPoint(e.xcurr, horzEdge.ycurr),
(IsTopHorz(horzEdge, e.xcurr)) ? Protects.ipLeft : Protects.ipBoth);
else
IntersectEdges(e, horzEdge, new IntPoint(e.xcurr, horzEdge.ycurr),
(IsTopHorz(horzEdge, e.xcurr)) ? Protects.ipRight : Protects.ipBoth);
}
else if (Direction == Direction.dLeftToRight)
{
IntersectEdges(horzEdge, e, new IntPoint(e.xcurr, horzEdge.ycurr),
(IsTopHorz(horzEdge, e.xcurr)) ? Protects.ipLeft : Protects.ipBoth);
}
else
{
IntersectEdges(e, horzEdge, new IntPoint(e.xcurr, horzEdge.ycurr),
(IsTopHorz(horzEdge, e.xcurr)) ? Protects.ipRight : Protects.ipBoth);
}
SwapPositionsInAEL(horzEdge, e);
}
else if ( (Direction == Direction.dLeftToRight && e.xcurr >= horzRight) ||
(Direction == Direction.dRightToLeft && e.xcurr <= horzLeft) ) break;
e = eNext;
} //end while ( e )
if (horzEdge.nextInLML != null)
{
if (horzEdge.outIdx >= 0)
AddOutPt(horzEdge, new IntPoint(horzEdge.xtop, horzEdge.ytop));
UpdateEdgeIntoAEL(ref horzEdge);
}
else
{
if (horzEdge.outIdx >= 0)
IntersectEdges(horzEdge, eMaxPair,
new IntPoint(horzEdge.xtop, horzEdge.ycurr), Protects.ipBoth);
DeleteFromAEL(eMaxPair);
DeleteFromAEL(horzEdge);
}
}
//------------------------------------------------------------------------------
private bool IsTopHorz(TEdge horzEdge, double XPos)
{
TEdge e = m_SortedEdges;
while (e != null)
{
if ((XPos >= Math.Min(e.xcurr, e.xtop)) && (XPos <= Math.Max(e.xcurr, e.xtop)))
return false;
e = e.nextInSEL;
}
return true;
}
//------------------------------------------------------------------------------
private TEdge GetNextInAEL(TEdge e, Direction Direction)
{
return Direction == Direction.dLeftToRight ? e.nextInAEL: e.prevInAEL;
}
//------------------------------------------------------------------------------
private bool IsMinima(TEdge e)
{
return e != null && (e.prev.nextInLML != e) && (e.next.nextInLML != e);
}
//------------------------------------------------------------------------------
private bool IsMaxima(TEdge e, double Y)
{
return (e != null && e.ytop == Y && e.nextInLML == null);
}
//------------------------------------------------------------------------------
private bool IsIntermediate(TEdge e, double Y)
{
return (e.ytop == Y && e.nextInLML != null);
}
//------------------------------------------------------------------------------
private TEdge GetMaximaPair(TEdge e)
{
if (!IsMaxima(e.next, e.ytop) || (e.next.xtop != e.xtop))
return e.prev; else
return e.next;
}
//------------------------------------------------------------------------------
private bool ProcessIntersections(Int64 botY, Int64 topY)
{
if( m_ActiveEdges == null ) return true;
try {
BuildIntersectList(botY, topY);
if ( m_IntersectNodes == null) return true;
if (m_IntersectNodes.next == null || FixupIntersectionOrder())
ProcessIntersectList();
else
return false;
}
catch {
m_SortedEdges = null;
DisposeIntersectNodes();
throw new ClipperException("ProcessIntersections error");
}
m_SortedEdges = null;
return true;
}
//------------------------------------------------------------------------------
private void BuildIntersectList(Int64 botY, Int64 topY)
{
if ( m_ActiveEdges == null ) return;
//prepare for sorting ...
TEdge e = m_ActiveEdges;
m_SortedEdges = e;
while( e != null )
{
e.prevInSEL = e.prevInAEL;
e.nextInSEL = e.nextInAEL;
e.xcurr = TopX( e, topY );
e = e.nextInAEL;
}
//bubblesort ...
bool isModified = true;
while( isModified && m_SortedEdges != null )
{
isModified = false;
e = m_SortedEdges;
while( e.nextInSEL != null )
{
TEdge eNext = e.nextInSEL;
IntPoint pt = new IntPoint();
if (e.xcurr > eNext.xcurr)
{
if (!IntersectPoint(e, eNext, ref pt) && e.xcurr > eNext.xcurr +1)
throw new ClipperException("Intersection error");
if (pt.Y > botY)
{
pt.Y = botY;
pt.X = TopX(e, pt.Y);
}
InsertIntersectNode(e, eNext, pt);
SwapPositionsInSEL(e, eNext);
isModified = true;
}
else
e = eNext;
}
if( e.prevInSEL != null ) e.prevInSEL.nextInSEL = null;
else break;
}
m_SortedEdges = null;
}
//------------------------------------------------------------------------------
private bool EdgesAdjacent(IntersectNode inode)
{
return (inode.edge1.nextInSEL == inode.edge2) ||
(inode.edge1.prevInSEL == inode.edge2);
}
//------------------------------------------------------------------------------
private bool FixupIntersectionOrder()
{
//pre-condition: intersections are sorted bottom-most (then left-most) first.
//Now it's crucial that intersections are made only between adjacent edges,
//so to ensure this the order of intersections may need adjusting ...
IntersectNode inode = m_IntersectNodes;
CopyAELToSEL();
while (inode != null)
{
if (!EdgesAdjacent(inode))
{
IntersectNode nextNode = inode.next;
while (nextNode != null && !EdgesAdjacent(nextNode))
nextNode = nextNode.next;
if (nextNode == null)
return false;
SwapIntersectNodes(inode, nextNode);
}
SwapPositionsInSEL(inode.edge1, inode.edge2);
inode = inode.next;
}
return true;
}
//------------------------------------------------------------------------------
private void ProcessIntersectList()
{
while (m_IntersectNodes != null)
{
IntersectNode iNode = m_IntersectNodes.next;
{
IntersectEdges( m_IntersectNodes.edge1 ,
m_IntersectNodes.edge2 , m_IntersectNodes.pt, Protects.ipBoth );
SwapPositionsInAEL( m_IntersectNodes.edge1 , m_IntersectNodes.edge2 );
}
m_IntersectNodes = null;
m_IntersectNodes = iNode;
}
}
//------------------------------------------------------------------------------
private static Int64 Round(double value)
{
return value < 0 ? (Int64)(value - 0.5) : (Int64)(value + 0.5);
}
//------------------------------------------------------------------------------
private static Int64 TopX(TEdge edge, Int64 currentY)
{
if (currentY == edge.ytop)
return edge.xtop;
return edge.xbot + Round(edge.dx *(currentY - edge.ybot));
}
//------------------------------------------------------------------------------
private void InsertIntersectNode(TEdge e1, TEdge e2, IntPoint pt)
{
IntersectNode newNode = new IntersectNode();
newNode.edge1 = e1;
newNode.edge2 = e2;
newNode.pt = pt;
newNode.next = null;
if (m_IntersectNodes == null) m_IntersectNodes = newNode;
else if (newNode.pt.Y > m_IntersectNodes.pt.Y)
{
newNode.next = m_IntersectNodes;
m_IntersectNodes = newNode;
}
else
{
IntersectNode iNode = m_IntersectNodes;
while (iNode.next != null && newNode.pt.Y < iNode.next.pt.Y)
iNode = iNode.next;
newNode.next = iNode.next;
iNode.next = newNode;
}
}
//------------------------------------------------------------------------------
private void SwapIntersectNodes(IntersectNode int1, IntersectNode int2)
{
TEdge e1 = int1.edge1;
TEdge e2 = int1.edge2;
IntPoint p = int1.pt;
int1.edge1 = int2.edge1;
int1.edge2 = int2.edge2;
int1.pt = int2.pt;
int2.edge1 = e1;
int2.edge2 = e2;
int2.pt = p;
}
//------------------------------------------------------------------------------
private bool IntersectPoint(TEdge edge1, TEdge edge2, ref IntPoint ip)
{
double b1, b2;
if (SlopesEqual(edge1, edge2, m_UseFullRange))
{
if (edge2.ybot > edge1.ybot)
ip.Y = edge2.ybot;
else
ip.Y = edge1.ybot;
return false;
}
else if (edge1.dx == 0)
{
ip.X = edge1.xbot;
if (edge2.dx == horizontal)
{
ip.Y = edge2.ybot;
}
else
{
b2 = edge2.ybot - (edge2.xbot / edge2.dx);
ip.Y = Round(ip.X / edge2.dx + b2);
}
}
else if (edge2.dx == 0)
{
ip.X = edge2.xbot;
if (edge1.dx == horizontal)
{
ip.Y = edge1.ybot;
}
else
{
b1 = edge1.ybot - (edge1.xbot / edge1.dx);
ip.Y = Round(ip.X / edge1.dx + b1);
}
}
else
{
b1 = edge1.xbot - edge1.ybot * edge1.dx;
b2 = edge2.xbot - edge2.ybot * edge2.dx;
double q = (b2 - b1) / (edge1.dx - edge2.dx);
ip.Y = Round(q);
if (Math.Abs(edge1.dx) < Math.Abs(edge2.dx))
ip.X = Round(edge1.dx * q + b1);
else
ip.X = Round(edge2.dx * q + b2);
}
if (ip.Y < edge1.ytop || ip.Y < edge2.ytop)
{
if (edge1.ytop > edge2.ytop)
{
ip.X = edge1.xtop;
ip.Y = edge1.ytop;
return TopX(edge2, edge1.ytop) < edge1.xtop;
}
else
{
ip.X = edge2.xtop;
ip.Y = edge2.ytop;
return TopX(edge1, edge2.ytop) > edge2.xtop;
}
}
else
return true;
}
//------------------------------------------------------------------------------
private void DisposeIntersectNodes()
{
while ( m_IntersectNodes != null )
{
IntersectNode iNode = m_IntersectNodes.next;
m_IntersectNodes = null;
m_IntersectNodes = iNode;
}
}
//------------------------------------------------------------------------------
private void ProcessEdgesAtTopOfScanbeam(Int64 topY)
{
TEdge e = m_ActiveEdges;
while( e != null )
{
//1. process maxima, treating them as if they're 'bent' horizontal edges,
// but exclude maxima with horizontal edges. nb: e can't be a horizontal.
if( IsMaxima(e, topY) && GetMaximaPair(e).dx != horizontal )
{
//'e' might be removed from AEL, as may any following edges so ...
TEdge ePrev = e.prevInAEL;
DoMaxima(e, topY);
if( ePrev == null ) e = m_ActiveEdges;
else e = ePrev.nextInAEL;
}
else
{
bool intermediateVert = IsIntermediate(e, topY);
//2. promote horizontal edges, otherwise update xcurr and ycurr ...
if (intermediateVert && e.nextInLML.dx == horizontal)
{
if (e.outIdx >= 0)
{
AddOutPt(e, new IntPoint(e.xtop, e.ytop));
for (int i = 0; i < m_HorizJoins.Count; ++i)
{
IntPoint pt = new IntPoint(), pt2 = new IntPoint();
HorzJoinRec hj = m_HorizJoins[i];
if (GetOverlapSegment(new IntPoint(hj.edge.xbot, hj.edge.ybot),
new IntPoint(hj.edge.xtop, hj.edge.ytop),
new IntPoint(e.nextInLML.xbot, e.nextInLML.ybot),
new IntPoint(e.nextInLML.xtop, e.nextInLML.ytop), ref pt, ref pt2))
AddJoin(hj.edge, e.nextInLML, hj.savedIdx, e.outIdx);
}
AddHorzJoin(e.nextInLML, e.outIdx);
}
UpdateEdgeIntoAEL(ref e);
AddEdgeToSEL(e);
}
else
{
e.xcurr = TopX( e, topY );
e.ycurr = topY;
if (m_ForceSimple && e.prevInAEL != null &&
e.prevInAEL.xcurr == e.xcurr &&
e.outIdx >= 0 && e.prevInAEL.outIdx >= 0)
{
if (intermediateVert)
AddOutPt(e.prevInAEL, new IntPoint(e.xcurr, topY));
else
AddOutPt(e, new IntPoint(e.xcurr, topY));
}
}
e = e.nextInAEL;
}
}
//3. Process horizontals at the top of the scanbeam ...
ProcessHorizontals();
//4. Promote intermediate vertices ...
e = m_ActiveEdges;
while( e != null )
{
if( IsIntermediate( e, topY ) )
{
if (e.outIdx >= 0) AddOutPt(e, new IntPoint(e.xtop, e.ytop));
UpdateEdgeIntoAEL(ref e);
//if output polygons share an edge, they'll need joining later ...
TEdge ePrev = e.prevInAEL;
TEdge eNext = e.nextInAEL;
if (ePrev != null && ePrev.xcurr == e.xbot &&
ePrev.ycurr == e.ybot && e.outIdx >= 0 &&
ePrev.outIdx >= 0 && ePrev.ycurr > ePrev.ytop &&
SlopesEqual(e, ePrev, m_UseFullRange))
{
AddOutPt(ePrev, new IntPoint(e.xbot, e.ybot));
AddJoin(e, ePrev, -1, -1);
}
else if (eNext != null && eNext.xcurr == e.xbot &&
eNext.ycurr == e.ybot && e.outIdx >= 0 &&
eNext.outIdx >= 0 && eNext.ycurr > eNext.ytop &&
SlopesEqual(e, eNext, m_UseFullRange))
{
AddOutPt(eNext, new IntPoint(e.xbot, e.ybot));
AddJoin(e, eNext, -1, -1);
}
}
e = e.nextInAEL;
}
}
//------------------------------------------------------------------------------
private void DoMaxima(TEdge e, Int64 topY)
{
TEdge eMaxPair = GetMaximaPair(e);
Int64 X = e.xtop;
TEdge eNext = e.nextInAEL;
while( eNext != eMaxPair )
{
if (eNext == null) throw new ClipperException("DoMaxima error");
IntersectEdges( e, eNext, new IntPoint(X, topY), Protects.ipBoth );
SwapPositionsInAEL(e, eNext);
eNext = e.nextInAEL;
}
if( e.outIdx < 0 && eMaxPair.outIdx < 0 )
{
DeleteFromAEL( e );
DeleteFromAEL( eMaxPair );
}
else if( e.outIdx >= 0 && eMaxPair.outIdx >= 0 )
{
IntersectEdges(e, eMaxPair, new IntPoint(X, topY), Protects.ipNone);
}
else throw new ClipperException("DoMaxima error");
}
//------------------------------------------------------------------------------
public static void ReversePolygons(Polygons polys)
{
polys.ForEach(delegate(Polygon poly) { poly.Reverse(); });
}
//------------------------------------------------------------------------------
public static bool Orientation(Polygon poly)
{
return Area(poly) >= 0;
}
//------------------------------------------------------------------------------
private int PointCount(OutPt pts)
{
if (pts == null) return 0;
int result = 0;
OutPt p = pts;
do
{
result++;
p = p.next;
}
while (p != pts);
return result;
}
//------------------------------------------------------------------------------
private void BuildResult(Polygons polyg)
{
polyg.Clear();
polyg.Capacity = m_PolyOuts.Count;
for (int i = 0; i < m_PolyOuts.Count; i++)
{
OutRec outRec = m_PolyOuts[i];
if (outRec.pts == null) continue;
OutPt p = outRec.pts;
int cnt = PointCount(p);
if (cnt < 3) continue;
Polygon pg = new Polygon(cnt);
for (int j = 0; j < cnt; j++)
{
pg.Add(p.pt);
p = p.prev;
}
polyg.Add(pg);
}
}
//------------------------------------------------------------------------------
private void BuildResult2(PolyTree polytree)
{
polytree.Clear();
//add each output polygon/contour to polytree ...
polytree.m_AllPolys.Capacity = m_PolyOuts.Count;
for (int i = 0; i < m_PolyOuts.Count; i++)
{
OutRec outRec = m_PolyOuts[i];
int cnt = PointCount(outRec.pts);
if (cnt < 3) continue;
FixHoleLinkage(outRec);
PolyNode pn = new PolyNode();
polytree.m_AllPolys.Add(pn);
outRec.polyNode = pn;
pn.m_polygon.Capacity = cnt;
OutPt op = outRec.pts;
for (int j = 0; j < cnt; j++)
{
pn.m_polygon.Add(op.pt);
op = op.prev;
}
}
//fixup PolyNode links etc ...
polytree.m_Childs.Capacity = m_PolyOuts.Count;
for (int i = 0; i < m_PolyOuts.Count; i++)
{
OutRec outRec = m_PolyOuts[i];
if (outRec.polyNode == null) continue;
if (outRec.FirstLeft == null)
polytree.AddChild(outRec.polyNode);
else
outRec.FirstLeft.polyNode.AddChild(outRec.polyNode);
}
}
//------------------------------------------------------------------------------
private void FixupOutPolygon(OutRec outRec)
{
//FixupOutPolygon() - removes duplicate points and simplifies consecutive
//parallel edges by removing the middle vertex.
OutPt lastOK = null;
outRec.bottomPt = null;
OutPt pp = outRec.pts;
for (;;)
{
if (pp.prev == pp || pp.prev == pp.next)
{
DisposeOutPts(pp);
outRec.pts = null;
return;
}
//test for duplicate points and for same slope (cross-product) ...
if (PointsEqual(pp.pt, pp.next.pt) ||
SlopesEqual(pp.prev.pt, pp.pt, pp.next.pt, m_UseFullRange))
{
lastOK = null;
OutPt tmp = pp;
pp.prev.next = pp.next;
pp.next.prev = pp.prev;
pp = pp.prev;
tmp = null;
}
else if (pp == lastOK) break;
else
{
if (lastOK == null) lastOK = pp;
pp = pp.next;
}
}
outRec.pts = pp;
}
//------------------------------------------------------------------------------
private bool JoinPoints(JoinRec j, out OutPt p1, out OutPt p2)
{
p1 = null; p2 = null;
OutRec outRec1 = m_PolyOuts[j.poly1Idx];
OutRec outRec2 = m_PolyOuts[j.poly2Idx];
if (outRec1 == null || outRec2 == null) return false;
OutPt pp1a = outRec1.pts;
OutPt pp2a = outRec2.pts;
IntPoint pt1 = j.pt2a, pt2 = j.pt2b;
IntPoint pt3 = j.pt1a, pt4 = j.pt1b;
if (!FindSegment(ref pp1a, m_UseFullRange, ref pt1, ref pt2)) return false;
if (outRec1 == outRec2)
{
//we're searching the same polygon for overlapping segments so
//segment 2 mustn't be the same as segment 1 ...
pp2a = pp1a.next;
if (!FindSegment(ref pp2a, m_UseFullRange, ref pt3, ref pt4) || (pp2a == pp1a))
return false;
}
else if (!FindSegment(ref pp2a, m_UseFullRange, ref pt3, ref pt4)) return false;
if (!GetOverlapSegment(pt1, pt2, pt3, pt4, ref pt1, ref pt2)) return false;
OutPt p3, p4, prev = pp1a.prev;
//get p1 & p2 polypts - the overlap start & endpoints on poly1
if (PointsEqual(pp1a.pt, pt1)) p1 = pp1a;
else if (PointsEqual(prev.pt, pt1)) p1 = prev;
else p1 = InsertPolyPtBetween(pp1a, prev, pt1);
if (PointsEqual(pp1a.pt, pt2)) p2 = pp1a;
else if (PointsEqual(prev.pt, pt2)) p2 = prev;
else if ((p1 == pp1a) || (p1 == prev))
p2 = InsertPolyPtBetween(pp1a, prev, pt2);
else if (Pt3IsBetweenPt1AndPt2(pp1a.pt, p1.pt, pt2))
p2 = InsertPolyPtBetween(pp1a, p1, pt2); else
p2 = InsertPolyPtBetween(p1, prev, pt2);
//get p3 & p4 polypts - the overlap start & endpoints on poly2
prev = pp2a.prev;
if (PointsEqual(pp2a.pt, pt1)) p3 = pp2a;
else if (PointsEqual(prev.pt, pt1)) p3 = prev;
else p3 = InsertPolyPtBetween(pp2a, prev, pt1);
if (PointsEqual(pp2a.pt, pt2)) p4 = pp2a;
else if (PointsEqual(prev.pt, pt2)) p4 = prev;
else if ((p3 == pp2a) || (p3 == prev))
p4 = InsertPolyPtBetween(pp2a, prev, pt2);
else if (Pt3IsBetweenPt1AndPt2(pp2a.pt, p3.pt, pt2))
p4 = InsertPolyPtBetween(pp2a, p3, pt2); else
p4 = InsertPolyPtBetween(p3, prev, pt2);
//p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ...
if (p1.next == p2 && p3.prev == p4)
{
p1.next = p3;
p3.prev = p1;
p2.prev = p4;
p4.next = p2;
return true;
}
else if (p1.prev == p2 && p3.next == p4)
{
p1.prev = p3;
p3.next = p1;
p2.next = p4;
p4.prev = p2;
return true;
}
else
return false; //an orientation is probably wrong
}
//----------------------------------------------------------------------
private void FixupJoinRecs(JoinRec j, OutPt pt, int startIdx)
{
for (int k = startIdx; k < m_Joins.Count; k++)
{
JoinRec j2 = m_Joins[k];
if (j2.poly1Idx == j.poly1Idx && PointIsVertex(j2.pt1a, pt))
j2.poly1Idx = j.poly2Idx;
if (j2.poly2Idx == j.poly1Idx && PointIsVertex(j2.pt2a, pt))
j2.poly2Idx = j.poly2Idx;
}
}
//----------------------------------------------------------------------
private bool Poly2ContainsPoly1(OutPt outPt1, OutPt outPt2, bool UseFullInt64Range)
{
OutPt pt = outPt1;
//Because the polygons may be touching, we need to find a vertex that
//isn't touching the other polygon ...
if (PointOnPolygon(pt.pt, outPt2, UseFullInt64Range))
{
pt = pt.next;
while (pt != outPt1 && PointOnPolygon(pt.pt, outPt2, UseFullInt64Range))
pt = pt.next;
if (pt == outPt1) return true;
}
return PointInPolygon(pt.pt, outPt2, UseFullInt64Range);
}
//----------------------------------------------------------------------
private void FixupFirstLefts1(OutRec OldOutRec, OutRec NewOutRec)
{
for (int i = 0; i < m_PolyOuts.Count; i++)
{
OutRec outRec = m_PolyOuts[i];
if (outRec.pts != null && outRec.FirstLeft == OldOutRec)
{
if (Poly2ContainsPoly1(outRec.pts, NewOutRec.pts, m_UseFullRange))
outRec.FirstLeft = NewOutRec;
}
}
}
//----------------------------------------------------------------------
private void FixupFirstLefts2(OutRec OldOutRec, OutRec NewOutRec)
{
foreach (OutRec outRec in m_PolyOuts)
if (outRec.FirstLeft == OldOutRec) outRec.FirstLeft = NewOutRec;
}
//----------------------------------------------------------------------
private void JoinCommonEdges()
{
for (int i = 0; i < m_Joins.Count; i++)
{
JoinRec j = m_Joins[i];
OutRec outRec1 = GetOutRec(j.poly1Idx);
OutRec outRec2 = GetOutRec(j.poly2Idx);
if (outRec1.pts == null || outRec2.pts == null) continue;
//get the polygon fragment with the correct hole state (FirstLeft)
//before calling JoinPoints() ...
OutRec holeStateRec;
if (outRec1 == outRec2) holeStateRec = outRec1;
else if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2;
else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1;
else holeStateRec = GetLowermostRec(outRec1, outRec2);
OutPt p1, p2;
if (!JoinPoints(j, out p1, out p2)) continue;
if (outRec1 == outRec2)
{
//instead of joining two polygons, we've just created a new one by
//splitting one polygon into two.
outRec1.pts = p1;
outRec1.bottomPt = null;
outRec2 = CreateOutRec();
outRec2.pts = p2;
if (Poly2ContainsPoly1(outRec2.pts, outRec1.pts, m_UseFullRange))
{
//outRec2 is contained by outRec1 ...
outRec2.isHole = !outRec1.isHole;
outRec2.FirstLeft = outRec1;
FixupJoinRecs(j, p2, i + 1);
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
FixupOutPolygon(outRec1); //nb: do this BEFORE testing orientation
FixupOutPolygon(outRec2); // but AFTER calling FixupJoinRecs()
if ((outRec2.isHole ^ m_ReverseOutput) == (Area(outRec2, m_UseFullRange) > 0))
ReversePolyPtLinks(outRec2.pts);
}
else if (Poly2ContainsPoly1(outRec1.pts, outRec2.pts, m_UseFullRange))
{
//outRec1 is contained by outRec2 ...
outRec2.isHole = outRec1.isHole;
outRec1.isHole = !outRec2.isHole;
outRec2.FirstLeft = outRec1.FirstLeft;
outRec1.FirstLeft = outRec2;
FixupJoinRecs(j, p2, i + 1);
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (m_UsingPolyTree) FixupFirstLefts2(outRec1, outRec2);
FixupOutPolygon(outRec1); //nb: do this BEFORE testing orientation
FixupOutPolygon(outRec2); // but AFTER calling FixupJoinRecs()
if ((outRec1.isHole ^ m_ReverseOutput) == (Area(outRec1, m_UseFullRange) > 0))
ReversePolyPtLinks(outRec1.pts);
}
else
{
//the 2 polygons are completely separate ...
outRec2.isHole = outRec1.isHole;
outRec2.FirstLeft = outRec1.FirstLeft;
FixupJoinRecs(j, p2, i + 1);
//fixup FirstLeft pointers that may need reassigning to OutRec2
if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec2);
FixupOutPolygon(outRec1); //nb: do this BEFORE testing orientation
FixupOutPolygon(outRec2); // but AFTER calling FixupJoinRecs()
}
}
else
{
//joined 2 polygons together ...
//cleanup redundant edges ...
FixupOutPolygon(outRec1);
outRec2.pts = null;
outRec2.bottomPt = null;
outRec2.idx = outRec1.idx;
outRec1.isHole = holeStateRec.isHole;
if (holeStateRec == outRec2)
outRec1.FirstLeft = outRec2.FirstLeft;
outRec2.FirstLeft = outRec1;
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);
}
}
}
//------------------------------------------------------------------------------
private void UpdateOutPtIdxs(OutRec outrec)
{
OutPt op = outrec.pts;
do
{
op.idx = outrec.idx;
op = op.prev;
}
while(op != outrec.pts);
}
//------------------------------------------------------------------------------
private void DoSimplePolygons()
{
int i = 0;
while (i < m_PolyOuts.Count)
{
OutRec outrec = m_PolyOuts[i++];
OutPt op = outrec.pts;
if (op == null) continue;
do //for each Pt in Polygon until duplicate found do ...
{
OutPt op2 = op.next;
while (op2 != outrec.pts)
{
if (PointsEqual(op.pt, op2.pt) && op2.next != op && op2.prev != op)
{
//split the polygon into two ...
OutPt op3 = op.prev;
OutPt op4 = op2.prev;
op.prev = op4;
op4.next = op;
op2.prev = op3;
op3.next = op2;
outrec.pts = op;
OutRec outrec2 = CreateOutRec();
outrec2.pts = op2;
UpdateOutPtIdxs(outrec2);
if (Poly2ContainsPoly1(outrec2.pts, outrec.pts, m_UseFullRange))
{
//OutRec2 is contained by OutRec1 ...
outrec2.isHole = !outrec.isHole;
outrec2.FirstLeft = outrec;
}
else
if (Poly2ContainsPoly1(outrec.pts, outrec2.pts, m_UseFullRange))
{
//OutRec1 is contained by OutRec2 ...
outrec2.isHole = outrec.isHole;
outrec.isHole = !outrec2.isHole;
outrec2.FirstLeft = outrec.FirstLeft;
outrec.FirstLeft = outrec2;
} else
{
//the 2 polygons are separate ...
outrec2.isHole = outrec.isHole;
outrec2.FirstLeft = outrec.FirstLeft;
}
op2 = op; //ie get ready for the next iteration
}
op2 = op2.next;
}
op = op.next;
}
while (op != outrec.pts);
}
}
//------------------------------------------------------------------------------
private static bool FullRangeNeeded(Polygon pts)
{
bool result = false;
for (int i = 0; i < pts.Count; i++)
{
if (Math.Abs(pts[i].X) > hiRange || Math.Abs(pts[i].Y) > hiRange)
throw new ClipperException("Coordinate exceeds range bounds.");
else if (Math.Abs(pts[i].X) > loRange || Math.Abs(pts[i].Y) > loRange)
result = true;
}
return result;
}
//------------------------------------------------------------------------------
public static double Area(Polygon poly)
{
int highI = poly.Count - 1;
if (highI < 2) return 0;
if (FullRangeNeeded(poly))
{
Int128 a = new Int128(0);
a = Int128.Int128Mul(poly[highI].X + poly[0].X, poly[0].Y - poly[highI].Y);
for (int i = 1; i <= highI; ++i)
a += Int128.Int128Mul(poly[i - 1].X + poly[i].X, poly[i].Y - poly[i - 1].Y);
return a.ToDouble() / 2;
}
else
{
double area = ((double)poly[highI].X + poly[0].X) * ((double)poly[0].Y - poly[highI].Y);
for (int i = 1; i <= highI; ++i)
area += ((double)poly[i - 1].X + poly[i].X) * ((double)poly[i].Y - poly[i -1].Y);
return area / 2;
}
}
//------------------------------------------------------------------------------
double Area(OutRec outRec, bool UseFull64BitRange)
{
OutPt op = outRec.pts;
if (op == null) return 0;
if (UseFull64BitRange)
{
Int128 a = new Int128(0);
do
{
a += Int128.Int128Mul(op.pt.X + op.prev.pt.X, op.prev.pt.Y - op.pt.Y);
op = op.next;
} while (op != outRec.pts);
return a.ToDouble() / 2;
}
else
{
double a = 0;
do {
a = a + (op.pt.X + op.prev.pt.X) * (op.prev.pt.Y - op.pt.Y);
op = op.next;
} while (op != outRec.pts);
return a/2;
}
}
//------------------------------------------------------------------------------
// OffsetPolygon functions ...
//------------------------------------------------------------------------------
internal static Polygon BuildArc(IntPoint pt, double a1, double a2, double r, double limit)
{
//see notes in clipper.pas regarding steps
double arcFrac = Math.Abs(a2 - a1) / (2 * Math.PI);
int steps = (int)(arcFrac * Math.PI / Math.Acos(1 - limit / Math.Abs(r)));
if (steps < 2)
steps = 2;
else if (steps > (int)(222.0 * arcFrac))
steps = (int)(222.0 * arcFrac);
double x = Math.Cos(a1);
double y = Math.Sin(a1);
double c = Math.Cos((a2 - a1) / steps);
double s = Math.Sin((a2 - a1) / steps);
Polygon result = new Polygon(steps +1);
for (int i = 0; i <= steps; ++i)
{
result.Add(new IntPoint(pt.X + Round(x * r), pt.Y + Round(y * r)));
double x2 = x;
x = x * c - s * y; //cross product
y = x2 * s + y * c; //dot product
}
return result;
}
//------------------------------------------------------------------------------
internal static DoublePoint GetUnitNormal(IntPoint pt1, IntPoint pt2)
{
double dx = (pt2.X - pt1.X);
double dy = (pt2.Y - pt1.Y);
if ((dx == 0) && (dy == 0)) return new DoublePoint();
double f = 1 * 1.0 / Math.Sqrt(dx * dx + dy * dy);
dx *= f;
dy *= f;
return new DoublePoint(dy, -dx);
}
//------------------------------------------------------------------------------
internal class DoublePoint
{
public double X { get; set; }
public double Y { get; set; }
public DoublePoint(double x = 0, double y = 0)
{
this.X = x; this.Y = y;
}
public DoublePoint(DoublePoint dp)
{
this.X = dp.X; this.Y = dp.Y;
}
};
//------------------------------------------------------------------------------
private class PolyOffsetBuilder
{
private Polygons m_p;
private Polygon currentPoly;
private List<DoublePoint> normals = new List<DoublePoint>();
private double m_delta, m_r, m_rmin;
private int m_i, m_j, m_k;
private const int m_buffLength = 128;
void OffsetPoint(JoinType jointype, double limit)
{
switch (jointype)
{
case JoinType.jtMiter:
{
m_r = 1 + (normals[m_j].X * normals[m_k].X +
normals[m_j].Y * normals[m_k].Y);
if (m_r >= m_rmin) DoMiter(); else DoSquare();
break;
}
case JoinType.jtSquare: DoSquare(); break;
case JoinType.jtRound: DoRound(limit); break;
}
m_k = m_j;
}
//------------------------------------------------------------------------------
public PolyOffsetBuilder(Polygons pts, Polygons solution, bool isPolygon, double delta,
JoinType jointype, EndType endtype, double limit = 0)
{
//precondition: solution != pts
if (delta == 0) {solution = pts; return; }
m_p = pts;
m_delta = delta;
m_rmin = 0.5;
if (jointype == JoinType.jtMiter)
{
if (limit > 2) m_rmin = 2.0 / (limit * limit);
limit = 0.25; //just in case endtype == etRound
}
else
{
if (limit <= 0) limit = 0.25;
else if (limit > Math.Abs(delta)) limit = Math.Abs(delta);
}
double deltaSq = delta * delta;
solution.Clear();
solution.Capacity = pts.Count;
for (m_i = 0; m_i < pts.Count; m_i++)
{
int len = pts[m_i].Count;
if (len == 0 || (len < 3 && delta <= 0))
continue;
else if (len == 1)
{
currentPoly = new Polygon();
currentPoly = BuildArc(pts[m_i][0], 0, 2*Math.PI, delta, limit);
solution.Add(currentPoly);
continue;
}
bool forceClose = PointsEqual(pts[m_i][0], pts[m_i][len - 1]);
if (forceClose) len--;
//build normals ...
normals.Clear();
normals.Capacity = len;
for (int j = 0; j < len -1; ++j)
normals.Add(GetUnitNormal(pts[m_i][j], pts[m_i][j+1]));
if (isPolygon || forceClose)
normals.Add(GetUnitNormal(pts[m_i][len - 1], pts[m_i][0]));
else
normals.Add(new DoublePoint(normals[len - 2]));
currentPoly = new Polygon();
if (isPolygon || forceClose)
{
m_k = len - 1;
for (m_j = 0; m_j < len; ++m_j)
OffsetPoint(jointype, limit);
solution.Add(currentPoly);
if (!isPolygon)
{
currentPoly = new Polygon();
m_delta = -m_delta;
m_k = len - 1;
for (m_j = 0; m_j < len; ++m_j)
OffsetPoint(jointype, limit);
m_delta = -m_delta;
currentPoly.Reverse();
solution.Add(currentPoly);
}
}
else
{
m_k = 0;
for (m_j = 1; m_j < len - 1; ++m_j)
OffsetPoint(jointype, limit);
IntPoint pt1;
if (endtype == EndType.etButt)
{
m_j = len - 1;
pt1 = new IntPoint((Int64)Round(pts[m_i][m_j].X + normals[m_j].X *
delta), (Int64)Round(pts[m_i][m_j].Y + normals[m_j].Y * delta));
AddPoint(pt1);
pt1 = new IntPoint((Int64)Round(pts[m_i][m_j].X - normals[m_j].X *
delta), (Int64)Round(pts[m_i][m_j].Y - normals[m_j].Y * delta));
AddPoint(pt1);
}
else
{
m_j = len - 1;
m_k = len - 2;
normals[m_j].X = -normals[m_j].X;
normals[m_j].Y = -normals[m_j].Y;
if (endtype == EndType.etSquare) DoSquare();
else DoRound(limit);
}
//re-build Normals ...
for (int j = len - 1; j > 0; j--)
{
normals[j].X = -normals[j - 1].X;
normals[j].Y = -normals[j - 1].Y;
}
normals[0].X = -normals[1].X;
normals[0].Y = -normals[1].Y;
m_k = len - 1;
for (m_j = m_k - 1; m_j > 0; --m_j)
OffsetPoint(jointype, limit);
if (endtype == EndType.etButt)
{
pt1 = new IntPoint((Int64)Round(pts[m_i][0].X - normals[0].X * delta),
(Int64)Round(pts[m_i][0].Y - normals[0].Y * delta));
AddPoint(pt1);
pt1 = new IntPoint((Int64)Round(pts[m_i][0].X + normals[0].X * delta),
(Int64)Round(pts[m_i][0].Y + normals[0].Y * delta));
AddPoint(pt1);
}
else
{
m_k = 1;
if (endtype == EndType.etSquare) DoSquare();
else DoRound(limit);
}
solution.Add(currentPoly);
}
}
//finally, clean up untidy corners ...
Clipper clpr = new Clipper();
clpr.AddPolygons(solution, PolyType.ptSubject);
if (delta > 0)
{
clpr.Execute(ClipType.ctUnion, solution, PolyFillType.pftPositive, PolyFillType.pftPositive);
}
else
{
IntRect r = clpr.GetBounds();
Polygon outer = new Polygon(4);
outer.Add(new IntPoint(r.left - 10, r.bottom + 10));
outer.Add(new IntPoint(r.right + 10, r.bottom + 10));
outer.Add(new IntPoint(r.right + 10, r.top - 10));
outer.Add(new IntPoint(r.left - 10, r.top - 10));
clpr.AddPolygon(outer, PolyType.ptSubject);
clpr.ReverseSolution = true;
clpr.Execute(ClipType.ctUnion, solution, PolyFillType.pftNegative, PolyFillType.pftNegative);
if (solution.Count > 0) solution.RemoveAt(0);
}
}
//------------------------------------------------------------------------------
internal void AddPoint(IntPoint pt)
{
if (currentPoly.Count == currentPoly.Capacity)
currentPoly.Capacity += m_buffLength;
currentPoly.Add(pt);
}
//------------------------------------------------------------------------------
internal void DoSquare()
{
IntPoint pt1 = new IntPoint((Int64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
(Int64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
IntPoint pt2 = new IntPoint((Int64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
(Int64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
{
double a1 = Math.Atan2(normals[m_k].Y, normals[m_k].X);
double a2 = Math.Atan2(-normals[m_j].Y, -normals[m_j].X);
a1 = Math.Abs(a2 - a1);
if (a1 > Math.PI) a1 = Math.PI * 2 - a1;
double dx = Math.Tan((Math.PI - a1) / 4) * Math.Abs(m_delta);
pt1 = new IntPoint((Int64)(pt1.X - normals[m_k].Y * dx),
(Int64)(pt1.Y + normals[m_k].X * dx));
AddPoint(pt1);
pt2 = new IntPoint((Int64)(pt2.X + normals[m_j].Y * dx),
(Int64)(pt2.Y - normals[m_j].X * dx));
AddPoint(pt2);
}
else
{
AddPoint(pt1);
AddPoint(m_p[m_i][m_j]);
AddPoint(pt2);
}
}
//------------------------------------------------------------------------------
internal void DoMiter()
{
if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
{
double q = m_delta / m_r;
AddPoint(new IntPoint((Int64)Round(m_p[m_i][m_j].X +
(normals[m_k].X + normals[m_j].X) * q),
(Int64)Round(m_p[m_i][m_j].Y + (normals[m_k].Y + normals[m_j].Y) * q)));
}
else
{
IntPoint pt1 = new IntPoint((Int64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
(Int64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
IntPoint pt2 = new IntPoint((Int64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
(Int64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
AddPoint(pt1);
AddPoint(m_p[m_i][m_j]);
AddPoint(pt2);
}
}
//------------------------------------------------------------------------------
internal void DoRound(double Limit)
{
IntPoint pt1 = new IntPoint(Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta),
Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta));
IntPoint pt2 = new IntPoint(Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta),
Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta));
AddPoint(pt1);
//round off reflex angles (ie > 180 deg) unless almost flat (ie < 10deg).
//cross product normals < 0 . angle > 180 deg.
//dot product normals == 1 . no angle
if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0)
{
if ((normals[m_j].X * normals[m_k].X + normals[m_j].Y * normals[m_k].Y) < 0.985)
{
double a1 = Math.Atan2(normals[m_k].Y, normals[m_k].X);
double a2 = Math.Atan2(normals[m_j].Y, normals[m_j].X);
if (m_delta > 0 && a2 < a1) a2 += Math.PI * 2;
else if (m_delta < 0 && a2 > a1) a2 -= Math.PI * 2;
Polygon arc = BuildArc(m_p[m_i][m_j], a1, a2, m_delta, Limit);
for (int m = 0; m < arc.Count; m++)
AddPoint(arc[m]);
}
}
else
AddPoint(m_p[m_i][m_j]);
AddPoint(pt2);
}
//------------------------------------------------------------------------------
} //end PolyOffsetBuilder
//------------------------------------------------------------------------------
internal static bool UpdateBotPt(IntPoint pt, ref IntPoint botPt)
{
if (pt.Y > botPt.Y || (pt.Y == botPt.Y && pt.X < botPt.X))
{
botPt = pt;
return true;
}
else return false;
}
//------------------------------------------------------------------------------
public static Polygons OffsetPolygons(Polygons poly, double delta,
JoinType jointype, double MiterLimit, bool AutoFix)
{
Polygons result = new Polygons();
//AutoFix - fixes polygon orientation if necessary and removes
//duplicate vertices. Can be set false when you're sure that polygon
//orientation is correct and that there are no duplicate vertices.
if (AutoFix)
{
int Len = poly.Count, botI = 0;
while (botI < Len && poly[botI].Count == 0) botI++;
if (botI == Len) return result;
//botPt: used to find the lowermost (in inverted Y-axis) & leftmost point
//This point (on pts[botI]) must be on an outer polygon ring and if
//its orientation is false (counterclockwise) then assume all polygons
//need reversing ...
IntPoint botPt = poly[botI][0];
for (int i = botI; i < Len; ++i)
{
if (poly[i].Count == 0) continue;
if (UpdateBotPt(poly[i][0], ref botPt)) botI = i;
for (int j = poly[i].Count - 1; j > 0; j--)
{
if (PointsEqual(poly[i][j], poly[i][j - 1]))
poly[i].RemoveAt(j);
else if (UpdateBotPt(poly[i][j], ref botPt))
botI = i;
}
}
if (!Orientation(poly[botI]))
ReversePolygons(poly);
}
new PolyOffsetBuilder(poly, result, true, delta, jointype, EndType.etClosed, MiterLimit);
return result;
}
//------------------------------------------------------------------------------
public static Polygons OffsetPolygons(Polygons poly, double delta,
JoinType jointype, double MiterLimit)
{
return OffsetPolygons(poly, delta, jointype, MiterLimit, true);
}
//------------------------------------------------------------------------------
public static Polygons OffsetPolygons(Polygons poly, double delta, JoinType jointype)
{
return OffsetPolygons(poly, delta, jointype, 0, true);
}
//------------------------------------------------------------------------------
public static Polygons OffsetPolygons(Polygons poly, double delta)
{
return OffsetPolygons(poly, delta, JoinType.jtSquare, 0, true);
}
//------------------------------------------------------------------------------
public static Polygons OffsetPolyLines(Polygons lines,
double delta, JoinType jointype, EndType endtype,
double limit)
{
Polygons result = new Polygons();
//automatically strip duplicate points because it gets complicated with
//open and closed lines and when to strip duplicates across begin-end ...
Polygons pts = new Polygons(lines);
for (int i = 0; i < pts.Count; ++i)
{
for (int j = pts[i].Count - 1; j > 0; j--)
if (PointsEqual(pts[i][j], pts[i][j - 1]))
pts[i].RemoveAt(j);
}
if (endtype == EndType.etClosed)
{
int sz = pts.Count;
pts.Capacity = sz * 2;
for (int i = 0; i < sz; ++i)
{
Polygon line = new Polygon(pts[i]);
line.Reverse();
pts.Add(line);
}
new PolyOffsetBuilder(pts, result, true, delta, jointype, endtype, limit);
}
else
new PolyOffsetBuilder(pts, result, false, delta, jointype, endtype, limit);
return result;
}
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
// SimplifyPolygon functions ...
// Convert self-intersecting polygons into simple polygons
//------------------------------------------------------------------------------
public static Polygons SimplifyPolygon(Polygon poly,
PolyFillType fillType = PolyFillType.pftEvenOdd)
{
Polygons result = new Polygons();
Clipper c = new Clipper();
c.ForceSimple = true;
c.AddPolygon(poly, PolyType.ptSubject);
c.Execute(ClipType.ctUnion, result, fillType, fillType);
return result;
}
//------------------------------------------------------------------------------
public static Polygons SimplifyPolygons(Polygons polys,
PolyFillType fillType = PolyFillType.pftEvenOdd)
{
Polygons result = new Polygons();
Clipper c = new Clipper();
c.ForceSimple = true;
c.AddPolygons(polys, PolyType.ptSubject);
c.Execute(ClipType.ctUnion, result, fillType, fillType);
return result;
}
//------------------------------------------------------------------------------
private static double DistanceSqrd(IntPoint pt1, IntPoint pt2)
{
double dx = ((double)pt1.X - pt2.X);
double dy = ((double)pt1.Y - pt2.Y);
return (dx*dx + dy*dy);
}
//------------------------------------------------------------------------------
private static DoublePoint ClosestPointOnLine(IntPoint pt, IntPoint linePt1, IntPoint linePt2)
{
double dx = ((double)linePt2.X - linePt1.X);
double dy = ((double)linePt2.Y - linePt1.Y);
if (dx == 0 && dy == 0)
return new DoublePoint(linePt1.X, linePt1.Y);
double q = ((pt.X-linePt1.X)*dx + (pt.Y-linePt1.Y)*dy) / (dx*dx + dy*dy);
return new DoublePoint(
(1-q)*linePt1.X + q*linePt2.X,
(1-q)*linePt1.Y + q*linePt2.Y);
}
//------------------------------------------------------------------------------
private static bool SlopesNearColinear(IntPoint pt1,
IntPoint pt2, IntPoint pt3, double distSqrd)
{
if (DistanceSqrd(pt1, pt2) > DistanceSqrd(pt1, pt3)) return false;
DoublePoint cpol = ClosestPointOnLine(pt2, pt1, pt3);
double dx = pt2.X - cpol.X;
double dy = pt2.Y - cpol.Y;
return (dx*dx + dy*dy) < distSqrd;
}
//------------------------------------------------------------------------------
private static bool PointsAreClose(IntPoint pt1, IntPoint pt2, double distSqrd)
{
double dx = (double)pt1.X - pt2.X;
double dy = (double)pt1.Y - pt2.Y;
return ((dx * dx) + (dy * dy) <= distSqrd);
}
//------------------------------------------------------------------------------
public static Polygon CleanPolygon(Polygon poly,
double distance = 1.415)
{
//distance = proximity in units/pixels below which vertices
//will be stripped. Default ~= sqrt(2) so when adjacent
//vertices have both x & y coords within 1 unit, then
//the second vertex will be stripped.
double distSqrd = (distance * distance);
int highI = poly.Count -1;
Polygon result = new Polygon(highI + 1);
while (highI > 0 && PointsAreClose(poly[highI], poly[0], distSqrd)) highI--;
if (highI < 2) return result;
IntPoint pt = poly[highI];
int i = 0;
for (;;)
{
while (i < highI && PointsAreClose(pt, poly[i], distSqrd)) i+=2;
int i2 = i;
while (i < highI && (PointsAreClose(poly[i], poly[i + 1], distSqrd) ||
SlopesNearColinear(pt, poly[i], poly[i + 1], distSqrd))) i++;
if (i >= highI) break;
else if (i != i2) continue;
pt = poly[i++];
result.Add(pt);
}
if (i <= highI) result.Add(poly[i]);
i = result.Count;
if (i > 2 && SlopesNearColinear(result[i - 2], result[i - 1], result[0], distSqrd))
result.RemoveAt(i -1);
if (result.Count < 3) result.Clear();
return result;
}
//------------------------------------------------------------------------------
public static Polygons CleanPolygons(Polygons polys,
double distance = 1.415)
{
Polygons result = new Polygons(polys.Count);
for (int i = 0; i < polys.Count; i++)
result.Add(CleanPolygon(polys[i], distance));
return result;
}
//------------------------------------------------------------------------------
public static void PolyTreeToPolygons(PolyTree polytree, Polygons polygons)
{
polygons.Clear();
polygons.Capacity = polytree.Total;
AddPolyNodeToPolygons(polytree, polygons);
}
//------------------------------------------------------------------------------
public static void AddPolyNodeToPolygons(PolyNode polynode, Polygons polygons)
{
if (polynode.Contour.Count > 0)
polygons.Add(polynode.Contour);
foreach (PolyNode pn in polynode.Childs)
AddPolyNodeToPolygons(pn, polygons);
}
//------------------------------------------------------------------------------
} //end ClipperLib namespace
class ClipperException : Exception
{
public ClipperException(string description) : base(description){}
}
//------------------------------------------------------------------------------
}