| clipper.cpp | clipper.cpp | |||
|---|---|---|---|---|
| /************************************************************************** ***** | /************************************************************************** ***** | |||
| * * | * * | |||
| * Author : Angus Johnson * | * Author : Angus Johnson * | |||
| * Version : 4.8.8 | * Version : 4.9.4 | |||
| * | * | |||
| * Date : 30 August 2012 | * Date : 2 November 2012 | |||
| * | * | |||
| * Website : http://www.angusj.com * | * Website : http://www.angusj.com * | |||
| * Copyright : Angus Johnson 2010-2012 * | * Copyright : Angus Johnson 2010-2012 * | |||
| * * | * * | |||
| * License: * | * License: * | |||
| * Use, modification & distribution is subject to Boost Software License Ver 1. * | * Use, modification & distribution is subject to Boost Software License Ver 1. * | |||
| * http://www.boost.org/LICENSE_1_0.txt * | * http://www.boost.org/LICENSE_1_0.txt * | |||
| * * | * * | |||
| * Attributions: * | * Attributions: * | |||
| * The code in this library is an extension of Bala Vatti's clipping algorit hm: * | * The code in this library is an extension of Bala Vatti's clipping algorit hm: * | |||
| * "A generic solution to polygon clipping" * | * "A generic solution to polygon clipping" * | |||
| skipping to change at line 106 | skipping to change at line 106 | |||
| {return (hi == val.hi && lo == val.lo);} | {return (hi == val.hi && lo == val.lo);} | |||
| bool operator != (const Int128 &val) const | bool operator != (const Int128 &val) const | |||
| { return !(*this == val);} | { return !(*this == val);} | |||
| bool operator > (const Int128 &val) const | bool operator > (const Int128 &val) const | |||
| { | { | |||
| if (hi != val.hi) | if (hi != val.hi) | |||
| return hi > val.hi; | return hi > val.hi; | |||
| else | else | |||
| return lo > val.lo; | return ulong64(lo) > ulong64(val.lo); | |||
| } | } | |||
| bool operator < (const Int128 &val) const | bool operator < (const Int128 &val) const | |||
| { | { | |||
| if (hi != val.hi) | if (hi != val.hi) | |||
| return hi < val.hi; | return hi < val.hi; | |||
| else | else | |||
| return lo < val.lo; | return ulong64(lo) < ulong64(val.lo); | |||
| } | } | |||
| bool operator >= (const Int128 &val) const | bool operator >= (const Int128 &val) const | |||
| { return !(*this < val);} | { return !(*this < val);} | |||
| bool operator <= (const Int128 &val) const | bool operator <= (const Int128 &val) const | |||
| { return !(*this > val);} | { return !(*this > val);} | |||
| Int128& operator += (const Int128 &rhs) | Int128& operator += (const Int128 &rhs) | |||
| { | { | |||
| skipping to change at line 228 | skipping to change at line 228 | |||
| if (p.hi < 0) p = p2; | if (p.hi < 0) p = p2; | |||
| else result.lo++; | else result.lo++; | |||
| } | } | |||
| if (negate) Negate(result); | if (negate) Negate(result); | |||
| return result; | return result; | |||
| } | } | |||
| double AsDouble() const | double AsDouble() const | |||
| { | { | |||
| const double shift64 = 18446744073709551616.0; //2^64 | const double shift64 = 18446744073709551616.0; //2^64 | |||
| const double bit64 = 9223372036854775808.0; | ||||
| if (hi < 0) | if (hi < 0) | |||
| { | { | |||
| Int128 tmp(*this); | if (lo == 0) | |||
| Negate(tmp); | return (double)hi * shift64; | |||
| if (tmp.lo < 0) | ||||
| return (double)tmp.lo - bit64 - tmp.hi * shift64; | ||||
| else | else | |||
| return -(double)tmp.lo - tmp.hi * shift64; | return -(double)(ulong64(-lo) + ~hi * shift64); | |||
| } | } | |||
| else if (lo < 0) | ||||
| return -(double)lo + bit64 + hi * shift64; | ||||
| else | else | |||
| return (double)lo + (double)hi * shift64; | return (double)(ulong64(lo) + hi * shift64); | |||
| } | } | |||
| //for bug testing ... | //for bug testing ... | |||
| //std::string AsString() const | //std::string AsString() const | |||
| //{ | //{ | |||
| // std::string result; | // std::string result; | |||
| // unsigned char r = 0; | // unsigned char r = 0; | |||
| // Int128 tmp(0), val(*this); | // Int128 tmp(0), val(*this); | |||
| // if (hi < 0) Negate(val); | // if (hi < 0) Negate(val); | |||
| // result.resize(50); | // result.resize(50); | |||
| skipping to change at line 358 | skipping to change at line 353 | |||
| vec2.Y = poly[jplus].Y - poly[j].Y; | vec2.Y = poly[jplus].Y - poly[j].Y; | |||
| if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange || | if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange || | |||
| Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange) | Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange) | |||
| { | { | |||
| if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange || | if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange || | |||
| Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange) | Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange) | |||
| throw "Coordinate exceeds range bounds."; | throw "Coordinate exceeds range bounds."; | |||
| Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - | Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - | |||
| Int128(vec2.X) * Int128(vec1.Y); | Int128(vec2.X) * Int128(vec1.Y); | |||
| return cross >= 0; | return (cross >= 0); | |||
| } | } | |||
| else | else | |||
| return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0; | return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) | inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) | |||
| { | { | |||
| return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); | return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); | |||
| } | } | |||
| skipping to change at line 506 | skipping to change at line 501 | |||
| } | } | |||
| while (pp2 != pp); | while (pp2 != pp); | |||
| } | } | |||
| return result; | return result; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range) | bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range) | |||
| { | { | |||
| if (UseFullInt64Range) | if (UseFullInt64Range) | |||
| return Int128(e1.ytop - e1.ybot) * Int128(e2.xtop - e2.xbot) == | return Int128(e1.deltaY) * Int128(e2.deltaX) == | |||
| Int128(e1.xtop - e1.xbot) * Int128(e2.ytop - e2.ybot); | Int128(e1.deltaX) * Int128(e2.deltaY); | |||
| else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) == | else return e1.deltaY * e2.deltaX == e1.deltaX * e2.deltaY; | |||
| (e1.xtop - e1.xbot)*(e2.ytop - e2.ybot); | ||||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, | bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, | |||
| const IntPoint pt3, bool UseFullInt64Range) | const IntPoint pt3, bool UseFullInt64Range) | |||
| { | { | |||
| if (UseFullInt64Range) | if (UseFullInt64Range) | |||
| return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) == | return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) == | |||
| Int128(pt1.X-pt2.X) * Int128(pt2.Y-pt3.Y); | Int128(pt1.X-pt2.X) * Int128(pt2.Y-pt3.Y); | |||
| else return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y); | else return (pt1.Y-pt2.Y)*(pt2.X-pt3.X) == (pt1.X-pt2.X)*(pt2.Y-pt3.Y); | |||
| skipping to change at line 542 | skipping to change at line 536 | |||
| double GetDx(const IntPoint pt1, const IntPoint pt2) | double GetDx(const IntPoint pt1, const IntPoint pt2) | |||
| { | { | |||
| return (pt1.Y == pt2.Y) ? | return (pt1.Y == pt2.Y) ? | |||
| HORIZONTAL : (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y); | HORIZONTAL : (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y); | |||
| } | } | |||
| //------------------------------------------------------------------------- -- | //------------------------------------------------------------------------- -- | |||
| void SetDx(TEdge &e) | void SetDx(TEdge &e) | |||
| { | { | |||
| if (e.ybot == e.ytop) e.dx = HORIZONTAL; | e.deltaX = (e.xtop - e.xbot); | |||
| else e.dx = (double)(e.xtop - e.xbot) / (double)(e.ytop - e.ybot); | e.deltaY = (e.ytop - e.ybot); | |||
| if (e.deltaY == 0) e.dx = HORIZONTAL; | ||||
| else e.dx = (double)(e.deltaX) / (double)(e.deltaY); | ||||
| } | } | |||
| //------------------------------------------------------------------------- -- | //------------------------------------------------------------------------- -- | |||
| void SwapSides(TEdge &edge1, TEdge &edge2) | void SwapSides(TEdge &edge1, TEdge &edge2) | |||
| { | { | |||
| EdgeSide side = edge1.side; | EdgeSide side = edge1.side; | |||
| edge1.side = edge2.side; | edge1.side = edge2.side; | |||
| edge2.side = side; | edge2.side = side; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| skipping to change at line 565 | skipping to change at line 562 | |||
| void SwapPolyIndexes(TEdge &edge1, TEdge &edge2) | void SwapPolyIndexes(TEdge &edge1, TEdge &edge2) | |||
| { | { | |||
| int outIdx = edge1.outIdx; | int outIdx = edge1.outIdx; | |||
| edge1.outIdx = edge2.outIdx; | edge1.outIdx = edge2.outIdx; | |||
| edge2.outIdx = outIdx; | edge2.outIdx = outIdx; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| inline long64 Round(double val) | inline long64 Round(double val) | |||
| { | { | |||
| return (val < 0) ? | return (val < 0) ? static_cast<long64>(val - 0.5) : static_cast<long64>(v | |||
| static_cast<long64>(val - 0.5) : static_cast<long64>(val + 0.5); | al + 0.5); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| long64 TopX(TEdge &edge, const long64 currentY) | long64 TopX(TEdge &edge, const long64 currentY) | |||
| { | { | |||
| return ( currentY == edge.ytop ) ? | return ( currentY == edge.ytop ) ? | |||
| edge.xtop : edge.xbot + Round(edge.dx *(currentY - edge.ybot)); | edge.xtop : edge.xbot + Round(edge.dx *(currentY - edge.ybot)); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| skipping to change at line 628 | skipping to change at line 624 | |||
| } | } | |||
| } else | } else | |||
| { | { | |||
| b1 = edge1.xbot - edge1.ybot * edge1.dx; | b1 = edge1.xbot - edge1.ybot * edge1.dx; | |||
| b2 = edge2.xbot - edge2.ybot * edge2.dx; | b2 = edge2.xbot - edge2.ybot * edge2.dx; | |||
| b2 = (b2-b1)/(edge1.dx - edge2.dx); | b2 = (b2-b1)/(edge1.dx - edge2.dx); | |||
| ip.Y = Round(b2); | ip.Y = Round(b2); | |||
| ip.X = Round(edge1.dx * b2 + b1); | ip.X = Round(edge1.dx * b2 + b1); | |||
| } | } | |||
| return | if (ip.Y < edge1.ytop || ip.Y < edge2.ytop) | |||
| //can be *so close* to the top of one edge that the rounded Y equals on | { | |||
| e ytop ... | if (edge1.ytop > edge2.ytop) | |||
| (ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > edge2.tmpX) | | { | |||
| | | ip.X = edge1.xtop; | |||
| (ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > edge2.tmpX) | | ip.Y = edge1.ytop; | |||
| | | return TopX(edge2, edge1.ytop) < edge1.xtop; | |||
| (ip.Y > edge1.ytop && ip.Y > edge2.ytop); | } else | |||
| { | ||||
| ip.X = edge2.xtop; | ||||
| ip.Y = edge2.ytop; | ||||
| return TopX(edge1, edge2.ytop) > edge2.xtop; | ||||
| } | ||||
| } | ||||
| else | ||||
| return true; | ||||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void ReversePolyPtLinks(OutPt &pp) | void ReversePolyPtLinks(OutPt &pp) | |||
| { | { | |||
| OutPt *pp1, *pp2; | OutPt *pp1, *pp2; | |||
| pp1 = &pp; | pp1 = &pp; | |||
| do { | do { | |||
| pp2 = pp1->next; | pp2 = pp1->next; | |||
| pp1->next = pp1->prev; | pp1->next = pp1->prev; | |||
| skipping to change at line 2126 | skipping to change at line 2133 | |||
| { | { | |||
| OutRec *outRec = m_PolyOuts[e->outIdx]; | OutRec *outRec = m_PolyOuts[e->outIdx]; | |||
| OutPt* op = outRec->pts; | OutPt* op = outRec->pts; | |||
| if ((ToFront && PointsEqual(pt, op->pt)) || | if ((ToFront && PointsEqual(pt, op->pt)) || | |||
| (!ToFront && PointsEqual(pt, op->prev->pt))) return; | (!ToFront && PointsEqual(pt, op->prev->pt))) return; | |||
| if ((e->side | outRec->sides) != outRec->sides) | if ((e->side | outRec->sides) != outRec->sides) | |||
| { | { | |||
| //check for 'rounding' artefacts ... | //check for 'rounding' artefacts ... | |||
| if (outRec->sides == esNeither && pt.Y == op->pt.Y) | if (outRec->sides == esNeither && pt.Y == op->pt.Y) | |||
| { | ||||
| if (ToFront) | if (ToFront) | |||
| { | { | |||
| if (pt.X == op->pt.X +1) return; //ie wrong side of bottomPt | if (pt.X == op->pt.X +1) return; //ie wrong side of bottomPt | |||
| } | } | |||
| else if (pt.X == op->pt.X -1) return; //ie wrong side of bottomPt | else if (pt.X == op->pt.X -1) return; //ie wrong side of bottomPt | |||
| } | ||||
| outRec->sides = (EdgeSide)(outRec->sides | e->side); | outRec->sides = (EdgeSide)(outRec->sides | e->side); | |||
| if (outRec->sides == esBoth) | if (outRec->sides == esBoth) | |||
| { | { | |||
| //A vertex from each side has now been added. | //A vertex from each side has now been added. | |||
| //Vertices of one side of an output polygon are quite commonly clos e to | //Vertices of one side of an output polygon are quite commonly clos e to | |||
| //or even 'touching' edges of the other side of the output polygon. | //or even 'touching' edges of the other side of the output polygon. | |||
| //Very occasionally vertices from one side can 'cross' an edge on t he | //Very occasionally vertices from one side can 'cross' an edge on t he | |||
| //the other side. The distance 'crossed' is always less that a unit | //the other side. The distance 'crossed' is always less that a unit | |||
| //and is purely an artefact of coordinate rounding. Nevertheless, t his | //and is purely an artefact of coordinate rounding. Nevertheless, t his | |||
| //results in very tiny self-intersections. Because of the way | //results in very tiny self-intersections. Because of the way | |||
| skipping to change at line 2632 | skipping to change at line 2640 | |||
| void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY) | void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY) | |||
| { | { | |||
| TEdge* e = m_ActiveEdges; | TEdge* e = m_ActiveEdges; | |||
| while( e ) | while( e ) | |||
| { | { | |||
| //1. process maxima, treating them as if they're 'bent' horizontal edge s, | //1. process maxima, treating them as if they're 'bent' horizontal edge s, | |||
| // but exclude maxima with horizontal edges. nb: e can't be a horizon tal. | // but exclude maxima with horizontal edges. nb: e can't be a horizon tal. | |||
| if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, HORIZONTAL) ) | if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, HORIZONTAL) ) | |||
| { | { | |||
| //'e' might be removed from AEL, as may any following edges so ... | //'e' might be removed from AEL, as may any following edges so ... | |||
| TEdge* ePrior = e->prevInAEL; | TEdge* ePrev = e->prevInAEL; | |||
| DoMaxima(e, topY); | DoMaxima(e, topY); | |||
| if( !ePrior ) e = m_ActiveEdges; | if( !ePrev ) e = m_ActiveEdges; | |||
| else e = ePrior->nextInAEL; | else e = ePrev->nextInAEL; | |||
| } | } | |||
| else | else | |||
| { | { | |||
| //2. promote horizontal edges, otherwise update xcurr and ycurr ... | //2. promote horizontal edges, otherwise update xcurr and ycurr ... | |||
| if( IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, HORIZONT AL) ) | if( IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, HORIZONT AL) ) | |||
| { | { | |||
| if (e->outIdx >= 0) | if (e->outIdx >= 0) | |||
| { | { | |||
| AddOutPt(e, IntPoint(e->xtop, e->ytop)); | AddOutPt(e, IntPoint(e->xtop, e->ytop)); | |||
| skipping to change at line 2684 | skipping to change at line 2692 | |||
| //4. Promote intermediate vertices ... | //4. Promote intermediate vertices ... | |||
| e = m_ActiveEdges; | e = m_ActiveEdges; | |||
| while( e ) | while( e ) | |||
| { | { | |||
| if( IsIntermediate( e, topY ) ) | if( IsIntermediate( e, topY ) ) | |||
| { | { | |||
| if( e->outIdx >= 0 ) AddOutPt(e, IntPoint(e->xtop,e->ytop)); | if( e->outIdx >= 0 ) AddOutPt(e, IntPoint(e->xtop,e->ytop)); | |||
| UpdateEdgeIntoAEL(e); | UpdateEdgeIntoAEL(e); | |||
| //if output polygons share an edge, they'll need joining later ... | //if output polygons share an edge, they'll need joining later ... | |||
| if (e->outIdx >= 0 && e->prevInAEL && e->prevInAEL->outIdx >= 0 && | TEdge* ePrev = e->prevInAEL; | |||
| e->prevInAEL->xcurr == e->xbot && e->prevInAEL->ycurr == e->ybot && | TEdge* eNext = e->nextInAEL; | |||
| SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop), | if (ePrev && ePrev->xcurr == e->xbot && | |||
| IntPoint(e->xbot,e->ybot), | ePrev->ycurr == e->ybot && e->outIdx >= 0 && | |||
| IntPoint(e->prevInAEL->xtop, e->prevInAEL->ytop), m_UseFullRange) | ePrev->outIdx >= 0 && ePrev->ycurr > ePrev->ytop && | |||
| ) | SlopesEqual(*e, *ePrev, m_UseFullRange)) | |||
| { | { | |||
| AddOutPt(e->prevInAEL, IntPoint(e->xbot, e->ybot)); | AddOutPt(ePrev, IntPoint(e->xbot, e->ybot)); | |||
| AddJoin(e, e->prevInAEL); | AddJoin(e, ePrev); | |||
| } | } | |||
| else if (e->outIdx >= 0 && e->nextInAEL && e->nextInAEL->outIdx >= 0 | else if (eNext && eNext->xcurr == e->xbot && | |||
| && | eNext->ycurr == e->ybot && e->outIdx >= 0 && | |||
| e->nextInAEL->ycurr > e->nextInAEL->ytop && | eNext->outIdx >= 0 && eNext->ycurr > eNext->ytop && | |||
| e->nextInAEL->ycurr <= e->nextInAEL->ybot && | SlopesEqual(*e, *eNext, m_UseFullRange)) | |||
| e->nextInAEL->xcurr == e->xbot && e->nextInAEL->ycurr == e->ybot && | ||||
| SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop), | ||||
| IntPoint(e->xbot,e->ybot), | ||||
| IntPoint(e->nextInAEL->xtop, e->nextInAEL->ytop), m_UseFullRange) | ||||
| ) | ||||
| { | { | |||
| AddOutPt(e->nextInAEL, IntPoint(e->xbot, e->ybot)); | AddOutPt(eNext, IntPoint(e->xbot, e->ybot)); | |||
| AddJoin(e, e->nextInAEL); | AddJoin(e, eNext); | |||
| } | } | |||
| } | } | |||
| e = e->nextInAEL; | e = e->nextInAEL; | |||
| } | } | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void Clipper::FixupOutPolygon(OutRec &outRec) | void Clipper::FixupOutPolygon(OutRec &outRec) | |||
| { | { | |||
| //FixupOutPolygon() - removes duplicate points and simplifies consecutive | //FixupOutPolygon() - removes duplicate points and simplifies consecutive | |||
| skipping to change at line 2931 | skipping to change at line 2937 | |||
| void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt) | void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt) | |||
| { | { | |||
| AddOutPt(edge1, pt); | AddOutPt(edge1, pt); | |||
| AddOutPt(edge2, pt); | AddOutPt(edge2, pt); | |||
| SwapSides( *edge1 , *edge2 ); | SwapSides( *edge1 , *edge2 ); | |||
| SwapPolyIndexes( *edge1 , *edge2 ); | SwapPolyIndexes( *edge1 , *edge2 ); | |||
| } | } | |||
| //---------------------------------------------------------------------- | //---------------------------------------------------------------------- | |||
| void Clipper::CheckHoleLinkages1(OutRec *outRec1, OutRec *outRec2) | ||||
| { | ||||
| //when a polygon is split into 2 polygons, make sure any holes the origin | ||||
| al | ||||
| //polygon contained link to the correct polygon ... | ||||
| for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) | ||||
| { | ||||
| OutRec *orec = m_PolyOuts[i]; | ||||
| if (orec->isHole && orec->bottomPt && orec->FirstLeft == outRec1 && | ||||
| !PointInPolygon(orec->bottomPt->pt, outRec1->pts, m_UseFullRange)) | ||||
| orec->FirstLeft = outRec2; | ||||
| } | ||||
| } | ||||
| //---------------------------------------------------------------------- | ||||
| void Clipper::CheckHoleLinkages2(OutRec *outRec1, OutRec *outRec2) | ||||
| { | ||||
| //if a hole is owned by outRec2 then make it owned by outRec1 ... | ||||
| for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) | ||||
| if (m_PolyOuts[i]->isHole && m_PolyOuts[i]->bottomPt && | ||||
| m_PolyOuts[i]->FirstLeft == outRec2) | ||||
| m_PolyOuts[i]->FirstLeft = outRec1; | ||||
| } | ||||
| //---------------------------------------------------------------------- | ||||
| void Clipper::JoinCommonEdges(bool fixHoleLinkages) | void Clipper::JoinCommonEdges(bool fixHoleLinkages) | |||
| { | { | |||
| for (JoinList::size_type i = 0; i < m_Joins.size(); i++) | for (JoinList::size_type i = 0; i < m_Joins.size(); i++) | |||
| { | { | |||
| JoinRec* j = m_Joins[i]; | JoinRec* j = m_Joins[i]; | |||
| OutRec *outRec1 = m_PolyOuts[j->poly1Idx]; | OutRec *outRec1 = m_PolyOuts[j->poly1Idx]; | |||
| OutPt *pp1a = outRec1->pts; | OutPt *pp1a = outRec1->pts; | |||
| OutRec *outRec2 = m_PolyOuts[j->poly2Idx]; | OutRec *outRec2 = m_PolyOuts[j->poly2Idx]; | |||
| OutPt *pp2a = outRec2->pts; | OutPt *pp2a = outRec2->pts; | |||
| IntPoint pt1 = j->pt2a, pt2 = j->pt2b; | IntPoint pt1 = j->pt2a, pt2 = j->pt2b; | |||
| skipping to change at line 3040 | skipping to change at line 3022 | |||
| outRec1->bottomPt = outRec1->pts; | outRec1->bottomPt = outRec1->pts; | |||
| outRec1->bottomPt->idx = outRec1->idx; | outRec1->bottomPt->idx = outRec1->idx; | |||
| outRec2 = CreateOutRec(); | outRec2 = CreateOutRec(); | |||
| m_PolyOuts.push_back(outRec2); | m_PolyOuts.push_back(outRec2); | |||
| outRec2->idx = (int)m_PolyOuts.size()-1; | outRec2->idx = (int)m_PolyOuts.size()-1; | |||
| j->poly2Idx = outRec2->idx; | j->poly2Idx = outRec2->idx; | |||
| outRec2->pts = GetBottomPt(p2); | outRec2->pts = GetBottomPt(p2); | |||
| outRec2->bottomPt = outRec2->pts; | outRec2->bottomPt = outRec2->pts; | |||
| outRec2->bottomPt->idx = outRec2->idx; | outRec2->bottomPt->idx = outRec2->idx; | |||
| int K = 0; | ||||
| if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange)) | if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange)) | |||
| { | { | |||
| //outRec2 is contained by outRec1 ... | //outRec2 is contained by outRec1 ... | |||
| K = 1; | ||||
| outRec2->isHole = !outRec1->isHole; | outRec2->isHole = !outRec1->isHole; | |||
| outRec2->FirstLeft = outRec1; | outRec2->FirstLeft = outRec1; | |||
| if (outRec2->isHole == | ||||
| (m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange))) | ||||
| ReversePolyPtLinks(*outRec2->pts); | ||||
| } else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRa nge)) | } else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRa nge)) | |||
| { | { | |||
| //outRec1 is contained by outRec2 ... | //outRec1 is contained by outRec2 ... | |||
| K = 2; | ||||
| outRec2->isHole = outRec1->isHole; | outRec2->isHole = outRec1->isHole; | |||
| outRec1->isHole = !outRec2->isHole; | outRec1->isHole = !outRec2->isHole; | |||
| outRec2->FirstLeft = outRec1->FirstLeft; | outRec2->FirstLeft = outRec1->FirstLeft; | |||
| outRec1->FirstLeft = outRec2; | outRec1->FirstLeft = outRec2; | |||
| if (outRec1->isHole == | ||||
| (m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange))) | ||||
| ReversePolyPtLinks(*outRec1->pts); | ||||
| //make sure any contained holes now link to the correct polygon ... | ||||
| if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2); | ||||
| } else | } else | |||
| { | { | |||
| outRec2->isHole = outRec1->isHole; | outRec2->isHole = outRec1->isHole; | |||
| outRec2->FirstLeft = outRec1->FirstLeft; | outRec2->FirstLeft = outRec1->FirstLeft; | |||
| //make sure any contained holes now link to the correct polygon ... | ||||
| if (fixHoleLinkages) CheckHoleLinkages1(outRec1, outRec2); | ||||
| } | } | |||
| //now fixup any subsequent joins that match this polygon | //now fixup any subsequent joins that match this polygon | |||
| for (JoinList::size_type k = i+1; k < m_Joins.size(); k++) | for (JoinList::size_type k = i+1; k < m_Joins.size(); k++) | |||
| { | { | |||
| JoinRec* j2 = m_Joins[k]; | JoinRec* j2 = m_Joins[k]; | |||
| if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2)) | if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2)) | |||
| j2->poly1Idx = j->poly2Idx; | j2->poly1Idx = j->poly2Idx; | |||
| if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2)) | if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2)) | |||
| j2->poly2Idx = j->poly2Idx; | j2->poly2Idx = j->poly2Idx; | |||
| } | } | |||
| //now cleanup redundant edges too ... | FixupOutPolygon(*outRec1); //nb: do this BEFORE testing orientation | |||
| FixupOutPolygon(*outRec1); | FixupOutPolygon(*outRec2); // but AFTER calling PointIsVertex() | |||
| FixupOutPolygon(*outRec2); | ||||
| switch( K ) { | ||||
| case 1: | ||||
| { | ||||
| if (outRec2->pts && outRec2->isHole == | ||||
| (m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange))) | ||||
| ReversePolyPtLinks(*outRec2->pts); | ||||
| break; | ||||
| } | ||||
| case 2: | ||||
| { | ||||
| if (outRec1->pts) | ||||
| { | ||||
| if (outRec1->isHole == | ||||
| (m_ReverseOutput ^ Orientation(outRec1, m_UseFullRange))) | ||||
| ReversePolyPtLinks(*outRec1->pts); | ||||
| //make sure any contained holes now link to the correct polyg | ||||
| on ... | ||||
| if (fixHoleLinkages && outRec1->isHole) | ||||
| for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); + | ||||
| +k) | ||||
| { | ||||
| OutRec *orec = m_PolyOuts[k]; | ||||
| if (orec->isHole && orec->bottomPt && orec->FirstLeft == | ||||
| outRec1) | ||||
| orec->FirstLeft = outRec2; | ||||
| } | ||||
| } | ||||
| break; | ||||
| } | ||||
| default: | ||||
| { | ||||
| //make sure any contained holes now link to the correct polygon | ||||
| ... | ||||
| if (fixHoleLinkages) | ||||
| for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k | ||||
| ) | ||||
| { | ||||
| OutRec *orec = m_PolyOuts[k]; | ||||
| if (orec->isHole && orec->bottomPt && orec->FirstLeft == ou | ||||
| tRec1 && | ||||
| !PointInPolygon(orec->bottomPt->pt, outRec1->pts, m_UseFu | ||||
| llRange)) | ||||
| orec->FirstLeft = outRec2; | ||||
| } | ||||
| } | ||||
| } | ||||
| if (Orientation(outRec1, m_UseFullRange) != (Area(*outRec1, m_UseFull Range) > 0)) | if (outRec1->pts && Orientation(outRec1, m_UseFullRange) != (Area(*ou tRec1, m_UseFullRange) > 0)) | |||
| DisposeBottomPt(*outRec1); | DisposeBottomPt(*outRec1); | |||
| if (Orientation(outRec2, m_UseFullRange) != (Area(*outRec2, m_UseFull Range) > 0)) | if (outRec2->pts && Orientation(outRec2, m_UseFullRange) != (Area(*ou tRec2, m_UseFullRange) > 0)) | |||
| DisposeBottomPt(*outRec2); | DisposeBottomPt(*outRec2); | |||
| } else | } else | |||
| { | { | |||
| //joined 2 polygons together ... | //joined 2 polygons together ... | |||
| //make sure any holes contained by outRec2 now link to outRec1 ... | //make sure any holes contained by outRec2 now link to outRec1 ... | |||
| if (fixHoleLinkages) CheckHoleLinkages2(outRec1, outRec2); | if (fixHoleLinkages) | |||
| for (PolyOutList::size_type k = 0; k < m_PolyOuts.size(); ++k) | ||||
| if (m_PolyOuts[k]->isHole && m_PolyOuts[k]->bottomPt && | ||||
| m_PolyOuts[k]->FirstLeft == outRec2) | ||||
| m_PolyOuts[k]->FirstLeft = outRec1; | ||||
| //now cleanup redundant edges too ... | //and cleanup redundant edges too ... | |||
| FixupOutPolygon(*outRec1); | FixupOutPolygon(*outRec1); | |||
| if (outRec1->pts) | if (outRec1->pts) | |||
| { | { | |||
| outRec1->isHole = !Orientation(outRec1, m_UseFullRange); | outRec1->isHole = !Orientation(outRec1, m_UseFullRange); | |||
| if (outRec1->isHole && !outRec1->FirstLeft) | if (outRec1->isHole && !outRec1->FirstLeft) | |||
| outRec1->FirstLeft = outRec2->FirstLeft; | outRec1->FirstLeft = outRec2->FirstLeft; | |||
| } | } | |||
| //delete the obsolete pointer ... | //delete the obsolete pointer ... | |||
| End of changes. 31 change blocks. | ||||
| 99 lines changed or deleted | 119 lines changed or added | |||
This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||