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