Clipper library:

Added some comments,
some methods were made inline, tiny methods moved to the header as inline,
dynamic allocation replaced with std:: containers,
changed some loops to the condensed C++11 syntax.

2 files changed, 287 insertions, 463 deletions

diff --git a/xs/src/clipper.cpp b/xs/src/clipper.cpp
index bac473d4b..1eac45a70 100644
--- a/xs/src/clipper.cpp
+++ b/xs/src/clipper.cpp
@@ -48,6 +48,7 @@
 #include <ostream>

 #include <functional>

 #include <assert.h>

+#include <Shiny/Shiny.h>

 

 namespace ClipperLib {

 

@@ -64,109 +65,49 @@ static int const Skip = -2;        //edge that would otherwise close a path
 #define TOLERANCE (1.0e-20)

 #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE))

 

-struct TEdge {

-  // Bottom point of this edge (with minimum Y).

-  IntPoint Bot;

-  // Current position.

-  IntPoint Curr;

-  // Top point of this edge (with maximum Y).

-  IntPoint Top;

-  // Vector from Bot to Top.

-  IntPoint Delta;

-  // Slope (dx/dy). For horiontal edges, the slope is set to HORIZONTAL (-1.0E+40).

-  double Dx;

-  PolyType PolyTyp;

-  EdgeSide Side;

-  // Winding number delta. 1 or -1 depending on winding direction, 0 for open paths and flat closed paths.

-  int WindDelta;

-  int WindCnt;

-  int WindCnt2; //winding count of the opposite polytype

-  int OutIdx;

-  // Next edge in the input path.

-  TEdge *Next;

-  // Previous edge in the input path.

-  TEdge *Prev;

-  // Next edge in the Local Minima List chain.

-  TEdge *NextInLML;

-  TEdge *NextInAEL;

-  TEdge *PrevInAEL;

-  TEdge *NextInSEL;

-  TEdge *PrevInSEL;

-};

-

-struct IntersectNode {

-  TEdge          *Edge1;

-  TEdge          *Edge2;

-  IntPoint        Pt;

-};

-

-struct LocalMinimum {

-  cInt          Y;

-  TEdge        *LeftBound;

-  TEdge        *RightBound;

+// Point of an output polygon.

+struct OutPt {

+  int       Idx;

+  IntPoint  Pt;

+  OutPt    *Next;

+  OutPt    *Prev;

 };

 

-struct OutPt;

-

+// Output polygon.

 struct OutRec {

   int       Idx;

   bool      IsHole;

   bool      IsOpen;

-  OutRec   *FirstLeft;  //see comments in clipper.pas

+  //The 'FirstLeft' field points to another OutRec that contains or is the

+  //'parent' of OutRec. It is 'first left' because the ActiveEdgeList (AEL) is

+  //parsed left from the current edge (owning OutRec) until the owner OutRec

+  //is found. This field simplifies sorting the polygons into a tree structure

+  //which reflects the parent/child relationships of all polygons.

+  //This field should be renamed Parent, and will be later.

+  OutRec   *FirstLeft;

+  // Used only by void Clipper::BuildResult2(PolyTree& polytree)

   PolyNode *PolyNd;

+  // Linked list of output points, dynamically allocated.

   OutPt    *Pts;

   OutPt    *BottomPt;

 };

 

-struct OutPt {

-  int       Idx;

-  IntPoint  Pt;

-  OutPt    *Next;

-  OutPt    *Prev;

-};

-

-//------------------------------------------------------------------------------

 //------------------------------------------------------------------------------

 

 inline cInt Round(double val)

 {

-  if ((val < 0)) return static_cast<cInt>(val - 0.5); 

-  else return static_cast<cInt>(val + 0.5);

-}

-//------------------------------------------------------------------------------

-

-inline cInt Abs(cInt val)

-{

-  return val < 0 ? -val : val;

+  return static_cast<cInt>((val < 0) ? (val - 0.5) : (val + 0.5));

 }

 

 //------------------------------------------------------------------------------

 // PolyTree methods ...

 //------------------------------------------------------------------------------

 

-void PolyTree::Clear()

-{

-    for (PolyNodes::size_type i = 0; i < AllNodes.size(); ++i)

-      delete AllNodes[i];

-    AllNodes.resize(0); 

-    Childs.resize(0);

-}

-//------------------------------------------------------------------------------

-

-PolyNode* PolyTree::GetFirst() const

-{

-  if (!Childs.empty())

-      return Childs[0];

-  else

-      return 0;

-}

-//------------------------------------------------------------------------------

-

 int PolyTree::Total() const

 {

   int result = (int)AllNodes.size();

   //with negative offsets, ignore the hidden outer polygon ...

-  if (result > 0 && Childs[0] != AllNodes[0]) result--;

+  if (result > 0 && Childs.front() != &AllNodes.front()) result--;

   return result;

 }

 

@@ -174,17 +115,6 @@ int PolyTree::Total() const
 // PolyNode methods ...

 //------------------------------------------------------------------------------

 

-PolyNode::PolyNode(): Childs(), Parent(0), Index(0), m_IsOpen(false)

-{

-}

-//------------------------------------------------------------------------------

-

-int PolyNode::ChildCount() const

-{

-  return (int)Childs.size();

-}

-//------------------------------------------------------------------------------

-

 void PolyNode::AddChild(PolyNode& child)

 {

   unsigned cnt = (unsigned)Childs.size();

@@ -194,26 +124,6 @@ void PolyNode::AddChild(PolyNode& child)
 }

 //------------------------------------------------------------------------------

 

-PolyNode* PolyNode::GetNext() const

-{ 

-  if (!Childs.empty()) 

-      return Childs[0]; 

-  else

-      return GetNextSiblingUp();    

-}  

-//------------------------------------------------------------------------------

-

-PolyNode* PolyNode::GetNextSiblingUp() const

-{ 

-  if (!Parent) //protects against PolyTree.GetNextSiblingUp()

-      return 0;

-  else if (Index == Parent->Childs.size() - 1)

-      return Parent->GetNextSiblingUp();

-  else

-      return Parent->Childs[Index + 1];

-}  

-//------------------------------------------------------------------------------

-

 // Edge delimits a hole if it has an odd number of parent loops.

 bool PolyNode::IsHole() const

 { 

@@ -228,12 +138,6 @@ bool PolyNode::IsHole() const
 }  

 //------------------------------------------------------------------------------

 

-bool PolyNode::IsOpen() const

-{ 

-  return m_IsOpen;

-}  

-//------------------------------------------------------------------------------

-

 #ifndef use_int32

 

 //------------------------------------------------------------------------------

@@ -359,9 +263,12 @@ inline Int128 Int128Mul (long64 lhs, long64 rhs)
   ulong64 int2Hi = ulong64(rhs) >> 32;

   ulong64 int2Lo = ulong64(rhs & 0xFFFFFFFF);

 

-  //nb: see comments in clipper.pas

+  //because the high (sign) bits in both int1Hi & int2Hi have been zeroed,

+  //there's no risk of 64 bit overflow in the following assignment

+  //(ie: $7FFFFFFF*$FFFFFFFF + $7FFFFFFF*$FFFFFFFF < 64bits)

   ulong64 a = int1Hi * int2Hi;

   ulong64 b = int1Lo * int2Lo;

+  //Result = A shl 64 + C shl 32 + B ...

   ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi;

 

   Int128 tmp;

@@ -471,12 +378,13 @@ int PointInPolygon(const IntPoint &pt, const Path &path)
 }

 //------------------------------------------------------------------------------

 

+// Called by Poly2ContainsPoly1()

 int PointInPolygon (const IntPoint &pt, OutPt *op)

 {

   //returns 0 if false, +1 if true, -1 if pt ON polygon boundary

   int result = 0;

   OutPt* startOp = op;

-  for(;;)

+  do

   {

     if (op->Next->Pt.Y == pt.Y)

     {

@@ -507,14 +415,15 @@ int PointInPolygon (const IntPoint &pt, OutPt *op)
       }

     } 

     op = op->Next;

-    if (startOp == op) break;

-  } 

+  } while (startOp != op);

   return result;

 }

 //------------------------------------------------------------------------------

 

