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