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 <cstdio>
30 #include <deque> // for deque
31 #include <vector> // for vector
32 #include <iosfwd> // for string, stringstream
33 #include <memory>
34 #include <set> // for set
35 #include <stdexcept> // for out_of_range
36 #include <stdlib.h> // for abs
37 #include <vector>
38 
39 #include <clipper.hpp> // for ClipType, PolyTree (ptr only)
40 #include <geometry/seg.h> // for SEG
41 #include <geometry/shape.h>
43 #include <math/box2.h> // for BOX2I
44 #include <math/vector2d.h> // for VECTOR2I
45 #include <md5_hash.h>
46 
47 
64 class SHAPE_POLY_SET : public SHAPE
65 {
66  public:
70  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
71 
73  {
74  public:
75  struct TRI : public SHAPE_LINE_CHAIN_BASE
76  {
77  TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
79  a( _a ), b( _b ), c( _c ), parent( aParent )
80  {
81  }
82 
83  virtual void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override {};
84 
85  virtual void Move( const VECTOR2I& aVector ) override {};
86 
87  virtual bool IsSolid() const override { return true; }
88 
89  virtual bool IsClosed() const override { return true; }
90 
91  virtual const BOX2I BBox( int aClearance = 0 ) const override;
92 
93  virtual const VECTOR2I GetPoint( int aIndex ) const override
94  {
95  switch(aIndex)
96  {
97  case 0: return parent->m_vertices[a];
98  case 1: return parent->m_vertices[b];
99  case 2: return parent->m_vertices[c];
100  default: assert(false);
101  }
102  return VECTOR2I(0, 0);
103  }
104 
105  virtual const SEG GetSegment( int aIndex ) const override
106  {
107  switch(aIndex)
108  {
109  case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
110  case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
111  case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
112  default: assert(false);
113  }
114  return SEG();
115  }
116 
117  virtual size_t GetPointCount() const override { return 3; }
118  virtual size_t GetSegmentCount() const override { return 3; }
119 
120 
121  int a, b, c;
123  };
124 
128 
129  void Clear()
130  {
131  m_vertices.clear();
132  m_triangles.clear();
133  }
134 
135  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
136  {
137  auto tri = m_triangles[ index ];
138  a = m_vertices[ tri.a ];
139  b = m_vertices[ tri.b ];
140  c = m_vertices[ tri.c ];
141  }
142 
144 
145  void AddTriangle( int a, int b, int c );
146 
147  void AddVertex( const VECTOR2I& aP )
148  {
149  m_vertices.push_back( aP );
150  }
151 
152  size_t GetTriangleCount() const
153  {
154  return m_triangles.size();
155  }
156 
157  std::deque<TRI>& Triangles()
158  {
159  return m_triangles;
160  }
161 
162  size_t GetVertexCount() const
163  {
164  return m_vertices.size();
165  }
166 
167  void Move( const VECTOR2I& aVec )
168  {
169  for( auto& vertex : m_vertices )
170  vertex += aVec;
171  }
172 
173  private:
174 
175  std::deque<TRI> m_triangles;
176  std::deque<VECTOR2I> m_vertices;
177  };
178 
186  typedef struct VERTEX_INDEX
187  {
188  int m_polygon;
189  int m_contour;
190  int m_vertex;
193  {
194  }
195  } VERTEX_INDEX;
196 
202  template <class T>
204  {
205  public:
206 
212  bool IsEndContour() const
213  {
214  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
215  }
216 
221  bool IsLastPolygon() const
222  {
224  }
225 
226  operator bool() const
227  {
229  return true;
230 
231  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
232  return false;
233 
234  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
235 
236  return m_currentContour < (int) currentPolygon.size() - 1
237  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
238  }
239 
245  void Advance()
246  {
247  // Advance vertex index
248  m_currentVertex ++;
249 
250  // Check whether the user wants to iterate through the vertices of the holes
251  // and behave accordingly
252  if( m_iterateHoles )
253  {
254  // If the last vertex of the contour was reached, advance the contour index
256  {
257  m_currentVertex = 0;
259 
260  // If the last contour of the current polygon was reached, advance the
261  // outline index
262  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
263 
264  if( m_currentContour >= totalContours )
265  {
266  m_currentContour = 0;
268  }
269  }
270  }
271  else
272  {
273  // If the last vertex of the outline was reached, advance to the following polygon
274  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
275  {
276  m_currentVertex = 0;
278  }
279  }
280  }
281 
282  void operator++( int dummy )
283  {
284  Advance();
285  }
286 
287  void operator++()
288  {
289  Advance();
290  }
291 
292  const T& Get()
293  {
294  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint(
295  m_currentVertex );
296  }
297 
298  const T& operator*()
299  {
300  return Get();
301  }
302 
303  const T* operator->()
304  {
305  return &Get();
306  }
307 
313  {
314  VERTEX_INDEX index;
315 
316  index.m_polygon = m_currentPolygon;
317  index.m_contour = m_currentContour;
318  index.m_vertex = m_currentVertex;
319 
320  return index;
321  }
322 
323 
324  private:
325  friend class SHAPE_POLY_SET;
326 
333  };
334 
340  template <class T>
342  {
343  public:
348  bool IsLastPolygon() const
349  {
351  }
352 
353  operator bool() const
354  {
356  }
357 
363  void Advance()
364  {
365  // Advance vertex index
367  int last;
368 
369  // Check whether the user wants to iterate through the vertices of the holes
370  // and behave accordingly
371  if( m_iterateHoles )
372  {
373  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
374 
375  // If the last vertex of the contour was reached, advance the contour index
376  if( m_currentSegment >= last )
377  {
378  m_currentSegment = 0;
380 
381  // If the last contour of the current polygon was reached, advance the
382  // outline index
383  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
384 
385  if( m_currentContour >= totalContours )
386  {
387  m_currentContour = 0;
389  }
390  }
391  }
392  else
393  {
394  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
395  // If the last vertex of the outline was reached, advance to the following
396  // polygon
397  if( m_currentSegment >= last )
398  {
399  m_currentSegment = 0;
401  }
402  }
403  }
404 
405  void operator++( int dummy )
406  {
407  Advance();
408  }
409 
410  void operator++()
411  {
412  Advance();
413  }
414 
415  T Get()
416  {
418  }
419 
421  {
422  return Get();
423  }
424 
430  {
431  VERTEX_INDEX index;
432 
433  index.m_polygon = m_currentPolygon;
434  index.m_contour = m_currentContour;
435  index.m_vertex = m_currentSegment;
436 
437  return index;
438  }
439 
448  {
449  // Check that both iterators point to the same contour of the same polygon of the
450  // same polygon set
451  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
453  {
454  // Compute the total number of segments
455  int numSeg;
456  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
457 
458  // Compute the difference of the segment indices. If it is exactly one, they
459  // are adjacent. The only missing case where they also are adjacent is when
460  // the segments are the first and last one, in which case the difference
461  // always equals the total number of segments minus one.
462  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
463 
464  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
465  }
466 
467  return false;
468  }
469 
470  private:
471  friend class SHAPE_POLY_SET;
472 
479  };
480 
481  // Iterator and const iterator types to visit polygon's points.
484 
485  // Iterator and const iterator types to visit polygon's edges.
488 
489  SHAPE_POLY_SET();
490 
496  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
497 
503  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
504 
505  ~SHAPE_POLY_SET();
506 
519  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
520 
530  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
531 
533  SHAPE* Clone() const override;
534 
536  int NewOutline();
537 
539  int NewHole( int aOutline = -1 );
540 
542  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
543 
545  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
546 
548 
560  int Append( int x, int y, int aOutline = -1, int aHole = -1,
561  bool aAllowDuplication = false );
562 
564  void Append( const SHAPE_POLY_SET& aSet );
565 
567  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
568 
576  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
577 
579  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
580 
582  const VECTOR2I& CVertex( int aGlobalIndex ) const;
583 
585  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
586 
598  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
599 
600 
608  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
609 
615  bool IsSelfIntersecting() const;
616 
618  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
619 
621  int OutlineCount() const { return m_polys.size(); }
622 
624  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
625 
627  int HoleCount( int aOutline ) const
628  {
629  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
630  return 0;
631 
632  // the first polygon in m_polys[aOutline] is the main contour,
633  // only others are holes:
634  return m_polys[aOutline].size() - 1;
635  }
636 
638  SHAPE_LINE_CHAIN& Outline( int aIndex )
639  {
640  return m_polys[aIndex][0];
641  }
642 
652  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
653 
654  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
655  {
656  return Subset( aPolygonIndex, aPolygonIndex + 1 );
657  }
658 
660  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
661  {
662  return m_polys[aOutline][aHole + 1];
663  }
664 
666  POLYGON& Polygon( int aIndex )
667  {
668  return m_polys[aIndex];
669  }
670 
671  const POLYGON& Polygon( int aIndex ) const
672  {
673  return m_polys[aIndex];
674  }
675 
676  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
677  {
678  return m_triangulatedPolys[aIndex].get();
679  }
680 
681  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
682  {
683  return m_polys[aIndex][0];
684  }
685 
686  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
687  {
688  return m_polys[aOutline][aHole + 1];
689  }
690 
691  const POLYGON& CPolygon( int aIndex ) const
692  {
693  return m_polys[aIndex];
694  }
695 
706  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
707  {
708  ITERATOR iter;
709 
710  iter.m_poly = this;
711  iter.m_currentPolygon = aFirst;
712  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
713  iter.m_currentContour = 0;
714  iter.m_currentVertex = 0;
715  iter.m_iterateHoles = aIterateHoles;
716 
717  return iter;
718  }
719 
726  ITERATOR Iterate( int aOutline )
727  {
728  return Iterate( aOutline, aOutline );
729  }
730 
737  ITERATOR IterateWithHoles( int aOutline )
738  {
739  return Iterate( aOutline, aOutline, true );
740  }
741 
748  {
749  return Iterate( 0, OutlineCount() - 1 );
750  }
751 
758  {
759  return Iterate( 0, OutlineCount() - 1, true );
760  }
761 
762 
763  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
764  {
765  CONST_ITERATOR iter;
766 
767  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
768  iter.m_currentPolygon = aFirst;
769  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
770  iter.m_currentContour = 0;
771  iter.m_currentVertex = 0;
772  iter.m_iterateHoles = aIterateHoles;
773 
774  return iter;
775  }
776 
777  CONST_ITERATOR CIterate( int aOutline ) const
778  {
779  return CIterate( aOutline, aOutline );
780  }
781 
782  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
783  {
784  return CIterate( aOutline, aOutline, true );
785  }
786 
788  {
789  return CIterate( 0, OutlineCount() - 1 );
790  }
791 
793  {
794  return CIterate( 0, OutlineCount() - 1, true );
795  }
796 
798  {
799  // Build iterator
800  ITERATOR iter = IterateWithHoles();
801 
802  // Get the relative indices of the globally indexed vertex
803  VERTEX_INDEX indices;
804 
805  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
806  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
807 
808  // Adjust where the iterator is pointing
809  iter.m_currentPolygon = indices.m_polygon;
810  iter.m_currentContour = indices.m_contour;
811  iter.m_currentVertex = indices.m_vertex;
812 
813  return iter;
814  }
815 
818  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
819  {
820  SEGMENT_ITERATOR iter;
821 
822  iter.m_poly = this;
823  iter.m_currentPolygon = aFirst;
824  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
825  iter.m_currentContour = 0;
826  iter.m_currentSegment = 0;
827  iter.m_iterateHoles = aIterateHoles;
828 
829  return iter;
830  }
831 
834  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
835  bool aIterateHoles = false ) const
836  {
838 
839  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
840  iter.m_currentPolygon = aFirst;
841  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
842  iter.m_currentContour = 0;
843  iter.m_currentSegment = 0;
844  iter.m_iterateHoles = aIterateHoles;
845 
846  return iter;
847  }
848 
851  {
852  return IterateSegments( aPolygonIdx, aPolygonIdx );
853  }
854 
856  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
857  {
858  return CIterateSegments( aPolygonIdx, aPolygonIdx );
859  }
860 
863  {
864  return IterateSegments( 0, OutlineCount() - 1 );
865  }
866 
869  {
870  return IterateSegments( 0, OutlineCount() - 1, true );
871  }
872 
875  {
876  return IterateSegments( aOutline, aOutline, true );
877  }
878 
881  {
882  return CIterateSegments( 0, OutlineCount() - 1, true );
883  }
884 
887  {
888  return CIterateSegments( aOutline, aOutline, true );
889  }
890 
899  {
900  PM_FAST = true,
902  };
903 
906  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
907 
910  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
911 
914  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
915 
918  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
919  POLYGON_MODE aFastMode );
920 
923  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
924  POLYGON_MODE aFastMode );
925 
928  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
929  POLYGON_MODE aFastMode );
930 
932  {
940  };
942 
955  void Inflate( int aAmount, int aCircleSegmentsCount,
956  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
957 
958  void Deflate( int aAmount, int aCircleSegmentsCount,
959  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
960  {
961  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
962  }
963 
969  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
970 
974  void Fracture( POLYGON_MODE aFastMode );
975 
978  void Unfracture( POLYGON_MODE aFastMode );
979 
981  bool HasHoles() const;
982 
984  bool HasTouchingHoles() const;
985 
986 
989  void Simplify( POLYGON_MODE aFastMode );
990 
998  int NormalizeAreaOutlines();
999 
1001  const std::string Format() const override;
1002 
1004  bool Parse( std::stringstream& aStream ) override;
1005 
1007  void Move( const VECTOR2I& aVector ) override;
1008 
1015  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1016 
1023  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1024 
1026  bool IsSolid() const override
1027  {
1028  return true;
1029  }
1030 
1031  const BOX2I BBox( int aClearance = 0 ) const override;
1032 
1040  bool PointOnEdge( const VECTOR2I& aP ) const;
1041 
1055  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1056  VECTOR2I* aLocation = nullptr ) const override;
1057 
1077  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1078  VECTOR2I* aLocation = nullptr ) const override;
1079 
1100  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1101  VECTOR2I* aLocation = nullptr ) const override;
1102 
1113  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1114  int aClearance = 0 ) const;
1115 
1126  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1127  int aClearance = 0 ) const;
1128 
1133  void BuildBBoxCaches();
1134 
1135  const BOX2I BBoxFromCaches() const;
1136 
1147  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1148  bool aUseBBoxCaches = false ) const;
1149 
1151  bool IsEmpty() const
1152  {
1153  return m_polys.size() == 0;
1154  }
1155 
1161  void RemoveVertex( int aGlobalIndex );
1162 
1168  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1169 
1171  void RemoveAllContours();
1172 
1181  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1182 
1188  int RemoveNullSegments();
1189 
1196  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1197 
1204  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1205 
1207  int TotalVertices() const;
1208 
1210  void DeletePolygon( int aIdx );
1211 
1219  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1220 
1229  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1230 
1237  SHAPE_POLY_SET Chamfer( int aDistance );
1238 
1246  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1247 
1258  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1259  VECTOR2I* aNearest ) const;
1260 
1274  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1275  VECTOR2I* aNearest) const;
1276 
1287  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1288 
1300  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1301 
1308  bool IsVertexInHole( int aGlobalIdx );
1309 
1310  private:
1311  void fractureSingle( POLYGON& paths );
1312  void unfractureSingle ( POLYGON& path );
1313  void importTree( ClipperLib::PolyTree* tree );
1314 
1326  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1327  POLYGON_MODE aFastMode );
1328 
1329  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1330  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1331 
1347  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1348  bool aUseBBoxCaches = false ) const;
1349 
1356  {
1359  };
1360 
1375  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1376  int aIndex, int aErrorMax );
1377 
1379  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1380 
1381  typedef std::vector<POLYGON> POLYSET;
1382 
1384 
1385  public:
1386 
1388 
1389  void CacheTriangulation( bool aPartition = true );
1390  bool IsTriangulationUpToDate() const;
1391 
1392  MD5_HASH GetHash() const;
1393 
1394  virtual bool HasIndexableSubshapes() const override;
1395 
1396  virtual size_t GetIndexableSubshapeCount() const override;
1397 
1398  virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
1399 
1400  private:
1401 
1402  MD5_HASH checksum() const;
1403 
1404  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1405  bool m_triangulationValid = false;
1407 
1408 };
1409 
1410 #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
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Returns the number of outlines in the set
All angles are chamfered.
virtual void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate.
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.
void GetTriangle(int index, VECTOR2I &a, VECTOR2I &b, VECTOR2I &c) const
std::vector< POLYGON > POLYSET
const BOX2I BBoxFromCaches() const
virtual bool IsSolid() const override
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
void Move(const VECTOR2I &aVec)
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
VECTOR2I::extended_type ecoord
Definition: seg.h:42
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
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
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Returns true if the polygon set has any holes.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
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
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate rotates all vertices by a given angle.
virtual const VECTOR2I GetPoint(int aIndex) const override
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
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.
virtual const SEG GetSegment(int aIndex) const override
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
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.
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...
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 &)
virtual size_t GetSegmentCount() const override
Acute angles are rounded.
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
SHAPE_POLY_SET.
virtual size_t GetPointCount() const override
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)
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...
SHAPE.
Definition: shape.h:122
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
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
Acute angles are chamfered.
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
virtual void Move(const VECTOR2I &aVector) override
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
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,...
Definition: seg.h:39
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
virtual const BOX2I BBox(int aClearance=0) const override
Function BBox()
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
void AddVertex(const VECTOR2I &aP)
empty shape (no shape...),
Definition: shape.h:52
void AddTriangle(int a, int b, int c)
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
TRI(int _a=0, int _b=0, int _c=0, TRIANGULATED_POLYGON *aParent=nullptr)
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.
SHAPE_LINE_CHAIN.
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Function Fillet returns a filleted version of the aIndex-th polygon.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
CONST_ITERATOR CIterate() const
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
CONST_ITERATOR CIterate(int aOutline) const
void CacheTriangulation(bool aPartition=true)
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()
just inflate the polygon. Acute angles create spikes
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
VERTEX_INDEX GetIndex()
Function GetIndex.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
CONST_ITERATOR CIterateWithHoles() const
virtual bool IsClosed() const override
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.