+// This is potentially very expensive! O(n^2)!

 bool Poly2ContainsPoly1(OutPt *OutPt1, OutPt *OutPt2)

 {

+  PROFILE_FUNC();

   OutPt* op = OutPt1;

   do

   {

@@ -576,22 +485,6 @@ inline double GetDx(const IntPoint &pt1, const IntPoint &pt2)
 }

 //---------------------------------------------------------------------------

 

-inline void SwapSides(TEdge &Edge1, TEdge &Edge2)

-{

-  EdgeSide Side =  Edge1.Side;

-  Edge1.Side = Edge2.Side;

-  Edge2.Side = Side;

-}

-//------------------------------------------------------------------------------

-

-inline void SwapPolyIndexes(TEdge &Edge1, TEdge &Edge2)

-{

-  int OutIdx =  Edge1.OutIdx;

-  Edge1.OutIdx = Edge2.OutIdx;

-  Edge2.OutIdx = OutIdx;

-}

-//------------------------------------------------------------------------------

-

 inline cInt TopX(TEdge &edge, const cInt currentY)

 {

   return ( currentY == edge.Top.Y ) ?

@@ -669,16 +562,17 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip)
 }

 //------------------------------------------------------------------------------

 

+// Reverse a linked loop of points representing a closed polygon.

+// This has a time complexity of O(n)

 void ReversePolyPtLinks(OutPt *pp)

 {

   if (!pp) return;

-  OutPt *pp1, *pp2;

-  pp1 = pp;

+  OutPt *pp1 = pp;

   do {

-  pp2 = pp1->Next;

-  pp1->Next = pp1->Prev;

-  pp1->Prev = pp2;

-  pp1 = pp2;

+    OutPt *pp2 = pp1->Next;

+    pp1->Next = pp1->Prev;

+    pp1->Prev = pp2;

+    pp1 = pp2;

   } while( pp1 != pp );

 }

 //------------------------------------------------------------------------------

@@ -751,29 +645,21 @@ inline void ReverseHorizontal(TEdge &e)
 }

 //------------------------------------------------------------------------------

 

-void SwapPoints(IntPoint &pt1, IntPoint &pt2)

-{

-  IntPoint tmp = pt1;

-  pt1 = pt2;

-  pt2 = tmp;

-}

-//------------------------------------------------------------------------------

-

 bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a,

   IntPoint pt2b, IntPoint &pt1, IntPoint &pt2)

 {

   //precondition: segments are Collinear.

-  if (Abs(pt1a.X - pt1b.X) > Abs(pt1a.Y - pt1b.Y))

+  if (std::abs(pt1a.X - pt1b.X) > std::abs(pt1a.Y - pt1b.Y))

   {

-    if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b);

-    if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b);

+    if (pt1a.X > pt1b.X) std::swap(pt1a, pt1b);

+    if (pt2a.X > pt2b.X) std::swap(pt2a, 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(pt1a, pt1b);

-    if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b);

+    if (pt1a.Y < pt1b.Y) std::swap(pt1a, pt1b);

+    if (pt2a.Y < pt2b.Y) std::swap(pt2a, 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;

@@ -800,6 +686,7 @@ bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2)
 }

 //------------------------------------------------------------------------------

 

+// Called by GetLowermostRec()

 OutPt* GetBottomPt(OutPt *pp)

 {

   OutPt* dups = 0;

@@ -861,18 +748,6 @@ bool HorzSegmentsOverlap(cInt seg1a, cInt seg1b, cInt seg2a, cInt seg2b)
 // ClipperBase class methods ...

 //------------------------------------------------------------------------------

 

-ClipperBase::ClipperBase() //constructor

-{

-  m_UseFullRange = false;

-}

-//------------------------------------------------------------------------------

-

-ClipperBase::~ClipperBase() //destructor

-{

-  Clear();

-}

-//------------------------------------------------------------------------------

-

 // Called from ClipperBase::AddPath() to verify the scale of the input polygon coordinates.

 inline void RangeTest(const IntPoint& Pt, bool& useFullRange)

 {

@@ -1028,6 +903,7 @@ TEdge* ClipperBase::ProcessBound(TEdge* E, bool NextIsForward)
 

 bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)

 {

+  PROFILE_FUNC();

 #ifdef use_lines

   if (!Closed && PolyTyp == ptClip)

     throw clipperException("AddPath: Open paths must be subject.");

@@ -1044,7 +920,7 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
   if ((Closed && highI < 2) || (!Closed && highI < 1)) return false;

 

   //create a new edge array ...

-  TEdge *edges = new TEdge [highI +1];

+  std::vector<TEdge> edges(highI + 1);

 

   //1. Basic (first) edge initialization ...

   try

@@ -1062,7 +938,6 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
   }

   catch(...)

   {

-    delete [] edges;

     throw; //range test fails

   }

   TEdge *eStart = &edges[0];

@@ -1103,7 +978,6 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
 

   if ((!Closed && (E == E->Next)) || (Closed && (E->Prev == E->Next)))

   {

-    delete [] edges;

     return false;

   }

 

@@ -1133,7 +1007,6 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
   {

     if (Closed) 

     {

-      delete [] edges;

       return false;

     }

     E->Prev->OutIdx = Skip;

@@ -1151,11 +1024,11 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
       E = E->Next;

     }

     m_MinimaList.push_back(locMin);

-    m_edges.push_back(edges);

+    m_edges.emplace_back(std::move(edges));

 	  return true;

   }

 

-  m_edges.push_back(edges);

+  m_edges.emplace_back(std::move(edges));

   bool leftBoundIsForward;

   TEdge* EMin = 0;

 

