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 247a8b5f5d093fe5b1740ae43c0d98274251dddf Author: Bas Couwenberg <sebas...@xs4all.nl> Date: Fri Apr 8 09:42:48 2016 +0200 Update clipper to 68c49e9a9adaff1ddddb008eaf49f71bf259c4e8. --- debian/changelog | 1 + debian/clipper.cpp | 497 +++++++++++++++++++++++++++++++++++++++++------------ debian/clipper.hpp | 6 +- 3 files changed, 394 insertions(+), 110 deletions(-) diff --git a/debian/changelog b/debian/changelog index fd5f0f6..c9587aa 100644 --- a/debian/changelog +++ b/debian/changelog @@ -1,6 +1,7 @@ mapnik-vector-tile (1.0.6+dfsg-1) UNRELEASED; urgency=medium * New upstream release. + * Update clipper to 68c49e9a9adaff1ddddb008eaf49f71bf259c4e8. -- Bas Couwenberg <sebas...@debian.org> Fri, 08 Apr 2016 09:41:38 +0200 diff --git a/debian/clipper.cpp b/debian/clipper.cpp index 61d89eb..3c1f3f0 100644 --- a/debian/clipper.cpp +++ b/debian/clipper.cpp @@ -684,23 +684,49 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) cInt y2 = ip.y; if (Edge1.Bot.x > ip.x) { - y1 = Round((ip.x + 0.5) / Edge1.Dx + by1); - if (ip.y >= Edge1.Bot.y && y1 < Edge1.Bot.y) y1 = Edge1.Bot.y; - else if (ip.y <= Edge1.Bot.y && y1 > Edge1.Bot.y) y1 = Edge1.Bot.y; + if (Edge1.Bot.y >= ip.y) + { + y1 = std::floor(((ip.x + 0.5) / Edge1.Dx + by1) + 0.5); + } + else + { + y1 = std::ceil(((ip.x + 0.5) / Edge1.Dx + by1) - 0.5); + } } else if (Edge1.Bot.x < ip.x) { - y1 = Round((ip.x - 0.5) / Edge1.Dx + by1); + if (Edge1.Bot.y >= ip.y) + { + y1 = std::floor(((ip.x - 0.5) / Edge1.Dx + by1) + 0.5); + } + else + { + y1 = std::ceil(((ip.x - 0.5) / Edge1.Dx + by1) - 0.5); + } } if (ip.y >= Edge1.Bot.y && y1 < Edge1.Bot.y) y1 = Edge1.Bot.y; else if (ip.y <= Edge1.Bot.y && y1 > Edge1.Bot.y) y1 = Edge1.Bot.y; if (Edge2.Bot.x > ip.x) { - y2 = Round((ip.x + 0.5) / Edge2.Dx + by2); + if (Edge2.Bot.y >= ip.y) + { + y2 = std::floor(((ip.x + 0.5) / Edge2.Dx + by2) + 0.5); + } + else + { + y2 = std::ceil(((ip.x + 0.5) / Edge2.Dx + by2) - 0.5); + } } else if (Edge2.Bot.x < ip.x) { - y2 = Round((ip.x - 0.5) / Edge2.Dx + by2); + if (Edge2.Bot.y >= ip.y) + { + y2 = std::floor(((ip.x - 0.5) / Edge2.Dx + by2) + 0.5); + } + else + { + y2 = std::ceil(((ip.x - 0.5) / Edge2.Dx + by2) - 0.5); + } } if (ip.y >= Edge2.Bot.y && y2 < Edge2.Bot.y) y2 = Edge2.Bot.y; else if (ip.y <= Edge2.Bot.y && y2 > Edge2.Bot.y) y2 = Edge2.Bot.y; @@ -708,21 +734,49 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) cInt x2 = ip.x; if (Edge1.Bot.y > ip.y) { - x1 = Round((ip.y + 0.5) * Edge1.Dx + bx1); + if (Edge1.Bot.x >= ip.x) + { + x1 = std::floor(((ip.y + 0.5) * Edge1.Dx + bx1) + 0.5); + } + else + { + x1 = std::ceil(((ip.y + 0.5) * Edge1.Dx + bx1) - 0.5); + } } else if (Edge1.Bot.y < ip.y) { - x1 = Round((ip.y - 0.5) * Edge1.Dx + bx1); + if (Edge1.Bot.x >= ip.x) + { + x1 = std::floor(((ip.y - 0.5) * Edge1.Dx + bx1) + 0.5); + } + else + { + x1 = std::ceil(((ip.y - 0.5) * Edge1.Dx + bx1) - 0.5); + } } if (ip.x >= Edge1.Bot.x && x1 < Edge1.Bot.x) x1 = Edge1.Bot.x; else if (ip.x <= Edge1.Bot.x && x1 > Edge1.Bot.x) x1 = Edge1.Bot.x; if (Edge2.Bot.y > ip.y) { - x2 = Round((ip.y + 0.5) * Edge2.Dx + bx2); + if (Edge2.Bot.x >= ip.x) + { + x2 = std::floor(((ip.y + 0.5) * Edge2.Dx + bx2) + 0.5); + } + else + { + x2 = std::ceil(((ip.y + 0.5) * Edge2.Dx + bx2) - 0.5); + } } else if (Edge2.Bot.y < ip.y) { - x2 = Round((ip.y - 0.5) * Edge2.Dx + bx2); + if (Edge2.Bot.x >= ip.x) + { + x2 = std::floor(((ip.y - 0.5) * Edge2.Dx + bx2) + 0.5); + } + else + { + x2 = std::ceil(((ip.y - 0.5) * Edge2.Dx + bx2) - 0.5); + } } if (ip.x >= Edge2.Bot.x && x2 < Edge2.Bot.x) x2 = Edge2.Bot.x; else if (ip.x <= Edge2.Bot.x && x2 > Edge2.Bot.x) x2 = Edge2.Bot.x; @@ -3090,7 +3144,14 @@ void Clipper::ProcessIntersectList() bool IntersectListSort(IntersectNode* node1, IntersectNode* node2) { - return node2->Pt.y < node1->Pt.y; + if (node2->Pt.y != node1->Pt.y) + { + return node2->Pt.y < node1->Pt.y; + } + else + { + return (node2->Edge1->WindCnt2 + node2->Edge2->WindCnt2) > (node1->Edge1->WindCnt2 + node1->Edge2->WindCnt2); + } } //------------------------------------------------------------------------------ @@ -3233,6 +3294,7 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY) { m_Maxima.push_back(e->Top.x); m_Maxima.push_back(e->Bot.x); + next_maxima.push_back(e->Bot.x); } } AddEdgeToSEL(e); @@ -3245,19 +3307,23 @@ void Clipper::ProcessEdgesAtTopOfScanbeam(const cInt topY) //When StrictlySimple and 'e' is being touched by another edge, then //make sure both edges have a vertex here ... - if (m_StrictSimple) + if (m_StrictSimple && e->OutIdx >= 0 && e->WindDelta != 0) { TEdge* ePrev = e->PrevInAEL; - if ((e->OutIdx >= 0) && (e->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) && - (ePrev->Curr.x == e->Curr.x) && (ePrev->WindDelta != 0)) + while (ePrev && ePrev->Curr.x == e->Curr.x) { - IntPoint pt = e->Curr; + if (ePrev->OutIdx >= 0 && ePrev->WindDelta != 0 && + !(e->Bot == ePrev->Bot && e->Top == ePrev->Top)) + { + IntPoint pt = e->Curr; #ifdef use_xyz - SetZ(pt, *ePrev, *e); + SetZ(pt, *ePrev, *e); #endif - OutPt* op = AddOutPt(ePrev, pt); - OutPt* op2 = AddOutPt(e, pt); - AddJoin(op, op2, pt); //StrictlySimple (type-3) join + OutPt* op = AddOutPt(ePrev, pt); + OutPt* op2 = AddOutPt(e, pt); + AddJoin(op, op2, pt); //StrictlySimple (type-3) join + } + ePrev = ePrev->PrevInAEL; } } @@ -3879,7 +3945,14 @@ void Clipper::FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec) if (outRec->Pts && firstLeft == OldOutRec) { if (Poly2ContainsPoly1(outRec->Pts, NewOutRec->Pts)) + { + if (outRec->IsHole == NewOutRec->IsHole) + { + outRec->IsHole = !outRec->IsHole; + ReversePolyPtLinks(outRec->Pts); + } outRec->FirstLeft = NewOutRec; + } } } } @@ -3891,7 +3964,6 @@ void Clipper::FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec) //It's possible that these polygons now wrap around other polygons, so check //every polygon that's also contained by OuterOutRec's FirstLeft container //(including 0) to see if they've become inner to the new inner polygon ... - OutRec* orfl = ParseFirstLeft(OuterOutRec->FirstLeft); for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) { OutRec* outRec = m_PolyOuts[i]; @@ -3899,14 +3971,28 @@ void Clipper::FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec) if (!outRec->Pts || outRec == OuterOutRec || outRec == InnerOutRec) continue; OutRec* firstLeft = ParseFirstLeft(outRec->FirstLeft); - if (firstLeft != orfl && firstLeft != InnerOutRec && firstLeft != OuterOutRec) + if (firstLeft != InnerOutRec && firstLeft != OuterOutRec) continue; if (Poly2ContainsPoly1(outRec->Pts, InnerOutRec->Pts)) - outRec->FirstLeft = InnerOutRec; - else if (Poly2ContainsPoly1(outRec->Pts, OuterOutRec->Pts)) - outRec->FirstLeft = OuterOutRec; - else if (firstLeft == InnerOutRec || firstLeft == OuterOutRec) - outRec->FirstLeft = orfl; + { + if (outRec->IsHole == InnerOutRec->IsHole) + { + outRec->IsHole = !outRec->IsHole; + ReversePolyPtLinks(outRec->Pts); + } + outRec->FirstLeft = InnerOutRec; + } + else + { + if (outRec->IsHole == OuterOutRec->IsHole) + { + outRec->FirstLeft = ParseFirstLeft(OuterOutRec->FirstLeft); + } + else + { + outRec->FirstLeft = OuterOutRec; + } + } } } //---------------------------------------------------------------------- @@ -3950,10 +4036,18 @@ void Clipper::JoinCommonEdges() { //instead of joining two polygons, we've just created a new one by //splitting one polygon into two. - outRec1->Pts = join->OutPt1; outRec1->BottomPt = 0; outRec2 = CreateOutRec(); - outRec2->Pts = join->OutPt2; + if (PointCount(join->OutPt1) > PointCount(join->OutPt2)) + { + outRec1->Pts = join->OutPt1; + outRec2->Pts = join->OutPt2; + } + else + { + outRec1->Pts = join->OutPt2; + outRec2->Pts = join->OutPt1; + } //update all OutRec2.Pts Idx's ... UpdateOutPtIdxs(*outRec2); @@ -4501,37 +4595,48 @@ struct OutPtIntersect //----------------------------------------------------------------------------- bool Clipper::FindIntersectLoop(std::unordered_multimap<int, OutPtIntersect> & dupeRec, - std::list<std::pair<const int, OutPtIntersect> > & iList, + std::list<std::pair<int, OutPtIntersect> > & iList, OutRec * outRec_parent, int idx_origin, - int idx_prev, - int idx_search) + int idx_search, + std::set<int> & visited, + OutPt * orig_pt, + OutPt * prev_pt) { auto range = dupeRec.equal_range(idx_search); // Check for direct connection - for (auto it = range.first; it != range.second; ++it) + for (auto it = range.first; it != range.second;) { - OutRec * itRec = GetOutRec(it->second.op2->Idx); - if (itRec->Idx == idx_prev) + OutRec * itRec1 = GetOutRec(it->second.op1->Idx); + OutRec * itRec2 = GetOutRec(it->second.op2->Idx); + if (itRec1->Idx != idx_search || (!itRec1->IsHole && !itRec2->IsHole)) { + it = dupeRec.erase(it); continue; } - if (itRec->Idx == idx_origin && (outRec_parent == itRec || outRec_parent == ParseFirstLeft(itRec->FirstLeft))) + if (itRec2->Idx == idx_origin && + (outRec_parent == itRec2 || outRec_parent == ParseFirstLeft(itRec2->FirstLeft)) && + prev_pt->Pt != it->second.op2->Pt && + orig_pt->Pt != it->second.op2->Pt) { iList.emplace_front(idx_search, it->second); return true; } + ++it; } + range = dupeRec.equal_range(idx_search); + visited.insert(idx_search); // 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))) + if (visited.count(itRec->Idx) > 0 || + (outRec_parent != itRec && outRec_parent != ParseFirstLeft(itRec->FirstLeft)) + || prev_pt->Pt == it->second.op2->Pt) { continue; } - if (FindIntersectLoop(dupeRec, iList, outRec_parent, idx_origin, idx_search, itRec->Idx)) + if (FindIntersectLoop(dupeRec, iList, outRec_parent, idx_origin, itRec->Idx, visited, orig_pt, it->second.op2)) { iList.emplace_front(idx_search, it->second); return true; @@ -4570,7 +4675,6 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR { 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; @@ -4582,7 +4686,6 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR 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; } @@ -4593,13 +4696,19 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR return false; } bool found = false; - std::list<std::pair<const int, OutPtIntersect> > iList; + std::list<std::pair<int, OutPtIntersect> > iList; auto range = dupeRec.equal_range(outRec_search->Idx); // Check for direct connection - for (auto it = range.first; it != range.second; ++it) + for (auto it = range.first; it != range.second;) { - OutRec * itRec = GetOutRec(it->second.op2->Idx); - if (itRec->Idx == outRec_origin->Idx) + OutRec * itRec1 = GetOutRec(it->second.op1->Idx); + OutRec * itRec2 = GetOutRec(it->second.op2->Idx); + if (outRec_search->Idx != itRec1->Idx || outRec_search->Idx == itRec2->Idx) + { + it = dupeRec.erase(it); + continue; + } + if (itRec2->Idx == outRec_origin->Idx) { found = true; if (op_origin_1->Pt != it->second.op2->Pt) @@ -4608,15 +4717,21 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR break; } } + ++it; } if (!found) { + range = dupeRec.equal_range(outRec_search->Idx); + std::set<int> visited; + visited.insert(outRec_search->Idx); // 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)) + if (itRec->Idx != outRec_search->Idx && + op_origin_2->Pt != it->second.op2->Pt && + (outRec_parent == itRec || outRec_parent == ParseFirstLeft(itRec->FirstLeft)) && + FindIntersectLoop(dupeRec, iList, outRec_parent, outRec_origin->Idx, itRec->Idx, visited, op_origin_2, it->second.op2)) { found = true; iList.emplace_front(outRec_search->Idx, it->second); @@ -4637,6 +4752,28 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR { return false; } + if (outRec_origin->IsHole) + { + for (auto & iRing : iList) + { + OutRec * outRec_itr = GetOutRec(iRing.first); + if (!outRec_itr->IsHole) + { + // Make the hole the origin! + OutPt * op1 = op_origin_1; + op_origin_1 = iRing.second.op1; + iRing.second.op1 = op1; + OutPt * op2 = op_origin_2; + op_origin_2 = iRing.second.op2; + iRing.second.op2 = op2; + iRing.first = outRec_origin->Idx; + outRec_origin = outRec_itr; + outRec_parent = outRec_origin; + break; + } + } + } + // Switch OutPt * op_origin_1_next = op_origin_1->Next; OutPt * op_origin_2_next = op_origin_2->Next; @@ -4659,7 +4796,7 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR OutRec * outRec_new = CreateOutRec(); outRec_new->IsHole = false; - if (outRec_origin->IsHole == ((Area(op_origin_1) > 0) && m_ReverseOutput)) + if (outRec_origin->IsHole && ((Area(op_origin_1) < 0) ^ m_ReverseOutput)) { outRec_origin->Pts = op_origin_1; outRec_new->Pts = op_origin_2; @@ -4669,17 +4806,16 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR 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; + std::list<std::pair<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; @@ -4696,59 +4832,114 @@ bool Clipper::FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeR { FixupFirstLefts3(outRec_itr, outRec_origin); } - auto range_itr = dupeRec.equal_range(itr_idx); + } + if (outRec_origin->IsHole) + { + outRec_new->FirstLeft = outRec_origin; + } + else + { + outRec_new->FirstLeft = outRec_origin->FirstLeft; + } + if (m_UsingPolyTree) + { + if (outRec_origin->IsHole) + { + FixupFirstLefts2(outRec_new, outRec_origin); + } + else + { + FixupFirstLefts1(outRec_origin, outRec_new); + } + } + for (auto iRing : iList) + { + auto range_itr = dupeRec.equal_range(iRing.first); 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 * itRec = 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)) + if (itRec == itRec2) + { + continue; + } + OutRec * flRec; + OutRec * flRec2; + if (itRec->IsHole) + { + flRec = ParseFirstLeft(itRec->FirstLeft); + } + else { - move_list.emplace_back(itRec1->Idx, it->second); + flRec = itRec; + } + if (itRec2->IsHole) + { + flRec2 = ParseFirstLeft(itRec2->FirstLeft); + } + else + { + flRec2 = itRec2; + } + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + move_list.emplace_back(itRec->Idx, it->second); } } - dupeRec.erase(itr_idx); + dupeRec.erase(iRing.first); } } - 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 * itRec = GetOutRec(it->second.op1->Idx); OutRec * itRec2 = GetOutRec(it->second.op2->Idx); - if (!(itRec1->Idx == outRec_origin->Idx) && - (itRec1->IsHole || itRec2->IsHole)) + if (itRec == itRec2) { - move_list.emplace_back(itRec1->Idx, it->second); it = dupeRec.erase(it); + continue; + } + OutRec * flRec; + OutRec * flRec2; + if (itRec->IsHole) + { + flRec = ParseFirstLeft(itRec->FirstLeft); } else { - ++it; + flRec = itRec; } - } - - if (m_UsingPolyTree) - { - if (outRec_origin->IsHole) + if (itRec2->IsHole) { - FixupFirstLefts2(outRec_new, outRec_origin); + flRec2 = ParseFirstLeft(itRec2->FirstLeft); } else { - FixupFirstLefts1(outRec_origin, outRec_new); + flRec2 = itRec2; + } + if (itRec->Idx != outRec_origin->Idx) + { + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + move_list.emplace_back(itRec->Idx, it->second); + } + it = dupeRec.erase(it); + } + else + { + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + ++it; + } + else + { + it = dupeRec.erase(it); + } } } + if (!move_list.empty()) { dupeRec.insert(move_list.begin(), move_list.end()); @@ -4814,9 +5005,18 @@ void Clipper::DoSimplePolygons() op2->Prev = op3; op3->Next = op2; - outrec->Pts = op; OutRec* outrec2 = CreateOutRec(); - outrec2->Pts = op2; + if (PointCount(op) > PointCount(op2)) + { + outrec->Pts = op; + outrec2->Pts = op2; + } + else + { + outrec->Pts = op2; + outrec2->Pts = op; + } + UpdateOutPtIdxs(*outrec); UpdateOutPtIdxs(*outrec2); if (Poly2ContainsPoly1(outrec2->Pts, outrec->Pts)) { @@ -4827,15 +5027,33 @@ void Clipper::DoSimplePolygons() { FixupFirstLefts2(outrec2, outrec); } - auto range = dupeRec.equal_range(idx_k); - std::list<std::pair<const int, OutPtIntersect> > move_list; + auto range = dupeRec.equal_range(idx_j); + std::list<std::pair<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); + OutRec * flRec; + OutRec * flRec2; + if (itRec->IsHole) + { + flRec = ParseFirstLeft(itRec->FirstLeft); + } + else + { + flRec = itRec; + } + if (itRec2->IsHole) { - OutRec * itRec2 = GetOutRec(it->second.op2->Idx); - if (itRec->IsHole || itRec2->IsHole) + flRec2 = ParseFirstLeft(itRec2->FirstLeft); + } + else + { + flRec2 = itRec2; + } + if (itRec->Idx != idx_j) + { + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) { move_list.emplace_back(itRec->Idx, it->second); } @@ -4843,17 +5061,27 @@ void Clipper::DoSimplePolygons() } else { - ++it; + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + ++it; + } + else + { + it = dupeRec.erase(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); + if (!outrec->IsHole) + { + OutPtIntersect intPt1 = { outrec->Pts, outrec2->Pts }; + OutPtIntersect intPt2 = { outrec2->Pts, outrec->Pts }; + dupeRec.emplace(outrec->Idx, intPt1); + dupeRec.emplace(outrec2->Idx, intPt2); + } } else if (Poly2ContainsPoly1(outrec->Pts, outrec2->Pts)) { @@ -4866,15 +5094,33 @@ void Clipper::DoSimplePolygons() { FixupFirstLefts2(outrec, outrec2); } - auto range = dupeRec.equal_range(idx_k); - std::list<std::pair<const int, OutPtIntersect> > move_list; + auto range = dupeRec.equal_range(idx_j); + std::list<std::pair<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); + OutRec * flRec; + OutRec * flRec2; + if (itRec->IsHole) + { + flRec = ParseFirstLeft(itRec->FirstLeft); + } + else + { + flRec = itRec; + } + if (itRec2->IsHole) { - OutRec * itRec2 = GetOutRec(it->second.op2->Idx); - if (itRec->IsHole || itRec2->IsHole) + flRec2 = ParseFirstLeft(itRec2->FirstLeft); + } + else + { + flRec2 = itRec2; + } + if (itRec->Idx != idx_j) + { + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) { move_list.emplace_back(itRec->Idx, it->second); } @@ -4882,17 +5128,27 @@ void Clipper::DoSimplePolygons() } else { - ++it; + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + ++it; + } + else + { + it = dupeRec.erase(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); + if (!outrec2->IsHole) + { + OutPtIntersect intPt1 = { outrec->Pts, outrec2->Pts }; + OutPtIntersect intPt2 = { outrec2->Pts, outrec->Pts }; + dupeRec.emplace(outrec->Idx, intPt1); + dupeRec.emplace(outrec2->Idx, intPt2); + } } else { @@ -4903,15 +5159,33 @@ void Clipper::DoSimplePolygons() { FixupFirstLefts1(outrec, outrec2); } - auto range = dupeRec.equal_range(idx_k); - std::list<std::pair<const int, OutPtIntersect> > move_list; + auto range = dupeRec.equal_range(idx_j); + std::list<std::pair<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); + OutRec * flRec; + OutRec * flRec2; + if (itRec->IsHole) + { + flRec = ParseFirstLeft(itRec->FirstLeft); + } + else + { + flRec = itRec; + } + if (itRec2->IsHole) + { + flRec2 = ParseFirstLeft(itRec2->FirstLeft); + } + else { - OutRec * itRec2 = GetOutRec(it->second.op2->Idx); - if (itRec->IsHole || itRec2->IsHole) + flRec2 = itRec2; + } + if (itRec->Idx != idx_j) + { + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) { move_list.emplace_back(itRec->Idx, it->second); } @@ -4919,7 +5193,14 @@ void Clipper::DoSimplePolygons() } else { - ++it; + if ((itRec->IsHole || itRec2->IsHole) && (flRec == flRec2)) + { + ++it; + } + else + { + it = dupeRec.erase(it); + } } } if (!move_list.empty()) @@ -4928,9 +5209,9 @@ void Clipper::DoSimplePolygons() } if (outrec2->IsHole) { - OutPtIntersect intPt1 = { op, op2 }; - OutPtIntersect intPt2 = { op2, op }; - dupeRec.emplace(idx_k, intPt1); + OutPtIntersect intPt1 = { outrec->Pts, outrec2->Pts }; + OutPtIntersect intPt2 = { outrec2->Pts, outrec->Pts }; + dupeRec.emplace(outrec->Idx, intPt1); dupeRec.emplace(outrec2->Idx, intPt2); } } diff --git a/debian/clipper.hpp b/debian/clipper.hpp index 43a942d..661aeb3 100644 --- a/debian/clipper.hpp +++ b/debian/clipper.hpp @@ -380,11 +380,13 @@ private: void JoinCommonEdges(); void DoSimplePolygons(); bool FindIntersectLoop(std::unordered_multimap<int, OutPtIntersect> & dupeRec, - std::list<std::pair<const int, OutPtIntersect> > & iList, + std::list<std::pair<int, OutPtIntersect> > & iList, OutRec * outRec_parent, int idx_origin, int idx_prev, - int idx_search); + std::set<int> & visited, + OutPt * orig_pt, + OutPt * prev_pt); bool FixIntersects(std::unordered_multimap<int, OutPtIntersect> & dupeRec, OutPt * op_j, OutPt * op_k, -- 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