Horizon
Loading...
Searching...
No Matches
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
63namespace ClipperLibKiCad {
64enum ClipType
65{
66 ctIntersection, ctUnion, ctDifference, ctXor
67};
68enum 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
76enum PolyFillType
77{
78 pftEvenOdd, pftNonZero, pftPositive, pftNegative
79};
80
81#ifdef use_int32
82typedef int cInt;
83static cInt const loRange = 0x7FFF;
84static cInt const hiRange = 0x7FFF;
85#else
86typedef signed long long cInt;
87static cInt const loRange = 0x3FFFFFFF;
88static cInt const hiRange = 0x3FFFFFFFFFFFFFFFLL;
89typedef signed long long long64; // used by Int128 class
90typedef unsigned long long ulong64;
91
92#endif
93
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
117typedef std::vector<IntPoint> Path;
118typedef std::vector<Path> Paths;
119
120inline Path& operator <<( Path& poly, const IntPoint& p )
121{
122 poly.push_back( p ); return poly;
123}
124
125
126inline Paths& operator <<( Paths& polys, const Path& p )
127{
128 polys.push_back( p ); return polys;
129}
130
131
132std::ostream& operator <<( std::ostream& s, const IntPoint& p );
133std::ostream& operator <<( std::ostream& s, const Path& p );
134std::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
146typedef std::function<void( IntPoint& e1bot, IntPoint& e1top, IntPoint& e2bot, IntPoint& e2top,
147 IntPoint& pt )> ZFillCallback;
148#endif
149
150enum InitOptions
151{
152 ioReverseSolution = 1, ioStrictlySimple = 2, ioPreserveCollinear = 4
153};
154enum JoinType
155{
156 jtSquare, jtRound, jtMiter
157};
158enum EndType
159{
160 etClosedPolygon, etClosedLine, etOpenButt, etOpenSquare, etOpenRound
161};
162
163class PolyNode;
164typedef std::vector<PolyNode*> PolyNodes;
165
167{
168public:
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
179private:
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
192class PolyTree : public PolyNode
193{
194public:
195 ~PolyTree() { Clear(); };
196 PolyNode* GetFirst() const;
197 void Clear();
198 int Total() const;
199
200private:
201 // PolyTree& operator =(PolyTree& other);
202 PolyNodes AllNodes;
203 friend class Clipper; // to access AllNodes
204};
205
206bool Orientation( const Path& poly );
207double Area( const Path& poly );
208int PointInPolygon( const IntPoint& pt, const Path& path );
209
210void SimplifyPolygon( const Path& in_poly, Paths& out_polys,
211 PolyFillType fillType = pftEvenOdd );
212void SimplifyPolygons( const Paths& in_polys,
213 Paths& out_polys,
214 PolyFillType fillType = pftEvenOdd );
215void SimplifyPolygons( Paths& polys, PolyFillType fillType = pftEvenOdd );
216
217void CleanPolygon( const Path& in_poly, Path& out_poly, double distance = 1.415 );
218void CleanPolygon( Path& poly, double distance = 1.415 );
219void CleanPolygons( const Paths& in_polys, Paths& out_polys, double distance = 1.415 );
220void CleanPolygons( Paths& polys, double distance = 1.415 );
221
222void MinkowskiSum( const Path& pattern, const Path& path, Paths& solution, bool pathIsClosed );
223void MinkowskiSum( const Path& pattern, const Paths& paths, Paths& solution, bool pathIsClosed );
224void MinkowskiDiff( const Path& poly1, const Path& poly2, Paths& solution );
225
226void PolyTreeToPaths( const PolyTree& polytree, Paths& paths );
227void ClosedPathsFromPolyTree( const PolyTree& polytree, Paths& paths );
228void OpenPathsFromPolyTree( PolyTree& polytree, Paths& paths );
229
230void ReversePath( Path& p );
231void ReversePaths( Paths& p );
232
234{
235 cInt left; cInt top; cInt right; cInt bottom;
236};
237
238// enums that are used internally ...
239enum EdgeSide
240{
241 esLeft = 1, esRight = 2
242};
243
244// forward declarations (for stuff used internally) ...
245struct TEdge;
246struct IntersectNode;
247struct LocalMinimum;
248struct OutPt;
249struct OutRec;
250struct Join;
251
252typedef std::vector <OutRec*> PolyOutList;
253typedef std::vector <TEdge*> EdgeList;
254typedef std::vector <Join*> JoinList;
255typedef 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{
264public:
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
275protected:
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
307class Clipper : public virtual ClipperBase
308{
309public:
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
336protected:
337 virtual bool ExecuteInternal();
338
339private:
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{
412public:
413 ClipperOffset( double miterLimit = 2.0, double roundPrecision = 0.25 );
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
425private:
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
444class clipperException : public std::exception
445{
446public:
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
451private:
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