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 <iosfwd> // for string, stringstream
32 #include <memory>
33 #include <set> // for set
34 #include <stdexcept> // for out_of_range
35 #include <stdlib.h> // for abs
36 #include <vector>
37 
38 #include <clipper.hpp> // for ClipType, PolyTree (ptr only)
39 #include <geometry/seg.h> // for SEG
40 #include <geometry/shape.h>
42 #include <math/box2.h> // for BOX2I
43 #include <math/vector2d.h> // for VECTOR2I
44 #include <md5_hash.h>
45 
46 
63 class SHAPE_POLY_SET : public SHAPE
64 {
65  public:
69  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
70 
72  {
73  public:
74  struct TRI : public SHAPE_LINE_CHAIN_BASE
75  {
76  TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
78  a( _a ), b( _b ), c( _c ), parent( aParent )
79  {
80  }
81 
82  virtual void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override {};
83 
84  virtual void Move( const VECTOR2I& aVector ) override {};
85 
86  virtual bool IsSolid() const override { return true; }
87 
88  virtual bool IsClosed() const override { return true; }
89 
90  virtual const BOX2I BBox( int aClearance = 0 ) const override
91  {
92  BOX2I bbox( parent->m_vertices[a] );
93  bbox.Merge( parent->m_vertices[b] );
94  bbox.Merge( parent->m_vertices[c] );
95 
96  if( aClearance != 0 )
97  bbox.Inflate( aClearance );
98 
99  return bbox;
100  }
101 
102  virtual const VECTOR2I GetPoint( int aIndex ) const override
103  {
104  switch(aIndex)
105  {
106  case 0: return parent->m_vertices[a];
107  case 1: return parent->m_vertices[b];
108  case 2: return parent->m_vertices[c];
109  default: assert(false);
110  }
111  return VECTOR2I(0, 0);
112  }
113 
114  virtual const SEG GetSegment( int aIndex ) const override
115  {
116  switch(aIndex)
117  {
118  case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
119  case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
120  case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
121  default: assert(false);
122  }
123  return SEG();
124  }
125 
126  virtual size_t GetPointCount() const override { return 3; }
127  virtual size_t GetSegmentCount() const override { return 3; }
128 
129 
130  int a, b, c;
132  };
133 
134  void Clear()
135  {
136  m_vertices.clear();
137  m_triangles.clear();
138  }
139 
140  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
141  {
142  auto tri = m_triangles[ index ];
143  a = m_vertices[ tri.a ];
144  b = m_vertices[ tri.b ];
145  c = m_vertices[ tri.c ];
146  }
147 
148  void AddTriangle( const TRI& aTri )
149  {
150  m_triangles.push_back( aTri );
151  }
152 
153  void AddTriangle( int a, int b, int c )
154  {
155  m_triangles.emplace_back( a, b, c, this );
156  }
157 
158  void AddVertex( const VECTOR2I& aP )
159  {
160  m_vertices.push_back( aP );
161  }
162 
163  size_t GetTriangleCount() const
164  {
165  return m_triangles.size();
166  }
167 
168  size_t GetVertexCount() const
169  {
170  return m_vertices.size();
171  }
172 
173  void Move( const VECTOR2I& aVec )
174  {
175  for( auto& vertex : m_vertices )
176  vertex += aVec;
177  }
178 
179  private:
180 
181  std::deque<TRI> m_triangles;
182  std::deque<VECTOR2I> m_vertices;
183  };
184 
192  typedef struct VERTEX_INDEX
193  {
194  int m_polygon;
195  int m_contour;
196  int m_vertex;
199  {
200  }
201  } VERTEX_INDEX;
202 
208  template <class T>
210  {
211  public:
212 
218  bool IsEndContour() const
219  {
220  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
221  }
222 
227  bool IsLastPolygon() const
228  {
230  }
231 
232  operator bool() const
233  {
235  return true;
236 
237  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
238  return false;
239 
240  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
241 
242  return m_currentContour < (int) currentPolygon.size() - 1
243  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
244  }
245 
251  void Advance()
252  {
253  // Advance vertex index
254  m_currentVertex ++;
255 
256  // Check whether the user wants to iterate through the vertices of the holes
257  // and behave accordingly
258  if( m_iterateHoles )
259  {
260  // If the last vertex of the contour was reached, advance the contour index
262  {
263  m_currentVertex = 0;
265 
266  // If the last contour of the current polygon was reached, advance the
267  // outline index
268  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
269 
270  if( m_currentContour >= totalContours )
271  {
272  m_currentContour = 0;
274  }
275  }
276  }
277  else
278  {
279  // If the last vertex of the outline was reached, advance to the following polygon
280  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
281  {
282  m_currentVertex = 0;
284  }
285  }
286  }
287 
288  void operator++( int dummy )
289  {
290  Advance();
291  }
292 
293  void operator++()
294  {
295  Advance();
296  }
297 
298  const T& Get()
299  {
300  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint(
301  m_currentVertex );
302  }
303 
304  const T& operator*()
305  {
306  return Get();
307  }
308 
309  const T* operator->()
310  {
311  return &Get();
312  }
313 
319  {
320  VERTEX_INDEX index;
321 
322  index.m_polygon = m_currentPolygon;
323  index.m_contour = m_currentContour;
324  index.m_vertex = m_currentVertex;
325 
326  return index;
327  }
328 
329 
330  private:
331  friend class SHAPE_POLY_SET;
332 
339  };
340 
346  template <class T>
348  {
349  public:
354  bool IsLastPolygon() const
355  {
357  }
358 
359  operator bool() const
360  {
362  }
363 
369  void Advance()
370  {
371  // Advance vertex index
373  int last;
374 
375  // Check whether the user wants to iterate through the vertices of the holes
376  // and behave accordingly
377  if( m_iterateHoles )
378  {
379  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
380 
381  // If the last vertex of the contour was reached, advance the contour index
382  if( m_currentSegment >= last )
383  {
384  m_currentSegment = 0;
386 
387  // If the last contour of the current polygon was reached, advance the
388  // outline index
389  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
390 
391  if( m_currentContour >= totalContours )
392  {
393  m_currentContour = 0;
395  }
396  }
397  }
398  else
399  {
400  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
401  // If the last vertex of the outline was reached, advance to the following
402  // polygon
403  if( m_currentSegment >= last )
404  {
405  m_currentSegment = 0;
407  }
408  }
409  }
410 
411  void operator++( int dummy )
412  {
413  Advance();
414  }
415 
416  void operator++()
417  {
418  Advance();
419  }
420 
421  T Get()
422  {
424  }
425 
427  {
428  return Get();
429  }
430 
436  {
437  VERTEX_INDEX index;
438 
439  index.m_polygon = m_currentPolygon;
440  index.m_contour = m_currentContour;
441  index.m_vertex = m_currentSegment;
442 
443  return index;
444  }
445 
454  {
455  // Check that both iterators point to the same contour of the same polygon of the
456  // same polygon set
457  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
459  {
460  // Compute the total number of segments
461  int numSeg;
462  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
463 
464  // Compute the difference of the segment indices. If it is exactly one, they
465  // are adjacent. The only missing case where they also are adjacent is when
466  // the segments are the first and last one, in which case the difference
467  // always equals the total number of segments minus one.
468  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
469 
470  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
471  }
472 
473  return false;
474  }
475 
476  private:
477  friend class SHAPE_POLY_SET;
478 
485  };
486 
487  // Iterator and const iterator types to visit polygon's points.
490 
491  // Iterator and const iterator types to visit polygon's edges.
494 
495  SHAPE_POLY_SET();
496 
502  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
503 
509  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
510 
511  ~SHAPE_POLY_SET();
512 
525  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
526 
536  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
537 
539  SHAPE* Clone() const override;
540 
542  int NewOutline();
543 
545  int NewHole( int aOutline = -1 );
546 
548  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
549 
551  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
552 
554 
566  int Append( int x, int y, int aOutline = -1, int aHole = -1,
567  bool aAllowDuplication = false );
568 
570  void Append( const SHAPE_POLY_SET& aSet );
571 
573  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
574 
582  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
583 
585  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
586 
588  const VECTOR2I& CVertex( int aGlobalIndex ) const;
589 
591  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
592 
604  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
605 
606 
614  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
615 
621  bool IsSelfIntersecting() const;
622 
624  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
625 
627  int OutlineCount() const { return m_polys.size(); }
628 
630  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
631 
633  int HoleCount( int aOutline ) const
634  {
635  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
636  return 0;
637 
638  // the first polygon in m_polys[aOutline] is the main contour,
639  // only others are holes:
640  return m_polys[aOutline].size() - 1;
641  }
642 
644  SHAPE_LINE_CHAIN& Outline( int aIndex )
645  {
646  return m_polys[aIndex][0];
647  }
648 
658  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
659 
660  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
661  {
662  return Subset( aPolygonIndex, aPolygonIndex + 1 );
663  }
664 
666  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
667  {
668  return m_polys[aOutline][aHole + 1];
669  }
670 
672  POLYGON& Polygon( int aIndex )
673  {
674  return m_polys[aIndex];
675  }
676 
677  const POLYGON& Polygon( int aIndex ) const
678  {
679  return m_polys[aIndex];
680  }
681 
682  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
683  {
684  return m_triangulatedPolys[aIndex].get();
685  }
686 
687  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
688  {
689  return m_polys[aIndex][0];
690  }
691 
692  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
693  {
694  return m_polys[aOutline][aHole + 1];
695  }
696 
697  const POLYGON& CPolygon( int aIndex ) const
698  {
699  return m_polys[aIndex];
700  }
701 
712  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
713  {
714  ITERATOR iter;
715 
716  iter.m_poly = this;
717  iter.m_currentPolygon = aFirst;
718  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
719  iter.m_currentContour = 0;
720  iter.m_currentVertex = 0;
721  iter.m_iterateHoles = aIterateHoles;
722 
723  return iter;
724  }
725 
732  ITERATOR Iterate( int aOutline )
733  {
734  return Iterate( aOutline, aOutline );
735  }
736 
743  ITERATOR IterateWithHoles( int aOutline )
744  {
745  return Iterate( aOutline, aOutline, true );
746  }
747 
754  {
755  return Iterate( 0, OutlineCount() - 1 );
756  }
757 
764  {
765  return Iterate( 0, OutlineCount() - 1, true );
766  }
767 
768 
769  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
770  {
771  CONST_ITERATOR iter;
772 
773  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
774  iter.m_currentPolygon = aFirst;
775  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
776  iter.m_currentContour = 0;
777  iter.m_currentVertex = 0;
778  iter.m_iterateHoles = aIterateHoles;
779 
780  return iter;
781  }
782 
783  CONST_ITERATOR CIterate( int aOutline ) const
784  {
785  return CIterate( aOutline, aOutline );
786  }
787 
788  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
789  {
790  return CIterate( aOutline, aOutline, true );
791  }
792 
794  {
795  return CIterate( 0, OutlineCount() - 1 );
796  }
797 
799  {
800  return CIterate( 0, OutlineCount() - 1, true );
801  }
802 
804  {
805  // Build iterator
806  ITERATOR iter = IterateWithHoles();
807 
808  // Get the relative indices of the globally indexed vertex
809  VERTEX_INDEX indices;
810 
811  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
812  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
813 
814  // Adjust where the iterator is pointing
815  iter.m_currentPolygon = indices.m_polygon;
816  iter.m_currentContour = indices.m_contour;
817  iter.m_currentVertex = indices.m_vertex;
818 
819  return iter;
820  }
821 
824  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
825  {
826  SEGMENT_ITERATOR iter;
827 
828  iter.m_poly = this;
829  iter.m_currentPolygon = aFirst;
830  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
831  iter.m_currentContour = 0;
832  iter.m_currentSegment = 0;
833  iter.m_iterateHoles = aIterateHoles;
834 
835  return iter;
836  }
837 
840  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
841  bool aIterateHoles = false ) const
842  {
844 
845  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
846  iter.m_currentPolygon = aFirst;
847  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
848  iter.m_currentContour = 0;
849  iter.m_currentSegment = 0;
850  iter.m_iterateHoles = aIterateHoles;
851 
852  return iter;
853  }
854 
857  {
858  return IterateSegments( aPolygonIdx, aPolygonIdx );
859  }
860 
862  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
863  {
864  return CIterateSegments( aPolygonIdx, aPolygonIdx );
865  }
866 
869  {
870  return IterateSegments( 0, OutlineCount() - 1 );
871  }
872 
875  {
876  return IterateSegments( 0, OutlineCount() - 1, true );
877  }
878 
881  {
882  return IterateSegments( aOutline, aOutline, true );
883  }
884 
887  {
888  return CIterateSegments( 0, OutlineCount() - 1, true );
889  }
890 
893  {
894  return CIterateSegments( aOutline, aOutline, true );
895  }
896 
905  {
906  PM_FAST = true,
908  };
909 
912  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
913 
916  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
917 
920  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
921 
924  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
925  POLYGON_MODE aFastMode );
926 
929  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
930  POLYGON_MODE aFastMode );
931 
934  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
935  POLYGON_MODE aFastMode );
936 
938  {
946  };
948 
961  void Inflate( int aAmount, int aCircleSegmentsCount,
962  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
963 
964  void Deflate( int aAmount, int aCircleSegmentsCount,
965  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
966  {
967  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
968  }
969 
975  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
976 
980  void Fracture( POLYGON_MODE aFastMode );
981 
984  void Unfracture( POLYGON_MODE aFastMode );
985 
987  bool HasHoles() const;
988 
990  bool HasTouchingHoles() const;
991 
992 
995  void Simplify( POLYGON_MODE aFastMode );
996 
1004  int NormalizeAreaOutlines();
1005 
1007  const std::string Format() const override;
1008 
1010  bool Parse( std::stringstream& aStream ) override;
1011 
1013  void Move( const VECTOR2I& aVector ) override;
1014 
1021  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1022 
1029  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1030 
1032  bool IsSolid() const override
1033  {
1034  return true;
1035  }
1036 
1037  const BOX2I BBox( int aClearance = 0 ) const override;
1038 
1046  bool PointOnEdge( const VECTOR2I& aP ) const;
1047 
1067  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr ) const override;
1068 
1089  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr ) const override;
1090 
1101  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1102  int aClearance = 0 ) const;
1103 
1114  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1115  int aClearance = 0 ) const;
1116 
1121  void BuildBBoxCaches();
1122 
1123  const BOX2I BBoxFromCaches() const;
1124 
1135  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1136  bool aUseBBoxCaches = false ) const;
1137 
1139  bool IsEmpty() const
1140  {
1141  return m_polys.size() == 0;
1142  }
1143 
1149  void RemoveVertex( int aGlobalIndex );
1150 
1156  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1157 
1159  void RemoveAllContours();
1160 
1169  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1170 
1176  int RemoveNullSegments();
1177 
1184  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1185 
1192  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1193 
1195  int TotalVertices() const;
1196 
1198  void DeletePolygon( int aIdx );
1199 
1207  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1208 
1217  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1218 
1225  SHAPE_POLY_SET Chamfer( int aDistance );
1226 
1234  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1235 
1244  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex ) const;
1245 
1258  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex ) const;
1259 
1268  SEG::ecoord SquaredDistance( VECTOR2I aPoint ) const;
1269 
1279  SEG::ecoord SquaredDistance( const SEG& aSegment ) const;
1280 
1287  bool IsVertexInHole( int aGlobalIdx );
1288 
1289  private:
1290  void fractureSingle( POLYGON& paths );
1291  void unfractureSingle ( POLYGON& path );
1292  void importTree( ClipperLib::PolyTree* tree );
1293 
1305  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1306  POLYGON_MODE aFastMode );
1307 
1308  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1309  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1310 
1326  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1327  bool aUseBBoxCaches = false ) const;
1328 
1335  {
1338  };
1339 
1354  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1355  int aIndex, int aErrorMax );
1356 
1358  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1359 
1360  typedef std::vector<POLYGON> POLYSET;
1361 
1363 
1364  public:
1365 
1367 
1368  void CacheTriangulation( bool aPartition = true );
1369  bool IsTriangulationUpToDate() const;
1370 
1371  MD5_HASH GetHash() const;
1372 
1373  private:
1374 
1375  MD5_HASH checksum() const;
1376 
1377  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1378  bool m_triangulationValid = false;
1380 
1381 };
1382 
1383 #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
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.
SEG::ecoord SquaredDistance(VECTOR2I aPoint) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
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:594
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
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)
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
SHAPE.
Definition: shape.h:120
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: box2.h:386
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
bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide Checks whether the point aP is either inside or on the edge of the polygon set.
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,...
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
Definition: seg.h:39
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
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...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
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:51
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.
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.
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
CONST_ITERATOR CIterate(int aOutline) const
virtual const BOX2I BBox(int aClearance=0) const override
Function BBox()
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.