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 46232be8f065a01ea328199957aeb5d1bb5ace5d Author: Bas Couwenberg <[email protected]> Date: Fri Mar 11 13:31:10 2016 +0100 Update clipper to 150f2c4f58a72c051bcad76c84f10362797bf5ab. --- debian/changelog | 2 +- debian/clipper.cpp | 453 +++++++++++++++++++++++++++++++++++++++++++++++++++-- debian/clipper.hpp | 3 + 3 files changed, 441 insertions(+), 17 deletions(-) diff --git a/debian/changelog b/debian/changelog index fcd5352..715d990 100644 --- a/debian/changelog +++ b/debian/changelog @@ -5,7 +5,7 @@ mapnik-vector-tile (1.0.4+dfsg-1) UNRELEASED; urgency=medium * Refresh patches. * Bump protozero dependency to 1.3.0. * Bump Standards-Version to 3.9.7, no changes. - * Update clipper to b82601d67830a84179888360e3dea645c1125a26. + * Update clipper to 150f2c4f58a72c051bcad76c84f10362797bf5ab. -- Bas Couwenberg <[email protected]> Fri, 11 Mar 2016 13:29:45 +0100 diff --git a/debian/clipper.cpp b/debian/clipper.cpp index 3772e1e..bf369ec 100644 --- a/debian/clipper.cpp +++ b/debian/clipper.cpp @@ -633,7 +633,7 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) ip.x = TopX(Edge1, ip.y); return; } - else if (Edge1.Dx == 0) + else if (Edge1.Dx == 0.0) { ip.x = Edge1.Bot.x; if (IsHorizontal(Edge2)) @@ -641,10 +641,14 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) else { b2 = Edge2.Bot.y - (Edge2.Bot.x / Edge2.Dx); - ip.y = Round(ip.x / Edge2.Dx + b2); + 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) + else if (Edge2.Dx == 0.0) { ip.x = Edge2.Bot.x; if (IsHorizontal(Edge1)) @@ -652,7 +656,11 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) else { b1 = Edge1.Bot.y - (Edge1.Bot.x / Edge1.Dx); - ip.y = Round(ip.x / Edge1.Dx + b1); + 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 @@ -665,6 +673,85 @@ void IntersectPoint(TEdge &Edge1, TEdge &Edge2, IntPoint &ip) ip.x = Round(Edge1.Dx * q + b1); else ip.x = Round(Edge2.Dx * q + b2); + // the idea is simply to looking closer + // towards the origins of the lines (Edge1.Bot and Edge2.Bot) + // until we do not find pixels that both lines travel through + bool keep_searching = false; + double by1 = Edge1.Bot.y - (Edge1.Bot.x / Edge1.Dx); + double by2 = Edge2.Bot.y - (Edge2.Bot.x / Edge2.Dx); + double bx1 = Edge1.Bot.x - (Edge1.Bot.y * Edge1.Dx); + double bx2 = Edge2.Bot.x - (Edge2.Bot.y * Edge2.Dx); + do + { + keep_searching = false; + cInt y1 = ip.y; + 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; + } + else 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 (Edge2.Bot.x > ip.x) + { + y2 = Round((ip.x + 0.5) / Edge2.Dx + by2); + } + else if (Edge2.Bot.x < ip.x) + { + y2 = Round((ip.x - 0.5) / Edge2.Dx + by2); + } + 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; + cInt x1 = ip.x; + cInt x2 = ip.x; + if (Edge1.Bot.y > ip.y) + { + x1 = Round((ip.y + 0.5) * Edge1.Dx + bx1); + } + else if (Edge1.Bot.y < ip.y) + { + x1 = Round((ip.y - 0.5) * Edge1.Dx + bx1); + } + 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); + } + else if (Edge2.Bot.y < ip.y) + { + x2 = Round((ip.y - 0.5) * Edge2.Dx + bx2); + } + 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; + if (y1 > ip.y && y2 > ip.y) + { + ip.y = std::min(y1,y2); + keep_searching = true; + } + else if (y1 < ip.y && y2 < ip.y) + { + ip.y = std::max(y1,y2); + keep_searching = true; + } + if (x1 > ip.x && x2 > ip.x) + { + ip.x = std::min(x1,x2); + keep_searching = true; + } + else if (x1 < ip.x && x2 < ip.x) + { + ip.x = std::max(x1,x2); + keep_searching = true; + } + } + while (keep_searching); } if (ip.y < Edge1.Top.y || ip.y < Edge2.Top.y) @@ -1963,6 +2050,14 @@ 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++) @@ -1981,6 +2076,16 @@ 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; @@ -1996,14 +2101,46 @@ void Clipper::InsertLocalMinimaIntoAEL(const cInt botY) InsertEdgeIntoAEL(rb, 0); SetWindingCount(*rb); if (IsContributing(*rb)) - Op1 = AddOutPt(rb, rb->Bot); + { + Op1 = AddOutPt(rb, rb->Bot); + TEdge* ePrev = rb->PrevInAEL; + if ((rb->OutIdx >= 0) && (rb->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) && + (ePrev->Curr.x == rb->Curr.x) && (ePrev->WindDelta != 0)) + { + IntPoint pt = rb->Curr; + AddOutPt(ePrev, pt); + } + TEdge* eNext = rb->NextInAEL; + if ((rb->OutIdx >= 0) && (rb->WindDelta != 0) && eNext && (eNext->OutIdx >= 0) && + (eNext->Curr.x == rb->Curr.x) && (eNext->WindDelta != 0)) + { + IntPoint pt = rb->Curr; + AddOutPt(eNext, pt); + } + } } else if (!rb) { InsertEdgeIntoAEL(lb, 0); SetWindingCount(*lb); if (IsContributing(*lb)) - Op1 = AddOutPt(lb, lb->Bot); + { + Op1 = AddOutPt(lb, lb->Bot); + TEdge* ePrev = lb->PrevInAEL; + if ((lb->OutIdx >= 0) && (lb->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) && + (ePrev->Curr.x == lb->Curr.x) && (ePrev->WindDelta != 0)) + { + IntPoint pt = lb->Curr; + AddOutPt(ePrev, pt); + } + TEdge* eNext = lb->NextInAEL; + if ((lb->OutIdx >= 0) && (lb->WindDelta != 0) && eNext && (eNext->OutIdx >= 0) && + (eNext->Curr.x == lb->Curr.x) && (eNext->WindDelta != 0)) + { + IntPoint pt = lb->Curr; + AddOutPt(eNext, pt); + } + } InsertScanbeam(lb->Top.y); } else @@ -2014,7 +2151,23 @@ void Clipper::InsertLocalMinimaIntoAEL(const cInt botY) rb->WindCnt = lb->WindCnt; rb->WindCnt2 = lb->WindCnt2; if (IsContributing(*lb)) - Op1 = AddLocalMinPoly(lb, rb, lb->Bot); + { + Op1 = AddLocalMinPoly(lb, rb, lb->Bot); + TEdge* ePrev = lb->PrevInAEL; + if ((lb->OutIdx >= 0) && (lb->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) && + (ePrev->Curr.x == lb->Curr.x) && (ePrev->WindDelta != 0)) + { + IntPoint pt = lb->Curr; + AddOutPt(ePrev, pt); + } + TEdge* eNext = rb->NextInAEL; + if ((rb->OutIdx >= 0) && (rb->WindDelta != 0) && eNext && (eNext->OutIdx >= 0) && + (eNext->Curr.x == rb->Curr.x) && (eNext->WindDelta != 0)) + { + IntPoint pt = rb->Curr; + AddOutPt(eNext, pt); + } + } InsertScanbeam(lb->Top.y); } @@ -2793,6 +2946,27 @@ void Clipper::ProcessHorizontal(TEdge *horzEdge) if(horzEdge->OutIdx >= 0) { op1 = AddOutPt( horzEdge, horzEdge->Top); + //When StrictlySimple and 'horzEdge' is being touched by another edge, then + //make sure both edges have a vertex here ... + if (m_StrictSimple) + { + TEdge* ePrev = horzEdge->PrevInAEL; + if ((horzEdge->WindDelta != 0) && ePrev && (ePrev->OutIdx >= 0) && + (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 + } + 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 + } + } UpdateEdgeIntoAEL(horzEdge); if (horzEdge->WindDelta == 0) return; //nb: HorzEdge is no longer horizontal here @@ -2962,17 +3136,96 @@ void Clipper::DoMaxima(TEdge *e) if (!eMaxPair) { 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; - while(eNext && eNext != eMaxPair) + TEdge* ePrev = e->PrevInAEL; + if (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; + } + } + TEdge* eNext2 = e->NextInAEL; + while(eNext2 && eNext2 != eMaxPair) { - IntersectEdges(e, eNext, e->Top); - SwapPositionsInAEL(e, eNext); - eNext = e->NextInAEL; + IntersectEdges(e, eNext2, e->Top); + SwapPositionsInAEL(e, eNext2); + eNext2 = e->NextInAEL; } if(e->OutIdx == Unassigned && eMaxPair->OutIdx == Unassigned) @@ -2982,9 +3235,17 @@ void Clipper::DoMaxima(TEdge *e) } else if( e->OutIdx >= 0 && eMaxPair->OutIdx >= 0 ) { - if (e->OutIdx >= 0) AddLocalMaxPoly(e, eMaxPair, e->Top); - DeleteFromAEL(e); - DeleteFromAEL(eMaxPair); + AddLocalMaxPoly(e, eMaxPair, e->Top); + if (ePrev) + { + AddOutPt(ePrev, pt); + } + if (eNext) + { + AddOutPt(eNext, pt); + } + DeleteFromAEL(e); + DeleteFromAEL(eMaxPair); } #ifdef use_lines else if (e->WindDelta == 0) @@ -3471,8 +3732,165 @@ bool Clipper::JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2) if (isHorizontal && (j->OffPt == j->OutPt1->Pt) && (j->OffPt == j->OutPt2->Pt)) { + if (outRec1 != outRec2) + { + // First Op1 Next and Op2 Prev + op1b = j->OutPt1->Next; + while (op1b != op1 && (op1b->Pt == j->OffPt)) + op1b = op1b->Next; + op2b = j->OutPt2->Prev; + while (op2b != op2 && (op2b->Pt == j->OffPt)) + op2b = op2b->Prev; + if (op1b->Pt == op2b->Pt) + { + OutPt* op1b_prev = op1b->Prev; + OutPt* op2b_next = op2b->Next; + op1b->Prev = op2b; + op2b->Next = op1b; + op1b_prev->Next = op2b_next; + 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; + while (op2b != op2 && (op2b->Pt == j->OffPt)) + op2b = op2b->Next; + op1b = j->OutPt1->Prev; + while (op1b != op1 && (op1b->Pt == j->OffPt)) + op1b = op1b->Prev; + if (op2b->Pt == op1b->Pt) + { + OutPt* op2b_prev = op2b->Prev; + OutPt* op1b_next = op1b->Next; + op2b->Prev = op1b; + op1b->Next = op2b; + op2b_prev->Next = op1b_next; + 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 ... - if (outRec1 != outRec2) return false; op1b = j->OutPt1->Next; while (op1b != op1 && (op1b->Pt == j->OffPt)) op1b = op1b->Next; @@ -3492,6 +3910,7 @@ 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 { @@ -3503,6 +3922,7 @@ 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; } } @@ -3760,6 +4180,7 @@ void Clipper::JoinCommonEdges() if (m_UsingPolyTree) FixupFirstLefts3(outRec2, outRec1); } } + ClearSSJoins(); } //------------------------------------------------------------------------------ diff --git a/debian/clipper.hpp b/debian/clipper.hpp index 7831b0b..d0845fe 100644 --- a/debian/clipper.hpp +++ b/debian/clipper.hpp @@ -320,6 +320,7 @@ protected: private: JoinList m_Joins; JoinList m_GhostJoins; + JoinList m_SSJoins; IntersectList m_IntersectList; ClipType m_ClipType; typedef std::list<cInt> MaximaList; @@ -373,7 +374,9 @@ 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(); -- 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 [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel
