This is an automated email from the git hooks/post-receive script.

sebastic pushed a commit to branch master
in repository mapnik-vector-tile.

commit bf5b814d9b583b3a0ac498aa61d6c1bd392b595e
Author: Bas Couwenberg <sebas...@xs4all.nl>
Date:   Fri Mar 25 00:22:10 2016 +0100

    Update clipper to 3eb6a85910affdf070927bba3b6ab12a67a1381b.
---
 debian/changelog   |   1 +
 debian/clipper.cpp | 835 ++++++++++++++++++++++++++++++++++-------------------
 debian/clipper.hpp |  16 +-
 3 files changed, 556 insertions(+), 296 deletions(-)

diff --git a/debian/changelog b/debian/changelog
index 7a16435..4385789 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,6 +1,7 @@
 mapnik-vector-tile (1.0.5+dfsg-1) UNRELEASED; urgency=medium
 
   * New upstream release.
+  * Update clipper to 3eb6a85910affdf070927bba3b6ab12a67a1381b.
 
  -- Bas Couwenberg <sebas...@debian.org>  Fri, 25 Mar 2016 00:21:16 +0100
 
diff --git a/debian/clipper.cpp b/debian/clipper.cpp
index bf369ec..61d89eb 100644
--- a/debian/clipper.cpp
+++ b/debian/clipper.cpp
@@ -644,8 +644,6 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint 
&ip)
       if (Edge2.Bot.x == Edge1.Bot.x) ip.y = Round(ip.x / Edge2.Dx + b2);
       else if (Edge2.Bot.x < Edge1.Bot.x) ip.y = Round((ip.x - 0.5) / Edge2.Dx 
+ b2);
       else ip.y = Round((ip.x + 0.5) / Edge2.Dx + b2);
-      if (Edge2.Dx > 0.0 && ip.y < Edge2.Bot.y) ip.y = Edge2.Bot.y;
-      else if (Edge2.Dx < 0.0 && ip.y > Edge2.Bot.y) ip.y = Edge2.Bot.y;
     }
   }
   else if (Edge2.Dx == 0.0)
@@ -659,8 +657,6 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint 
&ip)
       if (Edge1.Bot.x == Edge2.Bot.x) ip.y = Round(ip.x / Edge1.Dx + b1);
       else if (Edge1.Bot.x < Edge2.Bot.x) ip.y = Round((ip.x - 0.5) / Edge1.Dx 
+ b1);
       else ip.y = Round((ip.x + 0.5) / Edge1.Dx + b1);
-      if (Edge1.Dx > 0.0 && ip.y < Edge1.Bot.y) ip.y = Edge1.Bot.y;
-      else if (Edge1.Dx < 0.0 && ip.y > Edge1.Bot.y) ip.y = Edge1.Bot.y;
     }
   } 
   else 
@@ -1705,7 +1701,21 @@ bool Clipper::ExecuteInternal()
         FixupOutPolygon(*outRec);
     }
 
-    if (m_StrictSimple) DoSimplePolygons();
+    if (m_StrictSimple) 
+    {
+        DoSimplePolygons();
+        m_StrictSimple = false;
+        for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i)
+        {
+          OutRec *outRec = m_PolyOuts[i];
+          if (!outRec->Pts || outRec->IsOpen)
+          { 
+              continue; 
+          }
+          FixupOutPolygon(*outRec);
+        }
+        m_StrictSimple = true;
+    }
   }
 
   ClearJoins();
@@ -2050,14 +2060,6 @@ void Clipper::ClearJoins()
 }
 
//------------------------------------------------------------------------------
 
-void Clipper::ClearSSJoins()
-{
-  for (JoinList::size_type i = 0; i < m_SSJoins.size(); i++)
-    delete m_SSJoins[i];
-  m_SSJoins.resize(0);
-}
-//------------------------------------------------------------------------------
-
 void Clipper::ClearGhostJoins()
 {
   for (JoinList::size_type i = 0; i < m_GhostJoins.size(); i++)
@@ -2076,16 +2078,6 @@ void Clipper::AddGhostJoin(OutPt *op, const IntPoint 
OffPt)
 }
 
//------------------------------------------------------------------------------
 
