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  T& Get()
233  {
235  }
236 
238  {
239  return Get();
240  }
241 
243  {
244  return &Get();
245  }
246 
252  {
253  VERTEX_INDEX index;
254 
255  index.m_polygon = m_currentPolygon;
256  index.m_contour = m_currentContour;
257  index.m_vertex = m_currentVertex;
258 
259  return index;
260  }
261 
262 
263  private:
264  friend class SHAPE_POLY_SET;
265 
272  };
273 
279  template <class T>
281  {
282  public:
287  bool IsLastPolygon() const
288  {
290  }
291 
292  operator bool() const
293  {
295  }
296 
302  void Advance()
303  {
304  // Advance vertex index
306  int last;
307 
308  // Check whether the user wants to iterate through the vertices of the holes
309  // and behave accordingly
310  if( m_iterateHoles )
311  {
312  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
313 
314  // If the last vertex of the contour was reached, advance the contour index
315  if( m_currentSegment >= last )
316  {
317  m_currentSegment = 0;
319 
320  // If the last contour of the current polygon was reached, advance the
321  // outline index
322  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
323 
324  if( m_currentContour >= totalContours )
325  {
326  m_currentContour = 0;
328  }
329  }
330  }
331  else
332  {
333  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
334  // If the last vertex of the outline was reached, advance to the following
335  // polygon
336  if( m_currentSegment >= last )
337  {
338  m_currentSegment = 0;
340  }
341  }
342  }
343 
344  void operator++( int dummy )
345  {
346  Advance();
347  }
348 
349  void operator++()
350  {
351  Advance();
352  }
353 
354  T Get()
355  {
357  }
358 
360  {
361  return Get();
362  }
363 
369  {
370  VERTEX_INDEX index;
371 
372  index.m_polygon = m_currentPolygon;
373  index.m_contour = m_currentContour;
374  index.m_vertex = m_currentSegment;
375 
376  return index;
377  }
378 
387  {
388  // Check that both iterators point to the same contour of the same polygon of the
389  // same polygon set
390  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
392  {
393  // Compute the total number of segments
394  int numSeg;
395  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
396 
397  // Compute the difference of the segment indices. If it is exactly one, they
398  // are adjacent. The only missing case where they also are adjacent is when
399  // the segments are the first and last one, in which case the difference
400  // always equals the total number of segments minus one.
401  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
402 
403  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
404  }
405 
406  return false;
407  }
408 
409  private:
410  friend class SHAPE_POLY_SET;
411 
418  };
419 
420  // Iterator and const iterator types to visit polygon's points.
423 
424  // Iterator and const iterator types to visit polygon's edges.
427 
428  SHAPE_POLY_SET();
429 
436  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, bool aDeepCopy = false );
437 
438  ~SHAPE_POLY_SET();
439 
452  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
453 
463  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
464 
466  SHAPE* Clone() const override;
467 
469  int NewOutline();
470 
472  int NewHole( int aOutline = -1 );
473 
475  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
476 
478  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
479 
481 
493  int Append( int x, int y, int aOutline = -1, int aHole = -1,
494  bool aAllowDuplication = false );
495 
497  void Append( const SHAPE_POLY_SET& aSet );
498 
500  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
501 
509  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
510 
512  VECTOR2I& Vertex( int aIndex, int aOutline, int aHole );
513 
515  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
516 
518  VECTOR2I& Vertex( int aGlobalIndex );
519 
521  const VECTOR2I& CVertex( int aGlobalIndex ) const;
522 
524  VECTOR2I& Vertex( VERTEX_INDEX aIndex );
525 
527  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
528 
540  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
541 
542 
550  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
551 
557  bool IsSelfIntersecting() const;
558 
560  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
561 
563  int OutlineCount() const { return m_polys.size(); }
564 
566  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
567 
569  int HoleCount( int aOutline ) const
570  {
571  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
572  return 0;
573 
574  // the first polygon in m_polys[aOutline] is the main contour,
575  // only others are holes:
576  return m_polys[aOutline].size() - 1;
577  }
578 
580  SHAPE_LINE_CHAIN& Outline( int aIndex )
581  {
582  return m_polys[aIndex][0];
583  }
584 
594  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
595 
596  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
597  {
598  return Subset( aPolygonIndex, aPolygonIndex + 1 );
599  }
600 
602  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
603  {
604  return m_polys[aOutline][aHole + 1];
605  }
606 
608  POLYGON& Polygon( int aIndex )
609  {
610  return m_polys[aIndex];
611  }
612 
613  const POLYGON& Polygon( int aIndex ) const
614  {
615  return m_polys[aIndex];
616  }
617 
618  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
619  {
620  return m_triangulatedPolys[aIndex].get();
621  }
622 
623  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
624  {
625  return m_polys[aIndex][0];
626  }
627 
628  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
629  {
630  return m_polys[aOutline][aHole + 1];
631  }
632 
633  const POLYGON& CPolygon( int aIndex ) const
634  {
635  return m_polys[aIndex];
636  }
637 
648  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
649  {
650  ITERATOR iter;
651 
652  iter.m_poly = this;
653  iter.m_currentPolygon = aFirst;
654  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
655  iter.m_currentContour = 0;
656  iter.m_currentVertex = 0;
657  iter.m_iterateHoles = aIterateHoles;
658 
659  return iter;
660  }
661 
668  ITERATOR Iterate( int aOutline )
669  {
670  return Iterate( aOutline, aOutline );
671  }
672 
679  ITERATOR IterateWithHoles( int aOutline )
680  {
681  return Iterate( aOutline, aOutline, true );
682  }
683 
690  {
691  return Iterate( 0, OutlineCount() - 1 );
692  }
693 
700  {
701  return Iterate( 0, OutlineCount() - 1, true );
702  }
703 
704 
705  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
706  {
707  CONST_ITERATOR iter;
708 
709  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
710  iter.m_currentPolygon = aFirst;
711  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
712  iter.m_currentContour = 0;
713  iter.m_currentVertex = 0;
714  iter.m_iterateHoles = aIterateHoles;
715 
716  return iter;
717  }
718 
719  CONST_ITERATOR CIterate( int aOutline ) const
720  {
721  return CIterate( aOutline, aOutline );
722  }
723 
724  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
725  {
726  return CIterate( aOutline, aOutline, true );
727  }
728 
730  {
731  return CIterate( 0, OutlineCount() - 1 );
732  }
733 
735  {
736  return CIterate( 0, OutlineCount() - 1, true );
737  }
738 
740  {
741  // Build iterator
742  ITERATOR iter = IterateWithHoles();
743 
744  // Get the relative indices of the globally indexed vertex
745  VERTEX_INDEX indices;
746 
747  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
748  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
749 
750  // Adjust where the iterator is pointing
751  iter.m_currentPolygon = indices.m_polygon;
752  iter.m_currentContour = indices.m_contour;
753  iter.m_currentVertex = indices.m_vertex;
754 
755  return iter;
756  }
757 
760  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
761  {
762  SEGMENT_ITERATOR iter;
763 
764  iter.m_poly = this;
765  iter.m_currentPolygon = aFirst;
766  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
767  iter.m_currentContour = 0;
768  iter.m_currentSegment = 0;
769  iter.m_iterateHoles = aIterateHoles;
770 
771  return iter;
772  }
773 
776  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
777  bool aIterateHoles = false ) const
778  {
780 
781  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
782  iter.m_currentPolygon = aFirst;
783  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
784  iter.m_currentContour = 0;
785  iter.m_currentSegment = 0;
786  iter.m_iterateHoles = aIterateHoles;
787 
788  return iter;
789  }
790 
793  {
794  return IterateSegments( aPolygonIdx, aPolygonIdx );
795  }
796 
798  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
799  {
800  return CIterateSegments( aPolygonIdx, aPolygonIdx );
801  }
802 
805  {
806  return IterateSegments( 0, OutlineCount() - 1 );
807  }
808 
811  {
812  return IterateSegments( 0, OutlineCount() - 1, true );
813  }
814 
817  {
818  return IterateSegments( aOutline, aOutline, true );
819  }
820 
823  {
824  return CIterateSegments( aOutline, aOutline, true );
825  }
826 
835  {
836  PM_FAST = true,
838  };
839 
842  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
843 
846  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
847 
850  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
851 
854  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
855  POLYGON_MODE aFastMode );
856 
859  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
860  POLYGON_MODE aFastMode );
861 
864  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
865  POLYGON_MODE aFastMode );
866 
868  {
873  };
874 
887  void Inflate( int aAmount, int aCircleSegmentsCount,
888  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
889 
890  void Deflate( int aAmount, int aCircleSegmentsCount,
891  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
892  {
893  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
894  }
895 
901  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
902 
906  void Fracture( POLYGON_MODE aFastMode );
907 
910  void Unfracture( POLYGON_MODE aFastMode );
911 
913  bool HasHoles() const;
914 
916  bool HasTouchingHoles() const;
917 
918 
921  void Simplify( POLYGON_MODE aFastMode );
922 
930  int NormalizeAreaOutlines();
931 
933  const std::string Format() const override;
934 
936  bool Parse( std::stringstream& aStream ) override;
937 
939  void Move( const VECTOR2I& aVector ) override;
940 
947  void Rotate( double aAngle, const VECTOR2I& aCenter );
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 
1079  int TotalVertices() const;
1080 
1082  void DeletePolygon( int aIdx );
1083 
1092  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex,
1093  std::set<VECTOR2I>* aPreserveCorners );
1094 
1104  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex,
1105  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1106 
1114  SHAPE_POLY_SET Chamfer( int aDistance,
1115  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1116 
1125  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax,
1126  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1127 
1136  int DistanceToPolygon( VECTOR2I aPoint, int aIndex );
1137 
1150  int DistanceToPolygon( const SEG& aSegment, int aIndex, int aSegmentWidth = 0 );
1151 
1159  int Distance( VECTOR2I aPoint );
1160 
1169  int Distance( const SEG& aSegment, int aSegmentWidth = 0 );
1170 
1177  bool IsVertexInHole( int aGlobalIdx );
1178 
1179  private:
1180  void fractureSingle( POLYGON& paths );
1181  void unfractureSingle ( POLYGON& path );
1182  void importTree( ClipperLib::PolyTree* tree );
1183 
1195  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1196  POLYGON_MODE aFastMode );
1197 
1198  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1199  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1200 
1201  bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath,
1202  bool aIgnoreEdges, bool aUseBBoxCaches = false ) const;
1203 
1219  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1220  bool aUseBBoxCaches = false ) const;
1221 
1228  {
1231  };
1232 
1248  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1249  int aIndex, int aErrorMax,
1250  std::set<VECTOR2I>* aPreserveCorners );
1251 
1253  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1254 
1255  typedef std::vector<POLYGON> POLYSET;
1256 
1258 
1259  public:
1260 
1262 
1263  void CacheTriangulation();
1264  bool IsTriangulationUpToDate() const;
1265 
1266  MD5_HASH GetHash() const;
1267 
1268  private:
1269 
1270  MD5_HASH checksum() const;
1271 
1272  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1273  bool m_triangulationValid = false;
1275 
1276 };
1277 
1278 #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
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...
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.
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
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
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)
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
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.