@@ -1214,6 +1087,7 @@ bool ClipperBase::AddPath(const Path &pg, PolyType PolyTyp, bool Closed)
 

 bool ClipperBase::AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed)

 {

+  PROFILE_FUNC();

   bool result = false;

   for (Paths::size_type i = 0; i < ppg.size(); ++i)

     if (AddPath(ppg[i], PolyTyp, Closed)) result = true;

@@ -1223,14 +1097,8 @@ bool ClipperBase::AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed)
 

 void ClipperBase::Clear()

 {

+  PROFILE_FUNC();

   m_MinimaList.clear();

-  for (EdgeList::size_type i = 0; i < m_edges.size(); ++i)

-  {

-    //for each edge array in turn, find the first used edge and 

-    //check for and remove any hiddenPts in each edge in the array.

-    TEdge* edges = m_edges[i];

-    delete [] edges;

-  }

   m_edges.clear();

   m_UseFullRange = false;

   m_HasOpenPaths = false;

@@ -1241,6 +1109,7 @@ void ClipperBase::Clear()
 // Sort the LML entries, initialize the left / right bound edges of each Local Minima.

 void ClipperBase::Reset()

 {

+  PROFILE_FUNC();

   if (m_MinimaList.empty()) return; //ie nothing to process

   std::sort(m_MinimaList.begin(), m_MinimaList.end(), [](const LocalMinimum& lm1, const LocalMinimum& lm2){ return lm1.Y < lm2.Y; });

 

@@ -1269,6 +1138,7 @@ void ClipperBase::Reset()
 // Returns (0,0,0,0) for an empty rectangle.

 IntRect ClipperBase::GetBounds()

 {

+  PROFILE_FUNC();

   IntRect result;

   auto lm = m_MinimaList.begin();

   if (lm == m_MinimaList.end())

@@ -1324,22 +1194,9 @@ Clipper::Clipper(int initOptions) : ClipperBase() //constructor
 }

 //------------------------------------------------------------------------------

 

-Clipper::~Clipper() //destructor

-{

-  Clear();

-}

-//------------------------------------------------------------------------------

-

-#ifdef use_xyz  

-void Clipper::ZFillFunction(ZFillCallback zFillFunc)

-{  

-  m_ZFill = zFillFunc;

-}

-//------------------------------------------------------------------------------

-#endif

-

 void Clipper::Reset()

 {

+  PROFILE_FUNC();

   ClipperBase::Reset();

   m_Scanbeam = std::priority_queue<cInt>();

   m_Maxima.clear();

@@ -1348,23 +1205,13 @@ void Clipper::Reset()
   for (auto lm = m_MinimaList.rbegin(); lm != m_MinimaList.rend(); ++lm)

     m_Scanbeam.push(lm->Y);

 }

-//------------------------------------------------------------------------------

-

-bool Clipper::Execute(ClipType clipType, Paths &solution, PolyFillType fillType)

-{

-    return Execute(clipType, solution, fillType, fillType);

-}

-//------------------------------------------------------------------------------

 

-bool Clipper::Execute(ClipType clipType, PolyTree &polytree, PolyFillType fillType)

-{

-    return Execute(clipType, polytree, fillType, fillType);

-}

 //------------------------------------------------------------------------------

 

 bool Clipper::Execute(ClipType clipType, Paths &solution,

     PolyFillType subjFillType, PolyFillType clipFillType)

 {

+  PROFILE_FUNC();

   if (m_HasOpenPaths)

     throw clipperException("Error: PolyTree struct is needed for open path clipping.");

   solution.resize(0);

@@ -1382,6 +1229,7 @@ bool Clipper::Execute(ClipType clipType, Paths &solution,
 bool Clipper::Execute(ClipType clipType, PolyTree& polytree,

     PolyFillType subjFillType, PolyFillType clipFillType)

 {

+  PROFILE_FUNC();

   m_SubjFillType = subjFillType;

   m_ClipFillType = clipFillType;

   m_ClipType = clipType;

@@ -1393,34 +1241,23 @@ bool Clipper::Execute(ClipType clipType, PolyTree& polytree,
 }

 //------------------------------------------------------------------------------

 

-void Clipper::FixHoleLinkage(OutRec &outrec)

-{

-  //skip OutRecs that (a) contain outermost polygons or

-  //(b) already have the correct owner/child linkage ...

-  if (!outrec.FirstLeft ||                

-      (outrec.IsHole != outrec.FirstLeft->IsHole &&

-      outrec.FirstLeft->Pts)) return;

-

-  OutRec* orfl = outrec.FirstLeft;

-  while (orfl && ((orfl->IsHole == outrec.IsHole) || !orfl->Pts))

-      orfl = orfl->FirstLeft;

-  outrec.FirstLeft = orfl;

-}

-//------------------------------------------------------------------------------

-

 bool Clipper::ExecuteInternal()

 {

+  PROFILE_FUNC();

   bool succeeded = true;

   try {

+   PROFILE_BLOCK(Clipper_ExecuteInternal_Process);

     Reset();

     if (m_MinimaList.empty()) return true;

-    cInt botY = PopScanbeam();

+    cInt botY = m_Scanbeam.top();

+    do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && botY == m_Scanbeam.top());

     do {

       InsertLocalMinimaIntoAEL(botY);

       ProcessHorizontals();

 	    m_GhostJoins.clear();

 	    if (m_Scanbeam.empty()) break;

-      cInt topY = PopScanbeam();

+      cInt topY = m_Scanbeam.top();

+      do { m_Scanbeam.pop(); } while (! m_Scanbeam.empty() && topY == m_Scanbeam.top());

       succeeded = ProcessIntersections(topY);

       if (!succeeded) break;

       ProcessEdgesAtTopOfScanbeam(topY);

@@ -1434,28 +1271,37 @@ bool Clipper::ExecuteInternal()
 

   if (succeeded)

   {

+    PROFILE_BLOCK(Clipper_ExecuteInternal_Fix);

+

     //fix orientations ...

-    for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

+    //FIXME Vojtech: Does it not invalidate the loop hierarchy maintained as OutRec::FirstLeft pointers?

+    //FIXME Vojtech: The area is calculated with floats, it may not be numerically stable!

     {

-      OutRec *outRec = m_PolyOuts[i];

-      if (!outRec->Pts || outRec->IsOpen) continue;

-      if ((outRec->IsHole ^ m_ReverseOutput) == (Area(*outRec) > 0))

-        ReversePolyPtLinks(outRec->Pts);

+      PROFILE_BLOCK(Clipper_ExecuteInternal_Fix_orientations);

+      for (OutRec *outRec : m_PolyOuts)

+        if (outRec->Pts && !outRec->IsOpen && (outRec->IsHole ^ m_ReverseOutput) == (Area(*outRec) > 0))

+          ReversePolyPtLinks(outRec->Pts);

     }

 

-    if (!m_Joins.empty()) JoinCommonEdges();

+    JoinCommonEdges();

 

     //unfortunately FixupOutPolygon() must be done after JoinCommonEdges()

-    for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

     {

-      OutRec *outRec = m_PolyOuts[i];

-      if (!outRec->Pts) continue;

-      if (outRec->IsOpen)

-        FixupOutPolyline(*outRec);

-      else

-        FixupOutPolygon(*outRec);

+      PROFILE_BLOCK(Clipper_ExecuteInternal_Fix_fixup);

+      for (OutRec *outRec : m_PolyOuts)

+        if (outRec->Pts) {

+          if (outRec->IsOpen)

+            // Removes duplicate points.

+            FixupOutPolyline(*outRec);

+          else

+            // Removes duplicate points and simplifies consecutive parallel edges by removing the middle vertex.

+            FixupOutPolygon(*outRec);

+        }

     }

-

+    // For each polygon, search for exactly duplicate non-successive points.

+    // If such a point is found, the loop is split into two pieces.

+    // Search for the duplicate points is O(n^2)!

+    // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/Clipper/Properties/StrictlySimple.htm

     if (m_StrictSimple) DoSimplePolygons();

   }

 

@@ -1465,31 +1311,16 @@ bool Clipper::ExecuteInternal()
 }

 //------------------------------------------------------------------------------

 

-cInt Clipper::PopScanbeam()

-{

-    const cInt Y = m_Scanbeam.top();

-    m_Scanbeam.pop();

-    while (!m_Scanbeam.empty() && Y == m_Scanbeam.top()) { m_Scanbeam.pop(); } // Pop duplicates.

-    return Y;

-}

-//------------------------------------------------------------------------------

-

 void Clipper::DisposeAllOutRecs(){

-  for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

-    DisposeOutRec(i);

+  for (OutRec *outRec : m_PolyOuts) {

+    if (outRec->Pts)

+      DisposeOutPts(outRec->Pts);

+    delete outRec;

+  }

   m_PolyOuts.clear();

 }

 //------------------------------------------------------------------------------

 

-void Clipper::DisposeOutRec(PolyOutList::size_type index)

-{

-  OutRec *outRec = m_PolyOuts[index];

-  if (outRec->Pts) DisposeOutPts(outRec->Pts);

-  delete outRec;

-  m_PolyOuts[index] = 0;

-}

-//------------------------------------------------------------------------------

-

 void Clipper::SetWindingCount(TEdge &edge) const

 {

   TEdge *e = edge.PrevInAEL;

@@ -1537,7 +1368,7 @@ void Clipper::SetWindingCount(TEdge &edge) const
     {

       //prev edge is 'decreasing' WindCount (WC) toward zero

       //so we're outside the previous polygon ...

-      if (Abs(e->WindCnt) > 1)

+      if (std::abs(e->WindCnt) > 1)

       {

         //outside prev poly but still inside another.

         //when reversing direction of prev poly use the same WC 

@@ -1585,22 +1416,6 @@ void Clipper::SetWindingCount(TEdge &edge) const
 }

 //------------------------------------------------------------------------------

 

-bool Clipper::IsEvenOddFillType(const TEdge& edge) const

-{

-  if (edge.PolyTyp == ptSubject)

-    return m_SubjFillType == pftEvenOdd; else

-    return m_ClipFillType == pftEvenOdd;

-}

-//------------------------------------------------------------------------------

-

-bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const

-{

-  if (edge.PolyTyp == ptSubject)

-    return m_ClipFillType == pftEvenOdd; else

-    return m_SubjFillType == pftEvenOdd;

-}

-//------------------------------------------------------------------------------

-

 bool Clipper::IsContributing(const TEdge& edge) const

 {

   PolyFillType pft, pft2;

@@ -1621,7 +1436,7 @@ bool Clipper::IsContributing(const TEdge& edge) const
       if (edge.WindDelta == 0 && edge.WindCnt != 1) return false;

       break;

     case pftNonZero:

-      if (Abs(edge.WindCnt) != 1) return false;

+      if (std::abs(edge.WindCnt) != 1) return false;

       break;

     case pftPositive: 

       if (edge.WindCnt != 1) return false;

@@ -1701,8 +1516,10 @@ bool Clipper::IsContributing(const TEdge& edge) const
 }

 //------------------------------------------------------------------------------

 

+// Called from Clipper::InsertLocalMinimaIntoAEL() and Clipper::IntersectEdges().

 OutPt* Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &Pt)

 {

+  PROFILE_FUNC();

   OutPt* result;

   TEdge *e, *prevE;

   if (IsHorizontal(*e2) || ( e1->Dx > e2->Dx ))

@@ -1791,8 +1608,10 @@ void Clipper::CopyAELToSEL()
 

 //------------------------------------------------------------------------------

 

+// Called from Clipper::ExecuteInternal()

 void Clipper::InsertLocalMinimaIntoAEL(const cInt botY)

 {

+  PROFILE_FUNC();

   while (!m_MinimaList.empty() && m_MinimaList.back().Y == botY)

   {

     TEdge* lb = m_MinimaList.back().LeftBound;

@@ -1965,13 +1784,13 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
     else if (e1->PolyTyp != e2->PolyTyp)

     {

       //toggle subj open path OutIdx on/off when Abs(clip.WndCnt) == 1 ...

-      if ((e1->WindDelta == 0) && abs(e2->WindCnt) == 1 && 

+      if ((e1->WindDelta == 0) && std::abs(e2->WindCnt) == 1 && 

         (m_ClipType != ctUnion || e2->WindCnt2 == 0))

       {

         AddOutPt(e1, Pt);

         if (e1Contributing) e1->OutIdx = Unassigned;

       }

-      else if ((e2->WindDelta == 0) && (abs(e1->WindCnt) == 1) && 

+      else if ((e2->WindDelta == 0) && (std::abs(e1->WindCnt) == 1) && 

         (m_ClipType != ctUnion || e1->WindCnt2 == 0))

       {

         AddOutPt(e2, Pt);

@@ -2031,13 +1850,13 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
   {

     case pftPositive: e1Wc = e1->WindCnt; break;

     case pftNegative: e1Wc = -e1->WindCnt; break;

-    default: e1Wc = Abs(e1->WindCnt);

+    default: e1Wc = std::abs(e1->WindCnt);

   }

   switch(e2FillType)

   {

     case pftPositive: e2Wc = e2->WindCnt; break;

     case pftNegative: e2Wc = -e2->WindCnt; break;

-    default: e2Wc = Abs(e2->WindCnt);

+    default: e2Wc = std::abs(e2->WindCnt);

   }

 

   if ( e1Contributing && e2Contributing )

@@ -2051,8 +1870,8 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
     {

       AddOutPt(e1, Pt);

       AddOutPt(e2, Pt);

-      SwapSides( *e1 , *e2 );

-      SwapPolyIndexes( *e1 , *e2 );

+      std::swap(e1->Side, e2->Side);

+      std::swap(e1->OutIdx, e2->OutIdx);

     }

   }

   else if ( e1Contributing )

@@ -2060,8 +1879,8 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
     if (e2Wc == 0 || e2Wc == 1) 

     {

       AddOutPt(e1, Pt);

-      SwapSides(*e1, *e2);

-      SwapPolyIndexes(*e1, *e2);

+      std::swap(e1->Side, e2->Side);

+      std::swap(e1->OutIdx, e2->OutIdx);

     }

   }

   else if ( e2Contributing )

@@ -2069,8 +1888,8 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
     if (e1Wc == 0 || e1Wc == 1) 

     {

       AddOutPt(e2, Pt);

-      SwapSides(*e1, *e2);

-      SwapPolyIndexes(*e1, *e2);

+      std::swap(e1->Side, e2->Side);

+      std::swap(e1->OutIdx, e2->OutIdx);

     }

   } 

   else if ( (e1Wc == 0 || e1Wc == 1) && (e2Wc == 0 || e2Wc == 1))

@@ -2082,13 +1901,13 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
     {

       case pftPositive: e1Wc2 = e1->WindCnt2; break;

       case pftNegative : e1Wc2 = -e1->WindCnt2; break;

-      default: e1Wc2 = Abs(e1->WindCnt2);

+      default: e1Wc2 = std::abs(e1->WindCnt2);

     }

     switch (e2FillType2)

     {

       case pftPositive: e2Wc2 = e2->WindCnt2; break;

       case pftNegative: e2Wc2 = -e2->WindCnt2; break;

-      default: e2Wc2 = Abs(e2->WindCnt2);

+      default: e2Wc2 = std::abs(e2->WindCnt2);

     }

 

     if (e1->PolyTyp != e2->PolyTyp)

@@ -2114,7 +1933,7 @@ void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &Pt)
           AddLocalMinPoly(e1, e2, Pt);

       }

     else

-      SwapSides( *e1, *e2 );

+      std::swap(e1->Side, e2->Side);

   }

 }

 //------------------------------------------------------------------------------

@@ -2342,6 +2161,7 @@ OutPt* Clipper::GetLastOutPt(TEdge *e)
 

 void Clipper::ProcessHorizontals()

 {

+  PROFILE_FUNC();

   TEdge* horzEdge = m_SortedEdges;

   while(horzEdge)

   {

@@ -2352,12 +2172,6 @@ void Clipper::ProcessHorizontals()
 }

 //------------------------------------------------------------------------------

 

-inline bool IsMinima(TEdge *e)

-{

-  return e  && (e->Prev->NextInLML != e) && (e->Next->NextInLML != e);

-}

-//------------------------------------------------------------------------------

-

 inline bool IsMaxima(TEdge *e, const cInt Y)

 {

   return e && e->Top.Y == Y && !e->NextInLML;

@@ -2370,7 +2184,7 @@ inline bool IsIntermediate(TEdge *e, const cInt Y)
 }

 //------------------------------------------------------------------------------

 

-TEdge *GetMaximaPair(TEdge *e)

+inline TEdge *GetMaximaPair(TEdge *e)

 {

   TEdge* result = 0;

   if ((e->Next->Top == e->Top) && !e->Next->NextInLML)

@@ -2479,13 +2293,7 @@ void Clipper::SwapPositionsInSEL(TEdge *Edge1, TEdge *Edge2)
 }

 //------------------------------------------------------------------------------

 

-TEdge* GetNextInAEL(TEdge *e, Direction dir)

-{

-  return dir == dLeftToRight ? e->NextInAEL : e->PrevInAEL;

-}

-//------------------------------------------------------------------------------

-

-void GetHorzDirection(TEdge& HorzEdge, Direction& Dir, cInt& Left, cInt& Right)

+inline void GetHorzDirection(TEdge& HorzEdge, Direction& Dir, cInt& Left, cInt& Right)

 {

   if (HorzEdge.Bot.X < HorzEdge.Top.X)

   {

@@ -2525,8 +2333,8 @@ void Clipper::ProcessHorizontal(TEdge *horzEdge)
   if (!eLastHorz->NextInLML)

     eMaxPair = GetMaximaPair(eLastHorz);

 

-  MaximaList::const_iterator maxIt;

-  MaximaList::const_reverse_iterator maxRit;

+  std::vector<cInt>::const_iterator maxIt;

+  std::vector<cInt>::const_reverse_iterator maxRit;

   if (!m_Maxima.empty())

   {

       //get the first maxima in range (X) ...

@@ -2552,7 +2360,7 @@ void Clipper::ProcessHorizontal(TEdge *horzEdge)
   {

 		  

     bool IsLastHorz = (horzEdge == eLastHorz);

-    TEdge* e = GetNextInAEL(horzEdge, dir);

+    TEdge* e = (dir == dLeftToRight) ? horzEdge->NextInAEL : horzEdge->PrevInAEL;

     while(e)

     {

 

@@ -2628,7 +2436,7 @@ void Clipper::ProcessHorizontal(TEdge *horzEdge)
           IntPoint Pt = IntPoint(e->Curr.X, horzEdge->Curr.Y);

           IntersectEdges( e, horzEdge, Pt);

         }

-        TEdge* eNext = GetNextInAEL(e, dir);

+        TEdge* eNext = (dir == dLeftToRight) ? e->NextInAEL : e->PrevInAEL;

         SwapPositionsInAEL( horzEdge, e );

         e = eNext;

     } //end while(e)

@@ -2724,18 +2532,25 @@ void Clipper::UpdateEdgeIntoAEL(TEdge *&e)
 

 bool Clipper::ProcessIntersections(const cInt topY)

 {

+  PROFILE_FUNC();

   if( !m_ActiveEdges ) return true;

   try {

     BuildIntersectList(topY);

     size_t IlSize = m_IntersectList.size();

     if (IlSize == 0) return true;

-    if (IlSize == 1 || FixupIntersectionOrder()) ProcessIntersectList();

+    if (IlSize == 1 || FixupIntersectionOrder()) {

+      for (IntersectNode &iNode : m_IntersectList) {

+        IntersectEdges( iNode.Edge1, iNode.Edge2, iNode.Pt);

+        SwapPositionsInAEL( iNode.Edge1 , iNode.Edge2 );

+      }

+      m_IntersectList.clear();

+    }

     else return false;

   }

   catch(...) 

   {

     m_SortedEdges = 0;

-    DisposeIntersectNodes();

+    m_IntersectList.clear();

     throw clipperException("ProcessIntersections error");

   }

   m_SortedEdges = 0;

@@ -2743,14 +2558,6 @@ bool Clipper::ProcessIntersections(const cInt topY)
 }

 //------------------------------------------------------------------------------

 

-void Clipper::DisposeIntersectNodes()

-{

-  for (size_t i = 0; i < m_IntersectList.size(); ++i )

-    delete m_IntersectList[i];

-  m_IntersectList.clear();

-}

-//------------------------------------------------------------------------------

-

 void Clipper::BuildIntersectList(const cInt topY)

 {

   if ( !m_ActiveEdges ) return;

@@ -2779,12 +2586,7 @@ void Clipper::BuildIntersectList(const cInt topY)
       if(e->Curr.X > eNext->Curr.X)

       {

         IntersectPoint(*e, *eNext, Pt);

-        IntersectNode * newNode = new IntersectNode;

-        newNode->Edge1 = e;

-        newNode->Edge2 = eNext;

-        newNode->Pt = Pt;

-        m_IntersectList.push_back(newNode);

-

+        m_IntersectList.emplace_back(IntersectNode(e, eNext, Pt));

         SwapPositionsInSEL(e, eNext);

         isModified = true;

       }

@@ -2800,21 +2602,6 @@ void Clipper::BuildIntersectList(const cInt topY)
 //------------------------------------------------------------------------------

 

 

-void Clipper::ProcessIntersectList()

-{

-  for (size_t i = 0; i < m_IntersectList.size(); ++i)

-  {

-    IntersectNode* iNode = m_IntersectList[i];

-    {

-      IntersectEdges( iNode->Edge1, iNode->Edge2, iNode->Pt);

-      SwapPositionsInAEL( iNode->Edge1 , iNode->Edge2 );

-    }

-    delete iNode;

-  }

-  m_IntersectList.clear();

-}

-//------------------------------------------------------------------------------

-

 inline bool EdgesAdjacent(const IntersectNode &inode)

 {

   return (inode.Edge1->NextInSEL == inode.Edge2) ||

@@ -2828,19 +2615,19 @@ bool Clipper::FixupIntersectionOrder()
   //Now it's crucial that intersections are made only between adjacent edges,

   //so to ensure this the order of intersections may need adjusting ...

   CopyAELToSEL();

-  std::sort(m_IntersectList.begin(), m_IntersectList.end(), [](IntersectNode* node1, IntersectNode* node2) { return node2->Pt.Y < node1->Pt.Y; });

+  std::sort(m_IntersectList.begin(), m_IntersectList.end(), [](IntersectNode &node1, IntersectNode &node2) { return node2.Pt.Y < node1.Pt.Y; });

 

   size_t cnt = m_IntersectList.size();

   for (size_t i = 0; i < cnt; ++i) 

   {

-    if (!EdgesAdjacent(*m_IntersectList[i]))

+    if (!EdgesAdjacent(m_IntersectList[i]))

     {

       size_t j = i + 1;

-      while (j < cnt && !EdgesAdjacent(*m_IntersectList[j])) j++;

+      while (j < cnt && !EdgesAdjacent(m_IntersectList[j])) j++;

       if (j == cnt)  return false;

       std::swap(m_IntersectList[i], m_IntersectList[j]);

     }

-    SwapPositionsInSEL(m_IntersectList[i]->Edge1, m_IntersectList[i]->Edge2);

+    SwapPositionsInSEL(m_IntersectList[i].Edge1, m_IntersectList[i].Edge2);

   }

   return true;

 }

@@ -2900,6 +2687,7 @@ void Clipper::DoMaxima(TEdge *e)
 

 void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)

 {

+  PROFILE_FUNC();

   TEdge* e = m_ActiveEdges;

   while( e )

   {

@@ -2960,7 +2748,7 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)
   }

 

   //3. Process horizontals at the Top of the scanbeam ...

-  m_Maxima.sort();

+  std::sort(m_Maxima.begin(), m_Maxima.end());

   ProcessHorizontals();

   m_Maxima.clear();

 

@@ -3033,8 +2821,8 @@ void Clipper::FixupOutPolygon(OutRec &outrec)
 {

     //FixupOutPolygon() - removes duplicate points and simplifies consecutive

     //parallel edges by removing the middle vertex.

-    OutPt *lastOK = 0;

-    outrec.BottomPt = 0;

+    OutPt *lastOK = nullptr;

+    outrec.BottomPt = nullptr;

     OutPt *pp = outrec.Pts;

     bool preserveCol = m_PreserveCollinear || m_StrictSimple;

 

@@ -3042,8 +2830,9 @@ void Clipper::FixupOutPolygon(OutRec &outrec)
     {

         if (pp->Prev == pp || pp->Prev == pp->Next)

         {

+            // Empty loop or a stick. Release the polygon.

             DisposeOutPts(pp);

-            outrec.Pts = 0;

+            outrec.Pts = nullptr;

             return;

         }

 

@@ -3052,7 +2841,7 @@ void Clipper::FixupOutPolygon(OutRec &outrec)
             (SlopesEqual(pp->Prev->Pt, pp->Pt, pp->Next->Pt, m_UseFullRange) &&

             (!preserveCol || !Pt2IsBetweenPt1AndPt3(pp->Prev->Pt, pp->Pt, pp->Next->Pt))))

         {

-            lastOK = 0;

+            lastOK = nullptr;

             OutPt *tmp = pp;

             pp->Prev->Next = pp->Next;

             pp->Next->Prev = pp->Prev;

@@ -3070,6 +2859,7 @@ void Clipper::FixupOutPolygon(OutRec &outrec)
 }

 //------------------------------------------------------------------------------

 

+// Count the number of points in a closed linked loop starting with Pts.

 int PointCount(OutPt *Pts)

 {

     if (!Pts) return 0;

@@ -3088,20 +2878,21 @@ int PointCount(OutPt *Pts)
 void Clipper::BuildResult(Paths &polys)

 {

   polys.reserve(m_PolyOuts.size());

-  for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

+  for (OutRec* outRec : m_PolyOuts)

   {

-    if (!m_PolyOuts[i]->Pts) continue;

+    assert(! outRec->IsOpen);

+    if (!outRec->Pts) continue;

     Path pg;

-    OutPt* p = m_PolyOuts[i]->Pts->Prev;

+    OutPt* p = outRec->Pts->Prev;

     int cnt = PointCount(p);

     if (cnt < 2) continue;

     pg.reserve(cnt);

     for (int i = 0; i < cnt; ++i)

     {

-      pg.push_back(p->Pt);

+      pg.emplace_back(p->Pt);

       p = p->Prev;

     }

-    polys.push_back(pg);

+    polys.emplace_back(std::move(pg));

   }

 }

 //------------------------------------------------------------------------------

@@ -3111,15 +2902,26 @@ void Clipper::BuildResult2(PolyTree& polytree)
     polytree.Clear();

     polytree.AllNodes.reserve(m_PolyOuts.size());

     //add each output polygon/contour to polytree ...

-    for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); i++)

+    for (OutRec* outRec : m_PolyOuts)

     {

-        OutRec* outRec = m_PolyOuts[i];

         int cnt = PointCount(outRec->Pts);

-        if ((outRec->IsOpen && cnt < 2) || (!outRec->IsOpen && cnt < 3)) continue;

-        FixHoleLinkage(*outRec);

-        PolyNode* pn = new PolyNode();

+        if ((outRec->IsOpen && cnt < 2) || (!outRec->IsOpen && cnt < 3))

+          // Ignore an invalid output loop or a polyline.

+          continue;

+

+        //skip OutRecs that (a) contain outermost polygons or

+        //(b) already have the correct owner/child linkage ...

+        if (outRec->FirstLeft &&

+            (outRec->IsHole == outRec->FirstLeft->IsHole || ! outRec->FirstLeft->Pts)) {

+          OutRec* orfl = outRec->FirstLeft;

+          while (orfl && ((orfl->IsHole == outRec->IsHole) || !orfl->Pts))

+              orfl = orfl->FirstLeft;

+          outRec->FirstLeft = orfl;

+        }

+

         //nb: polytree takes ownership of all the PolyNodes

-        polytree.AllNodes.push_back(pn);

+        polytree.AllNodes.emplace_back(PolyNode());

+        PolyNode* pn = &polytree.AllNodes.back();

         outRec->PolyNd = pn;

         pn->Parent = 0;

         pn->Index = 0;

@@ -3127,16 +2929,15 @@ void Clipper::BuildResult2(PolyTree& polytree)
         OutPt *op = outRec->Pts->Prev;

         for (int j = 0; j < cnt; j++)

         {

-            pn->Contour.push_back(op->Pt);

+            pn->Contour.emplace_back(op->Pt);

             op = op->Prev;

         }

     }

 

     //fixup PolyNode links etc ...

     polytree.Childs.reserve(m_PolyOuts.size());

-    for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); i++)

+    for (OutRec* outRec : m_PolyOuts)

     {

-        OutRec* outRec = m_PolyOuts[i];

         if (!outRec->PolyNd) continue;

         if (outRec->IsOpen) 

         {

@@ -3151,19 +2952,6 @@ void Clipper::BuildResult2(PolyTree& polytree)
 }

 //------------------------------------------------------------------------------

 

-void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2)

-{

-  //just swap the contents (because fIntersectNodes is a single-linked-list)

-  IntersectNode inode = int1; //gets a copy of Int1

-  int1.Edge1 = int2.Edge1;

-  int1.Edge2 = int2.Edge2;

-  int1.Pt = int2.Pt;

-  int2.Edge1 = inode.Edge1;

-  int2.Edge2 = inode.Edge2;

-  int2.Pt = inode.Pt;

-}

-//------------------------------------------------------------------------------

-

 inline bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2)

 {

   if (e2.Curr.X == e1.Curr.X) 

@@ -3193,6 +2981,7 @@ bool GetOverlap(const cInt a1, const cInt a2, const cInt b1, const cInt b2,
 }

 //------------------------------------------------------------------------------

 

+// Make all points of outrec point to outrec.Idx

 inline void UpdateOutPtIdxs(OutRec& outrec)

 {  

   OutPt* op = outrec.Pts;

@@ -3503,27 +3292,19 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2)
 }

 //----------------------------------------------------------------------

 

-static OutRec* ParseFirstLeft(OutRec* FirstLeft)

-{

-  while (FirstLeft && !FirstLeft->Pts)

-    FirstLeft = FirstLeft->FirstLeft;

-  return FirstLeft;

-}

-//------------------------------------------------------------------------------

-

+// This is potentially very expensive! O(n^3)!

 void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec) const

 { 

+  PROFILE_FUNC();

   //tests if NewOutRec contains the polygon before reassigning FirstLeft

-  for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

+  for (OutRec *outRec : m_PolyOuts)

   {

-    OutRec* outRec = m_PolyOuts[i];

     if (!outRec->Pts || !outRec->FirstLeft) continue;

-    OutRec* firstLeft = ParseFirstLeft(outRec->FirstLeft);

-    if (firstLeft == OldOutRec)

-    {

-      if (Poly2ContainsPoly1(outRec->Pts, NewOutRec->Pts))

+    OutRec* firstLeft = outRec->FirstLeft;

+    // Skip empty polygons.

+    while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;

+    if (firstLeft == OldOutRec && Poly2ContainsPoly1(outRec->Pts, NewOutRec->Pts))

         outRec->FirstLeft = NewOutRec;

-    }

   }

 }

 //----------------------------------------------------------------------

@@ -3531,16 +3312,14 @@ void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec) const
 void Clipper::FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec) const

 { 

   //reassigns FirstLeft WITHOUT testing if NewOutRec contains the polygon

-  for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)

-  {

-    OutRec* outRec = m_PolyOuts[i];

+  for (OutRec *outRec : m_PolyOuts)

     if (outRec->FirstLeft == OldOutRec) outRec->FirstLeft = NewOutRec;

-  }

 }

 //----------------------------------------------------------------------

 

 void Clipper::JoinCommonEdges()

 {

+  PROFILE_FUNC();

   for (Join &join : m_Joins)

   {

     OutRec *outRec1 = GetOutRec(join.OutPt1->Idx);

@@ -3574,10 +3353,12 @@ void Clipper::JoinCommonEdges()
       //We now need to check every OutRec.FirstLeft pointer. If it points

       //to OutRec1 it may need to point to OutRec2 instead ...

       if (m_UsingPolyTree)

-        for (PolyOutList::size_type j = 0; j < m_PolyOuts.size() - 1; j++)

+        for (size_t j = 0; j < m_PolyOuts.size() - 1; j++)

         {

           OutRec* oRec = m_PolyOuts[j];

-          if (!oRec->Pts || ParseFirstLeft(oRec->FirstLeft) != outRec1 ||

+          OutRec* firstLeft = oRec->FirstLeft;

+          while (firstLeft && !firstLeft->Pts) firstLeft = firstLeft->FirstLeft;

+          if (!oRec->Pts || firstLeft != outRec1 ||

             oRec->IsHole == outRec1->IsHole) continue;

           if (Poly2ContainsPoly1(oRec->Pts, join.OutPt2))

             oRec->FirstLeft = outRec2;

@@ -3589,7 +3370,7 @@ void Clipper::JoinCommonEdges()
         outRec2->IsHole = !outRec1->IsHole;

         outRec2->FirstLeft = outRec1;

 

-        //fixup FirstLeft pointers that may need reassigning to OutRec1

+        // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.

         if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);

 

         if ((outRec2->IsHole ^ m_ReverseOutput) == (Area(*outRec2) > 0))

@@ -3603,7 +3384,7 @@ void Clipper::JoinCommonEdges()
         outRec2->FirstLeft = outRec1->FirstLeft;

         outRec1->FirstLeft = outRec2;

 

-        //fixup FirstLeft pointers that may need reassigning to OutRec1

+        // For each m_PolyOuts, replace FirstLeft from outRec1 to outRec2.

         if (m_UsingPolyTree) FixupFirstLefts2(outRec1, outRec2);

 

         if ((outRec1->IsHole ^ m_ReverseOutput) == (Area(*outRec1) > 0))

@@ -3616,6 +3397,8 @@ void Clipper::JoinCommonEdges()
         outRec2->FirstLeft = outRec1->FirstLeft;

 

         //fixup FirstLeft pointers that may need reassigning to OutRec2

+        // For each polygon of m_PolyOuts, replace FirstLeft from outRec1 to outRec2 if the polygon is inside outRec2.

+        //FIXME This is potentially very expensive! O(n^3)!

         if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec2);

       }

      

@@ -3632,7 +3415,7 @@ void Clipper::JoinCommonEdges()
         outRec1->FirstLeft = outRec2->FirstLeft;

       outRec2->FirstLeft = outRec1;

 

-      //fixup FirstLeft pointers that may need reassigning to OutRec1

+      // For each m_PolyOuts, replace FirstLeft from outRec2 to outRec1.

       if (m_UsingPolyTree) FixupFirstLefts2(outRec2, outRec1);

     }

   }

@@ -3667,12 +3450,6 @@ ClipperOffset::ClipperOffset(double miterLimit, double arcTolerance)
 }

 //------------------------------------------------------------------------------

 

-ClipperOffset::~ClipperOffset()

-{

-  Clear();

-}

-//------------------------------------------------------------------------------

-

 void ClipperOffset::Clear()

 {

   for (int i = 0; i < m_polyNodes.ChildCount(); ++i)

@@ -3953,11 +3730,11 @@ void ClipperOffset::DoOffset(double delta)
       if (node.m_endtype == etOpenButt)

       {

         int j = len - 1;

-        pt1 = IntPoint((cInt)Round(m_srcPoly[j].X + m_normals[j].X *

-          delta), (cInt)Round(m_srcPoly[j].Y + m_normals[j].Y * delta));

+        pt1 = IntPoint(Round(m_srcPoly[j].X + m_normals[j].X *

+          delta), Round(m_srcPoly[j].Y + m_normals[j].Y * delta));

         m_destPoly.push_back(pt1);

-        pt1 = IntPoint((cInt)Round(m_srcPoly[j].X - m_normals[j].X *

-          delta), (cInt)Round(m_srcPoly[j].Y - m_normals[j].Y * delta));

+        pt1 = IntPoint(Round(m_srcPoly[j].X - m_normals[j].X *

+          delta), Round(m_srcPoly[j].Y - m_normals[j].Y * delta));

         m_destPoly.push_back(pt1);

       }

       else

@@ -3982,11 +3759,11 @@ void ClipperOffset::DoOffset(double delta)
 

       if (node.m_endtype == etOpenButt)

       {

-        pt1 = IntPoint((cInt)Round(m_srcPoly[0].X - m_normals[0].X * delta),

-          (cInt)Round(m_srcPoly[0].Y - m_normals[0].Y * delta));

+        pt1 = IntPoint(Round(m_srcPoly[0].X - m_normals[0].X * delta),

+          Round(m_srcPoly[0].Y - m_normals[0].Y * delta));

         m_destPoly.push_back(pt1);

-        pt1 = IntPoint((cInt)Round(m_srcPoly[0].X + m_normals[0].X * delta),

-          (cInt)Round(m_srcPoly[0].Y + m_normals[0].Y * delta));

+        pt1 = IntPoint(Round(m_srcPoly[0].X + m_normals[0].X * delta),

+          Round(m_srcPoly[0].Y + m_normals[0].Y * delta));

         m_destPoly.push_back(pt1);

       }

       else

@@ -4094,9 +3871,15 @@ void ClipperOffset::DoRound(int j, int k)
 // Miscellaneous public functions

 //------------------------------------------------------------------------------

 

+// Called by Clipper::ExecuteInternal()

+// For each polygon, search for exactly duplicate non-successive points.

+// If such a point is found, the loop is split into two pieces.

+// Search for the duplicate points is O(n^2)!

+// http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/Clipper/Properties/StrictlySimple.htm

 void Clipper::DoSimplePolygons()

 {

-  PolyOutList::size_type i = 0;

+  PROFILE_FUNC();

+  size_t i = 0;

   while (i < m_PolyOuts.size()) 

   {

     OutRec* outrec = m_PolyOuts[i++];

@@ -4126,6 +3909,7 @@ void Clipper::DoSimplePolygons()
             //OutRec2 is contained by OutRec1 ...

             outrec2->IsHole = !outrec->IsHole;

             outrec2->FirstLeft = outrec;

+            // For each m_PolyOuts, replace FirstLeft from outRec2 to outrec.

             if (m_UsingPolyTree) FixupFirstLefts2(outrec2, outrec);

           }

           else

@@ -4136,6 +3920,7 @@ void Clipper::DoSimplePolygons()
             outrec->IsHole = !outrec2->IsHole;

             outrec2->FirstLeft = outrec->FirstLeft;

             outrec->FirstLeft = outrec2;

+            // For each m_PolyOuts, replace FirstLeft from outrec to outrec2.

             if (m_UsingPolyTree) FixupFirstLefts2(outrec, outrec2);

             }

             else

@@ -4143,8 +3928,10 @@ void Clipper::DoSimplePolygons()
             //the 2 polygons are separate ...

             outrec2->IsHole = outrec->IsHole;

             outrec2->FirstLeft = outrec->FirstLeft;

+            // For each polygon of m_PolyOuts, replace FirstLeft from outrec to outrec2 if the polygon is inside outRec2.

+            //FIXME This is potentially very expensive! O(n^3)!

             if (m_UsingPolyTree) FixupFirstLefts1(outrec, outrec2);

-            }

+          }

           op2 = op; //ie get ready for the Next iteration

         }

         op2 = op2->Next;

