[mapnik-vector-tile] 04/04: Update clipper to 3eb6a85910affdf070927bba3b6ab12a67a1381b.
Sebastiaan Couwenberg
sebastic at moszumanska.debian.org
Thu Mar 24 23:34:26 UTC 2016
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 <sebastic at 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 <sebastic at 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
More information about the Pkg-grass-devel
mailing list