-void Clipper::AddSSJoin(OutPt *op1, OutPt *op2, const IntPoint OffPt)
-{
-  Join* j = new Join;
-  j->OutPt1 = op1;
-  j->OutPt2 = op2;
-  j->OffPt = OffPt;
-  m_SSJoins.push_back(j);
-}
-//------------------------------------------------------------------------------
-
 void Clipper::InsertLocalMinimaIntoAEL(const cInt botY)
 {
   const LocalMinimum *lm;
@@ -2670,9 +2662,13 @@ OutPt* Clipper::GetLastOutPt(TEdge *e)
 
 void Clipper::ProcessHorizontals()
 {
-  TEdge* horzEdge;
-  while (PopEdgeFromSEL(horzEdge))
-    ProcessHorizontal(horzEdge);
+    m_Maxima.sort();
+    TEdge* horzEdge;
+    while (PopEdgeFromSEL(horzEdge))
+    {
+        ProcessHorizontal(horzEdge);
+    }
+    m_Maxima.clear();
 }
 
//------------------------------------------------------------------------------
 
@@ -2955,16 +2951,14 @@ void Clipper::ProcessHorizontal(TEdge *horzEdge)
           (ePrev->Curr.x == horzEdge->Top.x) && (ePrev->WindDelta != 0))
         {
           IntPoint pt = horzEdge->Top;
-          OutPt* op = AddOutPt(ePrev, pt);
-          AddJoin(op, op1, pt); //StrictlySimple (type-3) join
+          AddOutPt(ePrev, pt);
         }
         TEdge* eNext = horzEdge->NextInAEL;
         if ((horzEdge->WindDelta != 0) && eNext && (eNext->OutIdx >= 0) &&
           (eNext->Curr.x == horzEdge->Top.x) && (eNext->WindDelta != 0))
         {
           IntPoint pt = horzEdge->Top;
-          OutPt* op = AddOutPt(eNext, pt);
-          AddJoin(op, op1, pt); //StrictlySimple (type-3) join
+          AddOutPt(eNext, pt);
         }
       }
       UpdateEdgeIntoAEL(horzEdge);
@@ -3138,94 +3132,31 @@ void Clipper::DoMaxima(TEdge *e)
     if (e->OutIdx >= 0)
     {
       AddOutPt(e, e->Top);
-      if (e->WindDelta != 0)
-      {
-          TEdge* ePrev = e->PrevInAEL;
-          while (ePrev)
-          {
-            if (e->Top == ePrev->Top)
-            {
-                ePrev = ePrev->PrevInAEL;
-                continue;
-            }
-            if (ePrev->Curr.x != e->Curr.x) break;
-            if ((ePrev->OutIdx >= 0) && (ePrev->WindDelta != 0))
-            {
-              IntPoint pt = e->Curr;
-              AddOutPt(ePrev, pt);
-            }
-            ePrev = ePrev->PrevInAEL;
-          }
-          TEdge* eNext = e->NextInAEL;
-          while (eNext)
-          {
-            if (e->Top == eNext->Top)
-            {
-                eNext = eNext->NextInAEL;
-                continue;
-            }
-            if (eNext->Curr.x != e->Curr.x) break;
-            if ((eNext->OutIdx >= 0) && (eNext->WindDelta != 0))
-            {
-              IntPoint pt = e->Curr;
-              AddOutPt(eNext, pt);
-            }
-            eNext = eNext->NextInAEL;
-          }
-      }
     }
     DeleteFromAEL(e);
     return;
   }
   
-  IntPoint pt = e->Top;
-  TEdge* eNext = e->NextInAEL;
   TEdge* ePrev = e->PrevInAEL;
-  if (e->WindDelta != 0)
+  if (ePrev && ePrev->Curr.x == e->Top.x && ePrev->Top != e->Top && 
ePrev->OutIdx >= 0 && 
+      ePrev->WindDelta != 0 &&  e->OutIdx >= 0 && e->WindDelta != 0)
   {
-      while (eNext)
-      {
-        if (pt == eNext->Top)
-        {
-            eNext = eNext->NextInAEL;
-            continue;
-        }
-        if (TopX(*eNext, pt.y) != pt.x)
-        {
-            eNext = 0;
-            break;
-        }
-        else if ((eNext->OutIdx >= 0) && (eNext->WindDelta != 0))
-        {
-            break;
-        }
-        eNext = eNext->NextInAEL;
-      }
-      while (ePrev)
-      {
-        if (pt == ePrev->Top)
-        {
-            ePrev = ePrev->PrevInAEL;
-            continue;
-        }
-        if (TopX(*ePrev, pt.y) != pt.x)
-        {
-            ePrev = 0;
-            break;
-        }
-        else if ((ePrev->OutIdx >= 0) && (ePrev->WindDelta != 0))
-        {
-            break;
-        }
-        ePrev = ePrev->PrevInAEL;
-      }
+      IntPoint pt = e->Top;
+      AddOutPt(ePrev, pt);
   }
-  TEdge* eNext2 = e->NextInAEL;
-  while(eNext2 && eNext2 != eMaxPair)
+  TEdge* eNext = e->NextInAEL;
+  while(eNext && eNext != eMaxPair)
   {
-    IntersectEdges(e, eNext2, e->Top);
-    SwapPositionsInAEL(e, eNext2);
-    eNext2 = e->NextInAEL;
+    IntersectEdges(e, eNext, e->Top);
+    SwapPositionsInAEL(e, eNext);
+    eNext = e->NextInAEL;
+  }
+  eNext = eMaxPair->NextInAEL;
+  if (eNext && eNext->Curr.x == e->Top.x && eNext->Top != e->Top && 
eNext->OutIdx >= 0 && 
+      eNext->WindDelta != 0 &&  e->OutIdx >= 0 && e->WindDelta != 0)
+  {
+      IntPoint pt = e->Top;
+      AddOutPt(eNext, pt);
   }
 
   if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned)