@@ -4224,7 +4011,7 @@ bool SlopesNearCollinear(const IntPoint& pt1,
   //this function is more accurate when the point that's geometrically

   //between the other 2 points is the one that's tested for distance.

   //ie makes it more likely to pick up 'spikes' ...

-	if (Abs(pt1.X - pt2.X) > Abs(pt1.Y - pt2.Y))

+	if (std::abs(pt1.X - pt2.X) > std::abs(pt1.Y - pt2.Y))

 	{

     if ((pt1.X > pt2.X) == (pt1.X < pt3.X))

       return DistanceFromLineSqrd(pt1, pt2, pt3) < distSqrd;

@@ -4263,6 +4050,7 @@ OutPt* ExcludeOp(OutPt* op)
 }

 //------------------------------------------------------------------------------

 

+// Simplify a polygon using a linked list of points.

 void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)

 {

   //distance = proximity in units/pixels below which vertices

@@ -4276,7 +4064,7 @@ void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)
     return;

   }

 

-  OutPt* outPts = new OutPt[size];

+  std::vector<OutPt> outPts(size);

   for (size_t i = 0; i < size; ++i)

   {

     outPts[i].Pt = in_poly[i];

@@ -4319,7 +4107,6 @@ void CleanPolygon(const Path& in_poly, Path& out_poly, double distance)
     out_poly[i] = op->Pt;

     op = op->Next;

   }

