KiCad PCB EDA Suite
shape_poly_set.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2019 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>
34 
35 #include <md5_hash.h>
36 
37 
54 class SHAPE_POLY_SET : public SHAPE
55 {
56  public:
60  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
61 
63  {
64  public:
65  struct TRI
66  {
67  TRI( int _a = 0, int _b = 0, int _c = 0 ) : a( _a ), b( _b ), c( _c )
68  {
69  }
70 
71  int a, b, c;
72  };
73 
74  void Clear()
75  {
76  m_vertices.clear();
77  m_triangles.clear();
78  }
79 
80  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
81  {
82  auto tri = m_triangles[ index ];
83  a = m_vertices[ tri.a ];
84  b = m_vertices[ tri.b ];
85  c = m_vertices[ tri.c ];
86  }
87 
88  void AddTriangle( const TRI& aTri )
89  {
90  m_triangles.push_back( aTri );
91  }
92 
93  void AddTriangle( int a, int b, int c )
94  {
95  m_triangles.emplace_back( a, b, c );
96  }
97 
98  void AddVertex( const VECTOR2I& aP )
99  {
100  m_vertices.push_back( aP );
101  }
102 
103  size_t GetTriangleCount() const
104  {
105  return m_triangles.size();
106  }
107 
108  size_t GetVertexCount() const
109  {
110  return m_vertices.size();
111  }
112 
113  private:
114 
115  std::deque<TRI> m_triangles;
116  std::deque<VECTOR2I> m_vertices;
117  };
118 
126  typedef struct VERTEX_INDEX
127  {
128  int m_polygon;
129  int m_contour;
130  int m_vertex;
133  {
134  }
135  } VERTEX_INDEX;
136 
142  template <class T>
144  {
145  public:
146 
152  bool IsEndContour() const
153  {
154  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
155  }
156 
161  bool IsLastPolygon() const
162  {
164  }
165 
166  operator bool() const
167  {
169  return true;
170 
171  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
172  return false;
173 
174  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
175 
176  return m_currentContour < (int) currentPolygon.size() - 1
177  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
178  }
179 
185  void Advance()
186  {
187  // Advance vertex index
188  m_currentVertex ++;
189 
190  // Check whether the user wants to iterate through the vertices of the holes
191  // and behave accordingly
192  if( m_iterateHoles )
193  {
194  // If the last vertex of the contour was reached, advance the contour index
196  {
197  m_currentVertex = 0;
199 
200  // If the last contour of the current polygon was reached, advance the
201  // outline index
202  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
203 
204  if( m_currentContour >= totalContours )
205  {
206  m_currentContour = 0;
208  }
209  }
210  }
211  else
212  {
213  // If the last vertex of the outline was reached, advance to the following polygon
214  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
215  {
216  m_currentVertex = 0;
218  }
219  }
220  }
221 
222  void operator++( int dummy )
223  {
224  Advance();
225  }
226 
227  void operator++()
228  {
229  Advance();
230  }
231 
232  const T& Get()
233  {
234  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint(
235  m_currentVertex );
236  }
237 
238  const T& operator*()
239  {
240  return Get();
241  }
242 
243  const T* operator->()
244  {
245  return &Get();
246  }
247 
253  {
254  VERTEX_INDEX index;
255 
256  index.m_polygon = m_currentPolygon;
257  index.m_contour = m_currentContour;
258  index.m_vertex = m_currentVertex;
259 
260  return index;
261  }
262 
263 
264  private:
265  friend class SHAPE_POLY_SET;
266 
273  };
274 
280  template <class T>
282  {
283  public:
288  bool IsLastPolygon() const
289  {
291  }
292 
293  operator bool() const
294  {
296  }
297 
303  void Advance()
304  {
305  // Advance vertex index
307  int last;
308 
309  // Check whether the user wants to iterate through the vertices of the holes
310  // and behave accordingly
311  if( m_iterateHoles )
312  {
313  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
314 
315  // If the last vertex of the contour was reached, advance the contour index
316  if( m_currentSegment >= last )
317  {
318  m_currentSegment = 0;
320 
321  // If the last contour of the current polygon was reached, advance the
322  // outline index
323  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
324 
325  if( m_currentContour >= totalContours )
326  {
327  m_currentContour = 0;
329  }
330  }
331  }
332  else
333  {
334  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
335  // If the last vertex of the outline was reached, advance to the following
336  // polygon
337  if( m_currentSegment >= last )
338  {
339  m_currentSegment = 0;
341  }
342  }
343  }
344 
345  void operator++( int dummy )
346  {
347  Advance();
348  }
349 
350  void operator++()
351  {
352  Advance();
353  }
354 
355  T Get()
356  {
358  }
359 
361  {
362  return Get();
363  }
364 
370  {
371  VERTEX_INDEX index;
372 
373  index.m_polygon = m_currentPolygon;
374  index.m_contour = m_currentContour;
375  index.m_vertex = m_currentSegment;
376 
377  return index;
378  }
379 
388  {
389  // Check that both iterators point to the same contour of the same polygon of the
390  // same polygon set
391  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
393  {
394  // Compute the total number of segments
395  int numSeg;
396  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
397 
398  // Compute the difference of the segment indices. If it is exactly one, they
399  // are adjacent. The only missing case where they also are adjacent is when
400  // the segments are the first and last one, in which case the difference
401  // always equals the total number of segments minus one.
402  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
403 
404  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
405  }
406 
407  return false;
408  }
409 
410  private:
411  friend class SHAPE_POLY_SET;
412 
419  };
420 
421  // Iterator and const iterator types to visit polygon's points.
424 
425  // Iterator and const iterator types to visit polygon's edges.
428 
429  SHAPE_POLY_SET();
430 
437  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, bool aDeepCopy = false );
438 
439  ~SHAPE_POLY_SET();
440 
453  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
454 
464  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
465 
467  SHAPE* Clone() const override;
468 
470  int NewOutline();
471 
473  int NewHole( int aOutline = -1 );
474 
476  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
477 
479  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
480 
482 
494  int Append( int x, int y, int aOutline = -1, int aHole = -1,
495  bool aAllowDuplication = false );
496 
498  void Append( const SHAPE_POLY_SET& aSet );
499 
501  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
502 
510  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
511 
513  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
514 
516  const VECTOR2I& CVertex( int aGlobalIndex ) const;
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 ) const;
543 
549  bool IsSelfIntersecting() const;
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 
722  {
723  return CIterate( 0, OutlineCount() - 1 );
724  }
725 
727  {
728  return CIterate( 0, OutlineCount() - 1, true );
729  }
730 
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  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
769  bool aIterateHoles = false ) const
770  {
772 
773  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
774  iter.m_currentPolygon = aFirst;
775  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
776  iter.m_currentContour = 0;
777  iter.m_currentSegment = 0;
778  iter.m_iterateHoles = aIterateHoles;
779 
780  return iter;
781  }
782 
785  {
786  return IterateSegments( aPolygonIdx, aPolygonIdx );
787  }
788 
790  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
791  {
792  return CIterateSegments( aPolygonIdx, aPolygonIdx );
793  }
794 
797  {
798  return IterateSegments( 0, OutlineCount() - 1 );
799  }
800 
803  {
804  return IterateSegments( 0, OutlineCount() - 1, true );
805  }
806 
809  {
810  return IterateSegments( aOutline, aOutline, true );
811  }
812 
815  {
816  return CIterateSegments( aOutline, aOutline, true );
817  }
818 
827  {
828  PM_FAST = true,
830  };
831 
834  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
835 
838  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
839 
842  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
843 
846  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
847  POLYGON_MODE aFastMode );
848 
851  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
852  POLYGON_MODE aFastMode );
853 
856  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
857  POLYGON_MODE aFastMode );
858 
860  {
865  };
866 
879  void Inflate( int aAmount, int aCircleSegmentsCount,
880  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
881 
882  void Deflate( int aAmount, int aCircleSegmentsCount,
883  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
884  {
885  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
886  }
887 
893  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
894 
898  void Fracture( POLYGON_MODE aFastMode );
899 
902  void Unfracture( POLYGON_MODE aFastMode );
903 
905  bool HasHoles() const;
906 
908  bool HasTouchingHoles() const;
909 
910 
913  void Simplify( POLYGON_MODE aFastMode );
914 
922  int NormalizeAreaOutlines();
923 
925  const std::string Format() const override;
926 
928  bool Parse( std::stringstream& aStream ) override;
929 
931  void Move( const VECTOR2I& aVector ) override;
932 
939  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
940 
947  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } );
948 
950  bool IsSolid() const override
951  {
952  return true;
953  }
954 
955  const BOX2I BBox( int aClearance = 0 ) const override;
956 
964  bool PointOnEdge( const VECTOR2I& aP ) const;
965 
977  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
978 
991  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
992 
1003  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1004  int aClearance = 0 );
1005 
1016  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1017  int aClearance = 0 );
1018 
1023  void BuildBBoxCaches();
1024 
1035  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1036  bool aUseBBoxCaches = false ) const;
1037 
1039  bool IsEmpty() const
1040  {
1041  return m_polys.size() == 0;
1042  }
1043 
1049  void RemoveVertex( int aGlobalIndex );
1050 
1056  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1057 
1059  void RemoveAllContours();
1060 
1069  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1070 
1076  int RemoveNullSegments();
1077 
1084  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1085 
1092  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1093 
1095  int TotalVertices() const;
1096 
1098  void DeletePolygon( int aIdx );
1099 
1108  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex,
1109  std::set<VECTOR2I>* aPreserveCorners );
1110 
1120  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex,
1121  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1122 
1130  SHAPE_POLY_SET Chamfer( int aDistance,
1131  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1132 
1141  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax,
1142  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1143 
1152  int DistanceToPolygon( VECTOR2I aPoint, int aIndex );
1153 
1166  int DistanceToPolygon( const SEG& aSegment, int aIndex, int aSegmentWidth = 0 );
1167 
1175  int Distance( VECTOR2I aPoint );
1176 
1185  int Distance( const SEG& aSegment, int aSegmentWidth = 0 );
1186 
1193  bool IsVertexInHole( int aGlobalIdx );
1194 
1195  private:
1196  void fractureSingle( POLYGON& paths );
1197  void unfractureSingle ( POLYGON& path );
1198  void importTree( ClipperLib::PolyTree* tree );
1199 
1211  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1212  POLYGON_MODE aFastMode );
1213 
1214  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1215  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1216 
1217  bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath,
1218  bool aIgnoreEdges, bool aUseBBoxCaches = false ) const;
1219 
1235  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1236  bool aUseBBoxCaches = false ) const;
1237 
1244  {
1247  };
1248 
1264  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1265  int aIndex, int aErrorMax,
1266  std::set<VECTOR2I>* aPreserveCorners );
1267 
1269  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1270 
1271  typedef std::vector<POLYGON> POLYSET;
1272 
1274 
1275  public:
1276 
1278 
1279  void CacheTriangulation();
1280  bool IsTriangulationUpToDate() const;
1281 
1282  MD5_HASH GetHash() const;
1283 
1284  private:
1285 
1286  MD5_HASH checksum() const;
1287 
1288  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1289  bool m_triangulationValid = false;
1291 
1292 };
1293 
1294 #endif
int TotalVertices() const
Returns total number of vertices stored in the set.
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 })
Function Rotate rotates all vertices by a given angle.
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
const POLYGON & CPolygon(int aIndex) const
int OutlineCount() const
Returns the number of outlines in the set
bool IsEndContour() const
Function IsEndContour.
void fractureSingle(POLYGON &paths)
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
ITERATOR Iterate(int aOutline)
Function Iterate.
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...
void GetTriangle(int index, VECTOR2I &a, VECTOR2I &b, VECTOR2I &c) const
std::vector< POLYGON > POLYSET
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
bool IsSolid() const override
Class VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Returns true if the polygon set has any holes.
CONST_ITERATOR CIterateWithHoles(int aOutline) const
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Struct VERTEX_INDEX.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
MD5_HASH checksum() const
Class SEGMENT_ITERATOR_TEMPLATE.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
ITERATOR Iterate()
Function Iterate.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Returns true if a given subpolygon contains the point aP.
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...
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
#define abs(a)
Definition: auxiliary.h:84
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool IsTriangulationUpToDate() const
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
bool IsLastPolygon() const
Function IsLastOutline.
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
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...
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath, bool aIgnoreEdges, bool aUseBBoxCaches=false) const
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Function SetVertex Accessor function to set the position of a specific point.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
Class SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
void Deflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
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...
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Returns an iterator object, for the aOutline-th outline in the set (with holes)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Class SHAPE.
Definition: shape.h:58
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...
const std::string Format() const override
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int NewOutline()
Creates a new empty polygon in the set and returns its index
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void BuildBBoxCaches()
Constructs BBoxCaches for Contains(), below.
const POLYGON & Polygon(int aIndex) const
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the polygon set.
Definition: seg.h:36
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex, std::set< VECTOR2I > *aPreserveCorners)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
void AddVertex(const VECTOR2I &aP)
void AddTriangle(int a, int b, int c)
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
TRI(int _a=0, int _b=0, int _c=0)
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Class SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the aIndex-th polygon.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
Class ITERATOR_TEMPLATE.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
CONST_ITERATOR CIterate() const
SHAPE_POLY_SET Chamfer(int aDistance, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Chamfer returns a chamfered version of the polygon set.
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
CONST_ITERATOR CIterate(int aOutline) const
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
SHAPE * Clone() const override
Function Clone()
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
VERTEX_INDEX GetIndex()
Function GetIndex.
CONST_ITERATOR CIterateWithHoles() const
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...
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...
bool IsSelfIntersecting() const
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
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)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
bool IsLastPolygon() const
Function IsLastOutline.