@@ -3236,14 +3167,6 @@ void Clipper::DoMaxima(TEdge *e)
   else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 )
   {
       AddLocalMaxPoly(e, eMaxPair, e->Top);
-      if (ePrev)
-      {
-        AddOutPt(ePrev, pt);
-      }
-      if (eNext)
-      {
-        AddOutPt(eNext, pt);
-      }
       DeleteFromAEL(e);
       DeleteFromAEL(eMaxPair);
   }
@@ -3272,6 +3195,7 @@ void Clipper::DoMaxima(TEdge *e)
 void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY)
 {
   TEdge* e = m_ActiveEdges;
+  MaximaList next_maxima;
   while( e )
   {
     //1. process maxima, treating them as if they're 'bent' horizontal edges,
@@ -3286,7 +3210,11 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt 
topY)
 
     if(IsMaximaEdge)
     {
-      if (m_StrictSimple) m_Maxima.push_back(e->Top.x);
+      if (m_StrictSimple)
+      {
+          m_Maxima.push_back(e->Top.x);
+          next_maxima.push_back(e->Top.x);
+      }
       TEdge* ePrev = e->PrevInAEL;
       DoMaxima(e);
       if( !ePrev ) e = m_ActiveEdges;
@@ -3299,7 +3227,14 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt 
topY)
       {
         UpdateEdgeIntoAEL(e);
         if (e->OutIdx >= 0)
+        {
           AddOutPt(e, e->Bot);
+          if (m_StrictSimple) 
+          {
+              m_Maxima.push_back(e->Top.x);
+              m_Maxima.push_back(e->Bot.x);
+          }
+        }
         AddEdgeToSEL(e);
       } 
       else
@@ -3329,11 +3264,25 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt 
topY)
       e = e->NextInAEL;
     }
   }
+  if (m_StrictSimple)
+  {
+      MinimaList::iterator lm = m_CurrentLM;
+      while (lm != m_MinimaList.end() && lm->y == topY)
+      {
+          if (lm->LeftBound && lm->RightBound)
+          {
+              m_Maxima.push_back(lm->LeftBound->Bot.x);
+          }
+          ++lm;
+      }
+  }
 
   //3. Process horizontals at the Top of the scanbeam ...
-  m_Maxima.sort();
   ProcessHorizontals();
-  m_Maxima.clear();
+  if (m_StrictSimple && !next_maxima.empty())
+  {
+    m_Maxima.insert(m_Maxima.end(), next_maxima.begin(), next_maxima.end());
+  }
 
   //4. Promote intermediate vertices ...
   e = m_ActiveEdges;
@@ -3751,7 +3700,6 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, 
OutRec* outRec2)
             op2b_next->Prev = op1b_prev;
             return true;
         }
-        bool reverse1 = (op1b->Pt.y > j->OffPt.y);
         
         // Second Op1 Prev and Op2 Next
         op2b = j->OutPt2->Next;
@@ -3770,124 +3718,6 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, 
OutRec* outRec2)
             op1b_next->Prev = op2b_prev;
             return true;
         }
