1 /******************************************************************************* 2 * * 3 * Author : Angus Johnson * 4 * Version : 6.4.0 * 5 * Date : 2 July 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 QtClipperLib { 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; XIntPoint90 IntPoint(cInt x = 0, cInt y = 0, cInt z = 0): X(x), Y(y), Z(z) {}; 91 #else XIntPoint92 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; XDoublePoint120 DoublePoint(double x = 0, double y = 0) : X(x), Y(y) {} DoublePointDoublePoint121 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(); ~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: ~PolyTree()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 virtual 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(); PreserveCollinear()227 bool PreserveCollinear() {return m_PreserveCollinear;}; PreserveCollinear(bool value)228 void PreserveCollinear(bool value) {m_PreserveCollinear = value;}; 229 protected: 230 void DisposeLocalMinimaList(); 231 TEdge* AddBoundsToLML(TEdge *e, bool IsClosed); 232 virtual void Reset(); 233 TEdge* ProcessBound(TEdge* E, bool IsClockwise); 234 void InsertScanbeam(const cInt Y); 235 bool PopScanbeam(cInt &Y); 236 bool LocalMinimaPending(); 237 bool PopLocalMinima(cInt Y, const LocalMinimum *&locMin); 238 OutRec* CreateOutRec(); 239 void DisposeAllOutRecs(); 240 void DisposeOutRec(PolyOutList::size_type index); 241 void SwapPositionsInAEL(TEdge *edge1, TEdge *edge2); 242 void DeleteFromAEL(TEdge *e); 243 void UpdateEdgeIntoAEL(TEdge *&e); 244 245 typedef std::vector<LocalMinimum> MinimaList; 246 MinimaList::iterator m_CurrentLM; 247 MinimaList m_MinimaList; 248 249 bool m_UseFullRange; 250 EdgeList m_edges; 251 bool m_PreserveCollinear; 252 bool m_HasOpenPaths; 253 PolyOutList m_PolyOuts; 254 TEdge *m_ActiveEdges; 255 256 typedef std::priority_queue<cInt> ScanbeamList; 257 ScanbeamList m_Scanbeam; 258 }; 259 //------------------------------------------------------------------------------ 260 261 class Clipper : public virtual ClipperBase 262 { 263 public: 264 Clipper(int initOptions = 0); 265 bool Execute(ClipType clipType, 266 Paths &solution, 267 PolyFillType fillType = pftEvenOdd); 268 bool Execute(ClipType clipType, 269 Paths &solution, 270 PolyFillType subjFillType, 271 PolyFillType clipFillType); 272 bool Execute(ClipType clipType, 273 PolyTree &polytree, 274 PolyFillType fillType = pftEvenOdd); 275 bool Execute(ClipType clipType, 276 PolyTree &polytree, 277 PolyFillType subjFillType, 278 PolyFillType clipFillType); ReverseSolution()279 bool ReverseSolution() { return m_ReverseOutput; }; ReverseSolution(bool value)280 void ReverseSolution(bool value) {m_ReverseOutput = value;}; StrictlySimple()281 bool StrictlySimple() {return m_StrictSimple;}; StrictlySimple(bool value)282 void StrictlySimple(bool value) {m_StrictSimple = value;}; 283 //set the callback function for z value filling on intersections (otherwise Z is 0) 284 #ifdef use_xyz 285 void ZFillFunction(ZFillCallback zFillFunc); 286 #endif 287 protected: 288 virtual bool ExecuteInternal(); 289 private: 290 JoinList m_Joins; 291 JoinList m_GhostJoins; 292 IntersectList m_IntersectList; 293 ClipType m_ClipType; 294 typedef std::list<cInt> MaximaList; 295 MaximaList m_Maxima; 296 TEdge *m_SortedEdges; 297 bool m_ExecuteLocked; 298 PolyFillType m_ClipFillType; 299 PolyFillType m_SubjFillType; 300 bool m_ReverseOutput; 301 bool m_UsingPolyTree; 302 bool m_StrictSimple; 303 #ifdef use_xyz 304 ZFillCallback m_ZFill; //custom callback 305 #endif 306 void SetWindingCount(TEdge& edge); 307 bool IsEvenOddFillType(const TEdge& edge) const; 308 bool IsEvenOddAltFillType(const TEdge& edge) const; 309 void InsertLocalMinimaIntoAEL(const cInt botY); 310 void InsertEdgeIntoAEL(TEdge *edge, TEdge* startEdge); 311 void AddEdgeToSEL(TEdge *edge); 312 bool PopEdgeFromSEL(TEdge *&edge); 313 void CopyAELToSEL(); 314 void DeleteFromSEL(TEdge *e); 315 void SwapPositionsInSEL(TEdge *edge1, TEdge *edge2); 316 bool IsContributing(const TEdge& edge) const; 317 bool IsTopHorz(const cInt XPos); 318 void DoMaxima(TEdge *e); 319 void ProcessHorizontals(); 320 void ProcessHorizontal(TEdge *horzEdge); 321 void AddLocalMaxPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); 322 OutPt* AddLocalMinPoly(TEdge *e1, TEdge *e2, const IntPoint &pt); 323 OutRec* GetOutRec(int idx); 324 void AppendPolygon(TEdge *e1, TEdge *e2); 325 void IntersectEdges(TEdge *e1, TEdge *e2, IntPoint &pt); 326 OutPt* AddOutPt(TEdge *e, const IntPoint &pt); 327 OutPt* GetLastOutPt(TEdge *e); 328 bool ProcessIntersections(const cInt topY); 329 void BuildIntersectList(const cInt topY); 330 void ProcessIntersectList(); 331 void ProcessEdgesAtTopOfScanbeam(const cInt topY); 332 void BuildResult(Paths& polys); 333 void BuildResult2(PolyTree& polytree); 334 void SetHoleState(TEdge *e, OutRec *outrec); 335 void DisposeIntersectNodes(); 336 bool FixupIntersectionOrder(); 337 void FixupOutPolygon(OutRec &outrec); 338 void FixupOutPolyline(OutRec &outrec); 339 bool IsHole(TEdge *e); 340 bool FindOwnerFromSplitRecs(OutRec &outRec, OutRec *&currOrfl); 341 void FixHoleLinkage(OutRec &outrec); 342 void AddJoin(OutPt *op1, OutPt *op2, const IntPoint offPt); 343 void ClearJoins(); 344 void ClearGhostJoins(); 345 void AddGhostJoin(OutPt *op, const IntPoint offPt); 346 bool JoinPoints(Join *j, OutRec* outRec1, OutRec* outRec2); 347 void JoinCommonEdges(); 348 void DoSimplePolygons(); 349 void FixupFirstLefts1(OutRec* OldOutRec, OutRec* NewOutRec); 350 void FixupFirstLefts2(OutRec* InnerOutRec, OutRec* OuterOutRec); 351 void FixupFirstLefts3(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: clipperException(const char * description)392 clipperException(const char* description): m_descr(description) {} ~clipperException()393 virtual ~clipperException() throw() {} what()394 virtual const char* what() const throw() {return m_descr.c_str();} 395 private: 396 std::string m_descr; 397 }; 398 //------------------------------------------------------------------------------ 399 400 } //QtClipperLib namespace 401 402 #endif //clipper_hpp 403 404 405