Horizon
shape_poly_set.h
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #ifndef __SHAPE_POLY_SET_H
27 #define __SHAPE_POLY_SET_H
28 
29 #include <vector>
30 #include <cstdio>
31 #include <memory>
32 #include <geometry/shape.h>
33 #include <geometry/shape_line_chain.h>
34 
35 #include "clipper.hpp"
36 
37 #include <md5_hash.h>
38 
39 
56 class SHAPE_POLY_SET : public SHAPE
57 {
58  public:
61  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
62 
64 
66  {
67  public:
68  struct TRI
69  {
70  TRI() : a(0), b(0), c(0)
71  {
72  }
73 
74  int a, b, c;
75  };
76 
78 
79  void Clear();
80 
81  void AllocateVertices( int aSize );
82  void AllocateTriangles ( int aSize );
83 
84  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
85  {
86  auto tri = &m_triangles[ index ];
87  a = m_vertices[ tri->a ];
88  b = m_vertices[ tri->b ];
89  c = m_vertices[ tri->c ];
90  }
91 
92  void SetTriangle( int aIndex, const TRI& aTri )
93  {
94  m_triangles[aIndex] = aTri;
95  }
96 
97  int AddVertex( const VECTOR2I& aP )
98  {
99  m_vertices[ m_vertexCount ] = aP;
100  return (m_vertexCount++);
101  }
102 
103  int GetTriangleCount() const
104  {
105  return m_triangleCount;
106  }
107 
108  int GetVertexCount() const
109  {
110  return m_vertexCount;
111  }
112 
113  private:
114 
115  TRI* m_triangles = nullptr;
116  VECTOR2I* m_vertices = nullptr;
117  int m_vertexCount = 0;
118  int m_triangleCount = 0;
119  };
120 
128  typedef struct VERTEX_INDEX
129  {
130  int m_polygon;
131  int m_contour;
132  int m_vertex;
134  VERTEX_INDEX() : m_polygon(-1), m_contour(-1), m_vertex(-1)
135  {
136  }
137  } VERTEX_INDEX;
138 
144  template <class T>
146  {
147  public:
148 
154  bool IsEndContour() const
155  {
156  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
157  }
158 
163  bool IsLastPolygon() const
164  {
165  return m_currentPolygon == m_lastPolygon;
166  }
167 
168  operator bool() const
169  {
170  return m_currentPolygon <= m_lastPolygon;
171  }
172 
178  void Advance()
179  {
180  // Advance vertex index
181  m_currentVertex ++;
182 
183  // Check whether the user wants to iterate through the vertices of the holes
184  // and behave accordingly
185  if( m_iterateHoles )
186  {
187  // If the last vertex of the contour was reached, advance the contour index
188  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
189  {
190  m_currentVertex = 0;
191  m_currentContour++;
192 
193  // If the last contour of the current polygon was reached, advance the
194  // outline index
195  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
196 
197  if( m_currentContour >= totalContours )
198  {
199  m_currentContour = 0;
200  m_currentPolygon++;
201  }
202  }
203  }
204  else
205  {
206  // If the last vertex of the outline was reached, advance to the following polygon
207  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
208  {
209  m_currentVertex = 0;
210  m_currentPolygon++;
211  }
212  }
213  }
214 
215  void operator++( int dummy )
216  {
217  Advance();
218  }
219 
220  void operator++()
221  {
222  Advance();
223  }
224 
225  T& Get()
226  {
227  return m_poly->Polygon( m_currentPolygon )[m_currentContour].Point( m_currentVertex );
228  }
229 
230  T& operator*()
231  {
232  return Get();
233  }
234 
235  T* operator->()
236  {
237  return &Get();
238  }
239 
245  {
246  VERTEX_INDEX index;
247 
248  index.m_polygon = m_currentPolygon;
249  index.m_contour = m_currentContour;
250  index.m_vertex = m_currentVertex;
251 
252  return index;
253  }
254 
255 
256  private:
257  friend class SHAPE_POLY_SET;
258 
259  SHAPE_POLY_SET* m_poly;
260  int m_currentPolygon;
261  int m_currentContour;
262  int m_currentVertex;
263  int m_lastPolygon;
264  bool m_iterateHoles;
265  };
266 
272  template <class T>
274  {
275  public:
280  bool IsLastPolygon() const
281  {
282  return m_currentPolygon == m_lastPolygon;
283  }
284 
285  operator bool() const
286  {
287  return m_currentPolygon <= m_lastPolygon;
288  }
289 
295  void Advance()
296  {
297  // Advance vertex index
298  m_currentSegment++;
299  int last;
300 
301  // Check whether the user wants to iterate through the vertices of the holes
302  // and behave accordingly
303  if( m_iterateHoles )
304  {
305  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
306 
307  // If the last vertex of the contour was reached, advance the contour index
308  if( m_currentSegment >= last )
309  {
310  m_currentSegment = 0;
311  m_currentContour++;
312 
313  // If the last contour of the current polygon was reached, advance the
314  // outline index
315  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
316 
317  if( m_currentContour >= totalContours )
318  {
319  m_currentContour = 0;
320  m_currentPolygon++;
321  }
322  }
323  }
324  else
325  {
326  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
327  // If the last vertex of the outline was reached, advance to the following
328  // polygon
329  if( m_currentSegment >= last )
330  {
331  m_currentSegment = 0;
332  m_currentPolygon++;
333  }
334  }
335  }
336 
337  void operator++( int dummy )
338  {
339  Advance();
340  }
341 
342  void operator++()
343  {
344  Advance();
345  }
346 
347  T Get()
348  {
349  return m_poly->Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
350  }
351 
352  T operator*()
353  {
354  return Get();
355  }
356 
362  {
363  VERTEX_INDEX index;
364 
365  index.m_polygon = m_currentPolygon;
366  index.m_contour = m_currentContour;
367  index.m_vertex = m_currentSegment;
368 
369  return index;
370  }
371 
380  {
381  // Check that both iterators point to the same contour of the same polygon of the
382  // same polygon set
383  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
384  m_currentContour == aOther.m_currentContour )
385  {
386  // Compute the total number of segments
387  int numSeg;
388  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
389 
390  // Compute the difference of the segment indices. If it is exactly one, they
391  // are adjacent. The only missing case where they also are adjacent is when
392  // the segments are the first and last one, in which case the difference
393  // always equals the total number of segments minus one.
394  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
395 
396  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
397  }
398 
399  return false;
400  }
401 
402  private:
403  friend class SHAPE_POLY_SET;
404 
405  SHAPE_POLY_SET* m_poly;
406  int m_currentPolygon;
407  int m_currentContour;
408  int m_currentSegment;
409  int m_lastPolygon;
410  bool m_iterateHoles;
411  };
412 
413  // Iterator and const iterator types to visit polygon's points.
414  typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR;
415  typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR;
416 
417  // Iterator and const iterator types to visit polygon's edges.
418  typedef SEGMENT_ITERATOR_TEMPLATE<SEG> SEGMENT_ITERATOR;
419  typedef SEGMENT_ITERATOR_TEMPLATE<const SEG> CONST_SEGMENT_ITERATOR;
420 
421  SHAPE_POLY_SET();
422 
428  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
429 
430  ~SHAPE_POLY_SET();
431 
444  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
445 
455  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
456 
458  SHAPE* Clone() const override;
459 
461  int NewOutline();
462 
464  int NewHole( int aOutline = -1 );
465 
467  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
468 
470  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
471 
473 
485  int Append( int x, int y, int aOutline = -1, int aHole = -1,
486  bool aAllowDuplication = false );
487 
489  void Append( const SHAPE_POLY_SET& aSet );
490 
492  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
493 
501  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
502 
504  VECTOR2I& Vertex( int aIndex, int aOutline, int aHole );
505 
507  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
508 
510  VECTOR2I& Vertex( int aGlobalIndex );
511 
513  const VECTOR2I& CVertex( int aGlobalIndex ) const;
514 
516  VECTOR2I& Vertex( VERTEX_INDEX aIndex );
517 
519  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
520 
532  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
533 
534 
542  bool IsPolygonSelfIntersecting( int aPolygonIndex );
543 
549  bool IsSelfIntersecting();
550 
552  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
553 
555  int OutlineCount() const { return m_polys.size(); }
556 
558  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
559 
561  int HoleCount( int aOutline ) const
562  {
563  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
564  return 0;
565 
566  // the first polygon in m_polys[aOutline] is the main contour,
567  // only others are holes:
568  return m_polys[aOutline].size() - 1;
569  }
570 
572  SHAPE_LINE_CHAIN& Outline( int aIndex )
573  {
574  return m_polys[aIndex][0];
575  }
576 
586  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
587 
588  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
589  {
590  return Subset( aPolygonIndex, aPolygonIndex + 1 );
591  }
592 
594  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
595  {
596  return m_polys[aOutline][aHole + 1];
597  }
598 
600  POLYGON& Polygon( int aIndex )
601  {
602  return m_polys[aIndex];
603  }
604 
605  const POLYGON& Polygon( int aIndex ) const
606  {
607  return m_polys[aIndex];
608  }
609 
610  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
611  {
612  return m_triangulatedPolys[aIndex].get();
613  }
614 
615  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
616  {
617  return m_polys[aIndex][0];
618  }
619 
620  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
621  {
622  return m_polys[aOutline][aHole + 1];
623  }
624 
625  const POLYGON& CPolygon( int aIndex ) const
626  {
627  return m_polys[aIndex];
628  }
629 
640  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
641  {
642  ITERATOR iter;
643 
644  iter.m_poly = this;
645  iter.m_currentPolygon = aFirst;
646  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
647  iter.m_currentContour = 0;
648  iter.m_currentVertex = 0;
649  iter.m_iterateHoles = aIterateHoles;
650 
651  return iter;
652  }
653 
660  ITERATOR Iterate( int aOutline )
661  {
662  return Iterate( aOutline, aOutline );
663  }
664 
671  ITERATOR IterateWithHoles( int aOutline )
672  {
673  return Iterate( aOutline, aOutline, true );
674  }
675 
682  {
683  return Iterate( 0, OutlineCount() - 1 );
684  }
685 
692  {
693  return Iterate( 0, OutlineCount() - 1, true );
694  }
695 
696 
697  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
698  {
699  CONST_ITERATOR iter;
700 
701  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
702  iter.m_currentPolygon = aFirst;
703  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
704  iter.m_currentContour = 0;
705  iter.m_currentVertex = 0;
706  iter.m_iterateHoles = aIterateHoles;
707 
708  return iter;
709  }
710 
711  CONST_ITERATOR CIterate( int aOutline ) const
712  {
713  return CIterate( aOutline, aOutline );
714  }
715 
716  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
717  {
718  return CIterate( aOutline, aOutline, true );
719  }
720 
721  CONST_ITERATOR CIterate() const
722  {
723  return CIterate( 0, OutlineCount() - 1 );
724  }
725 
726  CONST_ITERATOR CIterateWithHoles() const
727  {
728  return CIterate( 0, OutlineCount() - 1, true );
729  }
730 
731  ITERATOR IterateFromVertexWithHoles( int aGlobalIdx )
732  {
733  // Build iterator
734  ITERATOR iter = IterateWithHoles();
735 
736  // Get the relative indices of the globally indexed vertex
737  VERTEX_INDEX indices;
738 
739  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
740  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
741 
742  // Adjust where the iterator is pointing
743  iter.m_currentPolygon = indices.m_polygon;
744  iter.m_currentContour = indices.m_contour;
745  iter.m_currentVertex = indices.m_vertex;
746 
747  return iter;
748  }
749 
752  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
753  {
754  SEGMENT_ITERATOR iter;
755 
756  iter.m_poly = this;
757  iter.m_currentPolygon = aFirst;
758  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
759  iter.m_currentContour = 0;
760  iter.m_currentSegment = 0;
761  iter.m_iterateHoles = aIterateHoles;
762 
763  return iter;
764  }
765 
768  {
769  return IterateSegments( aPolygonIdx, aPolygonIdx );
770  }
771 
774  {
775  return IterateSegments( 0, OutlineCount() - 1 );
776  }
777 
780  {
781  return IterateSegments( 0, OutlineCount() - 1, true );
782  }
783 
786  {
787  return IterateSegments( aOutline, aOutline, true );
788  }
789 
798  {
799  PM_FAST = true,
800  PM_STRICTLY_SIMPLE = false
801  };
802 
805  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
806 
809  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
810 
813  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
814 
817  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
818  POLYGON_MODE aFastMode );
819 
822  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
823  POLYGON_MODE aFastMode );
824 
827  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
828  POLYGON_MODE aFastMode );
829 
831  void Inflate( int aFactor, int aCircleSegmentsCount );
832 
836  void Fracture( POLYGON_MODE aFastMode );
837 
840  void Unfracture( POLYGON_MODE aFastMode );
841 
843  bool HasHoles() const;
844 
846  bool HasTouchingHoles() const;
847 
848 
851  void Simplify( POLYGON_MODE aFastMode );
852 
860  int NormalizeAreaOutlines();
861 
863  const std::string Format() const override;
864 
866  bool Parse( std::stringstream& aStream ) override;
867 
869  void Move( const VECTOR2I& aVector ) override;
870 
877  void Rotate( double aAngle, const VECTOR2I& aCenter );
878 
880  bool IsSolid() const override
881  {
882  return true;
883  }
884 
885  const BOX2I BBox( int aClearance = 0 ) const override;
886 
894  bool PointOnEdge( const VECTOR2I& aP ) const;
895 
907  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
908 
921  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
922 
933  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
934  int aClearance = 0 );
935 
946  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
947  int aClearance = 0 );
948 
957  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, bool aIgnoreHoles = false ) const;
958 
960  bool IsEmpty() const
961  {
962  return m_polys.size() == 0;
963  }
964 
970  void RemoveVertex( int aGlobalIndex );
971 
977  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
978 
980  void RemoveAllContours();
981 
990  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
991 
997  int RemoveNullSegments();
998 
1000  int TotalVertices() const;
1001 
1003  void DeletePolygon( int aIdx );
1004 
1012  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex = 0 );
1013 
1022  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex = 0 );
1023 
1030  SHAPE_POLY_SET Chamfer( int aDistance );
1031 
1039  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1040 
1049  int DistanceToPolygon( VECTOR2I aPoint, int aIndex );
1050 
1063  int DistanceToPolygon( SEG aSegment, int aIndex, int aSegmentWidth = 0 );
1064 
1072  int Distance( VECTOR2I aPoint );
1073 
1082  int Distance( const SEG& aSegment, int aSegmentWidth = 0 );
1083 
1090  bool IsVertexInHole( int aGlobalIdx );
1091 
1092  private:
1093 
1094  SHAPE_LINE_CHAIN& getContourForCorner( int aCornerId, int& aIndexWithinContour );
1095  VECTOR2I& vertex( int aCornerId );
1096  const VECTOR2I& cvertex( int aCornerId ) const;
1097 
1098 
1099  void fractureSingle( POLYGON& paths );
1100  void unfractureSingle ( POLYGON& path );
1101  void importTree( ClipperLib::PolyTree* tree );
1102 
1114  void booleanOp( ClipperLib::ClipType aType,
1115  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1116 
1117  void booleanOp( ClipperLib::ClipType aType,
1118  const SHAPE_POLY_SET& aShape,
1119  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1120 
1121  bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const;
1122 
1123  const ClipperLib::Path convertToClipper( const SHAPE_LINE_CHAIN& aPath, bool aRequiredOrientation );
1124  const SHAPE_LINE_CHAIN convertFromClipper( const ClipperLib::Path& aPath );
1125 
1138  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles = false ) const;
1139 
1145  enum CORNER_MODE
1146  {
1147  CHAMFERED,
1148  FILLETED
1149  };
1150 
1151 
1152 
1167  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1168  int aIndex, int aErrorMax = -1 );
1169 
1171  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1172 
1173  typedef std::vector<POLYGON> POLYSET;
1174 
1175  POLYSET m_polys;
1176 
1177  public:
1178 
1179  SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& );
1180 
1181  void CacheTriangulation();
1182  bool IsTriangulationUpToDate() const;
1183 
1184  MD5_HASH GetHash() const;
1185 
1186  private:
1187  void triangulateSingle( const POLYGON& aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON& aResult );
1188 
1189  MD5_HASH checksum() const;
1190 
1191  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1192  bool m_triangulationValid = false;
1193  MD5_HASH m_hash;
1194 
1195 };
1196 
1197 #endif
SHAPE_POLY_SET::ITERATOR_TEMPLATE::IsEndContour
bool IsEndContour() const
Function IsEndContour.
Definition: shape_poly_set.h:154
SHAPE_POLY_SET::IterateWithHoles
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Definition: shape_poly_set.h:691
SHAPE_POLY_SET::Distance
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
Definition: shape_poly_set.cpp:1619
SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE::IsAdjacent
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
Definition: shape_poly_set.h:379
SHAPE_POLY_SET::IsSelfIntersecting
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
Definition: shape_poly_set.cpp:416
SHAPE_POLY_SET::Move
void Move(const VECTOR2I &aVector) override
Definition: shape_poly_set.cpp:1504
SHAPE_POLY_SET::IsSolid
bool IsSolid() const override
Definition: shape_poly_set.h:880
SHAPE_POLY_SET::RemoveNullSegments
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
Definition: shape_poly_set.cpp:1295
ClipperLib::PolyTree
Definition: clipper.hpp:158
SHAPE_POLY_SET::BBox
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_poly_set.cpp:1198
SHAPE_POLY_SET::VERTEX_INDEX::m_polygon
int m_polygon
Definition: shape_poly_set.h:130
SHAPE_POLY_SET::InsertVertex
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
Definition: shape_poly_set.cpp:206
SHAPE_POLY_SET::BooleanSubtract
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:554
SHAPE_POLY_SET::TRIANGULATED_POLYGON
Definition: shape_poly_set.h:65
SHAPE_POLY_SET::IterateSegments
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...
Definition: shape_poly_set.h:752
SHAPE_POLY_SET::ITERATOR_TEMPLATE
Class ITERATOR_TEMPLATE.
Definition: shape_poly_set.h:145
SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE::GetIndex
VERTEX_INDEX GetIndex()
Function GetIndex.
Definition: shape_poly_set.h:361
SHAPE_POLY_SET::ITERATOR_TEMPLATE::GetIndex
VERTEX_INDEX GetIndex()
Function GetIndex.
Definition: shape_poly_set.h:244
SHAPE_POLY_SET::IsVertexInHole
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
Definition: shape_poly_set.cpp:1655
SHAPE_POLY_SET::ITERATOR_TEMPLATE::Advance
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Definition: shape_poly_set.h:178
SHAPE_POLY_SET::TRIANGULATION_CONTEXT
Definition: shape_poly_set.cpp:1866
SHAPE_POLY_SET::GetRelativeIndices
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
Definition: shape_poly_set.cpp:73
SHAPE_POLY_SET::Fracture
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
Definition: shape_poly_set.cpp:875
SHAPE_POLY_SET::RemoveVertex
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
Definition: shape_poly_set.cpp:1454
SHAPE_POLY_SET::Inflate
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
Definition: shape_poly_set.cpp:590
SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE::Advance
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Definition: shape_poly_set.h:295
SHAPE_POLY_SET::GetNeighbourIndexes
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a con...
Definition: shape_poly_set.cpp:342
SHAPE_POLY_SET::Vertex
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
Definition: shape_poly_set.cpp:268
SHAPE_POLY_SET::NewHole
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
Definition: shape_poly_set.cpp:168
SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE
Class SEGMENT_ITERATOR_TEMPLATE.
Definition: shape_poly_set.h:273
SHAPE_POLY_SET::VERTEX_INDEX
Struct VERTEX_INDEX.
Definition: shape_poly_set.h:128
SHAPE_POLY_SET::Rotate
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
Definition: shape_poly_set.cpp:1516
SHAPE_POLY_SET::Contains
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
Definition: shape_poly_set.cpp:1434
SHAPE_POLY_SET::IterateSegmentsWithHoles
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Returns an iterator object, for the aOutline-th outline in the set (with holes)
Definition: shape_poly_set.h:785
SHAPE_POLY_SET::RemoveAllContours
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
Definition: shape_poly_set.cpp:1279
SHAPE_POLY_SET::VERTEX_INDEX::m_contour
int m_contour
Definition: shape_poly_set.h:131
SHAPE_POLY_SET::Append
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
Definition: shape_poly_set.cpp:185
SHAPE_POLY_SET::TotalVertices
int TotalVertices() const
Returns total number of vertices stored in the set.
Definition: shape_poly_set.cpp:1528
VECTOR2< int >
SHAPE_POLY_SET::IterateSegments
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
Definition: shape_poly_set.h:773
SHAPE_POLY_SET::ChamferPolygon
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1544
SHAPE_POLY_SET::Iterate
ITERATOR Iterate(int aOutline)
Function Iterate.
Definition: shape_poly_set.h:660
SHAPE_POLY_SET::Unfracture
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
Definition: shape_poly_set.cpp:1062
SHAPE_POLY_SET::POLYGON_MODE
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
Definition: shape_poly_set.h:797
SHAPE_POLY_SET::Collide
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
Definition: shape_poly_set.cpp:1263
SHAPE_POLY_SET::VertexCount
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
Definition: shape_poly_set.cpp:228
SHAPE_POLY_SET::NewOutline
int NewOutline()
Creates a new empty polygon in the set and returns its index
Definition: shape_poly_set.cpp:156
SHAPE_POLY_SET::Subset
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
Definition: shape_poly_set.cpp:253
SHAPE_POLY_SET::HoleCount
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
Definition: shape_poly_set.h:561
SHAPE_POLY_SET::OutlineCount
int OutlineCount() const
Returns the number of outlines in the set
Definition: shape_poly_set.h:555
SHAPE_POLY_SET::RemoveContour
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
Definition: shape_poly_set.cpp:1285
SHAPE_POLY_SET::ITERATOR_TEMPLATE::IsLastPolygon
bool IsLastPolygon() const
Function IsLastOutline.
Definition: shape_poly_set.h:163
SHAPE_POLY_SET::DeletePolygon
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
Definition: shape_poly_set.cpp:1348
SHAPE_POLY_SET::PointOnEdge
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Definition: shape_poly_set.cpp:1215
SHAPE_POLY_SET::IsEmpty
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
Definition: shape_poly_set.h:960
SHAPE_POLY_SET::Polygon
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
Definition: shape_poly_set.h:600
SHAPE_POLY_SET::FilletPolygon
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1550
SHAPE_POLY_SET::HasTouchingHoles
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
Definition: shape_poly_set.cpp:2121
SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI
Definition: shape_poly_set.h:68
SHAPE_POLY_SET::BooleanAdd
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:548
SHAPE_POLY_SET::Clone
SHAPE * Clone() const override
Function Clone()
Definition: shape_poly_set.cpp:67
BOX2< VECTOR2I >
SHAPE_POLY_SET::POLYGON
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
Definition: shape_poly_set.h:61
SHAPE_POLY_SET::Iterate
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Function Iterate returns an object to iterate through the points of the polygons between aFirst and a...
Definition: shape_poly_set.h:640
SEG
Definition: seg.h:36
SHAPE_POLY_SET::IterateWithHoles
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
Definition: shape_poly_set.h:671
SHAPE_POLY_SET::BooleanIntersection
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
Definition: shape_poly_set.cpp:560
SHAPE_POLY_SET::Simplify
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Definition: shape_poly_set.cpp:1073
SHAPE_POLY_SET::IterateSegments
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
Definition: shape_poly_set.h:767
SHAPE_POLY_SET::Parse
bool Parse(std::stringstream &aStream) override
Definition: shape_poly_set.cpp:1139
SHAPE_POLY_SET::IterateSegmentsWithHoles
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
Definition: shape_poly_set.h:779
SHAPE_POLY_SET::VERTEX_INDEX::m_vertex
int m_vertex
Definition: shape_poly_set.h:132
SHAPE_POLY_SET::IsPolygonSelfIntersecting
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
Definition: shape_poly_set.cpp:389
SHAPE_POLY_SET::VERTEX_INDEX
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
SHAPE_POLY_SET::CVertex
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
Definition: shape_poly_set.cpp:287
SHAPE_POLY_SET::Fillet
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
Definition: shape_poly_set.cpp:1679
SHAPE_POLY_SET::DistanceToPolygon
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
Definition: shape_poly_set.cpp:1558
SHAPE_POLY_SET::CollideEdge
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
Definition: shape_poly_set.cpp:1404
SHAPE_POLY_SET::AddOutline
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
Definition: shape_poly_set.cpp:428
SHAPE_POLY_SET::CollideVertex
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
Definition: shape_poly_set.cpp:1366
SHAPE_LINE_CHAIN
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:47
SHAPE_POLY_SET::Iterate
ITERATOR Iterate()
Function Iterate.
Definition: shape_poly_set.h:681
SHAPE
Class SHAPE.
Definition: shape.h:58
SHAPE_POLY_SET::Outline
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
Definition: shape_poly_set.h:572
SHAPE_POLY_SET::Chamfer
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
Definition: shape_poly_set.cpp:1668
SHAPE_POLY_SET::GetGlobalIndex
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
Definition: shape_poly_set.cpp:113
SHAPE_POLY_SET::Format
const std::string Format() const override
Definition: shape_poly_set.cpp:1114
SHAPE_POLY_SET::Hole
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
Definition: shape_poly_set.h:594
SHAPE_POLY_SET::HasHoles
bool HasHoles() const
Returns true if the polygon set has any holes.
Definition: shape_poly_set.cpp:1047
SHAPE_POLY_SET::SEGMENT_ITERATOR_TEMPLATE::IsLastPolygon
bool IsLastPolygon() const
Function IsLastOutline.
Definition: shape_poly_set.h:280
SHAPE_POLY_SET::NormalizeAreaOutlines
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
Definition: shape_poly_set.cpp:1081
SHAPE_POLY_SET::AddHole
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
Definition: shape_poly_set.cpp:442
SHAPE_POLY_SET::TriangulatedPolyCount
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
Definition: shape_poly_set.h:552
SHAPE_POLY_SET
Class SHAPE_POLY_SET.
Definition: shape_poly_set.h:56