KiCad PCB EDA Suite
shape_poly_set.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2019 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #ifndef __SHAPE_POLY_SET_H
27 #define __SHAPE_POLY_SET_H
28 
29 #include <cstdio>
30 #include <deque> // for deque
31 #include <vector> // for vector
32 #include <iosfwd> // for string, stringstream
33 #include <memory>
34 #include <set> // for set
35 #include <stdexcept> // for out_of_range
36 #include <stdlib.h> // for abs
37 #include <vector>
38 
39 #include <clipper.hpp> // for ClipType, PolyTree (ptr only)
40 #include <geometry/seg.h> // for SEG
41 #include <geometry/shape.h>
43 #include <math/box2.h> // for BOX2I
44 #include <math/vector2d.h> // for VECTOR2I
45 #include <md5_hash.h>
46 
47 
64 class SHAPE_POLY_SET : public SHAPE
65 {
66 public:
70  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
71 
73  {
74  public:
75  struct TRI : public SHAPE_LINE_CHAIN_BASE
76  {
77  TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
79  a( _a ),
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 
188  typedef struct VERTEX_INDEX
189  {
190  int m_polygon;
191  int m_contour;
192  int m_vertex;
195  m_polygon(-1),
196  m_contour(-1),
197  m_vertex(-1)
198  {
199  }
200  } VERTEX_INDEX;
201 
207  template <class T>
209  {
210  public:
211 
217  bool IsEndContour() const
218  {
219  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
220  }
221 
226  bool IsLastPolygon() const
227  {
229  }
230 
231  operator bool() const
232  {
234  return true;
235 
236  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
237  return false;
238 
239  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
240 
241  return m_currentContour < (int) currentPolygon.size() - 1
242  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
243  }
244 
250  void Advance()
251  {
252  // Advance vertex index
253  m_currentVertex ++;
254 
255  // Check whether the user wants to iterate through the vertices of the holes
256  // and behave accordingly
257  if( m_iterateHoles )
258  {
259  // If the last vertex of the contour was reached, advance the contour index
261  {
262  m_currentVertex = 0;
264 
265  // If the last contour of the current polygon was reached, advance the
266  // outline index
267  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
268 
269  if( m_currentContour >= totalContours )
270  {
271  m_currentContour = 0;
273  }
274  }
275  }
276  else
277  {
278  // If the last vertex of the outline was reached, advance to the following polygon
279  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
280  {
281  m_currentVertex = 0;
283  }
284  }
285  }
286 
287  void operator++( int dummy )
288  {
289  Advance();
290  }
291 
292  void operator++()
293  {
294  Advance();
295  }
296 
297  const T& Get()
298  {
300  }
301 
302  const T& operator*()
303  {
304  return Get();
305  }
306 
307  const T* operator->()
308  {
309  return &Get();
310  }
311 
317  {
318  VERTEX_INDEX index;
319 
320  index.m_polygon = m_currentPolygon;
321  index.m_contour = m_currentContour;
322  index.m_vertex = m_currentVertex;
323 
324  return index;
325  }
326 
327  private:
328  friend class SHAPE_POLY_SET;
329 
336  };
337 
343  template <class T>
345  {
346  public:
351  bool IsLastPolygon() const
352  {
354  }
355 
356  operator bool() const
357  {
359  }
360 
366  void Advance()
367  {
368  // Advance vertex index
370  int last;
371 
372  // Check whether the user wants to iterate through the vertices of the holes
373  // and behave accordingly
374  if( m_iterateHoles )
375  {
376  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
377 
378  // If the last vertex of the contour was reached, advance the contour index
379  if( m_currentSegment >= last )
380  {
381  m_currentSegment = 0;
383 
384  // If the last contour of the current polygon was reached, advance the
385  // outline index
386  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
387 
388  if( m_currentContour >= totalContours )
389  {
390  m_currentContour = 0;
392  }
393  }
394  }
395  else
396  {
397  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
398  // If the last vertex of the outline was reached, advance to the following
399  // polygon
400  if( m_currentSegment >= last )
401  {
402  m_currentSegment = 0;
404  }
405  }
406  }
407 
408  void operator++( int dummy )
409  {
410  Advance();
411  }
412 
413  void operator++()
414  {
415  Advance();
416  }
417 
418  T Get()
419  {
421  }
422 
424  {
425  return Get();
426  }
427 
433  {
434  VERTEX_INDEX index;
435 
436  index.m_polygon = m_currentPolygon;
437  index.m_contour = m_currentContour;
438  index.m_vertex = m_currentSegment;
439 
440  return index;
441  }
442 
451  {
452  // Check that both iterators point to the same contour of the same polygon of the
453  // same polygon set
454  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
456  {
457  // Compute the total number of segments
458  int numSeg;
459  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
460 
461  // Compute the difference of the segment indices. If it is exactly one, they
462  // are adjacent. The only missing case where they also are adjacent is when
463  // the segments are the first and last one, in which case the difference
464  // always equals the total number of segments minus one.
465  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
466 
467  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
468  }
469 
470  return false;
471  }
472 
473  private:
474  friend class SHAPE_POLY_SET;
475 
482  };
483 
484  // Iterator and const iterator types to visit polygon's points.
487 
488  // Iterator and const iterator types to visit polygon's edges.
491 
492  SHAPE_POLY_SET();
493 
499  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
500 
506  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
507 
508  ~SHAPE_POLY_SET();
509 
511 
512  void CacheTriangulation( bool aPartition = true );
513  bool IsTriangulationUpToDate() const;
514 
515  MD5_HASH GetHash() const;
516 
517  virtual bool HasIndexableSubshapes() const override;
518 
519  virtual size_t GetIndexableSubshapeCount() const override;
520 
521  virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
522 
535  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
536 
546  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
547 
549  SHAPE* Clone() const override;
550 
552  int NewOutline();
553 
555  int NewHole( int aOutline = -1 );
556 
558  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
559 
561  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
562 
564 
576  int Append( int x, int y, int aOutline = -1, int aHole = -1,
577  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 
592  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
593 
595  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
596 
598  const VECTOR2I& CVertex( int aGlobalIndex ) const;
599 
601  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
602 
614  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
615 
616 
624  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
625 
631  bool IsSelfIntersecting() const;
632 
634  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
635 
637  int OutlineCount() const { return m_polys.size(); }
638 
640  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
641 
643  int HoleCount( int aOutline ) const
644  {
645  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
646  return 0;
647 
648  // the first polygon in m_polys[aOutline] is the main contour,
649  // only others are holes:
650  return m_polys[aOutline].size() - 1;
651  }
652 
654  SHAPE_LINE_CHAIN& Outline( int aIndex )
655  {
656  return m_polys[aIndex][0];
657  }
658 
659  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
660  {
661  return m_polys[aIndex][0];
662  }
663 
673  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
674 
675  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
676  {
677  return Subset( aPolygonIndex, aPolygonIndex + 1 );
678  }
679 
681  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
682  {
683  return m_polys[aOutline][aHole + 1];
684  }
685 
687  POLYGON& Polygon( int aIndex )
688  {
689  return m_polys[aIndex];
690  }
691 
692  const POLYGON& Polygon( int aIndex ) const
693  {
694  return m_polys[aIndex];
695  }
696 
697  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
698  {
699  return m_triangulatedPolys[aIndex].get();
700  }
701 
702  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
703  {
704  return m_polys[aIndex][0];
705  }
706 
707  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
708  {
709  return m_polys[aOutline][aHole + 1];
710  }
711 
712  const POLYGON& CPolygon( int aIndex ) const
713  {
714  return m_polys[aIndex];
715  }
716 
727  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
728  {
729  ITERATOR iter;
730 
731  iter.m_poly = this;
732  iter.m_currentPolygon = aFirst;
733  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
734  iter.m_currentContour = 0;
735  iter.m_currentVertex = 0;
736  iter.m_iterateHoles = aIterateHoles;
737 
738  return iter;
739  }
740 
747  ITERATOR Iterate( int aOutline )
748  {
749  return Iterate( aOutline, aOutline );
750  }
751 
758  ITERATOR IterateWithHoles( int aOutline )
759  {
760  return Iterate( aOutline, aOutline, true );
761  }
762 
769  {
770  return Iterate( 0, OutlineCount() - 1 );
771  }
772 
779  {
780  return Iterate( 0, OutlineCount() - 1, true );
781  }
782 
783 
784  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
785  {
786  CONST_ITERATOR iter;
787 
788  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
789  iter.m_currentPolygon = aFirst;
790  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
791  iter.m_currentContour = 0;
792  iter.m_currentVertex = 0;
793  iter.m_iterateHoles = aIterateHoles;
794 
795  return iter;
796  }
797 
798  CONST_ITERATOR CIterate( int aOutline ) const
799  {
800  return CIterate( aOutline, aOutline );
801  }
802 
803  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
804  {
805  return CIterate( aOutline, aOutline, true );
806  }
807 
809  {
810  return CIterate( 0, OutlineCount() - 1 );
811  }
812 
814  {
815  return CIterate( 0, OutlineCount() - 1, true );
816  }
817 
819  {
820  // Build iterator
821  ITERATOR iter = IterateWithHoles();
822 
823  // Get the relative indices of the globally indexed vertex
824  VERTEX_INDEX indices;
825 
826  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
827  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
828 
829  // Adjust where the iterator is pointing
830  iter.m_currentPolygon = indices.m_polygon;
831  iter.m_currentContour = indices.m_contour;
832  iter.m_currentVertex = indices.m_vertex;
833 
834  return iter;
835  }
836 
839  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
840  {
841  SEGMENT_ITERATOR iter;
842 
843  iter.m_poly = this;
844  iter.m_currentPolygon = aFirst;
845  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
846  iter.m_currentContour = 0;
847  iter.m_currentSegment = 0;
848  iter.m_iterateHoles = aIterateHoles;
849 
850  return iter;
851  }
852 
855  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
856  bool aIterateHoles = false ) const
857  {
859 
860  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
861  iter.m_currentPolygon = aFirst;
862  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
863  iter.m_currentContour = 0;
864  iter.m_currentSegment = 0;
865  iter.m_iterateHoles = aIterateHoles;
866 
867  return iter;
868  }
869 
872  {
873  return IterateSegments( aPolygonIdx, aPolygonIdx );
874  }
875 
877  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
878  {
879  return CIterateSegments( aPolygonIdx, aPolygonIdx );
880  }
881 
884  {
885  return IterateSegments( 0, OutlineCount() - 1 );
886  }
887 
890  {
891  return IterateSegments( 0, OutlineCount() - 1, true );
892  }
893 
896  {
897  return IterateSegments( aOutline, aOutline, true );
898  }
899 
902  {
903  return CIterateSegments( 0, OutlineCount() - 1, true );
904  }
905 
908  {
909  return CIterateSegments( aOutline, aOutline, true );
910  }
911 
920  {
921  PM_FAST = true,
923  };
924 
927  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
928 
931  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
932 
935  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
936 
939  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
940  POLYGON_MODE aFastMode );
941 
944  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
945  POLYGON_MODE aFastMode );
946 
949  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
950  POLYGON_MODE aFastMode );
951 
953  {
961  };
963 
976  void Inflate( int aAmount, int aCircleSegmentsCount,
977  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
978 
979  void Deflate( int aAmount, int aCircleSegmentsCount,
980  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
981  {
982  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
983  }
984 
990  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
991 
995  void Fracture( POLYGON_MODE aFastMode );
996 
999  void Unfracture( POLYGON_MODE aFastMode );
1000 
1002  bool HasHoles() const;
1003 
1005  bool HasTouchingHoles() const;
1006 
1007 
1010  void Simplify( POLYGON_MODE aFastMode );
1011 
1019  int NormalizeAreaOutlines();
1020 
1022  const std::string Format() const override;
1023 
1025  bool Parse( std::stringstream& aStream ) override;
1026 
1028  void Move( const VECTOR2I& aVector ) override;
1029 
1036  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1037 
1044  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1045 
1047  bool IsSolid() const override
1048  {
1049  return true;
1050  }
1051 
1052  const BOX2I BBox( int aClearance = 0 ) const override;
1053 
1061  bool PointOnEdge( const VECTOR2I& aP ) const;
1062 
1076  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1077  VECTOR2I* aLocation = nullptr ) const override;
1078 
1098  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1099  VECTOR2I* aLocation = nullptr ) const override;
1100 
1121  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1122  VECTOR2I* aLocation = nullptr ) const override;
1123 
1134  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1135  int aClearance = 0 ) const;
1136 
1147  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1148  int aClearance = 0 ) const;
1149 
1154  void BuildBBoxCaches();
1155 
1156  const BOX2I BBoxFromCaches() const;
1157 
1168  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1169  bool aUseBBoxCaches = false ) const;
1170 
1172  bool IsEmpty() const
1173  {
1174  return m_polys.size() == 0;
1175  }
1176 
1182  void RemoveVertex( int aGlobalIndex );
1183 
1189  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1190 
1192  void RemoveAllContours();
1193 
1202  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1203 
1209  int RemoveNullSegments();
1210 
1217  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1218 
1225  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1226 
1228  int TotalVertices() const;
1229 
1231  void DeletePolygon( int aIdx );
1232 
1240  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1241 
1250  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1251 
1258  SHAPE_POLY_SET Chamfer( int aDistance );
1259 
1267  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1268 
1279  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1280  VECTOR2I* aNearest ) const;
1281 
1295  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1296  VECTOR2I* aNearest) const;
1297 
1308  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1309 
1321  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1322 
1329  bool IsVertexInHole( int aGlobalIdx );
1330 
1331 private:
1332  void fractureSingle( POLYGON& paths );
1333  void unfractureSingle ( POLYGON& path );
1334  void importTree( ClipperLib::PolyTree* tree );
1335 
1347  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1348  POLYGON_MODE aFastMode );
1349 
1350  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1351  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1352 
1368  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1369  bool aUseBBoxCaches = false ) const;
1370 
1377  {
1380  };
1381 
1396  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1397  int aIndex, int aErrorMax );
1398 
1400  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1401 
1402  MD5_HASH checksum() const;
1403 
1404 private:
1405  typedef std::vector<POLYGON> POLYSET;
1406 
1408 
1409  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1410 
1411  bool m_triangulationValid = false;
1413 };
1414 
1415 #endif
int TotalVertices() const
Returns total number of vertices stored in the set.
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
const POLYGON & CPolygon(int aIndex) const
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Returns the number of outlines in the set
All angles are chamfered.
virtual void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate.
bool IsEndContour() const
Function IsEndContour.
void fractureSingle(POLYGON &paths)
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
ITERATOR Iterate(int aOutline)
Function Iterate.
void GetTriangle(int index, VECTOR2I &a, VECTOR2I &b, VECTOR2I &c) const
std::vector< POLYGON > POLYSET
const BOX2I BBoxFromCaches() const
virtual bool IsSolid() const override
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
void Move(const VECTOR2I &aVec)
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
VECTOR2I::extended_type ecoord
Definition: seg.h:42
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
bool IsSolid() const override
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Returns true if the polygon set has any holes.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
CONST_ITERATOR CIterateWithHoles(int aOutline) const
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
Struct VERTEX_INDEX.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
MD5_HASH checksum() const
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate rotates all vertices by a given angle.
virtual const VECTOR2I GetPoint(int aIndex) const override
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
ITERATOR Iterate()
Function Iterate.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Returns true if a given subpolygon contains the point aP.
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Function Iterate returns an object to iterate through the points of the polygons between aFirst and a...
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
virtual const SEG GetSegment(int aIndex) const override
VECTOR2< int > VECTOR2I
Definition: vector2d.h:630
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool IsTriangulationUpToDate() const
struct SHAPE_POLY_SET::VERTEX_INDEX VERTEX_INDEX
Struct VERTEX_INDEX.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
bool IsLastPolygon() const
Function IsLastOutline.
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a con...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Function SetVertex Accessor function to set the position of a specific point.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
virtual size_t GetSegmentCount() const override
Acute angles are rounded.
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
SHAPE_POLY_SET.
virtual size_t GetPointCount() const override
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
void Advance()
Function Advance advances the indices of the current vertex/outline/contour, checking whether the ver...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
void Deflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Returns an iterator object, for the aOutline-th outline in the set (with holes)
const SHAPE_LINE_CHAIN & Outline(int aIndex) const
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
SHAPE.
Definition: shape.h:123
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
const std::string Format() const override
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int NewOutline()
Creates a new empty polygon in the set and returns its index
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
Acute angles are chamfered.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
virtual void Move(const VECTOR2I &aVector) override
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
void BuildBBoxCaches()
Constructs BBoxCaches for Contains(), below.
const POLYGON & Polygon(int aIndex) const
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
Definition: seg.h:39
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
virtual const BOX2I BBox(int aClearance=0) const override
Function BBox()
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
void AddVertex(const VECTOR2I &aP)
empty shape (no shape...),
Definition: shape.h:52
void AddTriangle(int a, int b, int c)
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
TRI(int _a=0, int _b=0, int _c=0, TRIANGULATED_POLYGON *aParent=nullptr)
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
ITERATOR IterateWithHoles()
Function IterateWithHoles.
SHAPE_LINE_CHAIN.
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Function Fillet returns a filleted version of the aIndex-th polygon.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
CONST_ITERATOR CIterate() const
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
CONST_ITERATOR CIterate(int aOutline) const
void CacheTriangulation(bool aPartition=true)
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
SHAPE * Clone() const override
Function Clone()
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Returns an iterator object, for iterating aPolygonIdx-th polygon edges
const BOX2I BBox(int aClearance=0) const override
Function BBox()
just inflate the polygon. Acute angles create spikes
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
VERTEX_INDEX GetIndex()
Function GetIndex.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
CONST_ITERATOR CIterateWithHoles() const
virtual bool IsClosed() const override
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Returns an iterator object, for iterating between aFirst and aLast outline, with or without holes (de...
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
bool IsSelfIntersecting() const
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
bool IsLastPolygon() const
Function IsLastOutline.