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