-        bool reverse2 = (op2b->Pt.y > j->OffPt.y);
-        if (reverse1 == reverse2) return false;
-        // See if there was a situation where these 
-        // two were split into seperate polygons
-        // with a SS join
-        for (auto & sj : m_SSJoins)
-        {
-            if (!sj->OutPt1 || !sj->OutPt2) continue;
-            OutRec *sjOutRec1 = GetOutRec(sj->OutPt1->Idx);
-            OutRec *sjOutRec2 = GetOutRec(sj->OutPt2->Idx);
-            if (sjOutRec1->Idx == outRec1->Idx && sjOutRec2->Idx == 
outRec2->Idx)
-            {
-                // We a previous SS join that has the same ids, so we might 
need to make
-                // a different join type.
-                op1b = j->OutPt1->Next;
-                while (op1b != op1 && op1b != sj->OutPt1)
-                {
-                    op1b = op1b->Next;
-                }
-                if (op1b == op1) continue;
-                op2b = j->OutPt2->Next;
-                while (op2b != op2 && op2b != sj->OutPt2)
-                {
-                    op2b = op2b->Next;
-                }
-                if (op2b == op2) continue;
-                OutPt* op1b_next = op1b->Next;
-                OutPt* op2b_next = op2b->Next;
-                OutPt* op1_next = op1->Next;
-                OutPt* op2_next = op2->Next;
-                op2b->Next= op1b_next;
-                op1b->Next = op2b_next;
-                op2b_next->Prev = op1b;
-                op1b_next->Prev = op2b;
-                op2->Next= op1_next;
-                op1->Next = op2_next;
-                op2_next->Prev = op1;
-                op1_next->Prev = op2;
-                sj->OutPt1 = 0;
-                sj->OutPt2 = 0;
-            }
-            else if (sjOutRec1->Idx == outRec2->Idx && sjOutRec2->Idx == 
outRec1->Idx)
-            {
-                // We a previous SS join that has the same ids, so we might 
need to make
-                // a different join type.
-                op1b = j->OutPt1->Next;
-                while (op1b != op1 && op1b != sj->OutPt2)
-                {
-                    op1b = op1b->Next;
-                }
-                if (op1b == op1) continue;
-                op2b = j->OutPt2->Next;
-                while (op2b != op2 && op2b != sj->OutPt1)
-                {
-                    op2b = op2b->Next;
-                }
-                if (op2b == op2) continue;
-                OutPt* op1b_next = op1b->Next;
-                OutPt* op2b_next = op2b->Next;
-                OutPt* op1_next = op1->Next;
-                OutPt* op2_next = op2->Next;
-                op2b->Next= op1b_next;
-                op1b->Next = op2b_next;
-                op2b_next->Prev = op1b;
-                op1b_next->Prev = op2b;
-                op2->Next= op1_next;
-                op1->Next = op2_next;
-                op2_next->Prev = op1;
-                op1_next->Prev = op2;
-                sj->OutPt1 = 0;
-                sj->OutPt2 = 0;
-            }
-            else
-            {
-                continue;
-            }
-            // We still will return false here
-            // because if we returned true it would 
-            // continue and think these two polygons should be merged
-            bool holeState = (Area(j->OutPt1) > 0) && m_ReverseOutput;
-            if (outRec1->IsHole == holeState) // outRec1 is "parent"
-            {
-                outRec1->Pts = j->OutPt2;
-                outRec1->BottomPt = 0;
-                outRec2->Pts = 0;
-                outRec2->BottomPt = 0;
-                outRec2->Idx = outRec1->Idx;
-                outRec2->FirstLeft = outRec1;
-                outRec2->IsHole = outRec1->IsHole;
-                if (m_UsingPolyTree) FixupFirstLefts3(outRec2, outRec1);
-                OutRec * outRec3 = CreateOutRec();
-                outRec3->Pts = j->OutPt1;
-                UpdateOutPtIdxs(*outRec1);
-                UpdateOutPtIdxs(*outRec3);
-                outRec3->FirstLeft = outRec1->FirstLeft;
-                //fixup FirstLeft pointers that may need reassigning to OutRec3
-                if (m_UsingPolyTree) FixupFirstLefts1(outRec1, outRec3);
-            }
-            else
-            {
-                outRec2->Pts = j->OutPt1;
-                outRec2->BottomPt = 0;
-                outRec1->Pts = 0;
-                outRec1->BottomPt = 0;
-                outRec1->Idx = outRec2->Idx;
-                outRec1->FirstLeft = outRec2;
-                outRec1->IsHole = outRec2->IsHole;
-                if (m_UsingPolyTree) FixupFirstLefts3(outRec1, outRec2);
-                OutRec * outRec3 = CreateOutRec();
-                outRec3->Pts = j->OutPt2;
-                UpdateOutPtIdxs(*outRec2);
-                UpdateOutPtIdxs(*outRec3);
-                outRec3->FirstLeft = outRec2->FirstLeft;
-                //fixup FirstLeft pointers that may need reassigning to OutRec3
-                if (m_UsingPolyTree) FixupFirstLefts1(outRec2, outRec3);
-            }
-            return false;
-        }
         return false;
     }
     //Strictly Simple join ...
@@ -3910,7 +3740,6 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, 
OutRec* outRec2)
       op2b->Prev = op1b;
       j->OutPt1 = op1;
       j->OutPt2 = op1b;
-      AddSSJoin(op1, op1b, j->OffPt);
       return true;
     } else
     {
@@ -3922,7 +3751,6 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, 
OutRec* outRec2)
       op2b->Next = op1b;
       j->OutPt1 = op1;
       j->OutPt2 = op1b;
-      AddSSJoin(op1, op1b, j->OffPt);
       return true;
     }
   } 
@@ -4180,7 +4008,6 @@ void Clipper::JoinCommonEdges()
       if (m_UsingPolyTree) FixupFirstLefts3(outRec2, outRec1);
     }
   }
-  ClearSSJoins();
 }
 
 
//------------------------------------------------------------------------------
@@ -4639,65 +4466,487 @@ void ClipperOffset::DoRound(int j, int k)
 // Miscellaneous public functions
 
//------------------------------------------------------------------------------
 
