[688] | 1 | /******************************************************************************* |
---|
| 2 | * * |
---|
| 3 | * Author : Angus Johnson * |
---|
| 4 | * Version : 6.2.9 * |
---|
| 5 | * Date : 16 February 2015 * |
---|
| 6 | * Website : http://www.angusj.com * |
---|
| 7 | * Copyright : Angus Johnson 2010-2015 * |
---|
| 8 | * * |
---|
| 9 | * License: * |
---|
| 10 | * Use, modification & distribution is subject to Boost Software License Ver 1. * |
---|
| 11 | * http://www.boost.org/LICENSE_1_0.txt * |
---|
| 12 | * * |
---|
| 13 | * Attributions: * |
---|
| 14 | * The code in this library is an extension of Bala Vatti's clipping algorithm: * |
---|
| 15 | * "A generic solution to polygon clipping" * |
---|
| 16 | * Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. * |
---|
| 17 | * http://portal.acm.org/citation.cfm?id=129906 * |
---|
| 18 | * * |
---|
| 19 | * Computer graphics and geometric modeling: implementation and algorithms * |
---|
| 20 | * By Max K. Agoston * |
---|
| 21 | * Springer; 1 edition (January 4, 2005) * |
---|
| 22 | * http://books.google.com/books?q=vatti+clipping+agoston * |
---|
| 23 | * * |
---|
| 24 | * See also: * |
---|
| 25 | * "Polygon Offsetting by Computing Winding Numbers" * |
---|
| 26 | * Paper no. DETC2005-85513 pp. 565-575 * |
---|
| 27 | * ASME 2005 International Design Engineering Technical Conferences * |
---|
| 28 | * and Computers and Information in Engineering Conference (IDETC/CIE2005) * |
---|
| 29 | * September 24-28, 2005 , Long Beach, California, USA * |
---|
| 30 | * http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf * |
---|
| 31 | * * |
---|
| 32 | *******************************************************************************/ |
---|
| 33 | |
---|
| 34 | #ifndef clipper_hpp |
---|
| 35 | #define clipper_hpp |
---|
| 36 | |
---|
| 37 | #define CLIPPER_VERSION "6.2.6" |
---|
| 38 | |
---|
| 39 | //use_int32: When enabled 32bit ints are used instead of 64bit ints. This |
---|
| 40 | //improve performance but coordinate values are limited to the range +/- 46340 |
---|
| 41 | //#define use_int32 |
---|
| 42 | |
---|
| 43 | //use_xyz: adds a Z member to IntPoint. Adds a minor cost to perfomance. |
---|
| 44 | //#define use_xyz |
---|
| 45 | |
---|
| 46 | //use_lines: Enables line clipping. Adds a very minor cost to performance. |
---|
| 47 | #define use_lines |
---|
| 48 | |
---|
| 49 | //use_deprecated: Enables temporary support for the obsolete functions |
---|
| 50 | //#define use_deprecated |
---|
| 51 | |
---|
| 52 | #include <vector> |
---|
| 53 | #include <list> |
---|
| 54 | #include <set> |
---|
| 55 | #include <stdexcept> |
---|
| 56 | #include <cstring> |
---|
| 57 | #include <cstdlib> |
---|
| 58 | #include <ostream> |
---|
| 59 | #include <functional> |
---|
| 60 | #include <queue> |
---|
| 61 | |
---|
| 62 | namespace ClipperLib { |
---|
| 63 | |
---|
| 64 | enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor }; |
---|
| 65 | enum PolyType { ptSubject, ptClip }; |
---|
| 66 | //By far the most widely used winding rules for polygon filling are |
---|
| 67 | //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32) |
---|
| 68 | //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL) |
---|
| 69 | //see http://glprogramming.com/red/chapter11.html |
---|
| 70 | enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative }; |
---|
| 71 | |
---|
| 72 | #ifdef use_int32 |
---|
| 73 | typedef int cInt; |
---|
| 74 | static cInt const loRange = 0x7FFF; |
---|
| 75 | static cInt const hiRange = 0x7FFF; |
---|
| 76 | #else |
---|
| 77 | typedef signed long long cInt; |
---|
| 78 | static cInt const loRange = 0x3FFFFFFF; |
---|
| 79 | static cInt const hiRange = 0x3FFFFFFFFFFFFFFFLL; |
---|
| 80 | typedef signed long long long64; //used by Int128 class |
---|
| 81 | typedef unsigned long long ulong64; |
---|
| 82 | |
---|
| 83 | #endif |
---|
| 84 | |
---|
| 85 | struct IntPoint { |
---|
| 86 | cInt X; |
---|
| 87 | cInt Y; |
---|
| 88 | #ifdef use_xyz |
---|
| 89 | cInt Z; |
---|
| 90 | IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {}; |
---|
| 91 | #else |
---|
| 92 | IntPoint(cInt x = 0, cInt y = 0): X(x), Y(y) {}; |
---|
| 93 | #endif |
---|
| 94 | |
---|
| 95 | friend inline bool operator== (const IntPoint& a, const IntPoint& b) |
---|
| 96 | { |
---|
| 97 | return a.X == b.X && a.Y == b.Y; |
---|
| 98 | } |
---|
| 99 | friend inline bool operator!= (const IntPoint& a, const IntPoint& b) |
---|
| 100 | { |
---|
| 101 | return a.X != b.X || a.Y != b.Y; |
---|
| 102 | } |
---|
| 103 | }; |
---|
| 104 | //------------------------------------------------------------------------------ |
---|
| 105 | |
---|
| 106 | typedef std::vector< IntPoint > Path; |
---|
| 107 | typedef std::vector< Path > Paths; |
---|
| 108 | |
---|
| 109 | inline Path& operator <<(Path& poly, const IntPoint& p) {poly.push_back(p); return poly;} |
---|
| 110 | inline Paths& operator <<(Paths& polys, const Path& p) {polys.push_back(p); return polys;} |
---|
| 111 | |
---|
| 112 | std::ostream& operator <<(std::ostream &s, const IntPoint &p); |
---|
| 113 | std::ostream& operator <<(std::ostream &s, const Path &p); |
---|
| 114 | std::ostream& operator <<(std::ostream &s, const Paths &p); |
---|
| 115 | |
---|
| 116 | struct DoublePoint |
---|
| 117 | { |
---|
| 118 | double X; |
---|
| 119 | double Y; |
---|
| 120 | DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {} |
---|
| 121 | DoublePoint(IntPoint ip) : X((double)ip.X), Y((double)ip.Y) {} |
---|
| 122 | }; |
---|
| 123 | //------------------------------------------------------------------------------ |
---|
| 124 | |
---|
| 125 | #ifdef use_xyz |
---|
| 126 | typedef void (*ZFillCallback)(IntPoint& e1bot, IntPoint& e1top, IntPoint& e2bot, IntPoint& e2top, IntPoint& pt); |
---|
| 127 | #endif |
---|
| 128 | |
---|
| 129 | enum InitOptions {ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCollinear = 4}; |
---|
| 130 | enum JoinType {jtSquare, jtRound, jtMiter}; |
---|
| 131 | enum EndType {etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOpenRound}; |
---|
| 132 | |
---|
| 133 | class PolyNode; |
---|
| 134 | typedef std::vector< PolyNode* > PolyNodes; |
---|
| 135 | |
---|
| 136 | class PolyNode |
---|
| 137 | { |
---|
| 138 | public: |
---|
| 139 | PolyNode(); |
---|
| 140 | virtual ~PolyNode(){}; |
---|
| 141 | Path Contour; |
---|
| 142 | PolyNodes Childs; |
---|
| 143 | PolyNode* Parent; |
---|
| 144 | PolyNode* GetNext() const; |
---|
| 145 | bool IsHole() const; |
---|
| 146 | bool IsOpen() const; |
---|
| 147 | int ChildCount() const; |
---|
| 148 | private: |
---|
| 149 | unsigned Index; //node index in Parent.Childs |
---|
| 150 | bool m_IsOpen; |
---|
| 151 | JoinType m_jointype; |
---|
| 152 | EndType m_endtype; |
---|
| 153 | PolyNode* GetNextSiblingUp() const; |
---|
| 154 | void AddChild(PolyNode& child); |
---|
| 155 | friend class Clipper; //to access Index |
---|
| 156 | friend class ClipperOffset; |
---|
| 157 | }; |
---|
| 158 | |
---|
| 159 | class PolyTree: public PolyNode |
---|
| 160 | { |
---|
| 161 | public: |
---|
| 162 | ~PolyTree(){Clear();}; |
---|
| 163 | PolyNode* GetFirst() const; |
---|
| 164 | void Clear(); |
---|
| 165 | int Total() const; |
---|
| 166 | private: |
---|
| 167 | PolyNodes AllNodes; |
---|
| 168 | friend class Clipper; //to access AllNodes |
---|
| 169 | }; |
---|
| 170 | |
---|
| 171 | bool Orientation(const Path &poly); |
---|
| 172 | double Area(const Path &poly); |
---|
| 173 | int PointInPolygon(const IntPoint &pt, const Path &path); |
---|
| 174 | |
---|
| 175 | void SimplifyPolygon(const Path &in_poly, Paths &out_polys, PolyFillType fillType = pftEvenOdd); |
---|
| 176 | void SimplifyPolygons(const Paths &in_polys, Paths &out_polys, PolyFillType fillType = pftEvenOdd); |
---|
| 177 | void SimplifyPolygons(Paths &polys, PolyFillType fillType = pftEvenOdd); |
---|
| 178 | |
---|
| 179 | void CleanPolygon(const Path& in_poly, Path& out_poly, double distance = 1.415); |
---|
| 180 | void CleanPolygon(Path& poly, double distance = 1.415); |
---|
| 181 | void CleanPolygons(const Paths& in_polys, Paths& out_polys, double distance = 1.415); |
---|
| 182 | void CleanPolygons(Paths& polys, double distance = 1.415); |
---|
| 183 | |
---|
| 184 | void MinkowskiSum(const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed); |
---|
| 185 | void MinkowskiSum(const Path& pattern, const Paths& paths, Paths& solution, bool pathIsClosed); |
---|
| 186 | void MinkowskiDiff(const Path& poly1, const Path& poly2, Paths& solution); |
---|
| 187 | |
---|
| 188 | void PolyTreeToPaths(const PolyTree& polytree, Paths& paths); |
---|
| 189 | void ClosedPathsFromPolyTree(const PolyTree& polytree, Paths& paths); |
---|
| 190 | void OpenPathsFromPolyTree(PolyTree& polytree, Paths& paths); |
---|
| 191 | |
---|
| 192 | void ReversePath(Path& p); |
---|
| 193 | void ReversePaths(Paths& p); |
---|
| 194 | |
---|
| 195 | struct IntRect { cInt left; cInt top; cInt right; cInt bottom; }; |
---|
| 196 | |
---|
| 197 | //enums that are used internally ... |
---|
| 198 | enum EdgeSide { esLeft = 1, esRight = 2}; |
---|
| 199 | |
---|
| 200 | //forward declarations (for stuff used internally) ... |
---|
| 201 | struct TEdge; |
---|
| 202 | struct IntersectNode; |
---|
| 203 | struct LocalMinimum; |
---|
| 204 | struct OutPt; |
---|
| 205 | struct OutRec; |
---|
| 206 | struct Join; |
---|
| 207 | |
---|
| 208 | typedef std::vector < OutRec* > PolyOutList; |
---|
| 209 | typedef std::vector < TEdge* > EdgeList; |
---|
| 210 | typedef std::vector < Join* > JoinList; |
---|
| 211 | typedef std::vector < IntersectNode* > IntersectList; |
---|
| 212 | |
---|
| 213 | //------------------------------------------------------------------------------ |
---|
| 214 | |
---|
| 215 | //ClipperBase is the ancestor to the Clipper class. It should not be |
---|
| 216 | //instantiated directly. This class simply abstracts the conversion of sets of |
---|
| 217 | //polygon coordinates into edge objects that are stored in a LocalMinima list. |
---|
| 218 | class ClipperBase |
---|
| 219 | { |
---|
| 220 | public: |
---|
| 221 | ClipperBase(); |
---|
| 222 | virtual ~ClipperBase(); |
---|
| 223 | bool AddPath(const Path &pg, PolyType PolyTyp, bool Closed); |
---|
| 224 | bool AddPaths(const Paths &ppg, PolyType PolyTyp, bool Closed); |
---|
| 225 | virtual void Clear(); |
---|
| 226 | IntRect GetBounds(); |
---|
| 227 | bool PreserveCollinear() {return m_PreserveCollinear;}; |
---|
| 228 | void PreserveCollinear(bool value) {m_PreserveCollinear = value;}; |
---|
| 229 | protected: |
---|
| 230 | void DisposeLocalMinimaList(); |
---|
| 231 | TEdge* AddBoundsToLML(TEdge *e, bool IsClosed); |
---|
| 232 | void PopLocalMinima(); |
---|
| 233 | virtual void Reset(); |
---|
| 234 | TEdge* ProcessBound(TEdge* E, bool IsClockwise); |
---|
| 235 | TEdge* DescendToMin(TEdge *&E); |
---|
| 236 | void AscendToMax(TEdge *&E, bool Appending, bool IsClosed); |
---|
| 237 | |
---|
| 238 | typedef std::vector<LocalMinimum> MinimaList; |
---|
| 239 | MinimaList::iterator m_CurrentLM; |
---|
| 240 | MinimaList m_MinimaList; |
---|
| 241 | |
---|
| 242 | bool m_UseFullRange; |
---|
| 243 | EdgeList m_edges; |
---|
| 244 | bool m_PreserveCollinear; |
---|
| 245 | bool m_HasOpenPaths; |
---|
| 246 | }; |
---|
| 247 | //------------------------------------------------------------------------------ |
---|
| 248 | |
---|
| 249 | class Clipper : public virtual ClipperBase |
---|
| 250 | { |
---|
| 251 | public: |
---|
| 252 | Clipper(int initOptions = 0); |
---|
| 253 | ~Clipper(); |
---|
| 254 | bool Execute(ClipType clipType, |
---|
| 255 | Paths &solution, |
---|
| 256 | PolyFillType fillType = pftEvenOdd); |
---|
| 257 | bool Execute(ClipType clipType, |
---|
| 258 | Paths &solution, |
---|
| 259 | PolyFillType subjFillType, |
---|
| 260 | PolyFillType clipFillType); |
---|
| 261 | bool Execute(ClipType clipType, |
---|
| 262 | PolyTree &polytree, |
---|
| 263 | PolyFillType fillType = pftEvenOdd); |
---|
| 264 | bool Execute(ClipType clipType, |
---|
| 265 | PolyTree &polytree, |
---|
| 266 | PolyFillType subjFillType, |
---|
| 267 | PolyFillType clipFillType); |
---|
| 268 | bool ReverseSolution() { return m_ReverseOutput; }; |
---|
| 269 | void ReverseSolution(bool value) {m_ReverseOutput = value;}; |
---|
| 270 | bool StrictlySimple() {return m_StrictSimple;}; |
---|
| 271 | void StrictlySimple(bool value) {m_StrictSimple = value;}; |
---|
| 272 | //set the callback function for z value filling on intersections (otherwise Z is 0) |
---|
| 273 | #ifdef use_xyz |
---|
| 274 | void ZFillFunction(ZFillCallback zFillFunc); |
---|
| 275 | #endif |
---|
| 276 | protected: |
---|
| 277 | void Reset(); |
---|
| 278 | virtual bool ExecuteInternal(); |
---|
| 279 | private: |
---|
| 280 | PolyOutList m_PolyOuts; |
---|
| 281 | JoinList m_Joins; |
---|
| 282 | JoinList m_GhostJoins; |
---|
| 283 | IntersectList m_IntersectList; |
---|
| 284 | ClipType m_ClipType; |
---|
| 285 | typedef std::priority_queue<cInt> ScanbeamList; |
---|
| 286 | ScanbeamList m_Scanbeam; |
---|
| 287 | typedef std::list<cInt> MaximaList; |
---|
| 288 | MaximaList m_Maxima; |
---|
| 289 | TEdge *m_ActiveEdges; |
---|
| 290 | TEdge *m_SortedEdges; |
---|
| 291 | bool m_ExecuteLocked; |
---|
| 292 | PolyFillType m_ClipFillType; |
---|
| 293 | PolyFillType m_SubjFillType; |
---|
| 294 | bool m_ReverseOutput; |
---|
| 295 | bool m_UsingPolyTree; |
---|
| 296 | bool m_StrictSimple; |
---|
| 297 | #ifdef use_xyz |
---|
| 298 | ZFillCallback m_ZFill; //custom callback |
---|
| 299 | #endif |
---|
| 300 | void SetWindingCount(TEdge& edge); |
---|
| 301 | bool IsEvenOddFillType(const TEdge& edge) const; |
---|
| 302 | bool IsEvenOddAltFillType(const TEdge& edge) const; |
---|
| 303 | void InsertScanbeam(const cInt Y); |
---|
| 304 | cInt PopScanbeam(); |
---|
| 305 | void InsertLocalMinimaIntoAEL(const cInt botY); |
---|
| 306 | void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge); |
---|
| 307 | void AddEdgeToSEL(TEdge *edge); |
---|
| 308 | void CopyAELToSEL(); |
---|
| 309 | void DeleteFromSEL(TEdge *e); |
---|
| 310 | void DeleteFromAEL(TEdge *e); |
---|
| 311 | void UpdateEdgeIntoAEL(TEdge *&e); |
---|
| 312 | void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); |
---|
| 313 | bool IsContributing(const TEdge& edge) const; |
---|
| 314 | bool IsTopHorz(const cInt XPos); |
---|
| 315 | void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); |
---|
| 316 | void DoMaxima(TEdge *e); |
---|
| 317 | void ProcessHorizontals(); |
---|
| 318 | void ProcessHorizontal(TEdge *horzEdge); |
---|
| 319 | void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); |
---|
| 320 | OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); |
---|
| 321 | OutRec* GetOutRec(int idx); |
---|
| 322 | void AppendPolygon(TEdge *e1, TEdge *e2); |
---|
| 323 | void IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &pt); |
---|
| 324 | OutRec* CreateOutRec(); |
---|
| 325 | OutPt* AddOutPt(TEdge *e, const IntPoint &pt); |
---|
| 326 | OutPt* GetLastOutPt(TEdge *e); |
---|
| 327 | void DisposeAllOutRecs(); |
---|
| 328 | void DisposeOutRec(PolyOutList::size_type index); |
---|
| 329 | bool ProcessIntersections(const cInt topY); |
---|
| 330 | void BuildIntersectList(const cInt topY); |
---|
| 331 | void ProcessIntersectList(); |
---|
| 332 | void ProcessEdgesAtTopOfScanbeam(const cInt topY); |
---|
| 333 | void BuildResult(Paths& polys); |
---|
| 334 | void BuildResult2(PolyTree& polytree); |
---|
| 335 | void SetHoleState(TEdge *e, OutRec *outrec); |
---|
| 336 | void DisposeIntersectNodes(); |
---|
| 337 | bool FixupIntersectionOrder(); |
---|
| 338 | void FixupOutPolygon(OutRec &outrec); |
---|
| 339 | void FixupOutPolyline(OutRec &outrec); |
---|
| 340 | bool IsHole(TEdge *e); |
---|
| 341 | bool FindOwnerFromSplitRecs(OutRec &outRec, OutRec *&currOrfl); |
---|
| 342 | void FixHoleLinkage(OutRec &outrec); |
---|
| 343 | void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt); |
---|
| 344 | void ClearJoins(); |
---|
| 345 | void ClearGhostJoins(); |
---|
| 346 | void AddGhostJoin(OutPt *op, const IntPoint offPt); |
---|
| 347 | bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2); |
---|
| 348 | void JoinCommonEdges(); |
---|
| 349 | void DoSimplePolygons(); |
---|
| 350 | void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec); |
---|
| 351 | void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec); |
---|
| 352 | #ifdef use_xyz |
---|
| 353 | void SetZ(IntPoint& pt, TEdge& e1, TEdge& e2); |
---|
| 354 | #endif |
---|
| 355 | }; |
---|
| 356 | //------------------------------------------------------------------------------ |
---|
| 357 | |
---|
| 358 | class ClipperOffset |
---|
| 359 | { |
---|
| 360 | public: |
---|
| 361 | ClipperOffset(double miterLimit = 2.0, double roundPrecision = 0.25); |
---|
| 362 | ~ClipperOffset(); |
---|
| 363 | void AddPath(const Path& path, JoinType joinType, EndType endType); |
---|
| 364 | void AddPaths(const Paths& paths, JoinType joinType, EndType endType); |
---|
| 365 | void Execute(Paths& solution, double delta); |
---|
| 366 | void Execute(PolyTree& solution, double delta); |
---|
| 367 | void Clear(); |
---|
| 368 | double MiterLimit; |
---|
| 369 | double ArcTolerance; |
---|
| 370 | private: |
---|
| 371 | Paths m_destPolys; |
---|
| 372 | Path m_srcPoly; |
---|
| 373 | Path m_destPoly; |
---|
| 374 | std::vector<DoublePoint> m_normals; |
---|
| 375 | double m_delta, m_sinA, m_sin, m_cos; |
---|
| 376 | double m_miterLim, m_StepsPerRad; |
---|
| 377 | IntPoint m_lowest; |
---|
| 378 | PolyNode m_polyNodes; |
---|
| 379 | |
---|
| 380 | void FixOrientations(); |
---|
| 381 | void DoOffset(double delta); |
---|
| 382 | void OffsetPoint(int j, int& k, JoinType jointype); |
---|
| 383 | void DoSquare(int j, int k); |
---|
| 384 | void DoMiter(int j, int k, double r); |
---|
| 385 | void DoRound(int j, int k); |
---|
| 386 | }; |
---|
| 387 | //------------------------------------------------------------------------------ |
---|
| 388 | |
---|
| 389 | class clipperException : public std::exception |
---|
| 390 | { |
---|
| 391 | public: |
---|
| 392 | clipperException(const char* description): m_descr(description) {} |
---|
| 393 | virtual ~clipperException() throw() {} |
---|
| 394 | virtual const char* what() const throw() {return m_descr.c_str();} |
---|
| 395 | private: |
---|
| 396 | std::string m_descr; |
---|
| 397 | }; |
---|
| 398 | //------------------------------------------------------------------------------ |
---|
| 399 | |
---|
| 400 | } //ClipperLib namespace |
---|
| 401 | |
---|
| 402 | #endif //clipper_hpp |
---|
| 403 | |
---|
| 404 | |
---|