-  delete [] outPts;

 }

 //------------------------------------------------------------------------------

 

diff --git a/xs/src/clipper.hpp b/xs/src/clipper.hpp
index 743373a86..11626e396 100644
--- a/xs/src/clipper.hpp
+++ b/xs/src/clipper.hpp
@@ -50,8 +50,7 @@
 //#define use_deprecated  

 

 #include <vector>

-#include <list>

-#include <set>

+#include <deque>

 #include <stdexcept>

 #include <cstring>

 #include <cstdlib>

@@ -136,21 +135,22 @@ typedef std::vector< PolyNode* > PolyNodes;
 class PolyNode 

 { 

 public:

-    PolyNode();

+    PolyNode() : Childs(), Parent(0), Index(0), m_IsOpen(false) {}

     virtual ~PolyNode(){};

     Path Contour;

     PolyNodes Childs;

     PolyNode* Parent;

-    PolyNode* GetNext() const;

+    // Traversal of the polygon tree in a depth first fashion.

+    PolyNode* GetNext() const { return Childs.empty() ? GetNextSiblingUp() : Childs.front(); }

     bool IsHole() const;

-    bool IsOpen() const;

-    int ChildCount() const;

+    bool IsOpen() const { return m_IsOpen; }  

+    int  ChildCount() const { return (int)Childs.size(); }

 private:

     unsigned Index; //node index in Parent.Childs

     bool m_IsOpen;

     JoinType m_jointype;

     EndType m_endtype;

-    PolyNode* GetNextSiblingUp() const;

+    PolyNode* GetNextSiblingUp() const { return Parent ? ((Index == Parent->Childs.size() - 1) ? Parent->GetNextSiblingUp() : Parent->Childs[Index + 1]) : nullptr; }

     void AddChild(PolyNode& child);

     friend class Clipper; //to access Index

     friend class ClipperOffset;

@@ -176,13 +176,13 @@ public:
           Childs[i]->Parent = this;

         return *this; 

     }

