| clipper.cpp | clipper.cpp | |||
|---|---|---|---|---|
| /************************************************************************** ***** | /************************************************************************** ***** | |||
| * * | * * | |||
| * Author : Angus Johnson * | * Author : Angus Johnson * | |||
| * Version : 4.8.5 | * Version : 4.8.6 | |||
| * | * | |||
| * Date : 15 July 2012 | * Date : 11 August 2012 | |||
| * | * | |||
| * Website : http://www.angusj.com * | * Website : http://www.angusj.com * | |||
| * Copyright : Angus Johnson 2010-2012 * | * Copyright : Angus Johnson 2010-2012 * | |||
| * * | * * | |||
| * License: * | * License: * | |||
| * Use, modification & distribution is subject to Boost Software License Ver 1. * | * Use, modification & distribution is subject to Boost Software License Ver 1. * | |||
| * http://www.boost.org/LICENSE_1_0.txt * | * http://www.boost.org/LICENSE_1_0.txt * | |||
| * * | * * | |||
| * Attributions: * | * Attributions: * | |||
| * The code in this library is an extension of Bala Vatti's clipping algorit hm: * | * The code in this library is an extension of Bala Vatti's clipping algorit hm: * | |||
| * "A generic solution to polygon clipping" * | * "A generic solution to polygon clipping" * | |||
| skipping to change at line 52 | skipping to change at line 52 | |||
| #include <cmath> | #include <cmath> | |||
| #include <vector> | #include <vector> | |||
| #include <algorithm> | #include <algorithm> | |||
| #include <stdexcept> | #include <stdexcept> | |||
| #include <cstring> | #include <cstring> | |||
| #include <cstdlib> | #include <cstdlib> | |||
| #include <ostream> | #include <ostream> | |||
| namespace ClipperLib { | namespace ClipperLib { | |||
| static long64 const loRange = 1518500249; //sqrt(2^63 -1)/2 | static long64 const loRange = 0x3FFFFFFF; | |||
| static long64 const hiRange = 6521908912666391106LL; //sqrt(2^127 -1)/2 | static long64 const hiRange = 0x3FFFFFFFFFFFFFFFLL; | |||
| static double const pi = 3.141592653589793238; | static double const pi = 3.141592653589793238; | |||
| enum Direction { dRightToLeft, dLeftToRight }; | enum Direction { dRightToLeft, dLeftToRight }; | |||
| #define HORIZONTAL (-1.0E+40) | #define HORIZONTAL (-1.0E+40) | |||
| #define TOLERANCE (1.0e-20) | #define TOLERANCE (1.0e-20) | |||
| #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE)) | #define NEAR_ZERO(val) (((val) > -TOLERANCE) && ((val) < TOLERANCE)) | |||
| #define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b)) | #define NEAR_EQUAL(a, b) NEAR_ZERO((a) - (b)) | |||
| inline long64 Abs(long64 val) | inline long64 Abs(long64 val) | |||
| { | { | |||
| skipping to change at line 117 | skipping to change at line 117 | |||
| } | } | |||
| bool operator < (const Int128 &val) const | bool operator < (const Int128 &val) const | |||
| { | { | |||
| if (hi != val.hi) | if (hi != val.hi) | |||
| return hi < val.hi; | return hi < val.hi; | |||
| else | else | |||
| return lo < val.lo; | return 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) | Int128& operator += (const Int128 &rhs) | |||
| { | { | |||
| hi += rhs.hi; | hi += rhs.hi; | |||
| lo += rhs.lo; | lo += rhs.lo; | |||
| if (ulong64(lo) < ulong64(rhs.lo)) hi++; | if (ulong64(lo) < ulong64(rhs.lo)) hi++; | |||
| return *this; | return *this; | |||
| } | } | |||
| Int128 operator + (const Int128 &rhs) const | Int128 operator + (const Int128 &rhs) const | |||
| { | { | |||
| skipping to change at line 352 | skipping to change at line 358 | |||
| vec2.Y = poly[jplus].Y - poly[j].Y; | vec2.Y = poly[jplus].Y - poly[j].Y; | |||
| if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange || | if (Abs(vec1.X) > loRange || Abs(vec1.Y) > loRange || | |||
| Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange) | Abs(vec2.X) > loRange || Abs(vec2.Y) > loRange) | |||
| { | { | |||
| if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange || | if (Abs(vec1.X) > hiRange || Abs(vec1.Y) > hiRange || | |||
| Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange) | Abs(vec2.X) > hiRange || Abs(vec2.Y) > hiRange) | |||
| throw "Coordinate exceeds range bounds."; | throw "Coordinate exceeds range bounds."; | |||
| Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - | Int128 cross = Int128(vec1.X) * Int128(vec2.Y) - | |||
| Int128(vec2.X) * Int128(vec1.Y); | Int128(vec2.X) * Int128(vec1.Y); | |||
| return cross > 0; | return cross >= 0; | |||
| } | } | |||
| else | else | |||
| return (vec1.X * vec2.Y - vec2.X * vec1.Y) > 0; | return (vec1.X * vec2.Y - vec2.X * vec1.Y) >= 0; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) | inline bool PointsEqual( const IntPoint &pt1, const IntPoint &pt2) | |||
| { | { | |||
| return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); | return ( pt1.X == pt2.X && pt1.Y == pt2.Y ); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| bool Orientation(OutRec *outRec, bool UseFullInt64Range) | bool Orientation(OutRec *outRec, bool UseFullInt64Range) | |||
| skipping to change at line 397 | skipping to change at line 403 | |||
| while (op != opNext && PointsEqual(op->pt, opNext->pt)) | while (op != opNext && PointsEqual(op->pt, opNext->pt)) | |||
| opNext = opNext->next; | opNext = opNext->next; | |||
| IntPoint ip1, ip2; | IntPoint ip1, ip2; | |||
| ip1.X = op->pt.X - opPrev->pt.X; | ip1.X = op->pt.X - opPrev->pt.X; | |||
| ip1.Y = op->pt.Y - opPrev->pt.Y; | ip1.Y = op->pt.Y - opPrev->pt.Y; | |||
| ip2.X = opNext->pt.X - op->pt.X; | ip2.X = opNext->pt.X - op->pt.X; | |||
| ip2.Y = opNext->pt.Y - op->pt.Y; | ip2.Y = opNext->pt.Y - op->pt.Y; | |||
| if (UseFullInt64Range) | if (UseFullInt64Range) | |||
| return Int128(ip1.X) * Int128(ip2.Y) - Int128(ip2.X) * Int128(ip1.Y) > 0; | return Int128(ip1.X) * Int128(ip2.Y) - Int128(ip2.X) * Int128(ip1.Y) >= 0; | |||
| else | else | |||
| return (ip1.X * ip2.Y - ip2.X * ip1.Y) > 0; | return (ip1.X * ip2.Y - ip2.X * ip1.Y) >= 0; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| double Area(const Polygon &poly) | double Area(const Polygon &poly) | |||
| { | { | |||
| int highI = (int)poly.size() -1; | int highI = (int)poly.size() -1; | |||
| if (highI < 2) return 0; | if (highI < 2) return 0; | |||
| if (FullRangeNeeded(poly)) { | if (FullRangeNeeded(poly)) { | |||
| Int128 a; | Int128 a; | |||
| skipping to change at line 1952 | skipping to change at line 1958 | |||
| else if (outPt1->pt.Y < outPt2->pt.Y) return outRec2; | 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 outRec1; | |||
| else if (outPt1->pt.X > outPt2->pt.X) return outRec2; | else if (outPt1->pt.X > outPt2->pt.X) return outRec2; | |||
| else if (outPt1->next == outPt1) return outRec2; | else if (outPt1->next == outPt1) return outRec2; | |||
| else if (outPt2->next == outPt2) return outRec1; | else if (outPt2->next == outPt2) return outRec1; | |||
| else if (FirstIsBottomPt(outPt1, outPt2)) return outRec1; | else if (FirstIsBottomPt(outPt1, outPt2)) return outRec1; | |||
| else return outRec2; | 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) | void Clipper::AppendPolygon(TEdge *e1, TEdge *e2) | |||
| { | { | |||
| //get the start and ends of both output polygons ... | //get the start and ends of both output polygons ... | |||
| OutRec *outRec1 = m_PolyOuts[e1->outIdx]; | OutRec *outRec1 = m_PolyOuts[e1->outIdx]; | |||
| OutRec *outRec2 = m_PolyOuts[e2->outIdx]; | OutRec *outRec2 = m_PolyOuts[e2->outIdx]; | |||
| OutRec *holeStateRec; | OutRec *holeStateRec; | |||
| if (outRec1->FirstLeft == outRec2) holeStateRec = outRec2; | if (Param1RightOfParam2(outRec1, outRec2)) holeStateRec = outRec2; | |||
| else if (outRec2->FirstLeft == outRec1) holeStateRec = outRec1; | else if (Param1RightOfParam2(outRec2, outRec1)) holeStateRec = outRec1; | |||
| else holeStateRec = GetLowermostRec(outRec1, outRec2); | else holeStateRec = GetLowermostRec(outRec1, outRec2); | |||
| OutPt* p1_lft = outRec1->pts; | OutPt* p1_lft = outRec1->pts; | |||
| OutPt* p1_rt = p1_lft->prev; | OutPt* p1_rt = p1_lft->prev; | |||
| OutPt* p2_lft = outRec2->pts; | OutPt* p2_lft = outRec2->pts; | |||
| OutPt* p2_rt = p2_lft->prev; | OutPt* p2_rt = p2_lft->prev; | |||
| EdgeSide side; | EdgeSide side; | |||
| //join e2 poly onto e1 poly and delete pointers to e2 ... | //join e2 poly onto e1 poly and delete pointers to e2 ... | |||
| if( e1->side == esLeft ) | if( e1->side == esLeft ) | |||
| skipping to change at line 2522 | skipping to change at line 2539 | |||
| else | else | |||
| e = eNext; | e = eNext; | |||
| } | } | |||
| if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0; | if( e->prevInSEL ) e->prevInSEL->nextInSEL = 0; | |||
| else break; | else break; | |||
| } | } | |||
| m_SortedEdges = 0; | m_SortedEdges = 0; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| bool Process1Before2(IntersectNode &node1, IntersectNode &node2) | bool ProcessParam1BeforeParam2(IntersectNode &node1, IntersectNode &node2) | |||
| { | { | |||
| bool result; | bool result; | |||
| if (node1.pt.Y == node2.pt.Y) | if (node1.pt.Y == node2.pt.Y) | |||
| { | { | |||
| if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1) | if (node1.edge1 == node2.edge1 || node1.edge2 == node2.edge1) | |||
| { | { | |||
| result = node2.pt.X > node1.pt.X; | result = node2.pt.X > node1.pt.X; | |||
| return node2.edge1->dx > 0 ? !result : result; | return node2.edge1->dx > 0 ? !result : result; | |||
| } | } | |||
| else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2) | else if (node1.edge1 == node2.edge2 || node1.edge2 == node2.edge2) | |||
| skipping to change at line 2551 | skipping to change at line 2568 | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt) | void Clipper::AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt) | |||
| { | { | |||
| IntersectNode* newNode = new IntersectNode; | IntersectNode* newNode = new IntersectNode; | |||
| newNode->edge1 = e1; | newNode->edge1 = e1; | |||
| newNode->edge2 = e2; | newNode->edge2 = e2; | |||
| newNode->pt = pt; | newNode->pt = pt; | |||
| newNode->next = 0; | newNode->next = 0; | |||
| if( !m_IntersectNodes ) m_IntersectNodes = newNode; | if( !m_IntersectNodes ) m_IntersectNodes = newNode; | |||
| else if( Process1Before2(*newNode, *m_IntersectNodes) ) | else if( ProcessParam1BeforeParam2(*newNode, *m_IntersectNodes) ) | |||
| { | { | |||
| newNode->next = m_IntersectNodes; | newNode->next = m_IntersectNodes; | |||
| m_IntersectNodes = newNode; | m_IntersectNodes = newNode; | |||
| } | } | |||
| else | else | |||
| { | { | |||
| IntersectNode* iNode = m_IntersectNodes; | IntersectNode* iNode = m_IntersectNodes; | |||
| while( iNode->next && Process1Before2(*iNode->next, *newNode) ) | while( iNode->next && ProcessParam1BeforeParam2(*iNode->next, *newNode ) ) | |||
| iNode = iNode->next; | iNode = iNode->next; | |||
| newNode->next = iNode->next; | newNode->next = iNode->next; | |||
| iNode->next = newNode; | iNode->next = newNode; | |||
| } | } | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void Clipper::ProcessIntersectList() | void Clipper::ProcessIntersectList() | |||
| { | { | |||
| while( m_IntersectNodes ) | while( m_IntersectNodes ) | |||
| skipping to change at line 3100 | skipping to change at line 3117 | |||
| { | { | |||
| JoinRec* j2 = m_Joins[k]; | JoinRec* j2 = m_Joins[k]; | |||
| if (j2->poly1Idx == ObsoleteIdx) j2->poly1Idx = OKIdx; | if (j2->poly1Idx == ObsoleteIdx) j2->poly1Idx = OKIdx; | |||
| if (j2->poly2Idx == ObsoleteIdx) j2->poly2Idx = OKIdx; | if (j2->poly2Idx == ObsoleteIdx) j2->poly2Idx = OKIdx; | |||
| } | } | |||
| } | } | |||
| } | } | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void ReversePoints(Polygon& p) | void ReversePolygons(Polygon& p) | |||
| { | { | |||
| std::reverse(p.begin(), p.end()); | std::reverse(p.begin(), p.end()); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void ReversePoints(Polygons& p) | void ReversePolygons(Polygons& p) | |||
| { | { | |||
| for (Polygons::size_type i = 0; i < p.size(); ++i) | for (Polygons::size_type i = 0; i < p.size(); ++i) | |||
| ReversePoints(p[i]); | ReversePolygons(p[i]); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| // OffsetPolygon functions ... | // OffsetPolygon functions ... | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| struct DoublePoint | struct DoublePoint | |||
| { | { | |||
| double X; | double X; | |||
| double Y; | double Y; | |||
| skipping to change at line 3261 | skipping to change at line 3278 | |||
| Polygon outer(4); | Polygon outer(4); | |||
| outer[0] = IntPoint(r.left - 10, r.bottom + 10); | outer[0] = IntPoint(r.left - 10, r.bottom + 10); | |||
| outer[1] = IntPoint(r.right + 10, r.bottom + 10); | outer[1] = IntPoint(r.right + 10, r.bottom + 10); | |||
| outer[2] = IntPoint(r.right + 10, r.top - 10); | outer[2] = IntPoint(r.right + 10, r.top - 10); | |||
| outer[3] = IntPoint(r.left - 10, r.top - 10); | outer[3] = IntPoint(r.left - 10, r.top - 10); | |||
| clpr.AddPolygon(outer, ptSubject); | clpr.AddPolygon(outer, ptSubject); | |||
| if (clpr.Execute(ctUnion, out_polys, pftNegative, pftNegative)) | if (clpr.Execute(ctUnion, out_polys, pftNegative, pftNegative)) | |||
| { | { | |||
| out_polys.erase(out_polys.begin()); | out_polys.erase(out_polys.begin()); | |||
| ReversePoints(out_polys); | ReversePolygons(out_polys); | |||
| } else | } else | |||
| out_polys.clear(); | out_polys.clear(); | |||
| } | } | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| private: | private: | |||
| void AddPoint(const IntPoint& pt) | void AddPoint(const IntPoint& pt) | |||
| skipping to change at line 3291 | skipping to change at line 3308 | |||
| { | { | |||
| IntPoint pt1 = IntPoint((long64)Round(m_p[m_i][m_j].X + normals[m_k].X * m_delta), | 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)); | (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), | 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)); | (long64)Round(m_p[m_i][m_j].Y + normals[m_j].Y * m_delta)); | |||
| double sinAngle = normals[m_k].X * normals[m_j].Y - normals[m_j].X * no rmals[m_k].Y; | double sinAngle = normals[m_k].X * normals[m_j].Y - normals[m_j].X * no rmals[m_k].Y; | |||
| if (sinAngle * m_delta >= 0) | if (sinAngle * m_delta >= 0) | |||
| { | { | |||
| //occasionally (due to floating point math) sinAngle can be > 1 so .. . | //occasionally (due to floating point math) sinAngle can be > 1 so .. . | |||
| if (sinAngle > 1) sinAngle = 1; else if (sinAngle < -1) sinAngle = -1 ; | if (sinAngle > 1) sinAngle = 1; else if (sinAngle < -1) sinAngle = -1 ; | |||
| double dx = tan((pi - asin(sinAngle))/4) * abs(m_delta*mul); | double dx = std::tan((pi - std::asin(sinAngle))/4) * std::abs(m_delta *mul); | |||
| pt1 = IntPoint((long64)(pt1.X -normals[m_k].Y * dx), | pt1 = IntPoint((long64)(pt1.X -normals[m_k].Y * dx), | |||
| (long64)(pt1.Y + normals[m_k].X * dx)); | (long64)(pt1.Y + normals[m_k].X * dx)); | |||
| AddPoint(pt1); | AddPoint(pt1); | |||
| pt2 = IntPoint((long64)(pt2.X + normals[m_j].Y * dx), | pt2 = IntPoint((long64)(pt2.X + normals[m_j].Y * dx), | |||
| (long64)(pt2.Y -normals[m_j].X * dx)); | (long64)(pt2.Y -normals[m_j].X * dx)); | |||
| AddPoint(pt2); | AddPoint(pt2); | |||
| } | } | |||
| else | else | |||
| { | { | |||
| AddPoint(pt1); | AddPoint(pt1); | |||
| skipping to change at line 3374 | skipping to change at line 3391 | |||
| { | { | |||
| if (&out_polys == &in_polys) | if (&out_polys == &in_polys) | |||
| { | { | |||
| Polygons poly2(in_polys); | Polygons poly2(in_polys); | |||
| PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit); | PolyOffsetBuilder(poly2, out_polys, delta, jointype, MiterLimit); | |||
| } | } | |||
| else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit); | else PolyOffsetBuilder(in_polys, out_polys, delta, jointype, MiterLimit); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys) | void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillT ype fillType) | |||
| { | { | |||
| Clipper c; | Clipper c; | |||
| c.AddPolygon(in_poly, ptSubject); | c.AddPolygon(in_poly, ptSubject); | |||
| c.Execute(ctUnion, out_polys); | c.Execute(ctUnion, out_polys, fillType, fillType); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys) | void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFi llType fillType) | |||
| { | { | |||
| Clipper c; | Clipper c; | |||
| c.AddPolygons(in_polys, ptSubject); | c.AddPolygons(in_polys, ptSubject); | |||
| c.Execute(ctUnion, out_polys); | c.Execute(ctUnion, out_polys, fillType, fillType); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| void SimplifyPolygons(Polygons &polys) | void SimplifyPolygons(Polygons &polys, PolyFillType fillType) | |||
| { | { | |||
| SimplifyPolygons(polys, polys); | SimplifyPolygons(polys, polys, fillType); | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| std::ostream& operator <<(std::ostream &s, IntPoint& p) | std::ostream& operator <<(std::ostream &s, IntPoint& p) | |||
| { | { | |||
| s << p.X << ' ' << p.Y << "\n"; | s << p.X << ' ' << p.Y << "\n"; | |||
| return s; | return s; | |||
| } | } | |||
| //------------------------------------------------------------------------- ----- | //------------------------------------------------------------------------- ----- | |||
| End of changes. 23 change blocks. | ||||
| 26 lines changed or deleted | 44 lines changed or added | |||
This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||