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
75  {
76  TRI( int _a = 0, int _b = 0, int _c = 0 ) : a( _a ), b( _b ), c( _c )
77  {
78  }
79 
80  int a, b, c;
81  };
82 
83  void Clear()
84  {
85  m_vertices.clear();
86  m_triangles.clear();
87  }
88 
89  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
90  {
91  auto tri = m_triangles[ index ];
92  a = m_vertices[ tri.a ];
93  b = m_vertices[ tri.b ];
94  c = m_vertices[ tri.c ];
95  }
96 
97  void AddTriangle( const TRI& aTri )
98  {
99  m_triangles.push_back( aTri );
100  }
101 
102  void AddTriangle( int a, int b, int c )
103  {
104  m_triangles.emplace_back( a, b, c );
105  }
106 
107  void AddVertex( const VECTOR2I& aP )
108  {
109  m_vertices.push_back( aP );
110  }
111 
112  size_t GetTriangleCount() const
113  {
114  return m_triangles.size();
115  }
116 
117  size_t GetVertexCount() const
118  {
119  return m_vertices.size();
120  }
121 
122  private:
123 
124  std::deque<TRI> m_triangles;
125  std::deque<VECTOR2I> m_vertices;
126  };
127 
135  typedef struct VERTEX_INDEX
136  {
137  int m_polygon;
138  int m_contour;
139  int m_vertex;
142  {
143  }
144  } VERTEX_INDEX;
145 
151  template <class T>
153  {
154  public:
155 
161  bool IsEndContour() const
162  {
163  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
164  }
165 
170  bool IsLastPolygon() const
171  {
173  }
174 
175  operator bool() const
176  {
178  return true;
179 
180  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
181  return false;
182 
183  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
184 
185  return m_currentContour < (int) currentPolygon.size() - 1
186  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
187  }
188 
194  void Advance()
195  {
196  // Advance vertex index
197  m_currentVertex ++;
198 
199  // Check whether the user wants to iterate through the vertices of the holes
200  // and behave accordingly
201  if( m_iterateHoles )
202  {
203  // If the last vertex of the contour was reached, advance the contour index
205  {
206  m_currentVertex = 0;
208 
209  // If the last contour of the current polygon was reached, advance the
210  // outline index
211  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
212 
213  if( m_currentContour >= totalContours )
214  {
215  m_currentContour = 0;
217  }
218  }
219  }
220  else
221  {
222  // If the last vertex of the outline was reached, advance to the following polygon
223  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
224  {
225  m_currentVertex = 0;
227  }
228  }
229  }
230 
231  void operator++( int dummy )
232  {
233  Advance();
234  }
235 
236  void operator++()
237  {
238  Advance();
239  }
240 
241  const T& Get()
242  {
243  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint(
244  m_currentVertex );
245  }
246 
247  const T& operator*()
248  {
249  return Get();
250  }
251 
252  const T* operator->()
253  {
254  return &Get();
255  }
256 
262  {
263  VERTEX_INDEX index;
264 
265  index.m_polygon = m_currentPolygon;
266  index.m_contour = m_currentContour;
267  index.m_vertex = m_currentVertex;
268 
269  return index;
270  }
271 
272 
273  private:
274  friend class SHAPE_POLY_SET;
275 
282  };
283 
289  template <class T>
291  {
292  public:
297  bool IsLastPolygon() const
298  {
300  }
301 
302  operator bool() const
303  {
305  }
306 
312  void Advance()
313  {
314  // Advance vertex index
316  int last;
317 
318  // Check whether the user wants to iterate through the vertices of the holes
319  // and behave accordingly
320  if( m_iterateHoles )
321  {
322  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
323 
324  // If the last vertex of the contour was reached, advance the contour index
325  if( m_currentSegment >= last )
326  {
327  m_currentSegment = 0;
329 
330  // If the last contour of the current polygon was reached, advance the
331  // outline index
332  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
333 
334  if( m_currentContour >= totalContours )
335  {
336  m_currentContour = 0;
338  }
339  }
340  }
341  else
342  {
343  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
344  // If the last vertex of the outline was reached, advance to the following
345  // polygon
346  if( m_currentSegment >= last )
347  {
348  m_currentSegment = 0;
350  }
351  }
352  }
353 
354  void operator++( int dummy )
355  {
356  Advance();
357  }
358 
359  void operator++()
360  {
361  Advance();
362  }
363 
364  T Get()
365  {
367  }
368 
370  {
371  return Get();
372  }
373 
379  {
380  VERTEX_INDEX index;
381 
382  index.m_polygon = m_currentPolygon;
383  index.m_contour = m_currentContour;
384  index.m_vertex = m_currentSegment;
385 
386  return index;
387  }
388 
397  {
398  // Check that both iterators point to the same contour of the same polygon of the
399  // same polygon set
400  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
402  {
403  // Compute the total number of segments
404  int numSeg;
405  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
406 
407  // Compute the difference of the segment indices. If it is exactly one, they
408  // are adjacent. The only missing case where they also are adjacent is when
409  // the segments are the first and last one, in which case the difference
410  // always equals the total number of segments minus one.
411  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
412 
413  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
414  }
415 
416  return false;
417  }
418 
419  private:
420  friend class SHAPE_POLY_SET;
421 
428  };
429 
430  // Iterator and const iterator types to visit polygon's points.
433 
434  // Iterator and const iterator types to visit polygon's edges.
437 
438  SHAPE_POLY_SET();
439 
446  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, bool aDeepCopy = false );
447 
448  ~SHAPE_POLY_SET();
449 
462  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
463 
473  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
474 
476  SHAPE* Clone() const override;
477 
479  int NewOutline();
480 
482  int NewHole( int aOutline = -1 );
483 
485  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
486 
488  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
489 
491 
503  int Append( int x, int y, int aOutline = -1, int aHole = -1,
504  bool aAllowDuplication = false );
505 
507  void Append( const SHAPE_POLY_SET& aSet );
508 
510  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
511 
519  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
520 
522  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
523 
525  const VECTOR2I& CVertex( int aGlobalIndex ) const;
526 
528  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
529 
541  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
542 
543 
551  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
552 
558  bool IsSelfIntersecting() const;
559 
561  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
562 
564  int OutlineCount() const { return m_polys.size(); }
565 
567  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
568 
570  int HoleCount( int aOutline ) const
571  {
572  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
573  return 0;
574 
575  // the first polygon in m_polys[aOutline] is the main contour,
576  // only others are holes:
577  return m_polys[aOutline].size() - 1;
578  }
579 
581  SHAPE_LINE_CHAIN& Outline( int aIndex )
582  {
583  return m_polys[aIndex][0];
584  }
585 
595  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
596 
597  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
598  {
599  return Subset( aPolygonIndex, aPolygonIndex + 1 );
600  }
601 
603  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
604  {
605  return m_polys[aOutline][aHole + 1];
606  }
607 
609  POLYGON& Polygon( int aIndex )
610  {
611  return m_polys[aIndex];
612  }
613 
614  const POLYGON& Polygon( int aIndex ) const
615  {
616  return m_polys[aIndex];
617  }
618 
619  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
620  {
621  return m_triangulatedPolys[aIndex].get();
622  }
623 
624  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
625  {
626  return m_polys[aIndex][0];
627  }
628 
629  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
630  {
631  return m_polys[aOutline][aHole + 1];
632  }
633 
634  const POLYGON& CPolygon( int aIndex ) const
635  {
636  return m_polys[aIndex];
637  }
638 
649  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
650  {
651  ITERATOR iter;
652 
653  iter.m_poly = this;
654  iter.m_currentPolygon = aFirst;
655  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
656  iter.m_currentContour = 0;
657  iter.m_currentVertex = 0;
658  iter.m_iterateHoles = aIterateHoles;
659 
660  return iter;
661  }
662 
669  ITERATOR Iterate( int aOutline )
670  {
671  return Iterate( aOutline, aOutline );
672  }
673 
680  ITERATOR IterateWithHoles( int aOutline )
681  {
682  return Iterate( aOutline, aOutline, true );
683  }
684 
691  {
692  return Iterate( 0, OutlineCount() - 1 );
693  }
694 
701  {
702  return Iterate( 0, OutlineCount() - 1, true );
703  }
704 
705 
706  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
707  {
708  CONST_ITERATOR iter;
709 
710  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
711  iter.m_currentPolygon = aFirst;
712  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
713  iter.m_currentContour = 0;
714  iter.m_currentVertex = 0;
715  iter.m_iterateHoles = aIterateHoles;
716 
717  return iter;
718  }
719 
720  CONST_ITERATOR CIterate( int aOutline ) const
721  {
722  return CIterate( aOutline, aOutline );
723  }
724 
725  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
726  {
727  return CIterate( aOutline, aOutline, true );
728  }
729 
731  {
732  return CIterate( 0, OutlineCount() - 1 );
733  }
734 
736  {
737  return CIterate( 0, OutlineCount() - 1, true );
738  }
739 
741  {
742  // Build iterator
743  ITERATOR iter = IterateWithHoles();
744 
745  // Get the relative indices of the globally indexed vertex
746  VERTEX_INDEX indices;
747 
748  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
749  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
750 
751  // Adjust where the iterator is pointing
752  iter.m_currentPolygon = indices.m_polygon;
753  iter.m_currentContour = indices.m_contour;
754  iter.m_currentVertex = indices.m_vertex;
755 
756  return iter;
757  }
758 
761  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
762  {
763  SEGMENT_ITERATOR iter;
764 
765  iter.m_poly = this;
766  iter.m_currentPolygon = aFirst;
767  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
768  iter.m_currentContour = 0;
769  iter.m_currentSegment = 0;
770  iter.m_iterateHoles = aIterateHoles;
771 
772  return iter;
773  }
774 
777  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
778  bool aIterateHoles = false ) const
779  {
781 
782  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
783  iter.m_currentPolygon = aFirst;
784  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
785  iter.m_currentContour = 0;
786  iter.m_currentSegment = 0;
787  iter.m_iterateHoles = aIterateHoles;
788 
789  return iter;
790  }
791 
794  {
795  return IterateSegments( aPolygonIdx, aPolygonIdx );
796  }
797 
799  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
800  {
801  return CIterateSegments( aPolygonIdx, aPolygonIdx );
802  }
803 
806  {
807  return IterateSegments( 0, OutlineCount() - 1 );
808  }
809 
812  {
813  return IterateSegments( 0, OutlineCount() - 1, true );
814  }
815 
818  {
819  return IterateSegments( aOutline, aOutline, true );
820  }
821 
824  {
825  return CIterateSegments( aOutline, aOutline, true );
826  }
827 
836  {
837  PM_FAST = true,
839  };
840 
843  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
844 
847  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
848 
851  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
852 
855  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
856  POLYGON_MODE aFastMode );
857 
860  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
861  POLYGON_MODE aFastMode );
862 
865  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
866  POLYGON_MODE aFastMode );
867 
869  {
877  };
879 
892  void Inflate( int aAmount, int aCircleSegmentsCount,
893  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
894 
895  void Deflate( int aAmount, int aCircleSegmentsCount,
896  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
897  {
898  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
899  }
900 
906  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
907 
911  void Fracture( POLYGON_MODE aFastMode );
912 
915  void Unfracture( POLYGON_MODE aFastMode );
916 
918  bool HasHoles() const;
919 
921  bool HasTouchingHoles() const;
922 
923 
926  void Simplify( POLYGON_MODE aFastMode );
927 
935  int NormalizeAreaOutlines();
936 
938  const std::string Format() const override;
939 
941  bool Parse( std::stringstream& aStream ) override;
942 
944  void Move( const VECTOR2I& aVector ) override;
945 
952  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
953 
960  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } );
961 
963  bool IsSolid() const override
964  {
965  return true;
966  }
967 
968  const BOX2I BBox( int aClearance = 0 ) const override;
969 
977  bool PointOnEdge( const VECTOR2I& aP ) const;
978 
990  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
991 
1004  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
1005 
1016  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1017  int aClearance = 0 );
1018 
1029  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1030  int aClearance = 0 );
1031 
1036  void BuildBBoxCaches();
1037 
1048  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1049  bool aUseBBoxCaches = false ) const;
1050 
1052  bool IsEmpty() const
1053  {
1054  return m_polys.size() == 0;
1055  }
1056 
1062  void RemoveVertex( int aGlobalIndex );
1063 
1069  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1070 
1072  void RemoveAllContours();
1073 
1082  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1083 
1089  int RemoveNullSegments();
1090 
1097  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1098 
1105  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1106 
1108  int TotalVertices() const;
1109 
1111  void DeletePolygon( int aIdx );
1112 
1121  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex,
1122  std::set<VECTOR2I>* aPreserveCorners );
1123 
1133  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex,
1134  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1135 
1143  SHAPE_POLY_SET Chamfer( int aDistance,
1144  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1145 
1154  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax,
1155  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1156 
1165  int DistanceToPolygon( VECTOR2I aPoint, int aIndex );
1166 
1179  int DistanceToPolygon( const SEG& aSegment, int aIndex, int aSegmentWidth = 0 );
1180 
1188  int Distance( VECTOR2I aPoint );
1189 
1198  int Distance( const SEG& aSegment, int aSegmentWidth = 0 );
1199 
1206  bool IsVertexInHole( int aGlobalIdx );
1207 
1208  private:
1209  void fractureSingle( POLYGON& paths );
1210  void unfractureSingle ( POLYGON& path );
1211  void importTree( ClipperLib::PolyTree* tree );
1212 
1224  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1225  POLYGON_MODE aFastMode );
1226 
1227  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1228  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1229 
1230  bool pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath,
1231  bool aIgnoreEdges, bool aUseBBoxCaches = false ) const;
1232 
1248  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1249  bool aUseBBoxCaches = false ) const;
1250 
1257  {
1260  };
1261 
1277  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1278  int aIndex, int aErrorMax,
1279  std::set<VECTOR2I>* aPreserveCorners );
1280 
1282  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1283 
1284  typedef std::vector<POLYGON> POLYSET;
1285 
1287 
1288  public:
1289 
1291 
1292  void CacheTriangulation();
1293  bool IsTriangulationUpToDate() const;
1294 
1295  MD5_HASH GetHash() const;
1296 
1297  private:
1298 
1299  MD5_HASH checksum() const;
1300 
1301  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1302  bool m_triangulationValid = false;
1304 
1305 };
1306 
1307 #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
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 })
Function Rotate rotates all vertices by a given angle.
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.
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.
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
void GetTriangle(int index, VECTOR2I &a, VECTOR2I &b, VECTOR2I &c) const
std::vector< POLYGON > POLYSET
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsEmpty() const
Returns true if the set is empty (no polygons at all)
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
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
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
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.
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.
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
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...
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath, bool aIgnoreEdges, bool aUseBBoxCaches=false) const
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 &)
Acute angles are rounded.
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
ITERATOR IterateWithHoles(int aOutline)
Function IterateWithHoles.
SHAPE_POLY_SET.
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)
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
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:60
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
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
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
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,...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the polygon set.
Definition: seg.h:39
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
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...
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex, std::set< VECTOR2I > *aPreserveCorners)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
void AddVertex(const VECTOR2I &aP)
void AddTriangle(int a, int b, int c)
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
TRI(int _a=0, int _b=0, int _c=0)
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.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the aIndex-th polygon.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
CONST_ITERATOR CIterate() const
SHAPE_POLY_SET Chamfer(int aDistance, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Chamfer returns a chamfered version of the polygon set.
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
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
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.
CONST_ITERATOR CIterateWithHoles() const
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.