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 
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 
653  int HoleCount( int aOutline ) const
654  {
655  if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
656  || ( m_polys[aOutline].size() < 2 ) )
657  return 0;
658 
659  // the first polygon in m_polys[aOutline] is the main contour,
660  // only others are holes:
661  return m_polys[aOutline].size() - 1;
662  }
663 
665  SHAPE_LINE_CHAIN& Outline( int aIndex )
666  {
667  return m_polys[aIndex][0];
668  }
669 
670  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
671  {
672  return m_polys[aIndex][0];
673  }
674 
684  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
685 
686  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
687  {
688  return Subset( aPolygonIndex, aPolygonIndex + 1 );
689  }
690 
692  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
693  {
694  return m_polys[aOutline][aHole + 1];
695  }
696 
698  POLYGON& Polygon( int aIndex )
699  {
700  return m_polys[aIndex];
701  }
702 
703  const POLYGON& Polygon( int aIndex ) const
704  {
705  return m_polys[aIndex];
706  }
707 
708  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
709  {
710  return m_triangulatedPolys[aIndex].get();
711  }
712 
713  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
714  {
715  return m_polys[aIndex][0];
716  }
717 
718  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
719  {
720  return m_polys[aOutline][aHole + 1];
721  }
722 
723  const POLYGON& CPolygon( int aIndex ) const
724  {
725  return m_polys[aIndex];
726  }
727 
738  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
739  {
740  ITERATOR iter;
741 
742  iter.m_poly = this;
743  iter.m_currentPolygon = aFirst;
744  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
745  iter.m_currentContour = 0;
746  iter.m_currentVertex = 0;
747  iter.m_iterateHoles = aIterateHoles;
748 
749  return iter;
750  }
751 
757  ITERATOR Iterate( int aOutline )
758  {
759  return Iterate( aOutline, aOutline );
760  }
761 
767  ITERATOR IterateWithHoles( int aOutline )
768  {
769  return Iterate( aOutline, aOutline, true );
770  }
771 
777  {
778  return Iterate( 0, OutlineCount() - 1 );
779  }
780 
786  {
787  return Iterate( 0, OutlineCount() - 1, true );
788  }
789 
790 
791  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
792  {
793  CONST_ITERATOR iter;
794 
795  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
796  iter.m_currentPolygon = aFirst;
797  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
798  iter.m_currentContour = 0;
799  iter.m_currentVertex = 0;
800  iter.m_iterateHoles = aIterateHoles;
801 
802  return iter;
803  }
804 
805  CONST_ITERATOR CIterate( int aOutline ) const
806  {
807  return CIterate( aOutline, aOutline );
808  }
809 
810  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
811  {
812  return CIterate( aOutline, aOutline, true );
813  }
814 
816  {
817  return CIterate( 0, OutlineCount() - 1 );
818  }
819 
821  {
822  return CIterate( 0, OutlineCount() - 1, true );
823  }
824 
826  {
827  // Build iterator
828  ITERATOR iter = IterateWithHoles();
829 
830  // Get the relative indices of the globally indexed vertex
831  VERTEX_INDEX indices;
832 
833  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
834  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
835 
836  // Adjust where the iterator is pointing
837  iter.m_currentPolygon = indices.m_polygon;
838  iter.m_currentContour = indices.m_contour;
839  iter.m_currentVertex = indices.m_vertex;
840 
841  return iter;
842  }
843 
846  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
847  {
848  SEGMENT_ITERATOR iter;
849 
850  iter.m_poly = this;
851  iter.m_currentPolygon = aFirst;
852  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
853  iter.m_currentContour = 0;
854  iter.m_currentSegment = 0;
855  iter.m_iterateHoles = aIterateHoles;
856 
857  return iter;
858  }
859 
862  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
863  bool aIterateHoles = false ) const
864  {
866 
867  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
868  iter.m_currentPolygon = aFirst;
869  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
870  iter.m_currentContour = 0;
871  iter.m_currentSegment = 0;
872  iter.m_iterateHoles = aIterateHoles;
873 
874  return iter;
875  }
876 
879  {
880  return IterateSegments( aPolygonIdx, aPolygonIdx );
881  }
882 
884  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
885  {
886  return CIterateSegments( aPolygonIdx, aPolygonIdx );
887  }
888 
891  {
892  return IterateSegments( 0, OutlineCount() - 1 );
893  }
894 
897  {
898  return CIterateSegments( 0, OutlineCount() - 1 );
899  }
900 
903  {
904  return IterateSegments( 0, OutlineCount() - 1, true );
905  }
906 
909  {
910  return IterateSegments( aOutline, aOutline, true );
911  }
912 
915  {
916  return CIterateSegments( 0, OutlineCount() - 1, true );
917  }
918 
921  {
922  return CIterateSegments( aOutline, aOutline, true );
923  }
924 
934  {
935  PM_FAST = true,
937  };
938 
941  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
942 
945  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
946 
949  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
950 
953  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
954  POLYGON_MODE aFastMode );
955 
958  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
959  POLYGON_MODE aFastMode );
960 
963  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
964  POLYGON_MODE aFastMode );
965 
967  {
975  };
977 
992  void Inflate( int aAmount, int aCircleSegCount,
993  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
994 
995  void Deflate( int aAmount, int aCircleSegmentsCount,
996  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
997  {
998  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
999  }
1000 
1008  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1009 
1013  void Fracture( POLYGON_MODE aFastMode );
1014 
1017  void Unfracture( POLYGON_MODE aFastMode );
1018 
1020  bool HasHoles() const;
1021 
1023  bool HasTouchingHoles() const;
1024 
1025 
1028  void Simplify( POLYGON_MODE aFastMode );
1029 
1038  int NormalizeAreaOutlines();
1039 
1041  const std::string Format() const override;
1042 
1044  bool Parse( std::stringstream& aStream ) override;
1045 
1047  void Move( const VECTOR2I& aVector ) override;
1048 
1056  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1057 
1064  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1065 
1067  bool IsSolid() const override
1068  {
1069  return true;
1070  }
1071 
1072  const BOX2I BBox( int aClearance = 0 ) const override;
1073 
1080  bool PointOnEdge( const VECTOR2I& aP ) const;
1081 
1094  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1095  VECTOR2I* aLocation = nullptr ) const override;
1096 
1115  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1116  VECTOR2I* aLocation = nullptr ) const override;
1117 
1136  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1137  VECTOR2I* aLocation = nullptr ) const override;
1138 
1149  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1150  int aClearance = 0 ) const;
1151 
1162  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1163  int aClearance = 0 ) const;
1164 
1171  void BuildBBoxCaches() const;
1172 
1173  const BOX2I BBoxFromCaches() const;
1174 
1185  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1186  bool aUseBBoxCaches = false ) const;
1187 
1189  bool IsEmpty() const
1190  {
1191  return m_polys.empty();
1192  }
1193 
1199  void RemoveVertex( int aGlobalIndex );
1200 
1206  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1207 
1209  void RemoveAllContours();
1210 
1219  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1220 
1226  int RemoveNullSegments();
1227 
1234  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1235 
1244  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1245 
1247  int TotalVertices() const;
1248 
1250  void DeletePolygon( int aIdx );
1251 
1259  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1260 
1269  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1270 
1277  SHAPE_POLY_SET Chamfer( int aDistance );
1278 
1286  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1287 
1298  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1299  VECTOR2I* aNearest ) const;
1300 
1313  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1314  VECTOR2I* aNearest) const;
1315 
1326  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1327 
1339  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1340 
1347  bool IsVertexInHole( int aGlobalIdx );
1348 
1349 private:
1350  void fractureSingle( POLYGON& paths );
1351  void unfractureSingle ( POLYGON& path );
1352  void importTree( ClipperLib::PolyTree* tree,
1353  const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1354  const std::vector<SHAPE_ARC>& aArcBuffe );
1355 
1368  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1369  POLYGON_MODE aFastMode );
1370 
1371  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1372  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1373 
1388  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1389  bool aUseBBoxCaches = false ) const;
1390 
1397  {
1400  };
1401 
1415  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1416  int aIndex, int aErrorMax );
1417 
1419  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1420 
1421  MD5_HASH checksum() const;
1422 
1423 private:
1424  typedef std::vector<POLYGON> POLYSET;
1425 
1427 
1428  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1429 
1430  bool m_triangulationValid = false;
1432 };
1433 
1434 #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: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 (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.