+bool SortOutPt(OutPt* op1, OutPt* op2)
+{ 
+    if (op1->Pt.y > op2->Pt.y)
+    {
+        return true;
+    }
+    else if (op1->Pt.y < op2->Pt.y)
+    {
+        return false;
+    }
+    else if (op1->Pt.x < op2->Pt.x)
+    {
+        return true;
+    }
+    else if (op1->Pt.x > op2->Pt.x)
+    {
+        return false;
+    }
+    else
+    {
+        return (op1->Idx < op2->Idx);
+    }
+}
+
+//-----------------------------------------------------------------------------
+
+struct OutPtIntersect
+{
+    OutPt * op1;
+    OutPt * op2;
+};
+
+//-----------------------------------------------------------------------------
+
+bool Clipper::FindIntersectLoop(std::unordered_multimap<int, OutPtIntersect> & 
dupeRec,
+                                std::list<std::pair<const int, OutPtIntersect> 
> & iList,
+                                OutRec * outRec_parent,
+                                int idx_origin,
+                                int idx_prev,
+                                int idx_search)
+{
+    auto range = dupeRec.equal_range(idx_search);
+    // Check for direct connection
+    for (auto it = range.first; it != range.second; ++it)
+    {
+        OutRec * itRec = GetOutRec(it->second.op2->Idx);
+        if (itRec->Idx == idx_prev)
+        {
+            continue;
+        }
+        if (itRec->Idx == idx_origin && (outRec_parent == itRec || 
outRec_parent == ParseFirstLeft(itRec->FirstLeft)))
+        {
+            iList.emplace_front(idx_search, it->second);
+            return true;
+        }
+    }
+    // Check for connection through chain of other intersections
+    for (auto it = range.first; it != range.second; ++it)
+    {
+        OutRec * itRec = GetOutRec(it->second.op2->Idx);
+        if (itRec->Idx == idx_search || itRec->Idx == idx_prev || 
+            (outRec_parent != itRec && outRec_parent != 
ParseFirstLeft(itRec->FirstLeft)))
+        {
+            continue;
+        }
+        if (FindIntersectLoop(dupeRec, iList, outRec_parent, idx_origin, 
idx_search, itRec->Idx))
+        {
+            iList.emplace_front(idx_search, it->second);
+            return true;
+        }
+    }
+    return false;
+}
+
+//-----------------------------------------------------------------------------
+
+bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & 
dupeRec,
+                            OutPt * op_j,
+                            OutPt * op_k,
+                            OutRec * outRec_j,
+                            OutRec * outRec_k)
+{
+    if (!outRec_j->IsHole && !outRec_k->IsHole) 
+    {
+        // Both are not holes, return nothing to do.
+        return false;
+    }
+    OutRec * outRec_origin;
+    OutRec * outRec_search;
+    OutRec * outRec_parent;
+    OutPt * op_origin_1;
+    OutPt * op_origin_2;
+    if (!outRec_j->IsHole)
+    {
+        outRec_origin = outRec_j;
+        outRec_parent = outRec_origin;
+        outRec_search = outRec_k;
+        op_origin_1 = op_j;
+        op_origin_2 = op_k;
+    }
+    else if (!outRec_k->IsHole)
+    {
+        outRec_origin = outRec_k;
+        outRec_parent = outRec_origin;
+        outRec_search = outRec_k;
+        outRec_search = outRec_j;
+        op_origin_1 = op_k;
+        op_origin_2 = op_j;
+
+    }
+    else // both are holes
+    {
+        // Order doesn't matter
+        outRec_origin = outRec_j;
+        outRec_parent = ParseFirstLeft(outRec_origin->FirstLeft);
+        outRec_search = outRec_k;
+        outRec_search = outRec_k;
+        op_origin_1 = op_j;
+        op_origin_2 = op_k;
+    }
+    if (outRec_parent != ParseFirstLeft(outRec_search->FirstLeft))
+    {
+        // The two holes do not have the same parent, do not add them
+        // simply return!
+        return false;
+    }
+    bool found = false;
+    std::list<std::pair<const int, OutPtIntersect> > iList;
+    auto range = dupeRec.equal_range(outRec_search->Idx);
+    // Check for direct connection
+    for (auto it = range.first; it != range.second; ++it)
+    {
+        OutRec * itRec = GetOutRec(it->second.op2->Idx);
+        if (itRec->Idx == outRec_origin->Idx)
+        {
+            found = true;
+            if (op_origin_1->Pt != it->second.op2->Pt)
+            {
+                iList.emplace_back(outRec_search->Idx, it->second);
+                break;
+            }
+        }
+    }
+    if (!found)
+    {
+        // Check for connection through chain of other intersections
+        for (auto it = range.first; it != range.second; ++it)
+        {
+            OutRec * itRec = GetOutRec(it->second.op2->Idx);
+            if (itRec->IsHole && (outRec_parent == itRec || outRec_parent == 
ParseFirstLeft(itRec->FirstLeft)) &&
+                FindIntersectLoop(dupeRec, iList, outRec_parent, 
outRec_origin->Idx, outRec_search->Idx, itRec->Idx))
+            {
+                found = true;
+                iList.emplace_front(outRec_search->Idx, it->second);
+                break;
+            }
+        }
+    }
+    if (!found)
+    {
+        OutPtIntersect intPt_origin = { op_origin_1, op_origin_2 };
+        OutPtIntersect intPt_search = { op_origin_2, op_origin_1 };
+        dupeRec.emplace(outRec_origin->Idx, intPt_origin);
+        dupeRec.emplace(outRec_search->Idx, intPt_search);
+        return false;
+    }
+    
+    if (iList.empty())
+    {
+        return false;
+    }
+    // Switch 
+    OutPt * op_origin_1_next = op_origin_1->Next;
+    OutPt * op_origin_2_next = op_origin_2->Next;
+    op_origin_1->Next = op_origin_2_next;
+    op_origin_2->Next = op_origin_1_next;
+    op_origin_1_next->Prev = op_origin_2;
+    op_origin_2_next->Prev = op_origin_1;
+    
+    for (auto iRing : iList)
+    {
+        OutPt * op_search_1 = iRing.second.op1;
+        OutPt * op_search_2 = iRing.second.op2;
+        OutPt * op_search_1_next = op_search_1->Next;
+        OutPt * op_search_2_next = op_search_2->Next;
+        op_search_1->Next = op_search_2_next;
+        op_search_2->Next = op_search_1_next;
+        op_search_1_next->Prev = op_search_2;
+        op_search_2_next->Prev = op_search_1;
+    }
+
+    OutRec * outRec_new = CreateOutRec();
+    outRec_new->IsHole = false;
+    if (outRec_origin->IsHole == ((Area(op_origin_1) > 0) && m_ReverseOutput))
+    {
+        outRec_origin->Pts = op_origin_1;
+        outRec_new->Pts = op_origin_2;
+    }
+    else
+    {
+        outRec_origin->Pts = op_origin_2;
+        outRec_new->Pts = op_origin_1;
+    }
+    
+    UpdateOutPtIdxs(*outRec_origin);
+    UpdateOutPtIdxs(*outRec_new);
+    
+    outRec_origin->BottomPt = 0;
+
+    std::list<std::pair<const int, OutPtIntersect> > move_list;
+    for (auto iRing : iList)
+    {
+        OutRec * outRec_itr = GetOutRec(iRing.first);
+        int itr_idx = outRec_itr->Idx;
+        outRec_itr->Pts = 0;
+        outRec_itr->BottomPt = 0;
+        outRec_itr->Idx = outRec_origin->Idx;
+        if (outRec_origin->IsHole)
+        {
+            outRec_itr->FirstLeft = ParseFirstLeft(outRec_origin->FirstLeft);
+        }
+        else
+        {
+            outRec_itr->FirstLeft = outRec_origin;
+        }
+        outRec_itr->IsHole = outRec_origin->IsHole;
+        if (m_UsingPolyTree) 
+        {
+            FixupFirstLefts3(outRec_itr, outRec_origin);
+        }
+        auto range_itr = dupeRec.equal_range(itr_idx);
+        if (range_itr.first != range_itr.second)
+        {
+            for (auto it = range_itr.first; it != range_itr.second; ++it)
+            {
+                OutRec * itRec1 = GetOutRec(it->second.op1->Idx);
+                OutRec * itRec2 = GetOutRec(it->second.op2->Idx);
+                if (!(itRec1->Idx == outRec_new->Idx && itRec2->Idx == 
outRec_origin->Idx) &&
+                     !(itRec2->Idx == outRec_new->Idx && itRec1->Idx == 
outRec_origin->Idx) &&
+                    (itRec1->IsHole || itRec2->IsHole))
+                {
+                    move_list.emplace_back(itRec1->Idx, it->second);
+                }
+            }
+            dupeRec.erase(itr_idx);
+        }
+    }
+    if (outRec_origin->IsHole)
+    {
+        outRec_new->FirstLeft = outRec_origin;
+    }
+    else
+    {
+        outRec_new->FirstLeft = outRec_origin->FirstLeft;
+    }
+    auto range_itr = dupeRec.equal_range(outRec_origin->Idx);
+    for (auto it = range_itr.first; it != range_itr.second;)
+    {
+        OutRec * itRec1 = GetOutRec(it->second.op1->Idx);
+        OutRec * itRec2 = GetOutRec(it->second.op2->Idx);
+        if (!(itRec1->Idx == outRec_origin->Idx) &&
+            (itRec1->IsHole || itRec2->IsHole))
+        {
+            move_list.emplace_back(itRec1->Idx, it->second);
+            it = dupeRec.erase(it);
+        }
+        else
+        {
+            ++it;
+        }
+    }
+
+    if (m_UsingPolyTree)
+    {
+        if (outRec_origin->IsHole)
+        {
+            FixupFirstLefts2(outRec_new, outRec_origin);
+        }
+        else
+        {
+            FixupFirstLefts1(outRec_origin, outRec_new);
+        }
+    }
+    if (!move_list.empty())
+    {
+        dupeRec.insert(move_list.begin(), move_list.end());
+    }
+    return true;
+}
+
+//-----------------------------------------------------------------------------
+
 void Clipper::DoSimplePolygons()
 {
-  PolyOutList::size_type i = 0;
-  while (i < m_PolyOuts.size()) 
-  {
-    OutRec* outrec = m_PolyOuts[i++];
-    OutPt* op = outrec->Pts;
-    if (!op || outrec->IsOpen) continue;
-    do //for each Pt in Polygon until duplicate found do ...
+    std::vector < OutPt*> m_OutPts;
     {
-      OutPt* op2 = op->Next;
-      while (op2 != outrec->Pts) 
-      {
-        if ((op->Pt == op2->Pt) && op2->Next != op && op2->Prev != op) 
+        PolyOutList::size_type i = 0;
+        while (i < m_PolyOuts.size()) 
         {
-          //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))
-          {
-            //OutRec2 is contained by OutRec1 ...
-            outrec2->IsHole = !outrec->IsHole;
-            outrec2->FirstLeft = outrec;
-            if (m_UsingPolyTree) FixupFirstLefts2(outrec2, outrec);
-          }
-          else
-            if (Poly2ContainsPoly1(outrec->Pts, outrec2->Pts))
-          {
-            //OutRec1 is contained by OutRec2 ...
-            outrec2->IsHole = outrec->IsHole;
-            outrec->IsHole = !outrec2->IsHole;
-            outrec2->FirstLeft = outrec->FirstLeft;
-            outrec->FirstLeft = outrec2;
-            if (m_UsingPolyTree) FixupFirstLefts2(outrec, outrec2);
+            OutRec* outrec = m_PolyOuts[i++];
+            OutPt* op = outrec->Pts;
+            if (!op || outrec->IsOpen) continue;
+            do
+            {
+                m_OutPts.push_back(op);
+                op = op->Next;
             }
-            else
-          {
-            //the 2 polygons are separate ...
-            outrec2->IsHole = outrec->IsHole;
-            outrec2->FirstLeft = outrec->FirstLeft;
-            if (m_UsingPolyTree) FixupFirstLefts1(outrec, outrec2);
+            while (op != outrec->Pts);
+        }
+    }
+    std::stable_sort(m_OutPts.begin(), m_OutPts.end(), SortOutPt);
+    std::unordered_multimap<int, OutPtIntersect> dupeRec;
+    dupeRec.reserve(m_PolyOuts.size());
+    std::size_t count = 0;
+    for (std::size_t i = 1; i < m_OutPts.size(); ++i)
+    {
+        if (m_OutPts[i]->Pt == m_OutPts[i-1]->Pt) 
+        {
+            ++count;
+            continue;
+        }
+        if (count > 0)
+        {
+            for (std::size_t j = (i - count - 1); j < i; ++j)
+            {
+                if (m_OutPts[j]->Idx < 0) continue;
+                OutRec * outRec_j = GetOutRec(m_OutPts[j]->Idx);
+                int idx_j = outRec_j->Idx;
+                for (std::size_t k = j + 1; k < i; ++k)
+                {
+                    if (m_OutPts[k]->Idx < 0) continue;
+                    OutRec * outRec_k = GetOutRec(m_OutPts[k]->Idx);
+                    int idx_k = outRec_k->Idx;
+                    if (idx_k == idx_j)
+                    {
+                        OutPt * op = m_OutPts[j];
+                        OutPt * op2 = m_OutPts[k];
+                        OutRec * outrec = outRec_j;
+                        if (op != op2 && 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))
+                            {
+                                //OutRec2 is contained by OutRec1 ...
+                                outrec2->IsHole = !outrec->IsHole;
+                                outrec2->FirstLeft = outrec;
+                                if (m_UsingPolyTree) 
+                                {
+                                    FixupFirstLefts2(outrec2, outrec);
+                                }
+                                auto range = dupeRec.equal_range(idx_k);
+                                std::list<std::pair<const int, OutPtIntersect> 
> move_list;
+                                for (auto it = range.first; it != 
range.second;)
+                                {
+                                    OutRec * itRec = 
GetOutRec(it->second.op1->Idx);
+                                    if (itRec->Idx != idx_k)
+                                    {
+                                        OutRec * itRec2 = 
GetOutRec(it->second.op2->Idx);
+                                        if (itRec->IsHole || itRec2->IsHole)
+                                        {
+                                            move_list.emplace_back(itRec->Idx, 
it->second);
+                                        }
+                                        it = dupeRec.erase(it);
+                                    }
+                                    else
+                                    {
+                                        ++it;
+                                    }
+                                }
+                                if (!move_list.empty())
+                                {
+                                    dupeRec.insert(move_list.begin(), 
move_list.end());
+                                }
+                                OutPtIntersect intPt1 = { op, op2 };
+                                OutPtIntersect intPt2 = { op2, op };
+                                dupeRec.emplace(idx_k, intPt1);
+                                dupeRec.emplace(outrec2->Idx, intPt2);
+                            }
+                            else if (Poly2ContainsPoly1(outrec->Pts, 
outrec2->Pts))
+                            {
+                                //OutRec1 is contained by OutRec2 ...
+                                outrec2->IsHole = outrec->IsHole;
+                                outrec->IsHole = !outrec2->IsHole;
+                                outrec2->FirstLeft = outrec->FirstLeft;
+                                outrec->FirstLeft = outrec2;
+                                if (m_UsingPolyTree)
+                                {
+                                    FixupFirstLefts2(outrec, outrec2);
+                                }
+                                auto range = dupeRec.equal_range(idx_k);
+                                std::list<std::pair<const int, OutPtIntersect> 
> move_list;
+                                for (auto it = range.first; it != 
range.second;)
+                                {
+                                    OutRec * itRec = 
GetOutRec(it->second.op1->Idx);
+                                    if (itRec->Idx != idx_k)
+                                    {
+                                        OutRec * itRec2 = 
GetOutRec(it->second.op2->Idx);
+                                        if (itRec->IsHole || itRec2->IsHole)
+                                        {
+                                            move_list.emplace_back(itRec->Idx, 
it->second);
+                                        }
+                                        it = dupeRec.erase(it);
+                                    }
+                                    else
+                                    {
+                                        ++it;
+                                    }
+                                }
+                                if (!move_list.empty())
+                                {
+                                    dupeRec.insert(move_list.begin(), 
move_list.end());
+                                }
+                                OutPtIntersect intPt1 = { op, op2 };
+                                OutPtIntersect intPt2 = { op2, op };
+                                dupeRec.emplace(idx_k, intPt1);
+                                dupeRec.emplace(outrec2->Idx, intPt2);
+                            }
+                            else
+                            {
+                                //the 2 polygons are separate ...
+                                outrec2->IsHole = outrec->IsHole;
+                                outrec2->FirstLeft = outrec->FirstLeft;
+                                if (m_UsingPolyTree)
+                                {
+                                    FixupFirstLefts1(outrec, outrec2);
+                                }
+                                auto range = dupeRec.equal_range(idx_k);
+                                std::list<std::pair<const int, OutPtIntersect> 
> move_list;
+                                for (auto it = range.first; it != 
range.second;)
+                                {
+                                    OutRec * itRec = 
GetOutRec(it->second.op1->Idx);
+                                    if (itRec->Idx != idx_k)
+                                    {
+                                        OutRec * itRec2 = 
GetOutRec(it->second.op2->Idx);
+                                        if (itRec->IsHole || itRec2->IsHole)
+                                        {
+                                            move_list.emplace_back(itRec->Idx, 
it->second);
+                                        }
+                                        it = dupeRec.erase(it);
+                                    }
+                                    else
+                                    {
+                                        ++it;
+                                    }
+                                }
+                                if (!move_list.empty())
+                                {
+                                    dupeRec.insert(move_list.begin(), 
move_list.end());
+                                }
+                                if (outrec2->IsHole)
+                                {
+                                    OutPtIntersect intPt1 = { op, op2 };
+                                    OutPtIntersect intPt2 = { op2, op };
+                                    dupeRec.emplace(idx_k, intPt1);
+                                    dupeRec.emplace(outrec2->Idx, intPt2);
+                                }
+                            }
+                        }
+                        continue;
+                    }
+                    if (FixIntersects(dupeRec, m_OutPts[j], m_OutPts[k], 
outRec_j, outRec_k))
+                    {
+                        outRec_j = GetOutRec(m_OutPts[j]->Idx);
+                        idx_j = outRec_j->Idx;
+                    }
+                }
             }
-          op2 = op; //ie get ready for the Next iteration
+            count = 0;
         }
-        op2 = op2->Next;
-      }
-      op = op->Next;
     }
-    while (op != outrec->Pts);
-  }
 }
 
