| 1 | /******************************************************************************* | ||
| 2 | * * | ||
| 3 | * Author : Angus Johnson * | ||
| 4 | * Version : 5.1.5 * | ||
| 5 | * Date : 4 May 2013 * | ||
| 6 | * Website : http://www.angusj.com * | ||
| 7 | * Copyright : Angus Johnson 2010-2013 * | ||
| 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 | #include <vector> | ||
| 38 | #include <stdexcept> | ||
| 39 | #include <cstring> | ||
| 40 | #include <cstdlib> | ||
| 41 | #include <ostream> | ||
| 42 | |||
| 43 | namespace ClipperLib { | ||
| 44 | |||
| 45 | enum ClipType { ctIntersection, ctUnion, ctDifference, ctXor }; | ||
| 46 | enum PolyType { ptSubject, ptClip }; | ||
| 47 | //By far the most widely used winding rules for polygon filling are | ||
| 48 | //EvenOdd & NonZero (GDI, GDI+, XLib, OpenGL, Cairo, AGG, Quartz, SVG, Gr32) | ||
| 49 | //Others rules include Positive, Negative and ABS_GTR_EQ_TWO (only in OpenGL) | ||
| 50 | //see http://glprogramming.com/red/chapter11.html | ||
| 51 | enum PolyFillType { pftEvenOdd, pftNonZero, pftPositive, pftNegative }; | ||
| 52 | |||
| 53 | typedef signed long long long64; | ||
| 54 | typedef unsigned long long ulong64; | ||
| 55 | |||
| 56 | struct IntPoint { | ||
| 57 | public: | ||
| 58 | long64 X; | ||
| 59 | long64 Y; | ||
| 60 | 1553 | IntPoint(long64 x = 0, long64 y = 0): X(x), Y(y) {}; | |
| 61 | friend std::ostream& operator <<(std::ostream &s, IntPoint &p); | ||
| 62 | }; | ||
| 63 | |||
| 64 | typedef std::vector< IntPoint > Polygon; | ||
| 65 | typedef std::vector< Polygon > Polygons; | ||
| 66 | |||
| 67 | |||
| 68 | std::ostream& operator <<(std::ostream &s, Polygon &p); | ||
| 69 | std::ostream& operator <<(std::ostream &s, Polygons &p); | ||
| 70 | |||
| 71 | class PolyNode; | ||
| 72 | typedef std::vector< PolyNode* > PolyNodes; | ||
| 73 | |||
| 74 | class PolyNode | ||
| 75 | { | ||
| 76 | public: | ||
| 77 | PolyNode(); | ||
| 78 | Polygon Contour; | ||
| 79 | PolyNodes Childs; | ||
| 80 | PolyNode* Parent; | ||
| 81 | PolyNode* GetNext() const; | ||
| 82 | bool IsHole() const; | ||
| 83 | int ChildCount() const; | ||
| 84 | private: | ||
| 85 | PolyNode* GetNextSiblingUp() const; | ||
| 86 | unsigned Index; //node index in Parent.Childs | ||
| 87 | void AddChild(PolyNode& child); | ||
| 88 | friend class Clipper; //to access Index | ||
| 89 | }; | ||
| 90 | |||
| 91 | class PolyTree: public PolyNode | ||
| 92 | { | ||
| 93 | public: | ||
| 94 | 6 | ~PolyTree(){Clear();}; | |
| 95 | PolyNode* GetFirst() const; | ||
| 96 | void Clear(); | ||
| 97 | int Total() const; | ||
| 98 | private: | ||
| 99 | PolyNodes AllNodes; | ||
| 100 | friend class Clipper; //to access AllNodes | ||
| 101 | }; | ||
| 102 | |||
| 103 | enum JoinType { jtSquare, jtRound, jtMiter }; | ||
| 104 | |||
| 105 | bool Orientation(const Polygon &poly); | ||
| 106 | double Area(const Polygon &poly); | ||
| 107 | |||
| 108 | void OffsetPolygons(const Polygons &in_polys, Polygons &out_polys, | ||
| 109 | double delta, JoinType jointype = jtSquare, double limit = 0, bool autoFix = true); | ||
| 110 | |||
| 111 | void SimplifyPolygon(const Polygon &in_poly, Polygons &out_polys, PolyFillType fillType = pftEvenOdd); | ||
| 112 | void SimplifyPolygons(const Polygons &in_polys, Polygons &out_polys, PolyFillType fillType = pftEvenOdd); | ||
| 113 | void SimplifyPolygons(Polygons &polys, PolyFillType fillType = pftEvenOdd); | ||
| 114 | |||
| 115 | void CleanPolygon(Polygon& in_poly, Polygon& out_poly, double distance = 1.415); | ||
| 116 | void CleanPolygons(Polygons& in_polys, Polygons& out_polys, double distance = 1.415); | ||
| 117 | |||
| 118 | void PolyTreeToPolygons(PolyTree& polytree, Polygons& polygons); | ||
| 119 | |||
| 120 | void ReversePolygon(Polygon& p); | ||
| 121 | void ReversePolygons(Polygons& p); | ||
| 122 | |||
| 123 | //used internally ... | ||
| 124 | enum EdgeSide { esLeft = 1, esRight = 2}; | ||
| 125 | enum IntersectProtects { ipNone = 0, ipLeft = 1, ipRight = 2, ipBoth = 3 }; | ||
| 126 | |||
| 127 | struct TEdge { | ||
| 128 | long64 xbot; | ||
| 129 | long64 ybot; | ||
| 130 | long64 xcurr; | ||
| 131 | long64 ycurr; | ||
| 132 | long64 xtop; | ||
| 133 | long64 ytop; | ||
| 134 | double dx; | ||
| 135 | long64 deltaX; | ||
| 136 | long64 deltaY; | ||
| 137 | PolyType polyType; | ||
| 138 | EdgeSide side; | ||
| 139 | int windDelta; //1 or -1 depending on winding direction | ||
| 140 | int windCnt; | ||
| 141 | int windCnt2; //winding count of the opposite polytype | ||
| 142 | int outIdx; | ||
| 143 | TEdge *next; | ||
| 144 | TEdge *prev; | ||
| 145 | TEdge *nextInLML; | ||
| 146 | TEdge *nextInAEL; | ||
| 147 | TEdge *prevInAEL; | ||
| 148 | TEdge *nextInSEL; | ||
| 149 | TEdge *prevInSEL; | ||
| 150 | }; | ||
| 151 | |||
| 152 | struct IntersectNode { | ||
| 153 | TEdge *edge1; | ||
| 154 | TEdge *edge2; | ||
| 155 | IntPoint pt; | ||
| 156 | IntersectNode *next; | ||
| 157 | }; | ||
| 158 | |||
| 159 | struct LocalMinima { | ||
| 160 | long64 Y; | ||
| 161 | TEdge *leftBound; | ||
| 162 | TEdge *rightBound; | ||
| 163 | LocalMinima *next; | ||
| 164 | }; | ||
| 165 | |||
| 166 | struct Scanbeam { | ||
| 167 | long64 Y; | ||
| 168 | Scanbeam *next; | ||
| 169 | }; | ||
| 170 | |||
| 171 | struct OutPt; //forward declaration | ||
| 172 | |||
| 173 | struct OutRec { | ||
| 174 | int idx; | ||
| 175 | bool isHole; | ||
| 176 | OutRec *FirstLeft; //see comments in clipper.pas | ||
| 177 | PolyNode *polyNode; | ||
| 178 | OutPt *pts; | ||
| 179 | OutPt *bottomPt; | ||
| 180 | }; | ||
| 181 | |||
| 182 | struct OutPt { | ||
| 183 | int idx; | ||
| 184 | IntPoint pt; | ||
| 185 | OutPt *next; | ||
| 186 | OutPt *prev; | ||
| 187 | }; | ||
| 188 | |||
| 189 | struct JoinRec { | ||
| 190 | IntPoint pt1a; | ||
| 191 | IntPoint pt1b; | ||
| 192 | int poly1Idx; | ||
| 193 | IntPoint pt2a; | ||
| 194 | IntPoint pt2b; | ||
| 195 | int poly2Idx; | ||
| 196 | }; | ||
| 197 | |||
| 198 | struct HorzJoinRec { | ||
| 199 | TEdge *edge; | ||
| 200 | int savedIdx; | ||
| 201 | }; | ||
| 202 | |||
| 203 | struct IntRect { long64 left; long64 top; long64 right; long64 bottom; }; | ||
| 204 | |||
| 205 | typedef std::vector < OutRec* > PolyOutList; | ||
| 206 | typedef std::vector < TEdge* > EdgeList; | ||
| 207 | typedef std::vector < JoinRec* > JoinList; | ||
| 208 | typedef std::vector < HorzJoinRec* > HorzJoinList; | ||
| 209 | |||
| 210 | //ClipperBase is the ancestor to the Clipper class. It should not be | ||
| 211 | //instantiated directly. This class simply abstracts the conversion of sets of | ||
| 212 | //polygon coordinates into edge objects that are stored in a LocalMinima list. | ||
| 213 | class ClipperBase | ||
| 214 | { | ||
| 215 | public: | ||
| 216 | ClipperBase(); | ||
| 217 | virtual ~ClipperBase(); | ||
| 218 | bool AddPolygon(const Polygon &pg, PolyType polyType); | ||
| 219 | bool AddPolygons( const Polygons &ppg, PolyType polyType); | ||
| 220 | virtual void Clear(); | ||
| 221 | IntRect GetBounds(); | ||
| 222 | protected: | ||
| 223 | void DisposeLocalMinimaList(); | ||
| 224 | TEdge* AddBoundsToLML(TEdge *e); | ||
| 225 | void PopLocalMinima(); | ||
| 226 | virtual void Reset(); | ||
| 227 | void InsertLocalMinima(LocalMinima *newLm); | ||
| 228 | LocalMinima *m_CurrentLM; | ||
| 229 | LocalMinima *m_MinimaList; | ||
| 230 | bool m_UseFullRange; | ||
| 231 | EdgeList m_edges; | ||
| 232 | }; | ||
| 233 | |||
| 234 | class Clipper : public virtual ClipperBase | ||
| 235 | { | ||
| 236 | public: | ||
| 237 | Clipper(); | ||
| 238 | ~Clipper(); | ||
| 239 | bool Execute(ClipType clipType, | ||
| 240 | Polygons &solution, | ||
| 241 | PolyFillType subjFillType = pftEvenOdd, | ||
| 242 | PolyFillType clipFillType = pftEvenOdd); | ||
| 243 | bool Execute(ClipType clipType, | ||
| 244 | PolyTree &polytree, | ||
| 245 | PolyFillType subjFillType = pftEvenOdd, | ||
| 246 | PolyFillType clipFillType = pftEvenOdd); | ||
| 247 | void Clear(); | ||
| 248 | bool ReverseSolution() {return m_ReverseOutput;}; | ||
| 249 | void ReverseSolution(bool value) {m_ReverseOutput = value;}; | ||
| 250 | bool ForceSimple() {return m_ForceSimple;}; | ||
| 251 | void ForceSimple(bool value) {m_ForceSimple = value;}; | ||
| 252 | protected: | ||
| 253 | void Reset(); | ||
| 254 | virtual bool ExecuteInternal(); | ||
| 255 | private: | ||
| 256 | PolyOutList m_PolyOuts; | ||
| 257 | JoinList m_Joins; | ||
| 258 | HorzJoinList m_HorizJoins; | ||
| 259 | ClipType m_ClipType; | ||
| 260 | Scanbeam *m_Scanbeam; | ||
| 261 | TEdge *m_ActiveEdges; | ||
| 262 | TEdge *m_SortedEdges; | ||
| 263 | IntersectNode *m_IntersectNodes; | ||
| 264 | bool m_ExecuteLocked; | ||
| 265 | PolyFillType m_ClipFillType; | ||
| 266 | PolyFillType m_SubjFillType; | ||
| 267 | bool m_ReverseOutput; | ||
| 268 | bool m_UsingPolyTree; | ||
| 269 | bool m_ForceSimple; | ||
| 270 | void DisposeScanbeamList(); | ||
| 271 | void SetWindingCount(TEdge& edge); | ||
| 272 | bool IsEvenOddFillType(const TEdge& edge) const; | ||
| 273 | bool IsEvenOddAltFillType(const TEdge& edge) const; | ||
| 274 | void InsertScanbeam(const long64 Y); | ||
| 275 | long64 PopScanbeam(); | ||
| 276 | void InsertLocalMinimaIntoAEL(const long64 botY); | ||
| 277 | void InsertEdgeIntoAEL(TEdge *edge); | ||
| 278 | void AddEdgeToSEL(TEdge *edge); | ||
| 279 | void CopyAELToSEL(); | ||
| 280 | void DeleteFromSEL(TEdge *e); | ||
| 281 | void DeleteFromAEL(TEdge *e); | ||
| 282 | void UpdateEdgeIntoAEL(TEdge *&e); | ||
| 283 | void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); | ||
| 284 | bool IsContributing(const TEdge& edge) const; | ||
| 285 | bool IsTopHorz(const long64 XPos); | ||
| 286 | void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); | ||
| 287 | void DoMaxima(TEdge *e, long64 topY); | ||
| 288 | void ProcessHorizontals(); | ||
| 289 | void ProcessHorizontal(TEdge *horzEdge); | ||
| 290 | void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); | ||
| 291 | void AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); | ||
| 292 | OutRec* GetOutRec(int idx); | ||
| 293 | void AppendPolygon(TEdge *e1, TEdge *e2); | ||
| 294 | void IntersectEdges(TEdge *e1, TEdge *e2, | ||
| 295 | const IntPoint &pt, const IntersectProtects protects); | ||
| 296 | OutRec* CreateOutRec(); | ||
| 297 | void AddOutPt(TEdge *e, const IntPoint &pt); | ||
| 298 | void DisposeAllPolyPts(); | ||
| 299 | void DisposeOutRec(PolyOutList::size_type index); | ||
| 300 | bool ProcessIntersections(const long64 botY, const long64 topY); | ||
| 301 | void AddIntersectNode(TEdge *e1, TEdge *e2, const IntPoint &pt); | ||
| 302 | void BuildIntersectList(const long64 botY, const long64 topY); | ||
| 303 | void ProcessIntersectList(); | ||
| 304 | void ProcessEdgesAtTopOfScanbeam(const long64 topY); | ||
| 305 | void BuildResult(Polygons& polys); | ||
| 306 | void BuildResult2(PolyTree& polytree); | ||
| 307 | void SetHoleState(TEdge *e, OutRec *outrec); | ||
| 308 | void DisposeIntersectNodes(); | ||
| 309 | bool FixupIntersectionOrder(); | ||
| 310 | void FixupOutPolygon(OutRec &outrec); | ||
| 311 | bool IsHole(TEdge *e); | ||
| 312 | void FixHoleLinkage(OutRec &outrec); | ||
| 313 | void AddJoin(TEdge *e1, TEdge *e2, int e1OutIdx = -1, int e2OutIdx = -1); | ||
| 314 | void ClearJoins(); | ||
| 315 | void AddHorzJoin(TEdge *e, int idx); | ||
| 316 | void ClearHorzJoins(); | ||
| 317 | bool JoinPoints(const JoinRec *j, OutPt *&p1, OutPt *&p2); | ||
| 318 | void FixupJoinRecs(JoinRec *j, OutPt *pt, unsigned startIdx); | ||
| 319 | void JoinCommonEdges(); | ||
| 320 | void DoSimplePolygons(); | ||
| 321 | void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec); | ||
| 322 | void FixupFirstLefts2(OutRec* OldOutRec, OutRec* NewOutRec); | ||
| 323 | }; | ||
| 324 | |||
| 325 | //------------------------------------------------------------------------------ | ||
| 326 | //------------------------------------------------------------------------------ | ||
| 327 | |||
| 328 | class clipperException : public std::exception | ||
| 329 | { | ||
| 330 | public: | ||
| 331 | clipperException(const char* description): m_descr(description) {} | ||
| 332 | virtual ~clipperException() throw() {} | ||
| 333 | virtual const char* what() const throw() {return m_descr.c_str();} | ||
| 334 | private: | ||
| 335 | std::string m_descr; | ||
| 336 | }; | ||
| 337 | //------------------------------------------------------------------------------ | ||
| 338 | |||
| 339 | } //ClipperLib namespace | ||
| 340 | |||
| 341 | #endif //clipper_hpp | ||
| 342 | |||
| 343 |