-    PolyNode* GetFirst() const;

-    void Clear();

+    PolyNode* GetFirst() const { return Childs.empty() ? nullptr : Childs.front(); }

+    void Clear() {  AllNodes.clear(); Childs.clear(); }

     int Total() const;

 private:

     PolyTree(const PolyTree &src) = delete;

     PolyTree& operator=(const PolyTree &src) = delete;

-    PolyNodes AllNodes;

+    std::vector<PolyNode> AllNodes;

     friend class Clipper; //to access AllNodes

 };

 

@@ -215,24 +215,62 @@ struct IntRect { cInt left; cInt top; cInt right; cInt bottom; };
 //enums that are used internally ...

 enum EdgeSide { esLeft = 1, esRight = 2};

 

-//forward declarations (for stuff used internally) ...

-struct TEdge;

-struct IntersectNode;

-struct LocalMinimum;

-struct OutPt;

-struct OutRec;

-struct Join {

-  Join(OutPt *OutPt1, OutPt *OutPt2, IntPoint OffPt) :

-    OutPt1(OutPt1), OutPt2(OutPt2), OffPt(OffPt) {}

-  OutPt    *OutPt1;

-  OutPt    *OutPt2;

-  IntPoint  OffPt;

-};

-

-typedef std::vector < OutRec* > PolyOutList;

