| /******************************************************************************* |
| * * |
| * Author : Angus Johnson * |
| * Version : 4.8.8 * |
| * Date : 30 August 2012 * |
| * Website : http://www.angusj.com * |
| * Copyright : Angus Johnson 2010-2012 * |
| * * |
| * License: * |
| * Use, modification & distribution is subject to Boost Software License Ver 1. * |
| * http://www.boost.org/LICENSE_1_0.txt * |
| * * |
| * Attributions: * |
| * The code in this library is an extension of Bala Vatti's clipping algorithm: * |
| * "A generic solution to polygon clipping" * |
| * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. * |
| * http://portal.acm.org/citation.cfm?id=129906 * |
| * * |
| * Computer graphics and geometric modeling: implementation and algorithms * |
| * By Max K. Agoston * |
| * Springer; 1 edition (January 4, 2005) * |
| * http://books.google.com/books?q=vatti+clipping+agoston * |
| * * |
| * See also: * |
| * "Polygon Offsetting by Computing Winding Numbers" * |
| * Paper no. DETC2005-85513 pp. 565-575 * |
| * ASME 2005 International Design Engineering Technical Conferences * |
| * and Computers and Information in Engineering Conference (IDETC/CIE2005) * |
| * September 24-28, 2005 , Long Beach, California, USA * |
| * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf * |
| * * |
| *******************************************************************************/ |
| |
| /******************************************************************************* |
| * * |
| * This is a translation of the Delphi Clipper library and the naming style * |
| * used has retained a Delphi flavour. * |
| * * |
| *******************************************************************************/ |
| |
| #include "clipper.hpp" |
| #include <cmath> |
| #include <vector> |
| #include <algorithm> |
| #include <stdexcept> |
| #include <cassert> |
| #include <cstring> |
| #include <cstdlib> |
| #include <ostream> |
| |
| namespace ClipperLib { |
| |
| static long64 const loRange = 0x3FFFFFFF; |
| static long64 const hiRange = 0x3FFFFFFFFFFFFFFFLL; |
| static double const pi = 3.141592653589793238; |
| enum Direction { dRightToLeft, dLeftToRight }; |
| |
| #define HORIZONTAL (-1.0E+40) |
| #define TOLERANCE (1.0e-20) |
| #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE)) |
| #define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b)) |
| |
| inline long64 Abs(long64 val) |
| { |
| return val < 0 ? -val : val; |
| } |
| //------------------------------------------------------------------------------ |
| |
| //------------------------------------------------------------------------------ |
| // Int128 class (enables safe math on signed 64bit integers) |
| // eg Int128 val1((long64)9223372036854775807); //ie 2^63 -1 |
| // Int128 val2((long64)9223372036854775807); |
| // Int128 val3 = val1 * val2; |
| // val3.AsString => "85070591730234615847396907784232501249" (8.5e+37) |
| //------------------------------------------------------------------------------ |
| |
| class Int128 |
| { |
| public: |
| |
| Int128(long64 _lo = 0) |
| { |
| lo = _lo; |
| if (lo < 0) hi = -1; else hi = 0; |
| } |
| |
| Int128(const Int128 &val): hi(val.hi), lo(val.lo){} |
| |
| long64 operator = (const long64 &val) |
| { |
| lo = val; |
| if (lo < 0) hi = -1; else hi = 0; |
| return val; |
| } |
| |
| bool operator == (const Int128 &val) const |
| {return (hi == val.hi && lo == val.lo);} |
| |
| bool operator != (const Int128 &val) const |
| { return !(*this == val);} |
| |
| bool operator > (const Int128 &val) const |
| { |
| if (hi != val.hi) |
| return hi > val.hi; |
| else |
| return lo > val.lo; |
| } |
| |
| bool operator < (const Int128 &val) const |
| { |
| if (hi != val.hi) |
| return hi < val.hi; |
| else |
| return lo < val.lo; |
| } |
| |
| bool operator >= (const Int128 &val) const |
| { return !(*this < val);} |
| |
| bool operator <= (const Int128 &val) const |
| { return !(*this > val);} |
| |
| Int128& operator += (const Int128 &rhs) |
| { |
| hi += rhs.hi; |
| lo += rhs.lo; |
| if (ulong64(lo) < ulong64(rhs.lo)) hi++; |
| return *this; |
| } |
| |
| Int128 operator + (const Int128 &rhs) const |
| { |
| Int128 result(*this); |
| result+= rhs; |
| return result; |
| } |
| |
| Int128& operator -= (const Int128 &rhs) |
| { |
| Int128 tmp(rhs); |
| Negate(tmp); |
| *this += tmp; |
| return *this; |
| } |
| |
| //Int128 operator -() const |
| //{ |
| // Int128 result(*this); |
| // if (result.lo == 0) { |
| // if (result.hi != 0) result.hi = -1; |
| // } |
| // else { |
| // result.lo = -result.lo; |
| // result.hi = ~result.hi; |
| // } |
| // return result; |
| //} |
| |
| Int128 operator - (const Int128 &rhs) const |
| { |
| Int128 result(*this); |
| result -= rhs; |
| return result; |
| } |
| |
| Int128 operator * (const Int128 &rhs) const |
| { |
| if ( !(hi == 0 || hi == -1) || !(rhs.hi == 0 || rhs.hi == -1)) |
| throw "Int128 operator*: overflow error"; |
| bool negate = (hi < 0) != (rhs.hi < 0); |
| |
| Int128 tmp(*this); |
| if (tmp.hi < 0) Negate(tmp); |
| ulong64 int1Hi = ulong64(tmp.lo) >> 32; |
| ulong64 int1Lo = ulong64(tmp.lo & 0xFFFFFFFF); |
| |
| tmp = rhs; |
| if (tmp.hi < 0) Negate(tmp); |
| ulong64 int2Hi = ulong64(tmp.lo) >> 32; |
| ulong64 int2Lo = ulong64(tmp.lo & 0xFFFFFFFF); |
| |
| //nb: see comments in clipper.pas |
| ulong64 a = int1Hi * int2Hi; |
| ulong64 b = int1Lo * int2Lo; |
| ulong64 c = int1Hi * int2Lo + int1Lo * int2Hi; |
| |
| tmp.hi = long64(a + (c >> 32)); |
| tmp.lo = long64(c << 32); |
| tmp.lo += long64(b); |
| if (ulong64(tmp.lo) < b) tmp.hi++; |
| if (negate) Negate(tmp); |
| return tmp; |
| } |
| |
| Int128 operator/ (const Int128 &rhs) const |
| { |
| if (rhs.lo == 0 && rhs.hi == 0) |
| throw "Int128 operator/: divide by zero"; |
| bool negate = (rhs.hi < 0) != (hi < 0); |
| Int128 result(*this), denom(rhs); |
| if (result.hi < 0) Negate(result); |
| if (denom.hi < 0) Negate(denom); |
| if (denom > result) return Int128(0); //result is only a fraction of 1 |
| Negate(denom); |
| |
| Int128 p(0); |
| for (int i = 0; i < 128; ++i) |
| { |
| p.hi = p.hi << 1; |
| if (p.lo < 0) p.hi++; |
| p.lo = long64(p.lo) << 1; |
| if (result.hi < 0) p.lo++; |
| result.hi = result.hi << 1; |
| if (result.lo < 0) result.hi++; |
| result.lo = long64(result.lo) << 1; |
| Int128 p2(p); |
| p += denom; |
| if (p.hi < 0) p = p2; |
| else result.lo++; |
| } |
| if (negate) Negate(result); |
| return result; |
| } |
| |
| double AsDouble() const |
| { |
| const double shift64 = 18446744073709551616.0; //2^64 |
| const double bit64 = 9223372036854775808.0; |
| if (hi < 0) |
| { |
| Int128 tmp(*this); |
| Negate(tmp); |
| if (tmp.lo < 0) |
| return (double)tmp.lo - bit64 - tmp.hi * shift64; |
| else |
| return -(double)tmp.lo - tmp.hi * shift64; |
| } |
| else if (lo < 0) |
| return -(double)lo + bit64 + hi * shift64; |
| else |
| return (double)lo + (double)hi * shift64; |
| } |
| |
| //for bug testing ... |
| //std::string AsString() const |
| //{ |
| // std::string result; |
| // unsigned char r = 0; |
| // Int128 tmp(0), val(*this); |
| // if (hi < 0) Negate(val); |
| // result.resize(50); |
| // std::string::size_type i = result.size() -1; |
| // while (val.hi != 0 || val.lo != 0) |
| // { |
| // Div10(val, tmp, r); |
| // result[i--] = char('0' + r); |
| // val = tmp; |
| // } |
| // if (hi < 0) result[i--] = '-'; |
| // result.erase(0,i+1); |
| // if (result.size() == 0) result = "0"; |
| // return result; |
| //} |
| |
| private: |
| long64 hi; |
| long64 lo; |
| |
| static void Negate(Int128 &val) |
| { |
| if (val.lo == 0) { |
| if (val.hi != 0) val.hi = -val.hi;; |
| } |
| else { |
| val.lo = -val.lo; |
| val.hi = ~val.hi; |
| } |
| } |
| |
| //debugging only ... |
| //void Div10(const Int128 val, Int128& result, unsigned char & remainder) const |
| //{ |
| // remainder = 0; |
| // result = 0; |
| // for (int i = 63; i >= 0; --i) |
| // { |
| // if ((val.hi & ((long64)1 << i)) != 0) |
| // remainder = char((remainder * 2) + 1); else |
| // remainder *= char(2); |
| // if (remainder >= 10) |
| // { |
| // result.hi += ((long64)1 << i); |
| // remainder -= char(10); |
| // } |
| // } |
| // for (int i = 63; i >= 0; --i) |
| // { |
| // if ((val.lo & ((long64)1 << i)) != 0) |
| // remainder = char((remainder * 2) + 1); else |
| // remainder *= char(2); |
| // if (remainder >= 10) |
| // { |
| // result.lo += ((long64)1 << i); |
| // remainder -= char(10); |
| // } |
| // } |
| //} |
| }; |
| |
| //------------------------------------------------------------------------------ |
| //------------------------------------------------------------------------------ |
| |
| bool FullRangeNeeded(const Polygon &pts) |
| { |
| bool result = false; |
| for (Polygon::size_type i = 0; i < pts.size(); ++i) |
| { |
| if (Abs(pts[i].X) > hiRange || Abs(pts[i].Y) > hiRange) |
| throw "Coordinate exceeds range bounds."; |
| else if (Abs(pts[i].X) > loRange || Abs(pts[i].Y) > loRange) |
| result = true; |
| } |
| return result; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Orientation(const Polygon &poly) |
| { |
| int highI = (int)poly.size() -1; |
| if (highI < 2) return false; |
| |
| int j = 0, jplus, jminus; |
| for (int i = 0; i <= highI; ++i) |
| { |
| if (poly[i].Y < poly[j].Y) continue; |
| if ((poly[i].Y > poly[j].Y || poly[i].X < poly[j].X)) j = i; |
| }; |
| if (j == highI) jplus = 0; |
| else jplus = j +1; |
| if (j == 0) jminus = highI; |
| else jminus = j -1; |
| |
| IntPoint vec1, vec2; |
| //get cross product of vectors of the edges adjacent to highest point ... |
| vec1.X = poly[j].X - poly[jminus].X; |
| vec1.Y = poly[j].Y - poly[jminus].Y; |
| vec2.X = poly[jplus].X - poly[j].X; |
| vec2.Y = poly[jplus].Y - poly[j].Y; |
| |
| if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange || |
| Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange) |
| { |
| if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange || |
| Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange) |
| throw "Coordinate exceeds range bounds."; |
| Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - |
| Int128(vec2.X) * Int128(vec1.Y); |
| return cross >= 0; |
| } |
| else |
| return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) |
| { |
| return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Orientation(OutRec *outRec, bool UseFullInt64Range) |
| { |
| //first make sure bottomPt is correctly assigned ... |
| OutPt *opBottom = outRec->pts, *op = outRec->pts->next; |
| while (op != outRec->pts) |
| { |
| if (op->pt.Y >= opBottom->pt.Y) |
| { |
| if (op->pt.Y > opBottom->pt.Y || op->pt.X < opBottom->pt.X) |
| opBottom = op; |
| } |
| op = op->next; |
| } |
| outRec->bottomPt = opBottom; |
| opBottom->idx = outRec->idx; |
| |
| op = opBottom; |
| //find vertices either side of bottomPt (skipping duplicate points) .... |
| OutPt *opPrev = op->prev; |
| OutPt *opNext = op->next; |
| while (op != opPrev && PointsEqual(op->pt, opPrev->pt)) |
| opPrev = opPrev->prev; |
| while (op != opNext && PointsEqual(op->pt, opNext->pt)) |
| opNext = opNext->next; |
| |
| IntPoint ip1, ip2; |
| ip1.X = op->pt.X - opPrev->pt.X; |
| ip1.Y = op->pt.Y - opPrev->pt.Y; |
| ip2.X = opNext->pt.X - op->pt.X; |
| ip2.Y = opNext->pt.Y - op->pt.Y; |
| |
| if (UseFullInt64Range) |
| return Int128(ip1.X) * Int128(ip2.Y) - Int128(ip2.X) * Int128(ip1.Y) >= 0; |
| else |
| return (ip1.X * ip2.Y - ip2.X * ip1.Y) >= 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| double Area(const Polygon &poly) |
| { |
| int highI = (int)poly.size() -1; |
| if (highI < 2) return 0; |
| |
| if (FullRangeNeeded(poly)) { |
| Int128 a; |
| a = (Int128(poly[highI].X) * Int128(poly[0].Y)) - |
| Int128(poly[0].X) * Int128(poly[highI].Y); |
| for (int i = 0; i < highI; ++i) |
| a += Int128(poly[i].X) * Int128(poly[i+1].Y) - |
| Int128(poly[i+1].X) * Int128(poly[i].Y); |
| return a.AsDouble() / 2; |
| } |
| else |
| { |
| double a; |
| a = (double)poly[highI].X * poly[0].Y - (double)poly[0].X * poly[highI].Y; |
| for (int i = 0; i < highI; ++i) |
| a += (double)poly[i].X * poly[i+1].Y - (double)poly[i+1].X * poly[i].Y; |
| return a/2; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| double Area(const OutRec &outRec, bool UseFullInt64Range) |
| { |
| OutPt *op = outRec.pts; |
| if (UseFullInt64Range) { |
| Int128 a(0); |
| do { |
| a += (Int128(op->prev->pt.X) * Int128(op->pt.Y)) - |
| Int128(op->pt.X) * Int128(op->prev->pt.Y); |
| op = op->next; |
| } while (op != outRec.pts); |
| return a.AsDouble() / 2; |
| } |
| else |
| { |
| double a = 0; |
| do { |
| a += (op->prev->pt.X * op->pt.Y) - (op->pt.X * op->prev->pt.Y); |
| op = op->next; |
| } while (op != outRec.pts); |
| return a/2; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool PointIsVertex(const IntPoint &pt, OutPt *pp) |
| { |
| OutPt *pp2 = pp; |
| do |
| { |
| if (PointsEqual(pp2->pt, pt)) return true; |
| pp2 = pp2->next; |
| } |
| while (pp2 != pp); |
| return false; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool PointInPolygon(const IntPoint &pt, OutPt *pp, bool UseFullInt64Range) |
| { |
| OutPt *pp2 = pp; |
| bool result = false; |
| if (UseFullInt64Range) { |
| do |
| { |
| if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) || |
| ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) && |
| Int128(pt.X - pp2->pt.X) < (Int128(pp2->prev->pt.X - pp2->pt.X) * |
| Int128(pt.Y - pp2->pt.Y)) / Int128(pp2->prev->pt.Y - pp2->pt.Y)) |
| result = !result; |
| pp2 = pp2->next; |
| } |
| while (pp2 != pp); |
| } |
| else |
| { |
| do |
| { |
| if ((((pp2->pt.Y <= pt.Y) && (pt.Y < pp2->prev->pt.Y)) || |
| ((pp2->prev->pt.Y <= pt.Y) && (pt.Y < pp2->pt.Y))) && |
| (pt.X < (pp2->prev->pt.X - pp2->pt.X) * (pt.Y - pp2->pt.Y) / |
| (pp2->prev->pt.Y - pp2->pt.Y) + pp2->pt.X )) result = !result; |
| pp2 = pp2->next; |
| } |
| while (pp2 != pp); |
| } |
| return result; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool SlopesEqual(TEdge &e1, TEdge &e2, bool UseFullInt64Range) |
| { |
| if (UseFullInt64Range) |
| return Int128(e1.ytop - e1.ybot) * Int128(e2.xtop - e2.xbot) == |
| Int128(e1.xtop - e1.xbot) * Int128(e2.ytop - e2.ybot); |
| else return (e1.ytop - e1.ybot)*(e2.xtop - e2.xbot) == |
| (e1.xtop - e1.xbot)*(e2.ytop - e2.ybot); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, |
| const IntPoint pt3, bool UseFullInt64Range) |
| { |
| if (UseFullInt64Range) |
| return Int128(pt1.Y-pt2.Y) * Int128(pt2.X-pt3.X) == |
| 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); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool SlopesEqual(const IntPoint pt1, const IntPoint pt2, |
| const IntPoint pt3, const IntPoint pt4, bool UseFullInt64Range) |
| { |
| if (UseFullInt64Range) |
| return Int128(pt1.Y-pt2.Y) * Int128(pt3.X-pt4.X) == |
| Int128(pt1.X-pt2.X) * Int128(pt3.Y-pt4.Y); |
| else return (pt1.Y-pt2.Y)*(pt3.X-pt4.X) == (pt1.X-pt2.X)*(pt3.Y-pt4.Y); |
| } |
| //------------------------------------------------------------------------------ |
| |
| double GetDx(const IntPoint pt1, const IntPoint pt2) |
| { |
| return (pt1.Y == pt2.Y) ? |
| HORIZONTAL : (double)(pt2.X - pt1.X) / (double)(pt2.Y - pt1.Y); |
| } |
| //--------------------------------------------------------------------------- |
| |
| void SetDx(TEdge &e) |
| { |
| if (e.ybot == e.ytop) e.dx = HORIZONTAL; |
| else e.dx = (double)(e.xtop - e.xbot) / (double)(e.ytop - e.ybot); |
| } |
| //--------------------------------------------------------------------------- |
| |
| void SwapSides(TEdge &edge1, TEdge &edge2) |
| { |
| EdgeSide side = edge1.side; |
| edge1.side = edge2.side; |
| edge2.side = side; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SwapPolyIndexes(TEdge &edge1, TEdge &edge2) |
| { |
| int outIdx = edge1.outIdx; |
| edge1.outIdx = edge2.outIdx; |
| edge2.outIdx = outIdx; |
| } |
| //------------------------------------------------------------------------------ |
| |
| inline long64 Round(double val) |
| { |
| return (val < 0) ? |
| static_cast<long64>(val - 0.5) : static_cast<long64>(val + 0.5); |
| } |
| //------------------------------------------------------------------------------ |
| |
| long64 TopX(TEdge &edge, const long64 currentY) |
| { |
| return ( currentY == edge.ytop ) ? |
| edge.xtop : edge.xbot + Round(edge.dx *(currentY - edge.ybot)); |
| } |
| //------------------------------------------------------------------------------ |
| |
| long64 TopX(const IntPoint pt1, const IntPoint pt2, const long64 currentY) |
| { |
| //preconditions: pt1.Y <> pt2.Y and pt1.Y > pt2.Y |
| if (currentY >= pt1.Y) return pt1.X; |
| else if (currentY == pt2.Y) return pt2.X; |
| else if (pt1.X == pt2.X) return pt1.X; |
| else |
| { |
| double q = (double)(pt1.X-pt2.X)/(double)(pt1.Y-pt2.Y); |
| return Round(pt1.X + (currentY - pt1.Y) *q); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool IntersectPoint(TEdge &edge1, TEdge &edge2, |
| IntPoint &ip, bool UseFullInt64Range) |
| { |
| double b1, b2; |
| if (SlopesEqual(edge1, edge2, UseFullInt64Range)) return false; |
| else if (NEAR_ZERO(edge1.dx)) |
| { |
| ip.X = edge1.xbot; |
| if (NEAR_EQUAL(edge2.dx, HORIZONTAL)) |
| { |
| ip.Y = edge2.ybot; |
| } else |
| { |
| b2 = edge2.ybot - (edge2.xbot/edge2.dx); |
| ip.Y = Round(ip.X/edge2.dx + b2); |
| } |
| } |
| else if (NEAR_ZERO(edge2.dx)) |
| { |
| ip.X = edge2.xbot; |
| if (NEAR_EQUAL(edge1.dx, HORIZONTAL)) |
| { |
| ip.Y = edge1.ybot; |
| } else |
| { |
| b1 = edge1.ybot - (edge1.xbot/edge1.dx); |
| ip.Y = Round(ip.X/edge1.dx + b1); |
| } |
| } else |
| { |
| b1 = edge1.xbot - edge1.ybot * edge1.dx; |
| b2 = edge2.xbot - edge2.ybot * edge2.dx; |
| b2 = (b2-b1)/(edge1.dx - edge2.dx); |
| ip.Y = Round(b2); |
| ip.X = Round(edge1.dx * b2 + b1); |
| } |
| |
| return |
| //can be *so close* to the top of one edge that the rounded Y equals one ytop ... |
| (ip.Y == edge1.ytop && ip.Y >= edge2.ytop && edge1.tmpX > edge2.tmpX) || |
| (ip.Y == edge2.ytop && ip.Y >= edge1.ytop && edge1.tmpX > edge2.tmpX) || |
| (ip.Y > edge1.ytop && ip.Y > edge2.ytop); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ReversePolyPtLinks(OutPt &pp) |
| { |
| OutPt *pp1, *pp2; |
| pp1 = &pp; |
| do { |
| pp2 = pp1->next; |
| pp1->next = pp1->prev; |
| pp1->prev = pp2; |
| pp1 = pp2; |
| } while( pp1 != &pp ); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void DisposeOutPts(OutPt*& pp) |
| { |
| if (pp == 0) return; |
| pp->prev->next = 0; |
| while( pp ) |
| { |
| OutPt *tmpPp = pp; |
| pp = pp->next; |
| delete tmpPp ; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void InitEdge(TEdge *e, TEdge *eNext, |
| TEdge *ePrev, const IntPoint &pt, PolyType polyType) |
| { |
| std::memset( e, 0, sizeof( TEdge )); |
| |
| e->next = eNext; |
| e->prev = ePrev; |
| e->xcurr = pt.X; |
| e->ycurr = pt.Y; |
| if (e->ycurr >= e->next->ycurr) |
| { |
| e->xbot = e->xcurr; |
| e->ybot = e->ycurr; |
| e->xtop = e->next->xcurr; |
| e->ytop = e->next->ycurr; |
| e->windDelta = 1; |
| } else |
| { |
| e->xtop = e->xcurr; |
| e->ytop = e->ycurr; |
| e->xbot = e->next->xcurr; |
| e->ybot = e->next->ycurr; |
| e->windDelta = -1; |
| } |
| SetDx(*e); |
| e->polyType = polyType; |
| e->outIdx = -1; |
| } |
| //------------------------------------------------------------------------------ |
| |
| inline void SwapX(TEdge &e) |
| { |
| //swap horizontal edges' top and bottom x's so they follow the natural |
| //progression of the bounds - ie so their xbots will align with the |
| //adjoining lower edge. [Helpful in the ProcessHorizontal() method.] |
| e.xcurr = e.xtop; |
| e.xtop = e.xbot; |
| e.xbot = e.xcurr; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SwapPoints(IntPoint &pt1, IntPoint &pt2) |
| { |
| IntPoint tmp = pt1; |
| pt1 = pt2; |
| pt2 = tmp; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool GetOverlapSegment(IntPoint pt1a, IntPoint pt1b, IntPoint pt2a, |
| IntPoint pt2b, IntPoint &pt1, IntPoint &pt2) |
| { |
| //precondition: segments are colinear. |
| if ( pt1a.Y == pt1b.Y || Abs((pt1a.X - pt1b.X)/(pt1a.Y - pt1b.Y)) > 1 ) |
| { |
| if (pt1a.X > pt1b.X) SwapPoints(pt1a, pt1b); |
| if (pt2a.X > pt2b.X) SwapPoints(pt2a, pt2b); |
| if (pt1a.X > pt2a.X) pt1 = pt1a; else pt1 = pt2a; |
| if (pt1b.X < pt2b.X) pt2 = pt1b; else pt2 = pt2b; |
| return pt1.X < pt2.X; |
| } else |
| { |
| if (pt1a.Y < pt1b.Y) SwapPoints(pt1a, pt1b); |
| if (pt2a.Y < pt2b.Y) SwapPoints(pt2a, pt2b); |
| if (pt1a.Y < pt2a.Y) pt1 = pt1a; else pt1 = pt2a; |
| if (pt1b.Y > pt2b.Y) pt2 = pt1b; else pt2 = pt2b; |
| return pt1.Y > pt2.Y; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool FirstIsBottomPt(const OutPt* btmPt1, const OutPt* btmPt2) |
| { |
| OutPt *p = btmPt1->prev; |
| while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->prev; |
| double dx1p = std::fabs(GetDx(btmPt1->pt, p->pt)); |
| p = btmPt1->next; |
| while (PointsEqual(p->pt, btmPt1->pt) && (p != btmPt1)) p = p->next; |
| double dx1n = std::fabs(GetDx(btmPt1->pt, p->pt)); |
| |
| p = btmPt2->prev; |
| while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->prev; |
| double dx2p = std::fabs(GetDx(btmPt2->pt, p->pt)); |
| p = btmPt2->next; |
| while (PointsEqual(p->pt, btmPt2->pt) && (p != btmPt2)) p = p->next; |
| double dx2n = std::fabs(GetDx(btmPt2->pt, p->pt)); |
| return (dx1p >= dx2p && dx1p >= dx2n) || (dx1n >= dx2p && dx1n >= dx2n); |
| } |
| //------------------------------------------------------------------------------ |
| |
| OutPt* GetBottomPt(OutPt *pp) |
| { |
| OutPt* dups = 0; |
| OutPt* p = pp->next; |
| while (p != pp) |
| { |
| if (p->pt.Y > pp->pt.Y) |
| { |
| pp = p; |
| dups = 0; |
| } |
| else if (p->pt.Y == pp->pt.Y && p->pt.X <= pp->pt.X) |
| { |
| if (p->pt.X < pp->pt.X) |
| { |
| dups = 0; |
| pp = p; |
| } else |
| { |
| if (p->next != pp && p->prev != pp) dups = p; |
| } |
| } |
| p = p->next; |
| } |
| if (dups) |
| { |
| //there appears to be at least 2 vertices at bottomPt so ... |
| while (dups != p) |
| { |
| if (!FirstIsBottomPt(p, dups)) pp = dups; |
| dups = dups->next; |
| while (!PointsEqual(dups->pt, pp->pt)) dups = dups->next; |
| } |
| } |
| return pp; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool FindSegment(OutPt* &pp, IntPoint &pt1, IntPoint &pt2) |
| { |
| //outPt1 & outPt2 => the overlap segment (if the function returns true) |
| if (!pp) return false; |
| OutPt* pp2 = pp; |
| IntPoint pt1a = pt1, pt2a = pt2; |
| do |
| { |
| if (SlopesEqual(pt1a, pt2a, pp->pt, pp->prev->pt, true) && |
| SlopesEqual(pt1a, pt2a, pp->pt, true) && |
| GetOverlapSegment(pt1a, pt2a, pp->pt, pp->prev->pt, pt1, pt2)) |
| return true; |
| pp = pp->next; |
| } |
| while (pp != pp2); |
| return false; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Pt3IsBetweenPt1AndPt2(const IntPoint pt1, |
| const IntPoint pt2, const IntPoint pt3) |
| { |
| if (PointsEqual(pt1, pt3) || PointsEqual(pt2, pt3)) return true; |
| else if (pt1.X != pt2.X) return (pt1.X < pt3.X) == (pt3.X < pt2.X); |
| else return (pt1.Y < pt3.Y) == (pt3.Y < pt2.Y); |
| } |
| //------------------------------------------------------------------------------ |
| |
| OutPt* InsertPolyPtBetween(OutPt* p1, OutPt* p2, const IntPoint pt) |
| { |
| if (p1 == p2) throw "JoinError"; |
| OutPt* result = new OutPt; |
| result->pt = pt; |
| if (p2 == p1->next) |
| { |
| p1->next = result; |
| p2->prev = result; |
| result->next = p2; |
| result->prev = p1; |
| } else |
| { |
| p2->next = result; |
| p1->prev = result; |
| result->next = p1; |
| result->prev = p2; |
| } |
| return result; |
| } |
| |
| //------------------------------------------------------------------------------ |
| // ClipperBase class methods ... |
| //------------------------------------------------------------------------------ |
| |
| ClipperBase::ClipperBase() //constructor |
| { |
| m_MinimaList = 0; |
| m_CurrentLM = 0; |
| m_UseFullRange = true; |
| } |
| //------------------------------------------------------------------------------ |
| |
| ClipperBase::~ClipperBase() //destructor |
| { |
| Clear(); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool ClipperBase::AddPolygon( const Polygon &pg, PolyType polyType) |
| { |
| int len = (int)pg.size(); |
| if (len < 3) return false; |
| Polygon p(len); |
| p[0] = pg[0]; |
| int j = 0; |
| |
| long64 maxVal; |
| if (m_UseFullRange) maxVal = hiRange; else maxVal = loRange; |
| |
| for (int i = 0; i < len; ++i) |
| { |
| if (Abs(pg[i].X) > maxVal || Abs(pg[i].Y) > maxVal) |
| { |
| if (Abs(pg[i].X) > hiRange || Abs(pg[i].Y) > hiRange) |
| throw "Coordinate exceeds range bounds"; |
| maxVal = hiRange; |
| m_UseFullRange = true; |
| } |
| |
| if (i == 0 || PointsEqual(p[j], pg[i])) continue; |
| else if (j > 0 && SlopesEqual(p[j-1], p[j], pg[i], m_UseFullRange)) |
| { |
| if (PointsEqual(p[j-1], pg[i])) j--; |
| } else j++; |
| p[j] = pg[i]; |
| } |
| if (j < 2) return false; |
| |
| len = j+1; |
| while (len > 2) |
| { |
| //nb: test for point equality before testing slopes ... |
| if (PointsEqual(p[j], p[0])) j--; |
| else if (PointsEqual(p[0], p[1]) || |
| SlopesEqual(p[j], p[0], p[1], m_UseFullRange)) |
| p[0] = p[j--]; |
| else if (SlopesEqual(p[j-1], p[j], p[0], m_UseFullRange)) j--; |
| else if (SlopesEqual(p[0], p[1], p[2], m_UseFullRange)) |
| { |
| for (int i = 2; i <= j; ++i) p[i-1] = p[i]; |
| j--; |
| } |
| else break; |
| len--; |
| } |
| if (len < 3) return false; |
| |
| //create a new edge array ... |
| TEdge *edges = new TEdge [len]; |
| m_edges.push_back(edges); |
| |
| //convert vertices to a double-linked-list of edges and initialize ... |
| edges[0].xcurr = p[0].X; |
| edges[0].ycurr = p[0].Y; |
| InitEdge(&edges[len-1], &edges[0], &edges[len-2], p[len-1], polyType); |
| for (int i = len-2; i > 0; --i) |
| InitEdge(&edges[i], &edges[i+1], &edges[i-1], p[i], polyType); |
| InitEdge(&edges[0], &edges[1], &edges[len-1], p[0], polyType); |
| |
| //reset xcurr & ycurr and find 'eHighest' (given the Y axis coordinates |
| //increase downward so the 'highest' edge will have the smallest ytop) ... |
| TEdge *e = &edges[0]; |
| TEdge *eHighest = e; |
| do |
| { |
| e->xcurr = e->xbot; |
| e->ycurr = e->ybot; |
| if (e->ytop < eHighest->ytop) eHighest = e; |
| e = e->next; |
| } |
| while ( e != &edges[0]); |
| |
| //make sure eHighest is positioned so the following loop works safely ... |
| if (eHighest->windDelta > 0) eHighest = eHighest->next; |
| if (NEAR_EQUAL(eHighest->dx, HORIZONTAL)) eHighest = eHighest->next; |
| |
| //finally insert each local minima ... |
| e = eHighest; |
| do { |
| e = AddBoundsToLML(e); |
| } |
| while( e != eHighest ); |
| return true; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ClipperBase::InsertLocalMinima(LocalMinima *newLm) |
| { |
| if( ! m_MinimaList ) |
| { |
| m_MinimaList = newLm; |
| } |
| else if( newLm->Y >= m_MinimaList->Y ) |
| { |
| newLm->next = m_MinimaList; |
| m_MinimaList = newLm; |
| } else |
| { |
| LocalMinima* tmpLm = m_MinimaList; |
| while( tmpLm->next && ( newLm->Y < tmpLm->next->Y ) ) |
| tmpLm = tmpLm->next; |
| newLm->next = tmpLm->next; |
| tmpLm->next = newLm; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| TEdge* ClipperBase::AddBoundsToLML(TEdge *e) |
| { |
| //Starting at the top of one bound we progress to the bottom where there's |
| //a local minima. We then go to the top of the next bound. These two bounds |
| //form the left and right (or right and left) bounds of the local minima. |
| e->nextInLML = 0; |
| e = e->next; |
| for (;;) |
| { |
| if (NEAR_EQUAL(e->dx, HORIZONTAL)) |
| { |
| //nb: proceed through horizontals when approaching from their right, |
| // but break on horizontal minima if approaching from their left. |
| // This ensures 'local minima' are always on the left of horizontals. |
| if (e->next->ytop < e->ytop && e->next->xbot > e->prev->xbot) break; |
| if (e->xtop != e->prev->xbot) SwapX(*e); |
| e->nextInLML = e->prev; |
| } |
| else if (e->ycurr == e->prev->ycurr) break; |
| else e->nextInLML = e->prev; |
| e = e->next; |
| } |
| |
| //e and e.prev are now at a local minima ... |
| LocalMinima* newLm = new LocalMinima; |
| newLm->next = 0; |
| newLm->Y = e->prev->ybot; |
| |
| if ( NEAR_EQUAL(e->dx, HORIZONTAL) ) //horizontal edges never start a left bound |
| { |
| if (e->xbot != e->prev->xbot) SwapX(*e); |
| newLm->leftBound = e->prev; |
| newLm->rightBound = e; |
| } else if (e->dx < e->prev->dx) |
| { |
| newLm->leftBound = e->prev; |
| newLm->rightBound = e; |
| } else |
| { |
| newLm->leftBound = e; |
| newLm->rightBound = e->prev; |
| } |
| newLm->leftBound->side = esLeft; |
| newLm->rightBound->side = esRight; |
| InsertLocalMinima( newLm ); |
| |
| for (;;) |
| { |
| if ( e->next->ytop == e->ytop && !NEAR_EQUAL(e->next->dx, HORIZONTAL) ) break; |
| e->nextInLML = e->next; |
| e = e->next; |
| if ( NEAR_EQUAL(e->dx, HORIZONTAL) && e->xbot != e->prev->xtop) SwapX(*e); |
| } |
| return e->next; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool ClipperBase::AddPolygons(const Polygons &ppg, PolyType polyType) |
| { |
| bool result = false; |
| for (Polygons::size_type i = 0; i < ppg.size(); ++i) |
| if (AddPolygon(ppg[i], polyType)) result = true; |
| return result; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ClipperBase::Clear() |
| { |
| DisposeLocalMinimaList(); |
| for (EdgeList::size_type i = 0; i < m_edges.size(); ++i) delete [] m_edges[i]; |
| m_edges.clear(); |
| m_UseFullRange = false; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ClipperBase::Reset() |
| { |
| m_CurrentLM = m_MinimaList; |
| if( !m_CurrentLM ) return; //ie nothing to process |
| |
| //reset all edges ... |
| LocalMinima* lm = m_MinimaList; |
| while( lm ) |
| { |
| TEdge* e = lm->leftBound; |
| while( e ) |
| { |
| e->xcurr = e->xbot; |
| e->ycurr = e->ybot; |
| e->side = esLeft; |
| e->outIdx = -1; |
| e = e->nextInLML; |
| } |
| e = lm->rightBound; |
| while( e ) |
| { |
| e->xcurr = e->xbot; |
| e->ycurr = e->ybot; |
| e->side = esRight; |
| e->outIdx = -1; |
| e = e->nextInLML; |
| } |
| lm = lm->next; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ClipperBase::DisposeLocalMinimaList() |
| { |
| while( m_MinimaList ) |
| { |
| LocalMinima* tmpLm = m_MinimaList->next; |
| delete m_MinimaList; |
| m_MinimaList = tmpLm; |
| } |
| m_CurrentLM = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ClipperBase::PopLocalMinima() |
| { |
| if( ! m_CurrentLM ) return; |
| m_CurrentLM = m_CurrentLM->next; |
| } |
| //------------------------------------------------------------------------------ |
| |
| IntRect ClipperBase::GetBounds() |
| { |
| IntRect result; |
| LocalMinima* lm = m_MinimaList; |
| if (!lm) |
| { |
| result.left = result.top = result.right = result.bottom = 0; |
| return result; |
| } |
| result.left = lm->leftBound->xbot; |
| result.top = lm->leftBound->ybot; |
| result.right = lm->leftBound->xbot; |
| result.bottom = lm->leftBound->ybot; |
| while (lm) |
| { |
| if (lm->leftBound->ybot > result.bottom) |
| result.bottom = lm->leftBound->ybot; |
| TEdge* e = lm->leftBound; |
| for (;;) { |
| TEdge* bottomE = e; |
| while (e->nextInLML) |
| { |
| if (e->xbot < result.left) result.left = e->xbot; |
| if (e->xbot > result.right) result.right = e->xbot; |
| e = e->nextInLML; |
| } |
| if (e->xbot < result.left) result.left = e->xbot; |
| if (e->xbot > result.right) result.right = e->xbot; |
| if (e->xtop < result.left) result.left = e->xtop; |
| if (e->xtop > result.right) result.right = e->xtop; |
| if (e->ytop < result.top) result.top = e->ytop; |
| |
| if (bottomE == lm->leftBound) e = lm->rightBound; |
| else break; |
| } |
| lm = lm->next; |
| } |
| return result; |
| } |
| |
| |
| //------------------------------------------------------------------------------ |
| // TClipper methods ... |
| //------------------------------------------------------------------------------ |
| |
| Clipper::Clipper() : ClipperBase() //constructor |
| { |
| m_Scanbeam = 0; |
| m_ActiveEdges = 0; |
| m_SortedEdges = 0; |
| m_IntersectNodes = 0; |
| m_ExecuteLocked = false; |
| m_UseFullRange = false; |
| m_ReverseOutput = false; |
| } |
| //------------------------------------------------------------------------------ |
| |
| Clipper::~Clipper() //destructor |
| { |
| Clear(); |
| DisposeScanbeamList(); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::Clear() |
| { |
| if (m_edges.size() == 0) return; //avoids problems with ClipperBase destructor |
| DisposeAllPolyPts(); |
| ClipperBase::Clear(); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DisposeScanbeamList() |
| { |
| while ( m_Scanbeam ) { |
| Scanbeam* sb2 = m_Scanbeam->next; |
| delete m_Scanbeam; |
| m_Scanbeam = sb2; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::Reset() |
| { |
| ClipperBase::Reset(); |
| m_Scanbeam = 0; |
| m_ActiveEdges = 0; |
| m_SortedEdges = 0; |
| DisposeAllPolyPts(); |
| LocalMinima* lm = m_MinimaList; |
| while (lm) |
| { |
| InsertScanbeam(lm->Y); |
| InsertScanbeam(lm->leftBound->ytop); |
| lm = lm->next; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::Execute(ClipType clipType, Polygons &solution, |
| PolyFillType subjFillType, PolyFillType clipFillType) |
| { |
| if( m_ExecuteLocked ) return false; |
| m_ExecuteLocked = true; |
| solution.resize(0); |
| m_SubjFillType = subjFillType; |
| m_ClipFillType = clipFillType; |
| m_ClipType = clipType; |
| bool succeeded = ExecuteInternal(false); |
| if (succeeded) BuildResult(solution); |
| m_ExecuteLocked = false; |
| return succeeded; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::Execute(ClipType clipType, ExPolygons &solution, |
| PolyFillType subjFillType, PolyFillType clipFillType) |
| { |
| if( m_ExecuteLocked ) return false; |
| m_ExecuteLocked = true; |
| solution.resize(0); |
| m_SubjFillType = subjFillType; |
| m_ClipFillType = clipFillType; |
| m_ClipType = clipType; |
| bool succeeded = ExecuteInternal(true); |
| if (succeeded) BuildResultEx(solution); |
| m_ExecuteLocked = false; |
| return succeeded; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool PolySort(OutRec *or1, OutRec *or2) |
| { |
| if (or1 == or2) return false; |
| if (!or1->pts || !or2->pts) |
| { |
| if (or1->pts != or2->pts) |
| { |
| return or1->pts ? true : false; |
| } |
| else return false; |
| } |
| int i1, i2; |
| if (or1->isHole) |
| i1 = or1->FirstLeft->idx; else |
| i1 = or1->idx; |
| if (or2->isHole) |
| i2 = or2->FirstLeft->idx; else |
| i2 = or2->idx; |
| int result = i1 - i2; |
| if (result == 0 && (or1->isHole != or2->isHole)) |
| { |
| return or1->isHole ? false : true; |
| } |
| else return result < 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| OutRec* FindAppendLinkEnd(OutRec *outRec) |
| { |
| while (outRec->AppendLink) outRec = outRec->AppendLink; |
| return outRec; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::FixHoleLinkage(OutRec *outRec) |
| { |
| OutRec *tmp; |
| if (outRec->bottomPt) |
| tmp = m_PolyOuts[outRec->bottomPt->idx]->FirstLeft; |
| else |
| tmp = outRec->FirstLeft; |
| if (outRec == tmp) throw clipperException("HoleLinkage error"); |
| |
| if (tmp) |
| { |
| if (tmp->AppendLink) tmp = FindAppendLinkEnd(tmp); |
| if (tmp == outRec) tmp = 0; |
| else if (tmp->isHole) |
| { |
| FixHoleLinkage(tmp); |
| tmp = tmp->FirstLeft; |
| } |
| } |
| outRec->FirstLeft = tmp; |
| if (!tmp) outRec->isHole = false; |
| outRec->AppendLink = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::ExecuteInternal(bool fixHoleLinkages) |
| { |
| bool succeeded; |
| try { |
| Reset(); |
| if (!m_CurrentLM ) return true; |
| long64 botY = PopScanbeam(); |
| do { |
| InsertLocalMinimaIntoAEL(botY); |
| ClearHorzJoins(); |
| ProcessHorizontals(); |
| long64 topY = PopScanbeam(); |
| succeeded = ProcessIntersections(botY, topY); |
| if (!succeeded) break; |
| ProcessEdgesAtTopOfScanbeam(topY); |
| botY = topY; |
| } while( m_Scanbeam ); |
| } |
| catch(...) { |
| succeeded = false; |
| } |
| |
| if (succeeded) |
| { |
| //tidy up output polygons and fix orientations where necessary ... |
| for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) |
| { |
| OutRec *outRec = m_PolyOuts[i]; |
| if (!outRec->pts) continue; |
| FixupOutPolygon(*outRec); |
| if (!outRec->pts) continue; |
| if (outRec->isHole && fixHoleLinkages) FixHoleLinkage(outRec); |
| |
| if (outRec->bottomPt == outRec->bottomFlag && |
| (Orientation(outRec, m_UseFullRange) != (Area(*outRec, m_UseFullRange) > 0))) |
| DisposeBottomPt(*outRec); |
| |
| if (outRec->isHole == |
| (m_ReverseOutput ^ Orientation(outRec, m_UseFullRange))) |
| ReversePolyPtLinks(*outRec->pts); |
| } |
| |
| JoinCommonEdges(fixHoleLinkages); |
| if (fixHoleLinkages) |
| std::sort(m_PolyOuts.begin(), m_PolyOuts.end(), PolySort); |
| } |
| |
| ClearJoins(); |
| ClearHorzJoins(); |
| return succeeded; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::InsertScanbeam(const long64 Y) |
| { |
| if( !m_Scanbeam ) |
| { |
| m_Scanbeam = new Scanbeam; |
| m_Scanbeam->next = 0; |
| m_Scanbeam->Y = Y; |
| } |
| else if( Y > m_Scanbeam->Y ) |
| { |
| Scanbeam* newSb = new Scanbeam; |
| newSb->Y = Y; |
| newSb->next = m_Scanbeam; |
| m_Scanbeam = newSb; |
| } else |
| { |
| Scanbeam* sb2 = m_Scanbeam; |
| while( sb2->next && ( Y <= sb2->next->Y ) ) sb2 = sb2->next; |
| if( Y == sb2->Y ) return; //ie ignores duplicates |
| Scanbeam* newSb = new Scanbeam; |
| newSb->Y = Y; |
| newSb->next = sb2->next; |
| sb2->next = newSb; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| long64 Clipper::PopScanbeam() |
| { |
| long64 Y = m_Scanbeam->Y; |
| Scanbeam* sb2 = m_Scanbeam; |
| m_Scanbeam = m_Scanbeam->next; |
| delete sb2; |
| return Y; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DisposeAllPolyPts(){ |
| for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) |
| DisposeOutRec(i); |
| m_PolyOuts.clear(); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DisposeOutRec(PolyOutList::size_type index) |
| { |
| OutRec *outRec = m_PolyOuts[index]; |
| if (outRec->pts) DisposeOutPts(outRec->pts); |
| delete outRec; |
| m_PolyOuts[index] = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::SetWindingCount(TEdge &edge) |
| { |
| TEdge *e = edge.prevInAEL; |
| //find the edge of the same polytype that immediately preceeds 'edge' in AEL |
| while ( e && e->polyType != edge.polyType ) e = e->prevInAEL; |
| if ( !e ) |
| { |
| edge.windCnt = edge.windDelta; |
| edge.windCnt2 = 0; |
| e = m_ActiveEdges; //ie get ready to calc windCnt2 |
| } else if ( IsEvenOddFillType(edge) ) |
| { |
| //EvenOdd filling ... |
| edge.windCnt = 1; |
| edge.windCnt2 = e->windCnt2; |
| e = e->nextInAEL; //ie get ready to calc windCnt2 |
| } else |
| { |
| //nonZero, Positive or Negative filling ... |
| if ( e->windCnt * e->windDelta < 0 ) |
| { |
| if (Abs(e->windCnt) > 1) |
| { |
| if (e->windDelta * edge.windDelta < 0) edge.windCnt = e->windCnt; |
| else edge.windCnt = e->windCnt + edge.windDelta; |
| } else |
| edge.windCnt = e->windCnt + e->windDelta + edge.windDelta; |
| } else |
| { |
| if ( Abs(e->windCnt) > 1 && e->windDelta * edge.windDelta < 0) |
| edge.windCnt = e->windCnt; |
| else if ( e->windCnt + edge.windDelta == 0 ) |
| edge.windCnt = e->windCnt; |
| else edge.windCnt = e->windCnt + edge.windDelta; |
| } |
| edge.windCnt2 = e->windCnt2; |
| e = e->nextInAEL; //ie get ready to calc windCnt2 |
| } |
| |
| //update windCnt2 ... |
| if ( IsEvenOddAltFillType(edge) ) |
| { |
| //EvenOdd filling ... |
| while ( e != &edge ) |
| { |
| edge.windCnt2 = (edge.windCnt2 == 0) ? 1 : 0; |
| e = e->nextInAEL; |
| } |
| } else |
| { |
| //nonZero, Positive or Negative filling ... |
| while ( e != &edge ) |
| { |
| edge.windCnt2 += e->windDelta; |
| e = e->nextInAEL; |
| } |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::IsEvenOddFillType(const TEdge& edge) const |
| { |
| if (edge.polyType == ptSubject) |
| return m_SubjFillType == pftEvenOdd; else |
| return m_ClipFillType == pftEvenOdd; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::IsEvenOddAltFillType(const TEdge& edge) const |
| { |
| if (edge.polyType == ptSubject) |
| return m_ClipFillType == pftEvenOdd; else |
| return m_SubjFillType == pftEvenOdd; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::IsContributing(const TEdge& edge) const |
| { |
| PolyFillType pft, pft2; |
| if (edge.polyType == ptSubject) |
| { |
| pft = m_SubjFillType; |
| pft2 = m_ClipFillType; |
| } else |
| { |
| pft = m_ClipFillType; |
| pft2 = m_SubjFillType; |
| } |
| |
| switch(pft) |
| { |
| case pftEvenOdd: |
| case pftNonZero: |
| if (Abs(edge.windCnt) != 1) return false; |
| break; |
| case pftPositive: |
| if (edge.windCnt != 1) return false; |
| break; |
| default: //pftNegative |
| if (edge.windCnt != -1) return false; |
| } |
| |
| switch(m_ClipType) |
| { |
| case ctIntersection: |
| switch(pft2) |
| { |
| case pftEvenOdd: |
| case pftNonZero: |
| return (edge.windCnt2 != 0); |
| case pftPositive: |
| return (edge.windCnt2 > 0); |
| default: |
| return (edge.windCnt2 < 0); |
| } |
| case ctUnion: |
| switch(pft2) |
| { |
| case pftEvenOdd: |
| case pftNonZero: |
| return (edge.windCnt2 == 0); |
| case pftPositive: |
| return (edge.windCnt2 <= 0); |
| default: |
| return (edge.windCnt2 >= 0); |
| } |
| case ctDifference: |
| if (edge.polyType == ptSubject) |
| switch(pft2) |
| { |
| case pftEvenOdd: |
| case pftNonZero: |
| return (edge.windCnt2 == 0); |
| case pftPositive: |
| return (edge.windCnt2 <= 0); |
| default: |
| return (edge.windCnt2 >= 0); |
| } |
| else |
| switch(pft2) |
| { |
| case pftEvenOdd: |
| case pftNonZero: |
| return (edge.windCnt2 != 0); |
| case pftPositive: |
| return (edge.windCnt2 > 0); |
| default: |
| return (edge.windCnt2 < 0); |
| } |
| default: |
| return true; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt) |
| { |
| TEdge *e, *prevE; |
| if( NEAR_EQUAL(e2->dx, HORIZONTAL) || ( e1->dx > e2->dx ) ) |
| { |
| AddOutPt( e1, pt ); |
| e2->outIdx = e1->outIdx; |
| e1->side = esLeft; |
| e2->side = esRight; |
| e = e1; |
| if (e->prevInAEL == e2) |
| prevE = e2->prevInAEL; |
| else |
| prevE = e->prevInAEL; |
| } else |
| { |
| AddOutPt( e2, pt ); |
| e1->outIdx = e2->outIdx; |
| e1->side = esRight; |
| e2->side = esLeft; |
| e = e2; |
| if (e->prevInAEL == e1) |
| prevE = e1->prevInAEL; |
| else |
| prevE = e->prevInAEL; |
| } |
| if (prevE && prevE->outIdx >= 0 && |
| (TopX(*prevE, pt.Y) == TopX(*e, pt.Y)) && |
| SlopesEqual(*e, *prevE, m_UseFullRange)) |
| AddJoin(e, prevE, -1, -1); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt) |
| { |
| AddOutPt( e1, pt ); |
| if( e1->outIdx == e2->outIdx ) |
| { |
| e1->outIdx = -1; |
| e2->outIdx = -1; |
| } |
| else if (e1->outIdx < e2->outIdx) |
| AppendPolygon(e1, e2); |
| else |
| AppendPolygon(e2, e1); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddEdgeToSEL(TEdge *edge) |
| { |
| //SEL pointers in PEdge are reused to build a list of horizontal edges. |
| //However, we don't need to worry about order with horizontal edge processing. |
| if( !m_SortedEdges ) |
| { |
| m_SortedEdges = edge; |
| edge->prevInSEL = 0; |
| edge->nextInSEL = 0; |
| } |
| else |
| { |
| edge->nextInSEL = m_SortedEdges; |
| edge->prevInSEL = 0; |
| m_SortedEdges->prevInSEL = edge; |
| m_SortedEdges = edge; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::CopyAELToSEL() |
| { |
| TEdge* e = m_ActiveEdges; |
| m_SortedEdges = e; |
| if (!m_ActiveEdges) return; |
| m_SortedEdges->prevInSEL = 0; |
| e = e->nextInAEL; |
| while ( e ) |
| { |
| e->prevInSEL = e->prevInAEL; |
| e->prevInSEL->nextInSEL = e; |
| e->nextInSEL = 0; |
| e = e->nextInAEL; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx, int e2OutIdx) |
| { |
| JoinRec* jr = new JoinRec; |
| if (e1OutIdx >= 0) |
| jr->poly1Idx = e1OutIdx; else |
| jr->poly1Idx = e1->outIdx; |
| jr->pt1a = IntPoint(e1->xcurr, e1->ycurr); |
| jr->pt1b = IntPoint(e1->xtop, e1->ytop); |
| if (e2OutIdx >= 0) |
| jr->poly2Idx = e2OutIdx; else |
| jr->poly2Idx = e2->outIdx; |
| jr->pt2a = IntPoint(e2->xcurr, e2->ycurr); |
| jr->pt2b = IntPoint(e2->xtop, e2->ytop); |
| m_Joins.push_back(jr); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ClearJoins() |
| { |
| for (JoinList::size_type i = 0; i < m_Joins.size(); i++) |
| delete m_Joins[i]; |
| m_Joins.resize(0); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddHorzJoin(TEdge *e, int idx) |
| { |
| HorzJoinRec* hj = new HorzJoinRec; |
| hj->edge = e; |
| hj->savedIdx = idx; |
| m_HorizJoins.push_back(hj); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ClearHorzJoins() |
| { |
| for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); i++) |
| delete m_HorizJoins[i]; |
| m_HorizJoins.resize(0); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::InsertLocalMinimaIntoAEL( const long64 botY) |
| { |
| while( m_CurrentLM && ( m_CurrentLM->Y == botY ) ) |
| { |
| TEdge* lb = m_CurrentLM->leftBound; |
| TEdge* rb = m_CurrentLM->rightBound; |
| |
| InsertEdgeIntoAEL( lb ); |
| InsertScanbeam( lb->ytop ); |
| InsertEdgeIntoAEL( rb ); |
| |
| if (IsEvenOddFillType(*lb)) |
| { |
| lb->windDelta = 1; |
| rb->windDelta = 1; |
| } |
| else |
| { |
| rb->windDelta = -lb->windDelta; |
| } |
| SetWindingCount( *lb ); |
| rb->windCnt = lb->windCnt; |
| rb->windCnt2 = lb->windCnt2; |
| |
| if( NEAR_EQUAL(rb->dx, HORIZONTAL) ) |
| { |
| //nb: only rightbounds can have a horizontal bottom edge |
| AddEdgeToSEL( rb ); |
| InsertScanbeam( rb->nextInLML->ytop ); |
| } |
| else |
| InsertScanbeam( rb->ytop ); |
| |
| if( IsContributing(*lb) ) |
| AddLocalMinPoly( lb, rb, IntPoint(lb->xcurr, m_CurrentLM->Y) ); |
| |
| //if any output polygons share an edge, they'll need joining later ... |
| if (rb->outIdx >= 0) |
| { |
| if (NEAR_EQUAL(rb->dx, HORIZONTAL)) |
| { |
| for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i) |
| { |
| IntPoint pt, pt2; //returned by GetOverlapSegment() but unused here. |
| HorzJoinRec* hj = m_HorizJoins[i]; |
| //if horizontals rb and hj.edge overlap, flag for joining later ... |
| if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot), |
| IntPoint(hj->edge->xtop, hj->edge->ytop), |
| IntPoint(rb->xbot, rb->ybot), |
| IntPoint(rb->xtop, rb->ytop), pt, pt2)) |
| AddJoin(hj->edge, rb, hj->savedIdx); |
| } |
| } |
| } |
| |
| if( lb->nextInAEL != rb ) |
| { |
| if (rb->outIdx >= 0 && rb->prevInAEL->outIdx >= 0 && |
| SlopesEqual(*rb->prevInAEL, *rb, m_UseFullRange)) |
| AddJoin(rb, rb->prevInAEL); |
| |
| TEdge* e = lb->nextInAEL; |
| IntPoint pt = IntPoint(lb->xcurr, lb->ycurr); |
| while( e != rb ) |
| { |
| if(!e) throw clipperException("InsertLocalMinimaIntoAEL: missing rightbound!"); |
| //nb: For calculating winding counts etc, IntersectEdges() assumes |
| //that param1 will be to the right of param2 ABOVE the intersection ... |
| IntersectEdges( rb , e , pt , ipNone); //order important here |
| e = e->nextInAEL; |
| } |
| } |
| PopLocalMinima(); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DeleteFromAEL(TEdge *e) |
| { |
| TEdge* AelPrev = e->prevInAEL; |
| TEdge* AelNext = e->nextInAEL; |
| if( !AelPrev && !AelNext && (e != m_ActiveEdges) ) return; //already deleted |
| if( AelPrev ) AelPrev->nextInAEL = AelNext; |
| else m_ActiveEdges = AelNext; |
| if( AelNext ) AelNext->prevInAEL = AelPrev; |
| e->nextInAEL = 0; |
| e->prevInAEL = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DeleteFromSEL(TEdge *e) |
| { |
| TEdge* SelPrev = e->prevInSEL; |
| TEdge* SelNext = e->nextInSEL; |
| if( !SelPrev && !SelNext && (e != m_SortedEdges) ) return; //already deleted |
| if( SelPrev ) SelPrev->nextInSEL = SelNext; |
| else m_SortedEdges = SelNext; |
| if( SelNext ) SelNext->prevInSEL = SelPrev; |
| e->nextInSEL = 0; |
| e->prevInSEL = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::IntersectEdges(TEdge *e1, TEdge *e2, |
| const IntPoint &pt, IntersectProtects protects) |
| { |
| //e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before |
| //e2 in AEL except when e1 is being inserted at the intersection point ... |
| bool e1stops = !(ipLeft & protects) && !e1->nextInLML && |
| e1->xtop == pt.X && e1->ytop == pt.Y; |
| bool e2stops = !(ipRight & protects) && !e2->nextInLML && |
| e2->xtop == pt.X && e2->ytop == pt.Y; |
| bool e1Contributing = ( e1->outIdx >= 0 ); |
| bool e2contributing = ( e2->outIdx >= 0 ); |
| |
| //update winding counts... |
| //assumes that e1 will be to the right of e2 ABOVE the intersection |
| if ( e1->polyType == e2->polyType ) |
| { |
| if ( IsEvenOddFillType( *e1) ) |
| { |
| int oldE1WindCnt = e1->windCnt; |
| e1->windCnt = e2->windCnt; |
| e2->windCnt = oldE1WindCnt; |
| } else |
| { |
| if (e1->windCnt + e2->windDelta == 0 ) e1->windCnt = -e1->windCnt; |
| else e1->windCnt += e2->windDelta; |
| if ( e2->windCnt - e1->windDelta == 0 ) e2->windCnt = -e2->windCnt; |
| else e2->windCnt -= e1->windDelta; |
| } |
| } else |
| { |
| if (!IsEvenOddFillType(*e2)) e1->windCnt2 += e2->windDelta; |
| else e1->windCnt2 = ( e1->windCnt2 == 0 ) ? 1 : 0; |
| if (!IsEvenOddFillType(*e1)) e2->windCnt2 -= e1->windDelta; |
| else e2->windCnt2 = ( e2->windCnt2 == 0 ) ? 1 : 0; |
| } |
| |
| PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2; |
| if (e1->polyType == ptSubject) |
| { |
| e1FillType = m_SubjFillType; |
| e1FillType2 = m_ClipFillType; |
| } else |
| { |
| e1FillType = m_ClipFillType; |
| e1FillType2 = m_SubjFillType; |
| } |
| if (e2->polyType == ptSubject) |
| { |
| e2FillType = m_SubjFillType; |
| e2FillType2 = m_ClipFillType; |
| } else |
| { |
| e2FillType = m_ClipFillType; |
| e2FillType2 = m_SubjFillType; |
| } |
| |
| long64 e1Wc, e2Wc; |
| switch (e1FillType) |
| { |
| case pftPositive: e1Wc = e1->windCnt; break; |
| case pftNegative: e1Wc = -e1->windCnt; break; |
| default: e1Wc = Abs(e1->windCnt); |
| } |
| switch(e2FillType) |
| { |
| case pftPositive: e2Wc = e2->windCnt; break; |
| case pftNegative: e2Wc = -e2->windCnt; break; |
| default: e2Wc = Abs(e2->windCnt); |
| } |
| |
| if ( e1Contributing && e2contributing ) |
| { |
| if ( e1stops || e2stops || |
| (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) || |
| (e1->polyType != e2->polyType && m_ClipType != ctXor) ) |
| AddLocalMaxPoly(e1, e2, pt); |
| else |
| DoBothEdges( e1, e2, pt ); |
| } |
| else if ( e1Contributing ) |
| { |
| if ((e2Wc == 0 || e2Wc == 1) && |
| (m_ClipType != ctIntersection || |
| e2->polyType == ptSubject || (e2->windCnt2 != 0))) |
| DoEdge1(e1, e2, pt); |
| } |
| else if ( e2contributing ) |
| { |
| if ((e1Wc == 0 || e1Wc == 1) && |
| (m_ClipType != ctIntersection || |
| e1->polyType == ptSubject || (e1->windCnt2 != 0))) |
| DoEdge2(e1, e2, pt); |
| } |
| else if ( (e1Wc == 0 || e1Wc == 1) && |
| (e2Wc == 0 || e2Wc == 1) && !e1stops && !e2stops ) |
| { |
| //neither edge is currently contributing ... |
| |
| long64 e1Wc2, e2Wc2; |
| switch (e1FillType2) |
| { |
| case pftPositive: e1Wc2 = e1->windCnt2; break; |
| case pftNegative : e1Wc2 = -e1->windCnt2; break; |
| default: e1Wc2 = Abs(e1->windCnt2); |
| } |
| switch (e2FillType2) |
| { |
| case pftPositive: e2Wc2 = e2->windCnt2; break; |
| case pftNegative: e2Wc2 = -e2->windCnt2; break; |
| default: e2Wc2 = Abs(e2->windCnt2); |
| } |
| |
| if (e1->polyType != e2->polyType) |
| AddLocalMinPoly(e1, e2, pt); |
| else if (e1Wc == 1 && e2Wc == 1) |
| switch( m_ClipType ) { |
| case ctIntersection: |
| if (e1Wc2 > 0 && e2Wc2 > 0) |
| AddLocalMinPoly(e1, e2, pt); |
| break; |
| case ctUnion: |
| if ( e1Wc2 <= 0 && e2Wc2 <= 0 ) |
| AddLocalMinPoly(e1, e2, pt); |
| break; |
| case ctDifference: |
| if (((e1->polyType == ptClip) && (e1Wc2 > 0) && (e2Wc2 > 0)) || |
| ((e1->polyType == ptSubject) && (e1Wc2 <= 0) && (e2Wc2 <= 0))) |
| AddLocalMinPoly(e1, e2, pt); |
| break; |
| case ctXor: |
| AddLocalMinPoly(e1, e2, pt); |
| } |
| else |
| SwapSides( *e1, *e2 ); |
| } |
| |
| if( (e1stops != e2stops) && |
| ( (e1stops && (e1->outIdx >= 0)) || (e2stops && (e2->outIdx >= 0)) ) ) |
| { |
| SwapSides( *e1, *e2 ); |
| SwapPolyIndexes( *e1, *e2 ); |
| } |
| |
| //finally, delete any non-contributing maxima edges ... |
| if( e1stops ) DeleteFromAEL( e1 ); |
| if( e2stops ) DeleteFromAEL( e2 ); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::SetHoleState(TEdge *e, OutRec *outRec) |
| { |
| bool isHole = false; |
| TEdge *e2 = e->prevInAEL; |
| while (e2) |
| { |
| if (e2->outIdx >= 0) |
| { |
| isHole = !isHole; |
| if (! outRec->FirstLeft) |
| outRec->FirstLeft = m_PolyOuts[e2->outIdx]; |
| } |
| e2 = e2->prevInAEL; |
| } |
| if (isHole) outRec->isHole = true; |
| } |
| //------------------------------------------------------------------------------ |
| |
| OutRec* GetLowermostRec(OutRec *outRec1, OutRec *outRec2) |
| { |
| //work out which polygon fragment has the correct hole state ... |
| OutPt *outPt1 = outRec1->bottomPt; |
| OutPt *outPt2 = outRec2->bottomPt; |
| if (outPt1->pt.Y > outPt2->pt.Y) return outRec1; |
| else if (outPt1->pt.Y < outPt2->pt.Y) return outRec2; |
| else if (outPt1->pt.X < outPt2->pt.X) return outRec1; |
| else if (outPt1->pt.X > outPt2->pt.X) return outRec2; |
| else if (outPt1->next == outPt1) return outRec2; |
| else if (outPt2->next == outPt2) return outRec1; |
| else if (FirstIsBottomPt(outPt1, outPt2)) return outRec1; |
| else return outRec2; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Param1RightOfParam2(OutRec* outRec1, OutRec* outRec2) |
| { |
| do |
| { |
| outRec1 = outRec1->FirstLeft; |
| if (outRec1 == outRec2) return true; |
| } while (outRec1); |
| return false; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AppendPolygon(TEdge *e1, TEdge *e2) |
| { |
| //get the start and ends of both output polygons ... |
| OutRec *outRec1 = m_PolyOuts[e1->outIdx]; |
| OutRec *outRec2 = m_PolyOuts[e2->outIdx]; |
| |
| OutRec *holeStateRec; |
| if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2; |
| else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1; |
| else holeStateRec = GetLowermostRec(outRec1, outRec2); |
| |
| OutPt* p1_lft = outRec1->pts; |
| OutPt* p1_rt = p1_lft->prev; |
| OutPt* p2_lft = outRec2->pts; |
| OutPt* p2_rt = p2_lft->prev; |
| |
| EdgeSide side; |
| //join e2 poly onto e1 poly and delete pointers to e2 ... |
| if( e1->side == esLeft ) |
| { |
| if( e2->side == esLeft ) |
| { |
| //z y x a b c |
| ReversePolyPtLinks(*p2_lft); |
| p2_lft->next = p1_lft; |
| p1_lft->prev = p2_lft; |
| p1_rt->next = p2_rt; |
| p2_rt->prev = p1_rt; |
| outRec1->pts = p2_rt; |
| } else |
| { |
| //x y z a b c |
| p2_rt->next = p1_lft; |
| p1_lft->prev = p2_rt; |
| p2_lft->prev = p1_rt; |
| p1_rt->next = p2_lft; |
| outRec1->pts = p2_lft; |
| } |
| side = esLeft; |
| } else |
| { |
| if( e2->side == esRight ) |
| { |
| //a b c z y x |
| ReversePolyPtLinks( *p2_lft ); |
| p1_rt->next = p2_rt; |
| p2_rt->prev = p1_rt; |
| p2_lft->next = p1_lft; |
| p1_lft->prev = p2_lft; |
| } else |
| { |
| //a b c x y z |
| p1_rt->next = p2_lft; |
| p2_lft->prev = p1_rt; |
| p1_lft->prev = p2_rt; |
| p2_rt->next = p1_lft; |
| } |
| side = esRight; |
| } |
| |
| if (holeStateRec == outRec2) |
| { |
| outRec1->bottomPt = outRec2->bottomPt; |
| outRec1->bottomPt->idx = outRec1->idx; |
| if (outRec2->FirstLeft != outRec1) |
| outRec1->FirstLeft = outRec2->FirstLeft; |
| outRec1->isHole = outRec2->isHole; |
| } |
| outRec2->pts = 0; |
| outRec2->bottomPt = 0; |
| outRec2->AppendLink = outRec1; |
| int OKIdx = e1->outIdx; |
| int ObsoleteIdx = e2->outIdx; |
| |
| e1->outIdx = -1; //nb: safe because we only get here via AddLocalMaxPoly |
| e2->outIdx = -1; |
| |
| TEdge* e = m_ActiveEdges; |
| while( e ) |
| { |
| if( e->outIdx == ObsoleteIdx ) |
| { |
| e->outIdx = OKIdx; |
| e->side = side; |
| break; |
| } |
| e = e->nextInAEL; |
| } |
| |
| for (JoinList::size_type i = 0; i < m_Joins.size(); ++i) |
| { |
| if (m_Joins[i]->poly1Idx == ObsoleteIdx) m_Joins[i]->poly1Idx = OKIdx; |
| if (m_Joins[i]->poly2Idx == ObsoleteIdx) m_Joins[i]->poly2Idx = OKIdx; |
| } |
| |
| for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i) |
| { |
| if (m_HorizJoins[i]->savedIdx == ObsoleteIdx) |
| m_HorizJoins[i]->savedIdx = OKIdx; |
| } |
| |
| } |
| //------------------------------------------------------------------------------ |
| |
| OutRec* Clipper::CreateOutRec() |
| { |
| OutRec* result = new OutRec; |
| result->isHole = false; |
| result->FirstLeft = 0; |
| result->AppendLink = 0; |
| result->pts = 0; |
| result->bottomPt = 0; |
| result->sides = esNeither; |
| result->bottomFlag = 0; |
| |
| return result; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DisposeBottomPt(OutRec &outRec) |
| { |
| OutPt* next = outRec.bottomPt->next; |
| OutPt* prev = outRec.bottomPt->prev; |
| if (outRec.pts == outRec.bottomPt) outRec.pts = next; |
| delete outRec.bottomPt; |
| next->prev = prev; |
| prev->next = next; |
| outRec.bottomPt = next; |
| FixupOutPolygon(outRec); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddOutPt(TEdge *e, const IntPoint &pt) |
| { |
| bool ToFront = (e->side == esLeft); |
| if( e->outIdx < 0 ) |
| { |
| OutRec *outRec = CreateOutRec(); |
| m_PolyOuts.push_back(outRec); |
| outRec->idx = (int)m_PolyOuts.size()-1; |
| e->outIdx = outRec->idx; |
| OutPt* op = new OutPt; |
| outRec->pts = op; |
| outRec->bottomPt = op; |
| op->pt = pt; |
| op->idx = outRec->idx; |
| op->next = op; |
| op->prev = op; |
| SetHoleState(e, outRec); |
| } else |
| { |
| OutRec *outRec = m_PolyOuts[e->outIdx]; |
| OutPt* op = outRec->pts; |
| if ((ToFront && PointsEqual(pt, op->pt)) || |
| (!ToFront && PointsEqual(pt, op->prev->pt))) return; |
| |
| if ((e->side | outRec->sides) != outRec->sides) |
| { |
| //check for 'rounding' artefacts ... |
| if (outRec->sides == esNeither && pt.Y == op->pt.Y) |
| { |
| if (ToFront) |
| { |
| 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); |
| if (outRec->sides == esBoth) |
| { |
| //A vertex from each side has now been added. |
| //Vertices of one side of an output polygon are quite commonly close to |
| //or even 'touching' edges of the other side of the output polygon. |
| //Very occasionally vertices from one side can 'cross' an edge on the |
| //the other side. The distance 'crossed' is always less that a unit |
| //and is purely an artefact of coordinate rounding. Nevertheless, this |
| //results in very tiny self-intersections. Because of the way |
| //orientation is calculated, even tiny self-intersections can cause |
| //the Orientation function to return the wrong result. Therefore, it's |
| //important to ensure that any self-intersections close to BottomPt are |
| //detected and removed before orientation is assigned. |
| |
| OutPt *opBot, *op2; |
| if (ToFront) |
| { |
| opBot = outRec->pts; |
| op2 = opBot->next; //op2 == right side |
| if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y && |
| ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) < |
| (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y))) |
| outRec->bottomFlag = opBot; |
| } else |
| { |
| opBot = outRec->pts->prev; |
| op2 = opBot->prev; //op2 == left side |
| if (opBot->pt.Y != op2->pt.Y && opBot->pt.Y != pt.Y && |
| ((opBot->pt.X - pt.X)/(opBot->pt.Y - pt.Y) > |
| (opBot->pt.X - op2->pt.X)/(opBot->pt.Y - op2->pt.Y))) |
| outRec->bottomFlag = opBot; |
| } |
| } |
| } |
| |
| OutPt* op2 = new OutPt; |
| op2->pt = pt; |
| op2->idx = outRec->idx; |
| if (op2->pt.Y == outRec->bottomPt->pt.Y && |
| op2->pt.X < outRec->bottomPt->pt.X) |
| outRec->bottomPt = op2; |
| op2->next = op; |
| op2->prev = op->prev; |
| op2->prev->next = op2; |
| op->prev = op2; |
| if (ToFront) outRec->pts = op2; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ProcessHorizontals() |
| { |
| TEdge* horzEdge = m_SortedEdges; |
| while( horzEdge ) |
| { |
| DeleteFromSEL( horzEdge ); |
| ProcessHorizontal( horzEdge ); |
| horzEdge = m_SortedEdges; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::IsTopHorz(const long64 XPos) |
| { |
| TEdge* e = m_SortedEdges; |
| while( e ) |
| { |
| if( ( XPos >= std::min(e->xcurr, e->xtop) ) && |
| ( XPos <= std::max(e->xcurr, e->xtop) ) ) return false; |
| e = e->nextInSEL; |
| } |
| return true; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool IsMinima(TEdge *e) |
| { |
| return e && (e->prev->nextInLML != e) && (e->next->nextInLML != e); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool IsMaxima(TEdge *e, const long64 Y) |
| { |
| return e && e->ytop == Y && !e->nextInLML; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool IsIntermediate(TEdge *e, const long64 Y) |
| { |
| return e->ytop == Y && e->nextInLML; |
| } |
| //------------------------------------------------------------------------------ |
| |
| TEdge *GetMaximaPair(TEdge *e) |
| { |
| if( !IsMaxima(e->next, e->ytop) || e->next->xtop != e->xtop ) |
| return e->prev; else |
| return e->next; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::SwapPositionsInAEL(TEdge *edge1, TEdge *edge2) |
| { |
| if( !edge1->nextInAEL && !edge1->prevInAEL ) return; |
| if( !edge2->nextInAEL && !edge2->prevInAEL ) return; |
| |
| if( edge1->nextInAEL == edge2 ) |
| { |
| TEdge* next = edge2->nextInAEL; |
| if( next ) next->prevInAEL = edge1; |
| TEdge* prev = edge1->prevInAEL; |
| if( prev ) prev->nextInAEL = edge2; |
| edge2->prevInAEL = prev; |
| edge2->nextInAEL = edge1; |
| edge1->prevInAEL = edge2; |
| edge1->nextInAEL = next; |
| } |
| else if( edge2->nextInAEL == edge1 ) |
| { |
| TEdge* next = edge1->nextInAEL; |
| if( next ) next->prevInAEL = edge2; |
| TEdge* prev = edge2->prevInAEL; |
| if( prev ) prev->nextInAEL = edge1; |
| edge1->prevInAEL = prev; |
| edge1->nextInAEL = edge2; |
| edge2->prevInAEL = edge1; |
| edge2->nextInAEL = next; |
| } |
| else |
| { |
| TEdge* next = edge1->nextInAEL; |
| TEdge* prev = edge1->prevInAEL; |
| edge1->nextInAEL = edge2->nextInAEL; |
| if( edge1->nextInAEL ) edge1->nextInAEL->prevInAEL = edge1; |
| edge1->prevInAEL = edge2->prevInAEL; |
| if( edge1->prevInAEL ) edge1->prevInAEL->nextInAEL = edge1; |
| edge2->nextInAEL = next; |
| if( edge2->nextInAEL ) edge2->nextInAEL->prevInAEL = edge2; |
| edge2->prevInAEL = prev; |
| if( edge2->prevInAEL ) edge2->prevInAEL->nextInAEL = edge2; |
| } |
| |
| if( !edge1->prevInAEL ) m_ActiveEdges = edge1; |
| else if( !edge2->prevInAEL ) m_ActiveEdges = edge2; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::SwapPositionsInSEL(TEdge *edge1, TEdge *edge2) |
| { |
| if( !( edge1->nextInSEL ) && !( edge1->prevInSEL ) ) return; |
| if( !( edge2->nextInSEL ) && !( edge2->prevInSEL ) ) return; |
| |
| if( edge1->nextInSEL == edge2 ) |
| { |
| TEdge* next = edge2->nextInSEL; |
| if( next ) next->prevInSEL = edge1; |
| TEdge* prev = edge1->prevInSEL; |
| if( prev ) prev->nextInSEL = edge2; |
| edge2->prevInSEL = prev; |
| edge2->nextInSEL = edge1; |
| edge1->prevInSEL = edge2; |
| edge1->nextInSEL = next; |
| } |
| else if( edge2->nextInSEL == edge1 ) |
| { |
| TEdge* next = edge1->nextInSEL; |
| if( next ) next->prevInSEL = edge2; |
| TEdge* prev = edge2->prevInSEL; |
| if( prev ) prev->nextInSEL = edge1; |
| edge1->prevInSEL = prev; |
| edge1->nextInSEL = edge2; |
| edge2->prevInSEL = edge1; |
| edge2->nextInSEL = next; |
| } |
| else |
| { |
| TEdge* next = edge1->nextInSEL; |
| TEdge* prev = edge1->prevInSEL; |
| edge1->nextInSEL = edge2->nextInSEL; |
| if( edge1->nextInSEL ) edge1->nextInSEL->prevInSEL = edge1; |
| edge1->prevInSEL = edge2->prevInSEL; |
| if( edge1->prevInSEL ) edge1->prevInSEL->nextInSEL = edge1; |
| edge2->nextInSEL = next; |
| if( edge2->nextInSEL ) edge2->nextInSEL->prevInSEL = edge2; |
| edge2->prevInSEL = prev; |
| if( edge2->prevInSEL ) edge2->prevInSEL->nextInSEL = edge2; |
| } |
| |
| if( !edge1->prevInSEL ) m_SortedEdges = edge1; |
| else if( !edge2->prevInSEL ) m_SortedEdges = edge2; |
| } |
| //------------------------------------------------------------------------------ |
| |
| TEdge* GetNextInAEL(TEdge *e, Direction dir) |
| { |
| return dir == dLeftToRight ? e->nextInAEL : e->prevInAEL; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ProcessHorizontal(TEdge *horzEdge) |
| { |
| Direction dir; |
| long64 horzLeft, horzRight; |
| |
| if( horzEdge->xcurr < horzEdge->xtop ) |
| { |
| horzLeft = horzEdge->xcurr; |
| horzRight = horzEdge->xtop; |
| dir = dLeftToRight; |
| } else |
| { |
| horzLeft = horzEdge->xtop; |
| horzRight = horzEdge->xcurr; |
| dir = dRightToLeft; |
| } |
| |
| TEdge* eMaxPair; |
| if( horzEdge->nextInLML ) eMaxPair = 0; |
| else eMaxPair = GetMaximaPair(horzEdge); |
| |
| TEdge* e = GetNextInAEL( horzEdge , dir ); |
| while( e ) |
| { |
| TEdge* eNext = GetNextInAEL( e, dir ); |
| |
| if (eMaxPair || |
| ((dir == dLeftToRight) && (e->xcurr <= horzRight)) || |
| ((dir == dRightToLeft) && (e->xcurr >= horzLeft))) |
| { |
| //ok, so far it looks like we're still in range of the horizontal edge |
| if ( e->xcurr == horzEdge->xtop && !eMaxPair ) |
| { |
| assert(horzEdge->nextInLML); |
| if (SlopesEqual(*e, *horzEdge->nextInLML, m_UseFullRange)) |
| { |
| //if output polygons share an edge, they'll need joining later ... |
| if (horzEdge->outIdx >= 0 && e->outIdx >= 0) |
| AddJoin(horzEdge->nextInLML, e, horzEdge->outIdx); |
| break; //we've reached the end of the horizontal line |
| } |
| else if (e->dx < horzEdge->nextInLML->dx) |
| //we really have got to the end of the intermediate horz edge so quit. |
| //nb: More -ve slopes follow more +ve slopes ABOVE the horizontal. |
| break; |
| } |
| |
| if( e == eMaxPair ) |
| { |
| //horzEdge is evidently a maxima horizontal and we've arrived at its end. |
| if (dir == dLeftToRight) |
| IntersectEdges(horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), ipNone); |
| else |
| IntersectEdges(e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), ipNone); |
| if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error"); |
| return; |
| } |
| else if( NEAR_EQUAL(e->dx, HORIZONTAL) && !IsMinima(e) && !(e->xcurr > e->xtop) ) |
| { |
| //An overlapping horizontal edge. Overlapping horizontal edges are |
| //processed as if layered with the current horizontal edge (horizEdge) |
| //being infinitesimally lower that the next (e). Therfore, we |
| //intersect with e only if e.xcurr is within the bounds of horzEdge ... |
| if( dir == dLeftToRight ) |
| IntersectEdges( horzEdge , e, IntPoint(e->xcurr, horzEdge->ycurr), |
| (IsTopHorz( e->xcurr ))? ipLeft : ipBoth ); |
| else |
| IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), |
| (IsTopHorz( e->xcurr ))? ipRight : ipBoth ); |
| } |
| else if( dir == dLeftToRight ) |
| { |
| IntersectEdges( horzEdge, e, IntPoint(e->xcurr, horzEdge->ycurr), |
| (IsTopHorz( e->xcurr ))? ipLeft : ipBoth ); |
| } |
| else |
| { |
| IntersectEdges( e, horzEdge, IntPoint(e->xcurr, horzEdge->ycurr), |
| (IsTopHorz( e->xcurr ))? ipRight : ipBoth ); |
| } |
| SwapPositionsInAEL( horzEdge, e ); |
| } |
| else if( (dir == dLeftToRight && e->xcurr > horzRight && m_SortedEdges) || |
| (dir == dRightToLeft && e->xcurr < horzLeft && m_SortedEdges) ) break; |
| e = eNext; |
| } //end while |
| |
| if( horzEdge->nextInLML ) |
| { |
| if( horzEdge->outIdx >= 0 ) |
| AddOutPt( horzEdge, IntPoint(horzEdge->xtop, horzEdge->ytop)); |
| UpdateEdgeIntoAEL( horzEdge ); |
| } |
| else |
| { |
| if ( horzEdge->outIdx >= 0 ) |
| IntersectEdges( horzEdge, eMaxPair, |
| IntPoint(horzEdge->xtop, horzEdge->ycurr), ipBoth); |
| assert(eMaxPair); |
| if (eMaxPair->outIdx >= 0) throw clipperException("ProcessHorizontal error"); |
| DeleteFromAEL(eMaxPair); |
| DeleteFromAEL(horzEdge); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::UpdateEdgeIntoAEL(TEdge *&e) |
| { |
| if( !e->nextInLML ) throw |
| clipperException("UpdateEdgeIntoAEL: invalid call"); |
| TEdge* AelPrev = e->prevInAEL; |
| TEdge* AelNext = e->nextInAEL; |
| e->nextInLML->outIdx = e->outIdx; |
| if( AelPrev ) AelPrev->nextInAEL = e->nextInLML; |
| else m_ActiveEdges = e->nextInLML; |
| if( AelNext ) AelNext->prevInAEL = e->nextInLML; |
| e->nextInLML->side = e->side; |
| e->nextInLML->windDelta = e->windDelta; |
| e->nextInLML->windCnt = e->windCnt; |
| e->nextInLML->windCnt2 = e->windCnt2; |
| e = e->nextInLML; |
| e->prevInAEL = AelPrev; |
| e->nextInAEL = AelNext; |
| if( !NEAR_EQUAL(e->dx, HORIZONTAL) ) InsertScanbeam( e->ytop ); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::ProcessIntersections(const long64 botY, const long64 topY) |
| { |
| if( !m_ActiveEdges ) return true; |
| try { |
| BuildIntersectList(botY, topY); |
| if ( !m_IntersectNodes) return true; |
| if ( FixupIntersections() ) ProcessIntersectList(); |
| else return false; |
| } |
| catch(...) { |
| m_SortedEdges = 0; |
| DisposeIntersectNodes(); |
| throw clipperException("ProcessIntersections error"); |
| } |
| return true; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DisposeIntersectNodes() |
| { |
| while ( m_IntersectNodes ) |
| { |
| IntersectNode* iNode = m_IntersectNodes->next; |
| delete m_IntersectNodes; |
| m_IntersectNodes = iNode; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::BuildIntersectList(const long64 botY, const long64 topY) |
| { |
| if ( !m_ActiveEdges ) return; |
| |
| //prepare for sorting ... |
| TEdge* e = m_ActiveEdges; |
| e->tmpX = TopX( *e, topY ); |
| m_SortedEdges = e; |
| m_SortedEdges->prevInSEL = 0; |
| e = e->nextInAEL; |
| while( e ) |
| { |
| e->prevInSEL = e->prevInAEL; |
| e->prevInSEL->nextInSEL = e; |
| e->nextInSEL = 0; |
| e->tmpX = TopX( *e, topY ); |
| e = e->nextInAEL; |
| } |
| |
| //bubblesort ... |
| bool isModified = true; |
| while( isModified && m_SortedEdges ) |
| { |
| isModified = false; |
| e = m_SortedEdges; |
| while( e->nextInSEL ) |
| { |
| TEdge *eNext = e->nextInSEL; |
| IntPoint pt; |
| if(e->tmpX > eNext->tmpX && |
| IntersectPoint(*e, *eNext, pt, m_UseFullRange)) |
| { |
| if (pt.Y > botY) |
| { |
| pt.Y = botY; |
| pt.X = TopX(*e, pt.Y); |
| } |
| AddIntersectNode( e, eNext, pt ); |
| SwapPositionsInSEL(e, eNext); |
| isModified = true; |
| } |
| else |
| e = eNext; |
| } |
| if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0; |
| else break; |
| } |
| m_SortedEdges = 0; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool ProcessParam1BeforeParam2(IntersectNode &node1, IntersectNode &node2) |
| { |
| bool result; |
| if (node1.pt.Y == node2.pt.Y) |
| { |
| if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1) |
| { |
| result = node2.pt.X > node1.pt.X; |
| return node2.edge1->dx > 0 ? !result : result; |
| } |
| else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2) |
| { |
| result = node2.pt.X > node1.pt.X; |
| return node2.edge2->dx > 0 ? !result : result; |
| } |
| else return node2.pt.X > node1.pt.X; |
| } |
| else return node1.pt.Y > node2.pt.Y; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt) |
| { |
| IntersectNode* newNode = new IntersectNode; |
| newNode->edge1 = e1; |
| newNode->edge2 = e2; |
| newNode->pt = pt; |
| newNode->next = 0; |
| if( !m_IntersectNodes ) m_IntersectNodes = newNode; |
| else if( ProcessParam1BeforeParam2(*newNode, *m_IntersectNodes) ) |
| { |
| newNode->next = m_IntersectNodes; |
| m_IntersectNodes = newNode; |
| } |
| else |
| { |
| IntersectNode* iNode = m_IntersectNodes; |
| while( iNode->next && ProcessParam1BeforeParam2(*iNode->next, *newNode) ) |
| iNode = iNode->next; |
| newNode->next = iNode->next; |
| iNode->next = newNode; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ProcessIntersectList() |
| { |
| while( m_IntersectNodes ) |
| { |
| IntersectNode* iNode = m_IntersectNodes->next; |
| { |
| IntersectEdges( m_IntersectNodes->edge1 , |
| m_IntersectNodes->edge2 , m_IntersectNodes->pt, ipBoth ); |
| SwapPositionsInAEL( m_IntersectNodes->edge1 , m_IntersectNodes->edge2 ); |
| } |
| delete m_IntersectNodes; |
| m_IntersectNodes = iNode; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::DoMaxima(TEdge *e, long64 topY) |
| { |
| TEdge* eMaxPair = GetMaximaPair(e); |
| long64 X = e->xtop; |
| TEdge* eNext = e->nextInAEL; |
| while( eNext != eMaxPair ) |
| { |
| if (!eNext) throw clipperException("DoMaxima error"); |
| IntersectEdges( e, eNext, IntPoint(X, topY), ipBoth ); |
| eNext = eNext->nextInAEL; |
| } |
| if( e->outIdx < 0 && eMaxPair->outIdx < 0 ) |
| { |
| DeleteFromAEL( e ); |
| DeleteFromAEL( eMaxPair ); |
| } |
| else if( e->outIdx >= 0 && eMaxPair->outIdx >= 0 ) |
| { |
| IntersectEdges( e, eMaxPair, IntPoint(X, topY), ipNone ); |
| } |
| else throw clipperException("DoMaxima error"); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::ProcessEdgesAtTopOfScanbeam(const long64 topY) |
| { |
| TEdge* e = m_ActiveEdges; |
| while( e ) |
| { |
| //1. process maxima, treating them as if they're 'bent' horizontal edges, |
| // but exclude maxima with horizontal edges. nb: e can't be a horizontal. |
| if( IsMaxima(e, topY) && !NEAR_EQUAL(GetMaximaPair(e)->dx, HORIZONTAL) ) |
| { |
| //'e' might be removed from AEL, as may any following edges so ... |
| TEdge* ePrior = e->prevInAEL; |
| DoMaxima(e, topY); |
| if( !ePrior ) e = m_ActiveEdges; |
| else e = ePrior->nextInAEL; |
| } |
| else |
| { |
| //2. promote horizontal edges, otherwise update xcurr and ycurr ... |
| if( IsIntermediate(e, topY) && NEAR_EQUAL(e->nextInLML->dx, HORIZONTAL) ) |
| { |
| if (e->outIdx >= 0) |
| { |
| AddOutPt(e, IntPoint(e->xtop, e->ytop)); |
| |
| for (HorzJoinList::size_type i = 0; i < m_HorizJoins.size(); ++i) |
| { |
| IntPoint pt, pt2; |
| HorzJoinRec* hj = m_HorizJoins[i]; |
| if (GetOverlapSegment(IntPoint(hj->edge->xbot, hj->edge->ybot), |
| IntPoint(hj->edge->xtop, hj->edge->ytop), |
| IntPoint(e->nextInLML->xbot, e->nextInLML->ybot), |
| IntPoint(e->nextInLML->xtop, e->nextInLML->ytop), pt, pt2)) |
| AddJoin(hj->edge, e->nextInLML, hj->savedIdx, e->outIdx); |
| } |
| |
| AddHorzJoin(e->nextInLML, e->outIdx); |
| } |
| UpdateEdgeIntoAEL(e); |
| AddEdgeToSEL(e); |
| } else |
| { |
| //this just simplifies horizontal processing ... |
| e->xcurr = TopX( *e, topY ); |
| e->ycurr = topY; |
| } |
| e = e->nextInAEL; |
| } |
| } |
| |
| //3. Process horizontals at the top of the scanbeam ... |
| ProcessHorizontals(); |
| |
| //4. Promote intermediate vertices ... |
| e = m_ActiveEdges; |
| while( e ) |
| { |
| if( IsIntermediate( e, topY ) ) |
| { |
| if( e->outIdx >= 0 ) AddOutPt(e, IntPoint(e->xtop,e->ytop)); |
| UpdateEdgeIntoAEL(e); |
| |
| //if output polygons share an edge, they'll need joining later ... |
| if (e->outIdx >= 0 && e->prevInAEL && e->prevInAEL->outIdx >= 0 && |
| e->prevInAEL->xcurr == e->xbot && e->prevInAEL->ycurr == e->ybot && |
| SlopesEqual(IntPoint(e->xbot,e->ybot), IntPoint(e->xtop, e->ytop), |
| IntPoint(e->xbot,e->ybot), |
| IntPoint(e->prevInAEL->xtop, e->prevInAEL->ytop), m_UseFullRange)) |
| { |
| AddOutPt(e->prevInAEL, IntPoint(e->xbot, e->ybot)); |
| AddJoin(e, e->prevInAEL); |
| } |
| else if (e->outIdx >= 0 && e->nextInAEL && e->nextInAEL->outIdx >= 0 && |
| e->nextInAEL->ycurr > e->nextInAEL->ytop && |
| e->nextInAEL->ycurr <= e->nextInAEL->ybot && |
| 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)); |
| AddJoin(e, e->nextInAEL); |
| } |
| } |
| e = e->nextInAEL; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::FixupOutPolygon(OutRec &outRec) |
| { |
| //FixupOutPolygon() - removes duplicate points and simplifies consecutive |
| //parallel edges by removing the middle vertex. |
| OutPt *lastOK = 0; |
| outRec.pts = outRec.bottomPt; |
| OutPt *pp = outRec.bottomPt; |
| |
| for (;;) |
| { |
| if (pp->prev == pp || pp->prev == pp->next ) |
| { |
| DisposeOutPts(pp); |
| outRec.pts = 0; |
| outRec.bottomPt = 0; |
| return; |
| } |
| //test for duplicate points and for same slope (cross-product) ... |
| if ( PointsEqual(pp->pt, pp->next->pt) || |
| SlopesEqual(pp->prev->pt, pp->pt, pp->next->pt, m_UseFullRange) ) |
| { |
| lastOK = 0; |
| OutPt *tmp = pp; |
| if (pp == outRec.bottomPt) |
| outRec.bottomPt = 0; //flags need for updating |
| pp->prev->next = pp->next; |
| pp->next->prev = pp->prev; |
| pp = pp->prev; |
| delete tmp; |
| } |
| else if (pp == lastOK) break; |
| else |
| { |
| if (!lastOK) lastOK = pp; |
| pp = pp->next; |
| } |
| } |
| if (!outRec.bottomPt) { |
| outRec.bottomPt = GetBottomPt(pp); |
| outRec.bottomPt->idx = outRec.idx; |
| outRec.pts = outRec.bottomPt; |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::BuildResult(Polygons &polys) |
| { |
| int k = 0; |
| polys.resize(m_PolyOuts.size()); |
| for (PolyOutList::size_type i = 0; i < m_PolyOuts.size(); ++i) |
| { |
| if (m_PolyOuts[i]->pts) |
| { |
| Polygon* pg = &polys[k]; |
| pg->clear(); |
| OutPt* p = m_PolyOuts[i]->pts; |
| do |
| { |
| pg->push_back(p->pt); |
| p = p->next; |
| } while (p != m_PolyOuts[i]->pts); |
| //make sure each polygon has at least 3 vertices ... |
| if (pg->size() < 3) pg->clear(); else k++; |
| } |
| } |
| polys.resize(k); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::BuildResultEx(ExPolygons &polys) |
| { |
| PolyOutList::size_type i = 0; |
| int k = 0; |
| polys.resize(0); |
| polys.reserve(m_PolyOuts.size()); |
| while (i < m_PolyOuts.size() && m_PolyOuts[i]->pts) |
| { |
| ExPolygon epg; |
| OutPt* p = m_PolyOuts[i]->pts; |
| do { |
| epg.outer.push_back(p->pt); |
| p = p->next; |
| } while (p != m_PolyOuts[i]->pts); |
| i++; |
| //make sure polygons have at least 3 vertices ... |
| if (epg.outer.size() < 3) continue; |
| while (i < m_PolyOuts.size() |
| && m_PolyOuts[i]->pts && m_PolyOuts[i]->isHole) |
| { |
| Polygon pg; |
| p = m_PolyOuts[i]->pts; |
| do { |
| pg.push_back(p->pt); |
| p = p->next; |
| } while (p != m_PolyOuts[i]->pts); |
| epg.holes.push_back(pg); |
| i++; |
| } |
| polys.push_back(epg); |
| k++; |
| } |
| polys.resize(k); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SwapIntersectNodes(IntersectNode &int1, IntersectNode &int2) |
| { |
| TEdge *e1 = int1.edge1; |
| TEdge *e2 = int1.edge2; |
| IntPoint p = int1.pt; |
| |
| int1.edge1 = int2.edge1; |
| int1.edge2 = int2.edge2; |
| int1.pt = int2.pt; |
| |
| int2.edge1 = e1; |
| int2.edge2 = e2; |
| int2.pt = p; |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool Clipper::FixupIntersections() |
| { |
| if ( !m_IntersectNodes->next ) return true; |
| |
| CopyAELToSEL(); |
| IntersectNode *int1 = m_IntersectNodes; |
| IntersectNode *int2 = m_IntersectNodes->next; |
| while (int2) |
| { |
| TEdge *e1 = int1->edge1; |
| TEdge *e2; |
| if (e1->prevInSEL == int1->edge2) e2 = e1->prevInSEL; |
| else if (e1->nextInSEL == int1->edge2) e2 = e1->nextInSEL; |
| else |
| { |
| //The current intersection is out of order, so try and swap it with |
| //a subsequent intersection ... |
| while (int2) |
| { |
| if (int2->edge1->nextInSEL == int2->edge2 || |
| int2->edge1->prevInSEL == int2->edge2) break; |
| else int2 = int2->next; |
| } |
| if ( !int2 ) return false; //oops!!! |
| |
| //found an intersect node that can be swapped ... |
| SwapIntersectNodes(*int1, *int2); |
| e1 = int1->edge1; |
| e2 = int1->edge2; |
| } |
| SwapPositionsInSEL(e1, e2); |
| int1 = int1->next; |
| int2 = int1->next; |
| } |
| |
| m_SortedEdges = 0; |
| |
| //finally, check the last intersection too ... |
| return (int1->edge1->prevInSEL == int1->edge2 || |
| int1->edge1->nextInSEL == int1->edge2); |
| } |
| //------------------------------------------------------------------------------ |
| |
| bool E2InsertsBeforeE1(TEdge &e1, TEdge &e2) |
| { |
| return e2.xcurr == e1.xcurr ? e2.dx > e1.dx : e2.xcurr < e1.xcurr; |
| } |
| //------------------------------------------------------------------------------ |
| |
| void Clipper::InsertEdgeIntoAEL(TEdge *edge) |
| { |
| edge->prevInAEL = 0; |
| edge->nextInAEL = 0; |
| if( !m_ActiveEdges ) |
| { |
| m_ActiveEdges = edge; |
| } |
| else if( E2InsertsBeforeE1(*m_ActiveEdges, *edge) ) |
| { |
| edge->nextInAEL = m_ActiveEdges; |
| m_ActiveEdges->prevInAEL = edge; |
| m_ActiveEdges = edge; |
| } else |
| { |
| TEdge* e = m_ActiveEdges; |
| while( e->nextInAEL && !E2InsertsBeforeE1(*e->nextInAEL , *edge) ) |
| e = e->nextInAEL; |
| edge->nextInAEL = e->nextInAEL; |
| if( e->nextInAEL ) e->nextInAEL->prevInAEL = edge; |
| edge->prevInAEL = e; |
| e->nextInAEL = edge; |
| } |
| } |
| //---------------------------------------------------------------------- |
| |
| void Clipper::DoEdge1(TEdge *edge1, TEdge *edge2, const IntPoint &pt) |
| { |
| AddOutPt(edge1, pt); |
| SwapSides(*edge1, *edge2); |
| SwapPolyIndexes(*edge1, *edge2); |
| } |
| //---------------------------------------------------------------------- |
| |
| void Clipper::DoEdge2(TEdge *edge1, TEdge *edge2, const IntPoint &pt) |
| { |
| AddOutPt(edge2, pt); |
| SwapSides(*edge1, *edge2); |
| SwapPolyIndexes(*edge1, *edge2); |
| } |
| //---------------------------------------------------------------------- |
| |
| void Clipper::DoBothEdges(TEdge *edge1, TEdge *edge2, const IntPoint &pt) |
| { |
| AddOutPt(edge1, pt); |
| AddOutPt(edge2, pt); |
| SwapSides( *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 original |
| //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) |
| { |
| for (JoinList::size_type i = 0; i < m_Joins.size(); i++) |
| { |
| JoinRec* j = m_Joins[i]; |
| OutRec *outRec1 = m_PolyOuts[j->poly1Idx]; |
| OutPt *pp1a = outRec1->pts; |
| OutRec *outRec2 = m_PolyOuts[j->poly2Idx]; |
| OutPt *pp2a = outRec2->pts; |
| IntPoint pt1 = j->pt2a, pt2 = j->pt2b; |
| IntPoint pt3 = j->pt1a, pt4 = j->pt1b; |
| if (!FindSegment(pp1a, pt1, pt2)) continue; |
| if (j->poly1Idx == j->poly2Idx) |
| { |
| //we're searching the same polygon for overlapping segments so |
| //segment 2 mustn't be the same as segment 1 ... |
| pp2a = pp1a->next; |
| if (!FindSegment(pp2a, pt3, pt4) || (pp2a == pp1a)) continue; |
| } |
| else if (!FindSegment(pp2a, pt3, pt4)) continue; |
| |
| if (!GetOverlapSegment(pt1, pt2, pt3, pt4, pt1, pt2)) continue; |
| |
| OutPt *p1, *p2, *p3, *p4; |
| OutPt *prev = pp1a->prev; |
| //get p1 & p2 polypts - the overlap start & endpoints on poly1 |
| if (PointsEqual(pp1a->pt, pt1)) p1 = pp1a; |
| else if (PointsEqual(prev->pt, pt1)) p1 = prev; |
| else p1 = InsertPolyPtBetween(pp1a, prev, pt1); |
| |
| if (PointsEqual(pp1a->pt, pt2)) p2 = pp1a; |
| else if (PointsEqual(prev->pt, pt2)) p2 = prev; |
| else if ((p1 == pp1a) || (p1 == prev)) |
| p2 = InsertPolyPtBetween(pp1a, prev, pt2); |
| else if (Pt3IsBetweenPt1AndPt2(pp1a->pt, p1->pt, pt2)) |
| p2 = InsertPolyPtBetween(pp1a, p1, pt2); else |
| p2 = InsertPolyPtBetween(p1, prev, pt2); |
| |
| //get p3 & p4 polypts - the overlap start & endpoints on poly2 |
| prev = pp2a->prev; |
| if (PointsEqual(pp2a->pt, pt1)) p3 = pp2a; |
| else if (PointsEqual(prev->pt, pt1)) p3 = prev; |
| else p3 = InsertPolyPtBetween(pp2a, prev, pt1); |
| |
| if (PointsEqual(pp2a->pt, pt2)) p4 = pp2a; |
| else if (PointsEqual(prev->pt, pt2)) p4 = prev; |
| else if ((p3 == pp2a) || (p3 == prev)) |
| p4 = InsertPolyPtBetween(pp2a, prev, pt2); |
| else if (Pt3IsBetweenPt1AndPt2(pp2a->pt, p3->pt, pt2)) |
| p4 = InsertPolyPtBetween(pp2a, p3, pt2); else |
| p4 = InsertPolyPtBetween(p3, prev, pt2); |
| |
| //p1.pt == p3.pt and p2.pt == p4.pt so join p1 to p3 and p2 to p4 ... |
| if (p1->next == p2 && p3->prev == p4) |
| { |
| p1->next = p3; |
| p3->prev = p1; |
| p2->prev = p4; |
| p4->next = p2; |
| } |
| else if (p1->prev == p2 && p3->next == p4) |
| { |
| p1->prev = p3; |
| p3->next = p1; |
| p2->next = p4; |
| p4->prev = p2; |
| } |
| else |
| continue; //an orientation is probably wrong |
| |
| if (j->poly2Idx == j->poly1Idx) |
| { |
| //instead of joining two polygons, we've just created a new one by |
| //splitting one polygon into two. |
| outRec1->pts = GetBottomPt(p1); |
| outRec1->bottomPt = outRec1->pts; |
| outRec1->bottomPt->idx = outRec1->idx; |
| outRec2 = CreateOutRec(); |
| m_PolyOuts.push_back(outRec2); |
| outRec2->idx = (int)m_PolyOuts.size()-1; |
| j->poly2Idx = outRec2->idx; |
| outRec2->pts = GetBottomPt(p2); |
| outRec2->bottomPt = outRec2->pts; |
| outRec2->bottomPt->idx = outRec2->idx; |
| |
| if (PointInPolygon(outRec2->pts->pt, outRec1->pts, m_UseFullRange)) |
| { |
| //outRec2 is contained by outRec1 ... |
| outRec2->isHole = !outRec1->isHole; |
| outRec2->FirstLeft = outRec1; |
| if (outRec2->isHole == |
| (m_ReverseOutput ^ Orientation(outRec2, m_UseFullRange))) |
| ReversePolyPtLinks(*outRec2->pts); |
| } else if (PointInPolygon(outRec1->pts->pt, outRec2->pts, m_UseFullRange)) |
| { |
| //outRec1 is contained by outRec2 ... |
| outRec2->isHole = outRec1->isHole; |
| outRec1->isHole = !outRec2->isHole; |
| outRec2->FirstLeft = outRec1->FirstLeft; |
| 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 |
| { |
| outRec2->isHole = outRec1->isHole; |
| 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 |
| for (JoinList::size_type k = i+1; k < m_Joins.size(); k++) |
| { |
| JoinRec* j2 = m_Joins[k]; |
| if (j2->poly1Idx == j->poly1Idx && PointIsVertex(j2->pt1a, p2)) |
| j2->poly1Idx = j->poly2Idx; |
| if (j2->poly2Idx == j->poly1Idx && PointIsVertex(j2->pt2a, p2)) |
| j2->poly2Idx = j->poly2Idx; |
| } |
| |
| //now cleanup redundant edges too ... |
| FixupOutPolygon(*outRec1); |
| FixupOutPolygon(*outRec2); |
| |
| if (Orientation(outRec1, m_UseFullRange) != (Area(*outRec1, m_UseFullRange) > 0)) |
| DisposeBottomPt(*outRec1); |
| if (Orientation(outRec2, m_UseFullRange) != (Area(*outRec2, m_UseFullRange) > 0)) |
| DisposeBottomPt(*outRec2); |
| |
| } else |
| { |
| //joined 2 polygons together ... |
| |
| //make sure any holes contained by outRec2 now link to outRec1 ... |
| if (fixHoleLinkages) CheckHoleLinkages2(outRec1, outRec2); |
| |
| //now cleanup redundant edges too ... |
| FixupOutPolygon(*outRec1); |
| |
| if (outRec1->pts) |
| { |
| outRec1->isHole = !Orientation(outRec1, m_UseFullRange); |
| if (outRec1->isHole && !outRec1->FirstLeft) |
| outRec1->FirstLeft = outRec2->FirstLeft; |
| } |
| |
| //delete the obsolete pointer ... |
| int OKIdx = outRec1->idx; |
| int ObsoleteIdx = outRec2->idx; |
| outRec2->pts = 0; |
| outRec2->bottomPt = 0; |
| outRec2->AppendLink = outRec1; |
| |
| //now fixup any subsequent Joins that match this polygon |
| for (JoinList::size_type k = i+1; k < m_Joins.size(); k++) |
| { |
| JoinRec* j2 = m_Joins[k]; |
| if (j2->poly1Idx == ObsoleteIdx) j2->poly1Idx = OKIdx; |
| if (j2->poly2Idx == ObsoleteIdx) j2->poly2Idx = OKIdx; |
| } |
| } |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ReversePolygon(Polygon& p) |
| { |
| std::reverse(p.begin(), p.end()); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void ReversePolygons(Polygons& p) |
| { |
| for (Polygons::size_type i = 0; i < p.size(); ++i) |
| ReversePolygon(p[i]); |
| } |
| |
| //------------------------------------------------------------------------------ |
| // OffsetPolygon functions ... |
| //------------------------------------------------------------------------------ |
| |
| struct DoublePoint |
| { |
| double X; |
| double Y; |
| DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {} |
| }; |
| //------------------------------------------------------------------------------ |
| |
| Polygon BuildArc(const IntPoint &pt, |
| const double a1, const double a2, const double r) |
| { |
| long64 steps = std::max(6, int(std::sqrt(std::fabs(r)) * std::fabs(a2 - a1))); |
| if (steps > 0x100000) steps = 0x100000; |
| int n = (unsigned)steps; |
| Polygon result(n); |
| double da = (a2 - a1) / (n -1); |
| double a = a1; |
| for (int i = 0; i < n; ++i) |
| { |
| result[i].X = pt.X + Round(std::cos(a)*r); |
| result[i].Y = pt.Y + Round(std::sin(a)*r); |
| a += da; |
| } |
| return result; |
| } |
| //------------------------------------------------------------------------------ |
| |
| DoublePoint GetUnitNormal( const IntPoint &pt1, const IntPoint &pt2) |
| { |
| if(pt2.X == pt1.X && pt2.Y == pt1.Y) |
| return DoublePoint(0, 0); |
| |
| double dx = (double)(pt2.X - pt1.X); |
| double dy = (double)(pt2.Y - pt1.Y); |
| double f = 1 *1.0/ std::sqrt( dx*dx + dy*dy ); |
| dx *= f; |
| dy *= f; |
| return DoublePoint(dy, -dx); |
| } |
| |
| //------------------------------------------------------------------------------ |
| //------------------------------------------------------------------------------ |
| |
| class PolyOffsetBuilder |
| { |
| private: |
| Polygons m_p; |
| Polygon* m_curr_poly; |
| std::vector<DoublePoint> normals; |
| double m_delta, m_RMin, m_R; |
| size_t m_i, m_j, m_k; |
| static const int buffLength = 128; |
| JoinType m_jointype; |
| |
| public: |
| |
| PolyOffsetBuilder(const Polygons& in_polys, Polygons& out_polys, |
| double delta, JoinType jointype, double MiterLimit) |
| { |
| //nb precondition - out_polys != ptsin_polys |
| if (NEAR_ZERO(delta)) |
| { |
| out_polys = in_polys; |
| return; |
| } |
| |
| this->m_p = in_polys; |
| this->m_delta = delta; |
| this->m_jointype = jointype; |
| if (MiterLimit <= 1) MiterLimit = 1; |
| m_RMin = 2/(MiterLimit*MiterLimit); |
| |
| double deltaSq = delta*delta; |
| out_polys.clear(); |
| out_polys.resize(in_polys.size()); |
| for (m_i = 0; m_i < in_polys.size(); m_i++) |
| { |
| m_curr_poly = &out_polys[m_i]; |
| size_t len = in_polys[m_i].size(); |
| if (len > 1 && m_p[m_i][0].X == m_p[m_i][len - 1].X && |
| m_p[m_i][0].Y == m_p[m_i][len-1].Y) len--; |
| |
| //when 'shrinking' polygons - to minimize artefacts |
| //strip those polygons that have an area < pi * delta^2 ... |
| double a1 = Area(in_polys[m_i]); |
| if (delta < 0) { if (a1 > 0 && a1 < deltaSq *pi) len = 0; } |
| else if (a1 < 0 && -a1 < deltaSq *pi) len = 0; //holes have neg. area |
| |
| if (len == 0 || (len < 3 && delta <= 0)) |
| continue; |
| else if (len == 1) |
| { |
| Polygon arc; |
| arc = BuildArc(in_polys[m_i][len-1], 0, 2 * pi, delta); |
| out_polys[m_i] = arc; |
| continue; |
| } |
| |
| //build normals ... |
| normals.clear(); |
| normals.resize(len); |
| normals[len-1] = GetUnitNormal(in_polys[m_i][len-1], in_polys[m_i][0]); |
| for (m_j = 0; m_j < len -1; ++m_j) |
| normals[m_j] = GetUnitNormal(in_polys[m_i][m_j], in_polys[m_i][m_j+1]); |
| |
| m_k = len -1; |
| for (m_j = 0; m_j < len; ++m_j) |
| { |
| switch (jointype) |
| { |
| case jtMiter: |
| { |
| m_R = 1 + (normals[m_j].X*normals[m_k].X + |
| normals[m_j].Y*normals[m_k].Y); |
| if (m_R >= m_RMin) DoMiter(); else DoSquare(MiterLimit); |
| break; |
| } |
| case jtSquare: DoSquare(); break; |
| case jtRound: DoRound(); break; |
| } |
| m_k = m_j; |
| } |
| } |
| |
| //finally, clean up untidy corners using Clipper ... |
| Clipper clpr; |
| clpr.AddPolygons(out_polys, ptSubject); |
| if (delta > 0) |
| { |
| if (!clpr.Execute(ctUnion, out_polys, pftPositive, pftPositive)) |
| out_polys.clear(); |
| } |
| else |
| { |
| IntRect r = clpr.GetBounds(); |
| Polygon outer(4); |
| outer[0] = IntPoint(r.left - 10, r.bottom + 10); |
| outer[1] = IntPoint(r.right + 10, r.bottom + 10); |
| outer[2] = IntPoint(r.right + 10, r.top - 10); |
| outer[3] = IntPoint(r.left - 10, r.top - 10); |
| |
| clpr.AddPolygon(outer, ptSubject); |
| if (clpr.Execute(ctUnion, out_polys, pftNegative, pftNegative)) |
| { |
| out_polys.erase(out_polys.begin()); |
| ReversePolygons(out_polys); |
| |
| } else |
| out_polys.clear(); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| private: |
| |
| void AddPoint(const IntPoint& pt) |
| { |
| Polygon::size_type len = m_curr_poly->size(); |
| if (len == m_curr_poly->capacity()) |
| m_curr_poly->reserve(len + buffLength); |
| m_curr_poly->push_back(pt); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void DoSquare(double mul = 1.0) |
| { |
| IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta), |
| (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta)); |
| IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta), |
| (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta)); |
| if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0) |
| { |
| double a1 = std::atan2(normals[m_k].Y, normals[m_k].X); |
| double a2 = std::atan2(-normals[m_j].Y, -normals[m_j].X); |
| a1 = std::fabs(a2 - a1); |
| if (a1 > pi) a1 = pi * 2 - a1; |
| double dx = std::tan((pi - a1)/4) * std::fabs(m_delta * mul); |
| pt1 = IntPoint((long64)(pt1.X -normals[m_k].Y * dx), |
| (long64)(pt1.Y + normals[m_k].X * dx)); |
| AddPoint(pt1); |
| pt2 = IntPoint((long64)(pt2.X + normals[m_j].Y * dx), |
| (long64)(pt2.Y -normals[m_j].X * dx)); |
| AddPoint(pt2); |
| } |
| else |
| { |
| AddPoint(pt1); |
| AddPoint(m_p[m_i][m_j]); |
| AddPoint(pt2); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void DoMiter() |
| { |
| if ((normals[m_k].X * normals[m_j].Y - normals[m_j].X * normals[m_k].Y) * m_delta >= 0) |
| { |
| double q = m_delta / m_R; |
| AddPoint(IntPoint((long64)Round(m_p[m_i][m_j].X + |
| (normals[m_k].X + normals[m_j].X) * q), |
| (long64)Round(m_p[m_i][m_j].Y + (normals[m_k].Y + normals[m_j].Y) * q))); |
| } |
| else |
| { |
| IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * |
| m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta)); |
| IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * |
| m_delta), (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta)); |
| AddPoint(pt1); |
| AddPoint(m_p[m_i][m_j]); |
| AddPoint(pt2); |
| } |
| } |
| //------------------------------------------------------------------------------ |
| |
| void DoRound() |
| { |
| IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta), |
| (long64)Round(m_p[m_i][m_j].Y + normals[m_k].Y * m_delta)); |
| IntPoint pt2 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_j].X * m_delta), |
| (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta)); |
| AddPoint(pt1); |
| //round off reflex angles (ie > 180 deg) unless almost flat (ie < ~10deg). |
| if ((normals[m_k].X*normals[m_j].Y - normals[m_j].X*normals[m_k].Y) * m_delta >= 0) |
| { |
| if (normals[m_j].X * normals[m_k].X + normals[m_j].Y * normals[m_k].Y < 0.985) |
| { |
| double a1 = std::atan2(normals[m_k].Y, normals[m_k].X); |
| double a2 = std::atan2(normals[m_j].Y, normals[m_j].X); |
| if (m_delta > 0 && a2 < a1) a2 += pi *2; |
| else if (m_delta < 0 && a2 > a1) a2 -= pi *2; |
| Polygon arc = BuildArc(m_p[m_i][m_j], a1, a2, m_delta); |
| for (Polygon::size_type m = 0; m < arc.size(); m++) |
| AddPoint(arc[m]); |
| } |
| } |
| else |
| AddPoint(m_p[m_i][m_j]); |
| AddPoint(pt2); |
| } |
| //-------------------------------------------------------------------------- |
| |
| }; //end PolyOffsetBuilder |
| |
| //------------------------------------------------------------------------------ |
| //------------------------------------------------------------------------------ |
| |
| void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, |
| double delta, JoinType jointype, double MiterLimit) |
| { |
| if (&out_polys == &in_polys) |
| { |
| Polygons poly2(in_polys); |
| PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit); |
| } |
| else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType) |
| { |
| Clipper c; |
| c.AddPolygon(in_poly, ptSubject); |
| c.Execute(ctUnion, out_polys, fillType, fillType); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType) |
| { |
| Clipper c; |
| c.AddPolygons(in_polys, ptSubject); |
| c.Execute(ctUnion, out_polys, fillType, fillType); |
| } |
| //------------------------------------------------------------------------------ |
| |
| void SimplifyPolygons(Polygons &polys, PolyFillType fillType) |
| { |
| SimplifyPolygons(polys, polys, fillType); |
| } |
| //------------------------------------------------------------------------------ |
| |
| std::ostream& operator <<(std::ostream &s, IntPoint& p) |
| { |
| s << p.X << ' ' << p.Y << "\n"; |
| return s; |
| } |
| //------------------------------------------------------------------------------ |
| |
| std::ostream& operator <<(std::ostream &s, Polygon &p) |
| { |
| for (Polygon::size_type i = 0; i < p.size(); i++) |
| s << p[i]; |
| s << "\n"; |
| return s; |
| } |
| //------------------------------------------------------------------------------ |
| |
| std::ostream& operator <<(std::ostream &s, Polygons &p) |
| { |
| for (Polygons::size_type i = 0; i < p.size(); i++) |
| s << p[i]; |
| s << "\n"; |
| return s; |
| } |
| //------------------------------------------------------------------------------ |
| |
| } //ClipperLib namespace |