//------------------------------------------------------------------------------
 
diff --git a/debian/clipper.hpp b/debian/clipper.hpp
index d0845fe..43a942d 100644
--- a/debian/clipper.hpp
+++ b/debian/clipper.hpp
@@ -58,6 +58,7 @@
 #include <ostream>
 #include <functional>
 #include <queue>
+#include <unordered_map>
 #if defined(CLIPPER_IMPL_INCLUDE)
 #include CLIPPER_IMPL_INCLUDE
 #endif
@@ -235,6 +236,7 @@ struct LocalMinimum;
 struct OutPt;
 struct OutRec;
 struct Join;
+struct OutPtIntersect;
 
 typedef std::vector < OutRec* > PolyOutList;
 typedef std::vector < TEdge* > EdgeList;
@@ -320,7 +322,6 @@ protected:
 private:
   JoinList         m_Joins;
   JoinList         m_GhostJoins;
-  JoinList         m_SSJoins;
   IntersectList    m_IntersectList;
   ClipType         m_ClipType;
   typedef std::list<cInt> MaximaList;
@@ -374,12 +375,21 @@ private:
   void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt);
   void ClearJoins();
   void ClearGhostJoins();
-  void ClearSSJoins();
   void AddGhostJoin(OutPt *op, const IntPoint offPt);
-  void AddSSJoin(OutPt *op1, OutPt *op2, const IntPoint offPt);
   bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2);
   void JoinCommonEdges();
   void DoSimplePolygons();
+  bool FindIntersectLoop(std::unordered_multimap<int, OutPtIntersect> & 
dupeRec,
+                         std::list<std::pair<const int, OutPtIntersect> > & 
iList,
+                         OutRec * outRec_parent,
+                         int idx_origin,
+                         int idx_prev,
+                         int idx_search);
+  bool FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeRec,
+                     OutPt * op_j,
+                     OutPt * op_k,
+                     OutRec * outRec_j,
+                     OutRec * outRec_k);
   void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec);
   void FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec);
   void FixupFirstLefts3(OutRec* OldOutRec, OutRec* NewOutRec);

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-grass/mapnik-vector-tile.git

_______________________________________________
Pkg-grass-devel mailing list
Pkg-grass-devel@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel

Reply via email to