-typedef std::vector < TEdge* > EdgeList;

-typedef std::vector < Join > JoinList;

-typedef std::vector < IntersectNode* > IntersectList;

+// namespace Internal {

+  //forward declarations (for stuff used internally) ...

+  struct TEdge {

+    // Bottom point of this edge (with minimum Y).

+    IntPoint Bot;

+    // Current position.

+    IntPoint Curr;

+    // Top point of this edge (with maximum Y).

+    IntPoint Top;

+    // Vector from Bot to Top.

+    IntPoint Delta;

+    // Slope (dx/dy). For horiontal edges, the slope is set to HORIZONTAL (-1.0E+40).

+    double Dx;

+    PolyType PolyTyp;

+    EdgeSide Side;

+    // Winding number delta. 1 or -1 depending on winding direction, 0 for open paths and flat closed paths.

+    int WindDelta;

+    int WindCnt;

+    int WindCnt2; //winding count of the opposite polytype

+    int OutIdx;

+    // Next edge in the input path.

+    TEdge *Next;

+    // Previous edge in the input path.

+    TEdge *Prev;

+    // Next edge in the Local Minima List chain.

+    TEdge *NextInLML;

+    TEdge *NextInAEL;

+    TEdge *PrevInAEL;

+    TEdge *NextInSEL;

+    TEdge *PrevInSEL;

+  };

