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 
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  };
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  int ArcCount() const;
555 
557  void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
558 
560  void ClearArcs();
561 
563 
575  int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
576 
578  void Append( const SHAPE_POLY_SET& aSet );
579 
581  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
582 
591  int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1 );
592 
600  void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
601 
603  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
604 
606  const VECTOR2I& CVertex( int aGlobalIndex ) const;
607 
609  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
610 
624  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
625 
632  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
633 
639  bool IsSelfIntersecting() const;
640 
642  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
643 
645  int OutlineCount() const { return m_polys.size(); }
646 
648  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
649 
651  int HoleCount( int aOutline ) const
652  {
653  if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
654  || ( m_polys[aOutline].size() < 2 ) )
655  return 0;
656 
657  // the first polygon in m_polys[aOutline] is the main contour,
658  // only others are holes:
659  return m_polys[aOutline].size() - 1;
660  }
661 
663  SHAPE_LINE_CHAIN& Outline( int aIndex )
664  {
665  return m_polys[aIndex][0];
666  }
667 
668  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
669  {
670  return m_polys[aIndex][0];
671  }
672 
682  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
683 
684  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
685  {
686  return Subset( aPolygonIndex, aPolygonIndex + 1 );
687  }
688 
690  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
691  {
692  return m_polys[aOutline][aHole + 1];
693  }
694 
696  POLYGON& Polygon( int aIndex )
697  {
698  return m_polys[aIndex];
699  }
700 
701  const POLYGON& Polygon( int aIndex ) const
702  {
703  return m_polys[aIndex];
704  }
705 
706  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
707  {
708  return m_triangulatedPolys[aIndex].get();
709  }
710 
711  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
712  {
713  return m_polys[aIndex][0];
714  }
715 
716  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
717  {
718  return m_polys[aOutline][aHole + 1];
719  }
720 
721  const POLYGON& CPolygon( int aIndex ) const
722  {
723  return m_polys[aIndex];
724  }
725 
736  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
737  {
738  ITERATOR iter;
739 
740  iter.m_poly = this;
741  iter.m_currentPolygon = aFirst;
742  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
743  iter.m_currentContour = 0;
744  iter.m_currentVertex = 0;
745  iter.m_iterateHoles = aIterateHoles;
746 
747  return iter;
748  }
749 
755  ITERATOR Iterate( int aOutline )
756  {
757  return Iterate( aOutline, aOutline );
758  }
759 
765  ITERATOR IterateWithHoles( int aOutline )
766  {
767  return Iterate( aOutline, aOutline, true );
768  }
769 
775  {
776  return Iterate( 0, OutlineCount() - 1 );
777  }
778 
784  {
785  return Iterate( 0, OutlineCount() - 1, true );
786  }
787 
788 
789  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
790  {
791  CONST_ITERATOR iter;
792 
793  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
794  iter.m_currentPolygon = aFirst;
795  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
796  iter.m_currentContour = 0;
797  iter.m_currentVertex = 0;
798  iter.m_iterateHoles = aIterateHoles;
799 
800  return iter;
801  }
802 
803  CONST_ITERATOR CIterate( int aOutline ) const
804  {
805  return CIterate( aOutline, aOutline );
806  }
807 
808  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
809  {
810  return CIterate( aOutline, aOutline, true );
811  }
812 
814  {
815  return CIterate( 0, OutlineCount() - 1 );
816  }
817 
819  {
820  return CIterate( 0, OutlineCount() - 1, true );
821  }
822 
824  {
825  // Build iterator
826  ITERATOR iter = IterateWithHoles();
827 
828  // Get the relative indices of the globally indexed vertex
829  VERTEX_INDEX indices;
830 
831  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
832  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
833 
834  // Adjust where the iterator is pointing
835  iter.m_currentPolygon = indices.m_polygon;
836  iter.m_currentContour = indices.m_contour;
837  iter.m_currentVertex = indices.m_vertex;
838 
839  return iter;
840  }
841 
844  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
845  {
846  SEGMENT_ITERATOR iter;
847 
848  iter.m_poly = this;
849  iter.m_currentPolygon = aFirst;
850  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
851  iter.m_currentContour = 0;
852  iter.m_currentSegment = 0;
853  iter.m_iterateHoles = aIterateHoles;
854 
855  return iter;
856  }
857 
860  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
861  bool aIterateHoles = false ) const
862  {
864 
865  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
866  iter.m_currentPolygon = aFirst;
867  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
868  iter.m_currentContour = 0;
869  iter.m_currentSegment = 0;
870  iter.m_iterateHoles = aIterateHoles;
871 
872  return iter;
873  }
874 
877  {
878  return IterateSegments( aPolygonIdx, aPolygonIdx );
879  }
880 
882  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
883  {
884  return CIterateSegments( aPolygonIdx, aPolygonIdx );
885  }
886 
889  {
890  return IterateSegments( 0, OutlineCount() - 1 );
891  }
892 
895  {
896  return CIterateSegments( 0, OutlineCount() - 1 );
897  }
898 
901  {
902  return IterateSegments( 0, OutlineCount() - 1, true );
903  }
904 
907  {
908  return IterateSegments( aOutline, aOutline, true );
909  }
910 
913  {
914  return CIterateSegments( 0, OutlineCount() - 1, true );
915  }
916 
919  {
920  return CIterateSegments( aOutline, aOutline, true );
921  }
922 
932  {
933  PM_FAST = true,
935  };
936 
939  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
940 
943  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
944 
947  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
948 
951  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
952  POLYGON_MODE aFastMode );
953 
956  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
957  POLYGON_MODE aFastMode );
958 
961  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
962  POLYGON_MODE aFastMode );
963 
965  {
973  };
975 
990  void Inflate( int aAmount, int aCircleSegCount,
991  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
992 
993  void Deflate( int aAmount, int aCircleSegmentsCount,
994  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
995  {
996  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
997  }
998 
1006  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1007 
1011  void Fracture( POLYGON_MODE aFastMode );
1012 
1015  void Unfracture( POLYGON_MODE aFastMode );
1016 
1018  bool HasHoles() const;
1019 
1021  bool HasTouchingHoles() const;
1022 
1023 
1026  void Simplify( POLYGON_MODE aFastMode );
1027 
1036  int NormalizeAreaOutlines();
1037 
1039  const std::string Format() const override;
1040 
1042  bool Parse( std::stringstream& aStream ) override;
1043 
1045  void Move( const VECTOR2I& aVector ) override;
1046 
1054  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1055 
1062  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1063 
1065  bool IsSolid() const override
1066  {
1067  return true;
1068  }
1069 
1070  const BOX2I BBox( int aClearance = 0 ) const override;
1071 
1078  bool PointOnEdge( const VECTOR2I& aP ) const;
1079 
1092  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1093  VECTOR2I* aLocation = nullptr ) const override;
1094 
1113  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1114  VECTOR2I* aLocation = nullptr ) const override;
1115 
1134  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1135  VECTOR2I* aLocation = nullptr ) const override;
1136 
1147  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1148  int aClearance = 0 ) const;
1149 
1160  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1161  int aClearance = 0 ) const;
1162 
1169  void BuildBBoxCaches() const;
1170 
1171  const BOX2I BBoxFromCaches() const;
1172 
1183  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1184  bool aUseBBoxCaches = false ) const;
1185 
1187  bool IsEmpty() const
1188  {
1189  return m_polys.empty();
1190  }
1191 
1197  void RemoveVertex( int aGlobalIndex );
1198 
1204  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1205 
1207  void RemoveAllContours();
1208 
1217  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1218 
1224  int RemoveNullSegments();
1225 
1232  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1233 
1242  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1243 
1245  int TotalVertices() const;
1246 
1248  void DeletePolygon( int aIdx );
1249 
1257  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1258 
1267  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1268 
1275  SHAPE_POLY_SET Chamfer( int aDistance );
1276 
1284  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1285 
1296  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1297  VECTOR2I* aNearest ) const;
1298 
1311  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1312  VECTOR2I* aNearest) const;
1313 
1324  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1325 
1337  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1338 
1345  bool IsVertexInHole( int aGlobalIdx );
1346 
1347 private:
1348  void fractureSingle( POLYGON& paths );
1349  void unfractureSingle ( POLYGON& path );
1350  void importTree( ClipperLib::PolyTree* tree,
1351  const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1352  const std::vector<SHAPE_ARC>& aArcBuffe );
1353 
1366  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1367  POLYGON_MODE aFastMode );
1368 
1369  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1370  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1371 
1386  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1387  bool aUseBBoxCaches = false ) const;
1388 
1395  {
1398  };
1399 
1413  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1414  int aIndex, int aErrorMax );
1415 
1417  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1418 
1419  MD5_HASH checksum() const;
1420 
1421 private:
1422  typedef std::vector<POLYGON> POLYSET;
1423 
1425 
1426  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1427 
1428  bool m_triangulationValid = false;
1430 };
1431 
1432 #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:43
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()
Count the number of arc shapes present.
MD5_HASH checksum() const
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
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.
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
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...
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:71
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.
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
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
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
Definition: seg.h:40
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 GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
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()
Represent a polyline (an zero-thickness chain of connected line segments).
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
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
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
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.
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
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 Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.