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