+

+  struct IntersectNode {

+    IntersectNode(TEdge *Edge1, TEdge *Edge2, IntPoint Pt) :

+      Edge1(Edge1), Edge2(Edge2), Pt(Pt) {}

+    TEdge          *Edge1;

+    TEdge          *Edge2;

+    IntPoint        Pt;

+  };

+

+  struct LocalMinimum {

+    cInt          Y;

+    TEdge        *LeftBound;

+    TEdge        *RightBound;

+  };

+

+  struct OutPt;

+  struct OutRec;

+  struct Join {

+    Join(OutPt *OutPt1, OutPt *OutPt2, IntPoint OffPt) :

+      OutPt1(OutPt1), OutPt2(OutPt2), OffPt(OffPt) {}

+    OutPt    *OutPt1;

+    OutPt    *OutPt2;

+    IntPoint  OffPt;

+  };

+// }; // namespace Internal

 

 //------------------------------------------------------------------------------

 

@@ -242,8 +280,8 @@ typedef std::vector < IntersectNode* > IntersectList;
 class ClipperBase

 {

 public:

-  ClipperBase();

-  virtual ~ClipperBase();

+  ClipperBase() : m_UseFullRange(false), m_HasOpenPaths(false) {}

+  virtual ~ClipperBase() { Clear(); }

   bool AddPath(const Path &pg, PolyType PolyTyp, bool Closed);

   bool AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed);

   virtual void Clear();

@@ -254,7 +292,6 @@ public:
   void PreserveCollinear(bool value) {m_PreserveCollinear = value;};

 protected:

   TEdge* AddBoundsToLML(TEdge *e, bool IsClosed);

-  void PopLocalMinima();

   virtual void Reset();

   TEdge* ProcessBound(TEdge* E, bool IsClockwise);

   TEdge* DescendToMin(TEdge *&E);

@@ -267,7 +304,7 @@ protected:
   // False if the input polygons have abs values lower or equal to loRange.

   bool              m_UseFullRange;

   // A vector of edges per each input path.

-  EdgeList          m_edges;

+  std::vector<std::vector<TEdge>> m_edges;

   // Don't remove intermediate vertices of a collinear sequence of points.

   bool             m_PreserveCollinear;

   // Is any of the paths inserted by AddPath() or AddPaths() open?

@@ -279,17 +316,19 @@ class Clipper : public virtual ClipperBase
 {

 public:

   Clipper(int initOptions = 0);

-  ~Clipper();

+  ~Clipper() { Clear(); }

   bool Execute(ClipType clipType,

       Paths &solution,

-      PolyFillType fillType = pftEvenOdd);

+      PolyFillType fillType = pftEvenOdd) 

+    { return Execute(clipType, solution, fillType, fillType); }

   bool Execute(ClipType clipType,

       Paths &solution,

       PolyFillType subjFillType,

       PolyFillType clipFillType);

   bool Execute(ClipType clipType,

       PolyTree &polytree,

-      PolyFillType fillType = pftEvenOdd);

+      PolyFillType fillType = pftEvenOdd)

+    { return Execute(clipType, polytree, fillType, fillType); }

   bool Execute(ClipType clipType,

       PolyTree &polytree,

       PolyFillType subjFillType,

@@ -300,21 +339,21 @@ public:
   void StrictlySimple(bool value) {m_StrictSimple = value;};

   //set the callback function for z value filling on intersections (otherwise Z is 0)

 #ifdef use_xyz

-  void ZFillFunction(ZFillCallback zFillFunc);

+  void ZFillFunction(ZFillCallback zFillFunc) { m_ZFill = zFillFunc; }

 #endif

 protected:

   void Reset();

   virtual bool ExecuteInternal();

 private:

-  PolyOutList      m_PolyOuts;

-  JoinList         m_Joins;

-  JoinList         m_GhostJoins;

-  IntersectList    m_IntersectList;

+  std::vector<OutRec*> m_PolyOuts;

+  std::vector<Join> m_Joins;

+  std::vector<Join> m_GhostJoins;

+  std::vector<IntersectNode> m_IntersectList;

   ClipType         m_ClipType;

   // A priority queue (a binary heap) of Y coordinates.

   std::priority_queue<cInt> m_Scanbeam;

-  typedef std::list<cInt> MaximaList;

-  MaximaList       m_Maxima;

+  // Maxima are collected by ProcessEdgesAtTopOfScanbeam(), consumed by ProcessHorizontal().

+  std::vector<cInt> m_Maxima;

   TEdge           *m_ActiveEdges;

   TEdge           *m_SortedEdges;

   PolyFillType     m_ClipFillType;

@@ -327,9 +366,10 @@ private:
   ZFillCallback   m_ZFill; //custom callback 

 #endif

   void SetWindingCount(TEdge& edge) const;

-  bool IsEvenOddFillType(const TEdge& edge) const;

-  bool IsEvenOddAltFillType(const TEdge& edge) const;

-  cInt PopScanbeam();

+  bool IsEvenOddFillType(const TEdge& edge) const 

+    { return (edge.PolyTyp == ptSubject) ? m_SubjFillType == pftEvenOdd : m_ClipFillType == pftEvenOdd; }

+  bool IsEvenOddAltFillType(const TEdge& edge) const

+    { return (edge.PolyTyp == ptSubject) ? m_ClipFillType == pftEvenOdd : m_SubjFillType == pftEvenOdd; }

   void InsertLocalMinimaIntoAEL(const cInt botY);

   void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge);

   void AddEdgeToSEL(TEdge *edge);

@@ -353,15 +393,12 @@ private:
   OutPt* AddOutPt(TEdge *e, const IntPoint &pt);

   OutPt* GetLastOutPt(TEdge *e);

   void DisposeAllOutRecs();

-  void DisposeOutRec(PolyOutList::size_type index);

   bool ProcessIntersections(const cInt topY);

   void BuildIntersectList(const cInt topY);

-  void ProcessIntersectList();

   void ProcessEdgesAtTopOfScanbeam(const cInt topY);

   void BuildResult(Paths& polys);

   void BuildResult2(PolyTree& polytree);

   void SetHoleState(TEdge *e, OutRec *outrec) const;

-  void DisposeIntersectNodes();

   bool FixupIntersectionOrder();

   void FixupOutPolygon(OutRec &outrec);

   void FixupOutPolyline(OutRec &outrec);

@@ -382,7 +419,7 @@ class ClipperOffset
 {

 public:

   ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25);

-  ~ClipperOffset();

+  ~ClipperOffset() { Clear(); }

   void AddPath(const Path& path, JoinType joinType, EndType endType);

   void AddPaths(const Paths& paths, JoinType joinType, EndType endType);

   void Execute(Paths& solution, double delta);