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 <[email protected]>
8  * @author Alejandro García Montoro <[email protected]>
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 
481  SHAPE_POLY_SET( const BOX2D& aRect );
482 
488  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
489 
496  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
497 
498  ~SHAPE_POLY_SET();
499 
500  SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
501 
502  void CacheTriangulation( bool aPartition = true );
503  bool IsTriangulationUpToDate() const;
504 
505  MD5_HASH GetHash() const;
506 
507  virtual bool HasIndexableSubshapes() const override;
508 
509  virtual size_t GetIndexableSubshapeCount() const override;
510 
511  virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
512 
524  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
525 
535  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
536 
538  SHAPE* Clone() const override;
539 
541  int NewOutline();
542 
544  int NewHole( int aOutline = -1 );
545 
547  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
548 
550  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
551 
553  double Area();
554 
556  int ArcCount() const;
557 
559  void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
560 
562  void ClearArcs();
563 
565 
577  int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
578 
580  void Append( const SHAPE_POLY_SET& aSet );
581 
583  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
584 
593  int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1 );
594 
602  void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
603 
605  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
606 
608  const VECTOR2I& CVertex( int aGlobalIndex ) const;
609 
611  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
612 
626  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
627 
634  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
635 
641  bool IsSelfIntersecting() const;
642 
644  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
645 
647  int OutlineCount() const { return m_polys.size(); }
648 
650  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
651 
654  int FullPointCount() const;
655 
657  int HoleCount( int aOutline ) const
658  {
659  if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
660  || ( m_polys[aOutline].size() < 2 ) )
661  return 0;
662 
663  // the first polygon in m_polys[aOutline] is the main contour,
664  // only others are holes:
665  return m_polys[aOutline].size() - 1;
666  }
667 
669  SHAPE_LINE_CHAIN& Outline( int aIndex )
670  {
671  return m_polys[aIndex][0];
672  }
673 
674  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
675  {
676  return m_polys[aIndex][0];
677  }
678 
688  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
689 
690  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
691  {
692  return Subset( aPolygonIndex, aPolygonIndex + 1 );
693  }
694 
696  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
697  {
698  return m_polys[aOutline][aHole + 1];
699  }
700 
702  POLYGON& Polygon( int aIndex )
703  {
704  return m_polys[aIndex];
705  }
706 
707  const POLYGON& Polygon( int aIndex ) const
708  {
709  return m_polys[aIndex];
710  }
711 
712  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
713  {
714  return m_triangulatedPolys[aIndex].get();
715  }
716 
717  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
718  {
719  return m_polys[aIndex][0];
720  }
721 
722  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
723  {
724  return m_polys[aOutline][aHole + 1];
725  }
726 
727  const POLYGON& CPolygon( int aIndex ) const
728  {
729  return m_polys[aIndex];
730  }
731 
742  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
743  {
744  ITERATOR iter;
745 
746  iter.m_poly = this;
747  iter.m_currentPolygon = aFirst;
748  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
749  iter.m_currentContour = 0;
750  iter.m_currentVertex = 0;
751  iter.m_iterateHoles = aIterateHoles;
752 
753  return iter;
754  }
755 
761  ITERATOR Iterate( int aOutline )
762  {
763  return Iterate( aOutline, aOutline );
764  }
765 
771  ITERATOR IterateWithHoles( int aOutline )
772  {
773  return Iterate( aOutline, aOutline, true );
774  }
775 
781  {
782  return Iterate( 0, OutlineCount() - 1 );
783  }
784 
790  {
791  return Iterate( 0, OutlineCount() - 1, true );
792  }
793 
794 
795  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
796  {
797  CONST_ITERATOR iter;
798 
799  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
800  iter.m_currentPolygon = aFirst;
801  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
802  iter.m_currentContour = 0;
803  iter.m_currentVertex = 0;
804  iter.m_iterateHoles = aIterateHoles;
805 
806  return iter;
807  }
808 
809  CONST_ITERATOR CIterate( int aOutline ) const
810  {
811  return CIterate( aOutline, aOutline );
812  }
813 
814  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
815  {
816  return CIterate( aOutline, aOutline, true );
817  }
818 
820  {
821  return CIterate( 0, OutlineCount() - 1 );
822  }
823 
825  {
826  return CIterate( 0, OutlineCount() - 1, true );
827  }
828 
830  {
831  // Build iterator
832  ITERATOR iter = IterateWithHoles();
833 
834  // Get the relative indices of the globally indexed vertex
835  VERTEX_INDEX indices;
836 
837  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
838  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
839 
840  // Adjust where the iterator is pointing
841  iter.m_currentPolygon = indices.m_polygon;
842  iter.m_currentContour = indices.m_contour;
843  iter.m_currentVertex = indices.m_vertex;
844 
845  return iter;
846  }
847 
850  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
851  {
852  SEGMENT_ITERATOR iter;
853 
854  iter.m_poly = this;
855  iter.m_currentPolygon = aFirst;
856  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
857  iter.m_currentContour = 0;
858  iter.m_currentSegment = 0;
859  iter.m_iterateHoles = aIterateHoles;
860 
861  return iter;
862  }
863 
866  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
867  bool aIterateHoles = false ) const
868  {
870 
871  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
872  iter.m_currentPolygon = aFirst;
873  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
874  iter.m_currentContour = 0;
875  iter.m_currentSegment = 0;
876  iter.m_iterateHoles = aIterateHoles;
877 
878  return iter;
879  }
880 
883  {
884  return IterateSegments( aPolygonIdx, aPolygonIdx );
885  }
886 
888  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
889  {
890  return CIterateSegments( aPolygonIdx, aPolygonIdx );
891  }
892 
895  {
896  return IterateSegments( 0, OutlineCount() - 1 );
897  }
898 
901  {
902  return CIterateSegments( 0, OutlineCount() - 1 );
903  }
904 
907  {
908  return IterateSegments( 0, OutlineCount() - 1, true );
909  }
910 
913  {
914  return IterateSegments( aOutline, aOutline, true );
915  }
916 
919  {
920  return CIterateSegments( 0, OutlineCount() - 1, true );
921  }
922 
925  {
926  return CIterateSegments( aOutline, aOutline, true );
927  }
928 
938  {
939  PM_FAST = true,
941  };
942 
945  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
946 
949  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
950 
953  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
954 
957  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
958  POLYGON_MODE aFastMode );
959 
962  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
963  POLYGON_MODE aFastMode );
964 
967  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
968  POLYGON_MODE aFastMode );
969 
971  {
979  };
981 
996  void Inflate( int aAmount, int aCircleSegCount,
997  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
998 
999  void Deflate( int aAmount, int aCircleSegmentsCount,
1000  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
1001  {
1002  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1003  }
1004 
1012  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1013 
1017  void Fracture( POLYGON_MODE aFastMode );
1018 
1021  void Unfracture( POLYGON_MODE aFastMode );
1022 
1024  bool HasHoles() const;
1025 
1027  bool HasTouchingHoles() const;
1028 
1029 
1032  void Simplify( POLYGON_MODE aFastMode );
1033 
1042  int NormalizeAreaOutlines();
1043 
1045  const std::string Format() const override;
1046 
1048  bool Parse( std::stringstream& aStream ) override;
1049 
1051  void Move( const VECTOR2I& aVector ) override;
1052 
1060  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1061 
1068  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1069 
1071  bool IsSolid() const override
1072  {
1073  return true;
1074  }
1075 
1076  const BOX2I BBox( int aClearance = 0 ) const override;
1077 
1084  bool PointOnEdge( const VECTOR2I& aP ) const;
1085 
1098  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1099  VECTOR2I* aLocation = nullptr ) const override;
1100 
1119  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1120  VECTOR2I* aLocation = nullptr ) const override;
1121 
1140  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1141  VECTOR2I* aLocation = nullptr ) const override;
1142 
1153  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1154  int aClearance = 0 ) const;
1155 
1166  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1167  int aClearance = 0 ) const;
1168 
1175  void BuildBBoxCaches() const;
1176 
1177  const BOX2I BBoxFromCaches() const;
1178 
1189  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1190  bool aUseBBoxCaches = false ) const;
1191 
1193  bool IsEmpty() const
1194  {
1195  return m_polys.empty();
1196  }
1197 
1203  void RemoveVertex( int aGlobalIndex );
1204 
1210  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1211 
1213  void RemoveAllContours();
1214 
1223  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1224 
1230  int RemoveNullSegments();
1231 
1238  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1239 
1248  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1249 
1251  int TotalVertices() const;
1252 
1254  void DeletePolygon( int aIdx );
1255 
1263  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1264 
1273  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1274 
1281  SHAPE_POLY_SET Chamfer( int aDistance );
1282 
1290  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1291 
1302  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1303  VECTOR2I* aNearest ) const;
1304 
1317  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1318  VECTOR2I* aNearest) const;
1319 
1330  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1331 
1343  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1344 
1351  bool IsVertexInHole( int aGlobalIdx );
1352 
1353 private:
1354  void fractureSingle( POLYGON& paths );
1355  void unfractureSingle ( POLYGON& path );
1356  void importTree( ClipperLib::PolyTree* tree,
1357  const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1358  const std::vector<SHAPE_ARC>& aArcBuffe );
1359 
1372  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1373  POLYGON_MODE aFastMode );
1374 
1375  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1376  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1377 
1392  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1393  bool aUseBBoxCaches = false ) const;
1394 
1401  {
1404  };
1405 
1419  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1420  int aIndex, int aErrorMax );
1421 
1423  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1424 
1425  MD5_HASH checksum() const;
1426 
1427 private:
1428  typedef std::vector<POLYGON> POLYSET;
1429 
1431 
1432  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1433 
1434  bool m_triangulationValid = false;
1436 };
1437 
1438 #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
Return the number of points in the shape poly set.
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:622
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:72
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 containing arcs as well as line segments: A chain of connected line and/or arc s...
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)
int FullPointCount() const
Returns the number of holes in a given outline.
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.