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  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  * @author Alejandro García Montoro <alejandro.garciamontoro@gmail.com>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 #ifndef __SHAPE_POLY_SET_H
29 #define __SHAPE_POLY_SET_H
30 
31 #include <cstdio>
32 #include <deque> // for deque
33 #include <vector> // for vector
34 #include <iosfwd> // for string, stringstream
35 #include <memory>
36 #include <set> // for set
37 #include <stdexcept> // for out_of_range
38 #include <stdlib.h> // for abs
39 #include <vector>
40 
41 #include <clipper.hpp> // for ClipType, PolyTree (ptr only)
42 #include <geometry/seg.h> // for SEG
43 #include <geometry/shape.h>
45 #include <math/box2.h> // for BOX2I
46 #include <math/vector2d.h> // for VECTOR2I
47 #include <md5_hash.h>
48 
49 
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 ),
80  b( _b ),
81  c( _c ),
82  parent( aParent )
83  {
84  }
85 
86  virtual void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override {};
87 
88  virtual void Move( const VECTOR2I& aVector ) override {};
89 
90  virtual bool IsSolid() const override { return true; }
91 
92  virtual bool IsClosed() const override { return true; }
93 
94  virtual const BOX2I BBox( int aClearance = 0 ) const override;
95 
96  virtual const VECTOR2I GetPoint( int aIndex ) const override
97  {
98  switch(aIndex)
99  {
100  case 0: return parent->m_vertices[a];
101  case 1: return parent->m_vertices[b];
102  case 2: return parent->m_vertices[c];
103  default: assert(false);
104  }
105  return VECTOR2I(0, 0);
106  }
107 
108  virtual const SEG GetSegment( int aIndex ) const override
109  {
110  switch(aIndex)
111  {
112  case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
113  case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
114  case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
115  default: assert(false);
116  }
117  return SEG();
118  }
119 
120  virtual size_t GetPointCount() const override { return 3; }
121  virtual size_t GetSegmentCount() const override { return 3; }
122 
123 
124  int a, b, c;
126  };
127 
131 
132  void Clear()
133  {
134  m_vertices.clear();
135  m_triangles.clear();
136  }
137 
138  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
139  {
140  auto tri = m_triangles[ index ];
141  a = m_vertices[ tri.a ];
142  b = m_vertices[ tri.b ];
143  c = m_vertices[ tri.c ];
144  }
145 
147 
148  void AddTriangle( int a, int b, int c );
149 
150  void AddVertex( const VECTOR2I& aP )
151  {
152  m_vertices.push_back( aP );
153  }
154 
155  size_t GetTriangleCount() const
156  {
157  return m_triangles.size();
158  }
159 
160  std::deque<TRI>& Triangles()
161  {
162  return m_triangles;
163  }
164 
165  size_t GetVertexCount() const
166  {
167  return m_vertices.size();
168  }
169 
170  void Move( const VECTOR2I& aVec )
171  {
172  for( auto& vertex : m_vertices )
173  vertex += aVec;
174  }
175 
176  private:
177  std::deque<TRI> m_triangles;
178  std::deque<VECTOR2I> m_vertices;
179  };
180 
186  typedef struct VERTEX_INDEX
187  {
188  int m_polygon;
189  int m_contour;
190  int m_vertex;
193  m_polygon(-1),
194  m_contour(-1),
195  m_vertex(-1)
196  {
197  }
198  } VERTEX_INDEX;
199 
203  template <class T>
205  {
206  public:
207 
212  bool IsEndContour() const
213  {
214  return m_currentVertex + 1 ==
216  }
217 
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 
244  void Advance()
245  {
246  // Advance vertex index
247  m_currentVertex ++;
248 
249  // Check whether the user wants to iterate through the vertices of the holes
250  // and behave accordingly
251  if( m_iterateHoles )
252  {
253  // If the last vertex of the contour was reached, advance the contour index
254  if( m_currentVertex >=
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  {
295  }
296 
297  const T& operator*()
298  {
299  return Get();
300  }
301 
302  const T* operator->()
303  {
304  return &Get();
305  }
306 
311  {
312  VERTEX_INDEX index;
313 
314  index.m_polygon = m_currentPolygon;
315  index.m_contour = m_currentContour;
316  index.m_vertex = m_currentVertex;
317 
318  return index;
319  }
320 
321  private:
322  friend class SHAPE_POLY_SET;
323 
330  };
331 
335  template <class T>
337  {
338  public:
342  bool IsLastPolygon() const
343  {
345  }
346 
347  operator bool() const
348  {
350  }
351 
356  void Advance()
357  {
358  // Advance vertex index
360  int last;
361 
362  // Check whether the user wants to iterate through the vertices of the holes
363  // and behave accordingly.
364  if( m_iterateHoles )
365  {
366  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
367 
368  // If the last vertex of the contour was reached, advance the contour index.
369  if( m_currentSegment >= last )
370  {
371  m_currentSegment = 0;
373 
374  // If the last contour of the current polygon was reached, advance the
375  // outline index.
376  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
377 
378  if( m_currentContour >= totalContours )
379  {
380  m_currentContour = 0;
382  }
383  }
384  }
385  else
386  {
387  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
388  // If the last vertex of the outline was reached, advance to the following
389  // polygon
390  if( m_currentSegment >= last )
391  {
392  m_currentSegment = 0;
394  }
395  }
396  }
397 
398  void operator++( int dummy )
399  {
400  Advance();
401  }
402 
403  void operator++()
404  {
405  Advance();
406  }
407 
408  T Get()
409  {
411  }
412 
414  {
415  return Get();
416  }
417 
422  {
423  VERTEX_INDEX index;
424 
425  index.m_polygon = m_currentPolygon;
426  index.m_contour = m_currentContour;
427  index.m_vertex = m_currentSegment;
428 
429  return index;
430  }
431 
438  {
439  // Check that both iterators point to the same contour of the same polygon of the
440  // same polygon set.
441  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
443  {
444  // Compute the total number of segments.
445  int numSeg;
446  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
447 
448  // Compute the difference of the segment indices. If it is exactly one, they
449  // are adjacent. The only missing case where they also are adjacent is when
450  // the segments are the first and last one, in which case the difference
451  // always equals the total number of segments minus one.
452  int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
453 
454  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
455  }
456 
457  return false;
458  }
459 
460  private:
461  friend class SHAPE_POLY_SET;
462 
469  };
470 
471  // Iterator and const iterator types to visit polygon's points.
474 
475  // Iterator and const iterator types to visit polygon's edges.
478 
479  SHAPE_POLY_SET();
480 
486  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
487 
494  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
495 
496  ~SHAPE_POLY_SET();
497 
498  SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
499 
500  void CacheTriangulation( bool aPartition = true );
501  bool IsTriangulationUpToDate() const;
502 
503  MD5_HASH GetHash() const;
504 
505  virtual bool HasIndexableSubshapes() const override;
506 
507  virtual size_t GetIndexableSubshapeCount() const override;
508 
509  virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
510 
522  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
523 
533  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
534 
536  SHAPE* Clone() const override;
537 
539  int NewOutline();
540 
542  int NewHole( int aOutline = -1 );
543 
545  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
546 
548  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
549 
551  double Area();
552 
554 
566  int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
567 
569  void Append( const SHAPE_POLY_SET& aSet );
570 
572  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
573 
581  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
582 
584  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
585 
587  const VECTOR2I& CVertex( int aGlobalIndex ) const;
588 
590  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
591 
605  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
606 
613  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
614 
620  bool IsSelfIntersecting() const;
621 
623  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
624 
626  int OutlineCount() const { return m_polys.size(); }
627 
629  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
630 
632  int HoleCount( int aOutline ) const
633  {
634  if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
635  || ( m_polys[aOutline].size() < 2 ) )
636  return 0;
637 
638  // the first polygon in m_polys[aOutline] is the main contour,
639  // only others are holes:
640  return m_polys[aOutline].size() - 1;
641  }
642 
644  SHAPE_LINE_CHAIN& Outline( int aIndex )
645  {
646  return m_polys[aIndex][0];
647  }
648 
649  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
650  {
651  return m_polys[aIndex][0];
652  }
653 
663  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
664 
665  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
666  {
667  return Subset( aPolygonIndex, aPolygonIndex + 1 );
668  }
669 
671  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
672  {
673  return m_polys[aOutline][aHole + 1];
674  }
675 
677  POLYGON& Polygon( int aIndex )
678  {
679  return m_polys[aIndex];
680  }
681 
682  const POLYGON& Polygon( int aIndex ) const
683  {
684  return m_polys[aIndex];
685  }
686 
687  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
688  {
689  return m_triangulatedPolys[aIndex].get();
690  }
691 
692  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
693  {
694  return m_polys[aIndex][0];
695  }
696 
697  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
698  {
699  return m_polys[aOutline][aHole + 1];
700  }
701 
702  const POLYGON& CPolygon( int aIndex ) const
703  {
704  return m_polys[aIndex];
705  }
706 
717  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
718  {
719  ITERATOR iter;
720 
721  iter.m_poly = this;
722  iter.m_currentPolygon = aFirst;
723  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
724  iter.m_currentContour = 0;
725  iter.m_currentVertex = 0;
726  iter.m_iterateHoles = aIterateHoles;
727 
728  return iter;
729  }
730 
736  ITERATOR Iterate( int aOutline )
737  {
738  return Iterate( aOutline, aOutline );
739  }
740 
746  ITERATOR IterateWithHoles( int aOutline )
747  {
748  return Iterate( aOutline, aOutline, true );
749  }
750 
756  {
757  return Iterate( 0, OutlineCount() - 1 );
758  }
759 
765  {
766  return Iterate( 0, OutlineCount() - 1, true );
767  }
768 
769 
770  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
771  {
772  CONST_ITERATOR iter;
773 
774  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
775  iter.m_currentPolygon = aFirst;
776  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
777  iter.m_currentContour = 0;
778  iter.m_currentVertex = 0;
779  iter.m_iterateHoles = aIterateHoles;
780 
781  return iter;
782  }
783 
784  CONST_ITERATOR CIterate( int aOutline ) const
785  {
786  return CIterate( aOutline, aOutline );
787  }
788 
789  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
790  {
791  return CIterate( aOutline, aOutline, true );
792  }
793 
795  {
796  return CIterate( 0, OutlineCount() - 1 );
797  }
798 
800  {
801  return CIterate( 0, OutlineCount() - 1, true );
802  }
803 
805  {
806  // Build iterator
807  ITERATOR iter = IterateWithHoles();
808 
809  // Get the relative indices of the globally indexed vertex
810  VERTEX_INDEX indices;
811 
812  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
813  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
814 
815  // Adjust where the iterator is pointing
816  iter.m_currentPolygon = indices.m_polygon;
817  iter.m_currentContour = indices.m_contour;
818  iter.m_currentVertex = indices.m_vertex;
819 
820  return iter;
821  }
822 
825  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
826  {
827  SEGMENT_ITERATOR iter;
828 
829  iter.m_poly = this;
830  iter.m_currentPolygon = aFirst;
831  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
832  iter.m_currentContour = 0;
833  iter.m_currentSegment = 0;
834  iter.m_iterateHoles = aIterateHoles;
835 
836  return iter;
837  }
838 
841  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
842  bool aIterateHoles = false ) const
843  {
845 
846  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
847  iter.m_currentPolygon = aFirst;
848  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
849  iter.m_currentContour = 0;
850  iter.m_currentSegment = 0;
851  iter.m_iterateHoles = aIterateHoles;
852 
853  return iter;
854  }
855 
858  {
859  return IterateSegments( aPolygonIdx, aPolygonIdx );
860  }
861 
863  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
864  {
865  return CIterateSegments( aPolygonIdx, aPolygonIdx );
866  }
867 
870  {
871  return IterateSegments( 0, OutlineCount() - 1 );
872  }
873 
876  {
877  return CIterateSegments( 0, OutlineCount() - 1 );
878  }
879 
882  {
883  return IterateSegments( 0, OutlineCount() - 1, true );
884  }
885 
888  {
889  return IterateSegments( aOutline, aOutline, true );
890  }
891 
894  {
895  return CIterateSegments( 0, OutlineCount() - 1, true );
896  }
897 
900  {
901  return CIterateSegments( aOutline, aOutline, true );
902  }
903 
913  {
914  PM_FAST = true,
916  };
917 
920  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
921 
924  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
925 
928  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
929 
932  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
933  POLYGON_MODE aFastMode );
934 
937  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
938  POLYGON_MODE aFastMode );
939 
942  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
943  POLYGON_MODE aFastMode );
944 
946  {
954  };
956 
971  void Inflate( int aAmount, int aCircleSegmentsCount,
972  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
973 
974  void Deflate( int aAmount, int aCircleSegmentsCount,
975  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
976  {
977  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
978  }
979 
987  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
988 
992  void Fracture( POLYGON_MODE aFastMode );
993 
996  void Unfracture( POLYGON_MODE aFastMode );
997 
999  bool HasHoles() const;
1000 
1002  bool HasTouchingHoles() const;
1003 
1004 
1007  void Simplify( POLYGON_MODE aFastMode );
1008 
1017  int NormalizeAreaOutlines();
1018 
1020  const std::string Format() const override;
1021 
1023  bool Parse( std::stringstream& aStream ) override;
1024 
1026  void Move( const VECTOR2I& aVector ) override;
1027 
1035  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1036 
1043  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1044 
1046  bool IsSolid() const override
1047  {
1048  return true;
1049  }
1050 
1051  const BOX2I BBox( int aClearance = 0 ) const override;
1052 
1059  bool PointOnEdge( const VECTOR2I& aP ) const;
1060 
1073  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1074  VECTOR2I* aLocation = nullptr ) const override;
1075 
1094  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1095  VECTOR2I* aLocation = nullptr ) const override;
1096 
1115  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1116  VECTOR2I* aLocation = nullptr ) const override;
1117 
1128  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1129  int aClearance = 0 ) const;
1130 
1141  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1142  int aClearance = 0 ) const;
1143 
1150  void BuildBBoxCaches() const;
1151 
1152  const BOX2I BBoxFromCaches() const;
1153 
1164  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1165  bool aUseBBoxCaches = false ) const;
1166 
1168  bool IsEmpty() const
1169  {
1170  return m_polys.empty();
1171  }
1172 
1178  void RemoveVertex( int aGlobalIndex );
1179 
1185  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1186 
1188  void RemoveAllContours();
1189 
1198  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1199 
1205  int RemoveNullSegments();
1206 
1213  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1214 
1223  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1224 
1226  int TotalVertices() const;
1227 
1229  void DeletePolygon( int aIdx );
1230 
1238  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1239 
1248  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1249 
1256  SHAPE_POLY_SET Chamfer( int aDistance );
1257 
1265  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1266 
1277  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1278  VECTOR2I* aNearest ) const;
1279 
1292  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1293  VECTOR2I* aNearest) const;
1294 
1305  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1306 
1318  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1319 
1326  bool IsVertexInHole( int aGlobalIdx );
1327 
1328 private:
1329  void fractureSingle( POLYGON& paths );
1330  void unfractureSingle ( POLYGON& path );
1331  void importTree( ClipperLib::PolyTree* tree );
1332 
1345  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1346  POLYGON_MODE aFastMode );
1347 
1348  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1349  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1350 
1365  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1366  bool aUseBBoxCaches = false ) const;
1367 
1374  {
1377  };
1378 
1392  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1393  int aIndex, int aErrorMax );
1394 
1396  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1397 
1398  MD5_HASH checksum() const;
1399 
1400 private:
1401  typedef std::vector<POLYGON> POLYSET;
1402 
1404 
1405  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1406 
1407  bool m_triangulationValid = false;
1409 };
1410 
1411 #endif // __SHAPE_POLY_SET_H
int TotalVertices() const
Delete aIdx-th polygon from 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)
This is the engine to execute all polygon boolean transforms (AND, OR, ...
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
const POLYGON & CPolygon(int aIndex) const
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Return the number of vertices in a given outline/hole.
All angles are chamfered.
virtual void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
void fractureSingle(POLYGON &paths)
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
ITERATOR Iterate(int aOutline)
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
Return the aGlobalIndex-th vertex in the poly set.
void Move(const VECTOR2I &aVec)
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsEmpty() const
VECTOR2I::extended_type ecoord
Definition: seg.h:44
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of holes in a given outline.
bool IsSolid() const override
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
CONST_ITERATOR CIterateWithHoles(int aOutline) const
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
double Area()
Appends a vertex at the end of the given outline/hole (default: the last outline)
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
Definition: sch_symbol.cpp:69
MD5_HASH checksum() const
Base class for iterating over all segments in a given SHAPE_POLY_SET.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
virtual const VECTOR2I GetPoint(int aIndex) const override
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
ITERATOR Iterate()
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Return an object to iterate through the points of the polygons between aFirst and aLast.
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
virtual const SEG GetSegment(int aIndex) const override
CONST_SEGMENT_ITERATOR CIterateSegments() const
Returns an iterator object, for all outlines in the set (with holes)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
bool IsTriangulationUpToDate() const
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void DeletePolygon(int aIdx)
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
virtual size_t GetSegmentCount() const override
Acute angles are rounded.
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
ITERATOR IterateWithHoles(int aOutline)
Represent a set of closed polygons.
virtual size_t GetPointCount() const override
SHAPE_LINE_CHAIN & Outline(int aIndex)
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
void Deflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Return an iterator object, for the aOutline-th outline in the set (with holes).
const SHAPE_LINE_CHAIN & Outline(int aIndex) const
void Simplify(POLYGON_MODE aFastMode)
An abstract shape on 2D plane.
Definition: shape.h:116
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
const std::string Format() const override
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
int NewOutline()
Creates a new hole in a given outline.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Acute angles are chamfered.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
virtual void Move(const VECTOR2I &aVector) override
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
const POLYGON & Polygon(int aIndex) const
Definition: seg.h:41
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
void AddVertex(const VECTOR2I &aP)
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:52
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
void AddTriangle(int a, int b, int c)
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
Return the reference to aHole-th hole in the aIndex-th outline.
TRI(int _a=0, int _b=0, int _c=0, TRIANGULATED_POLYGON *aParent=nullptr)
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
ITERATOR IterateWithHoles()
SHAPE_LINE_CHAIN.
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
CONST_ITERATOR CIterate() const
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
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)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
POLYGON & Polygon(int aIndex)
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Return an iterator object, for all outlines in the set (no holes).
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
just inflate the polygon. Acute angles create spikes
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
CONST_ITERATOR CIterateWithHoles() const
virtual bool IsClosed() const override
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &aOther)
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.