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  void Move( const VECTOR2I& aVec )
123  {
124  for( auto& vertex : m_vertices )
125  vertex += aVec;
126  }
127 
128  private:
129 
130  std::deque<TRI> m_triangles;
131  std::deque<VECTOR2I> m_vertices;
132  };
133 
141  typedef struct VERTEX_INDEX
142  {
143  int m_polygon;
144  int m_contour;
145  int m_vertex;
148  {
149  }
150  } VERTEX_INDEX;
151 
157  template <class T>
159  {
160  public:
161 
167  bool IsEndContour() const
168  {
169  return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
170  }
171 
176  bool IsLastPolygon() const
177  {
179  }
180 
181  operator bool() const
182  {
184  return true;
185 
186  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
187  return false;
188 
189  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
190 
191  return m_currentContour < (int) currentPolygon.size() - 1
192  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
193  }
194 
200  void Advance()
201  {
202  // Advance vertex index
203  m_currentVertex ++;
204 
205  // Check whether the user wants to iterate through the vertices of the holes
206  // and behave accordingly
207  if( m_iterateHoles )
208  {
209  // If the last vertex of the contour was reached, advance the contour index
211  {
212  m_currentVertex = 0;
214 
215  // If the last contour of the current polygon was reached, advance the
216  // outline index
217  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
218 
219  if( m_currentContour >= totalContours )
220  {
221  m_currentContour = 0;
223  }
224  }
225  }
226  else
227  {
228  // If the last vertex of the outline was reached, advance to the following polygon
229  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
230  {
231  m_currentVertex = 0;
233  }
234  }
235  }
236 
237  void operator++( int dummy )
238  {
239  Advance();
240  }
241 
242  void operator++()
243  {
244  Advance();
245  }
246 
247  const T& Get()
248  {
249  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint(
250  m_currentVertex );
251  }
252 
253  const T& operator*()
254  {
255  return Get();
256  }
257 
258  const T* operator->()
259  {
260  return &Get();
261  }
262 
268  {
269  VERTEX_INDEX index;
270 
271  index.m_polygon = m_currentPolygon;
272  index.m_contour = m_currentContour;
273  index.m_vertex = m_currentVertex;
274 
275  return index;
276  }
277 
278 
279  private:
280  friend class SHAPE_POLY_SET;
281 
288  };
289 
295  template <class T>
297  {
298  public:
303  bool IsLastPolygon() const
304  {
306  }
307 
308  operator bool() const
309  {
311  }
312 
318  void Advance()
319  {
320  // Advance vertex index
322  int last;
323 
324  // Check whether the user wants to iterate through the vertices of the holes
325  // and behave accordingly
326  if( m_iterateHoles )
327  {
328  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
329 
330  // If the last vertex of the contour was reached, advance the contour index
331  if( m_currentSegment >= last )
332  {
333  m_currentSegment = 0;
335 
336  // If the last contour of the current polygon was reached, advance the
337  // outline index
338  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
339 
340  if( m_currentContour >= totalContours )
341  {
342  m_currentContour = 0;
344  }
345  }
346  }
347  else
348  {
349  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
350  // If the last vertex of the outline was reached, advance to the following
351  // polygon
352  if( m_currentSegment >= last )
353  {
354  m_currentSegment = 0;
356  }
357  }
358  }
359 
360  void operator++( int dummy )
361  {
362  Advance();
363  }
364 
365  void operator++()
366  {
367  Advance();
368  }
369 
370  T Get()
371  {
373  }
374 
376  {
377  return Get();
378  }
379 
385  {
386  VERTEX_INDEX index;
387 
388  index.m_polygon = m_currentPolygon;
389  index.m_contour = m_currentContour;
390  index.m_vertex = m_currentSegment;
391 
392  return index;
393  }
394 
403  {
404  // Check that both iterators point to the same contour of the same polygon of the
405  // same polygon set
406  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
408  {
409  // Compute the total number of segments
410  int numSeg;
411  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
412 
413  // Compute the difference of the segment indices. If it is exactly one, they
414  // are adjacent. The only missing case where they also are adjacent is when
415  // the segments are the first and last one, in which case the difference
416  // always equals the total number of segments minus one.
417  int indexDiff = abs( m_currentSegment - aOther.m_currentSegment );
418 
419  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
420  }
421 
422  return false;
423  }
424 
425  private:
426  friend class SHAPE_POLY_SET;
427 
434  };
435 
436  // Iterator and const iterator types to visit polygon's points.
439 
440  // Iterator and const iterator types to visit polygon's edges.
443 
444  SHAPE_POLY_SET();
445 
451  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
452 
458  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
459 
460  ~SHAPE_POLY_SET();
461 
474  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices) const;
475 
485  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx );
486 
488  SHAPE* Clone() const override;
489 
491  int NewOutline();
492 
494  int NewHole( int aOutline = -1 );
495 
497  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
498 
500  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
501 
503 
515  int Append( int x, int y, int aOutline = -1, int aHole = -1,
516  bool aAllowDuplication = false );
517 
519  void Append( const SHAPE_POLY_SET& aSet );
520 
522  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
523 
531  void InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex );
532 
534  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
535 
537  const VECTOR2I& CVertex( int aGlobalIndex ) const;
538 
540  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
541 
553  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
554 
555 
563  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
564 
570  bool IsSelfIntersecting() const;
571 
573  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
574 
576  int OutlineCount() const { return m_polys.size(); }
577 
579  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
580 
582  int HoleCount( int aOutline ) const
583  {
584  if( ( aOutline < 0 ) || (aOutline >= (int)m_polys.size()) || (m_polys[aOutline].size() < 2) )
585  return 0;
586 
587  // the first polygon in m_polys[aOutline] is the main contour,
588  // only others are holes:
589  return m_polys[aOutline].size() - 1;
590  }
591 
593  SHAPE_LINE_CHAIN& Outline( int aIndex )
594  {
595  return m_polys[aIndex][0];
596  }
597 
607  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
608 
609  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
610  {
611  return Subset( aPolygonIndex, aPolygonIndex + 1 );
612  }
613 
615  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
616  {
617  return m_polys[aOutline][aHole + 1];
618  }
619 
621  POLYGON& Polygon( int aIndex )
622  {
623  return m_polys[aIndex];
624  }
625 
626  const POLYGON& Polygon( int aIndex ) const
627  {
628  return m_polys[aIndex];
629  }
630 
631  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
632  {
633  return m_triangulatedPolys[aIndex].get();
634  }
635 
636  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
637  {
638  return m_polys[aIndex][0];
639  }
640 
641  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
642  {
643  return m_polys[aOutline][aHole + 1];
644  }
645 
646  const POLYGON& CPolygon( int aIndex ) const
647  {
648  return m_polys[aIndex];
649  }
650 
661  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
662  {
663  ITERATOR iter;
664 
665  iter.m_poly = this;
666  iter.m_currentPolygon = aFirst;
667  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
668  iter.m_currentContour = 0;
669  iter.m_currentVertex = 0;
670  iter.m_iterateHoles = aIterateHoles;
671 
672  return iter;
673  }
674 
681  ITERATOR Iterate( int aOutline )
682  {
683  return Iterate( aOutline, aOutline );
684  }
685 
692  ITERATOR IterateWithHoles( int aOutline )
693  {
694  return Iterate( aOutline, aOutline, true );
695  }
696 
703  {
704  return Iterate( 0, OutlineCount() - 1 );
705  }
706 
713  {
714  return Iterate( 0, OutlineCount() - 1, true );
715  }
716 
717 
718  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
719  {
720  CONST_ITERATOR iter;
721 
722  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
723  iter.m_currentPolygon = aFirst;
724  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
725  iter.m_currentContour = 0;
726  iter.m_currentVertex = 0;
727  iter.m_iterateHoles = aIterateHoles;
728 
729  return iter;
730  }
731 
732  CONST_ITERATOR CIterate( int aOutline ) const
733  {
734  return CIterate( aOutline, aOutline );
735  }
736 
737  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
738  {
739  return CIterate( aOutline, aOutline, true );
740  }
741 
743  {
744  return CIterate( 0, OutlineCount() - 1 );
745  }
746 
748  {
749  return CIterate( 0, OutlineCount() - 1, true );
750  }
751 
753  {
754  // Build iterator
755  ITERATOR iter = IterateWithHoles();
756 
757  // Get the relative indices of the globally indexed vertex
758  VERTEX_INDEX indices;
759 
760  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
761  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
762 
763  // Adjust where the iterator is pointing
764  iter.m_currentPolygon = indices.m_polygon;
765  iter.m_currentContour = indices.m_contour;
766  iter.m_currentVertex = indices.m_vertex;
767 
768  return iter;
769  }
770 
773  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
774  {
775  SEGMENT_ITERATOR iter;
776 
777  iter.m_poly = this;
778  iter.m_currentPolygon = aFirst;
779  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
780  iter.m_currentContour = 0;
781  iter.m_currentSegment = 0;
782  iter.m_iterateHoles = aIterateHoles;
783 
784  return iter;
785  }
786 
789  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
790  bool aIterateHoles = false ) const
791  {
793 
794  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
795  iter.m_currentPolygon = aFirst;
796  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
797  iter.m_currentContour = 0;
798  iter.m_currentSegment = 0;
799  iter.m_iterateHoles = aIterateHoles;
800 
801  return iter;
802  }
803 
806  {
807  return IterateSegments( aPolygonIdx, aPolygonIdx );
808  }
809 
811  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
812  {
813  return CIterateSegments( aPolygonIdx, aPolygonIdx );
814  }
815 
818  {
819  return IterateSegments( 0, OutlineCount() - 1 );
820  }
821 
824  {
825  return IterateSegments( 0, OutlineCount() - 1, true );
826  }
827 
830  {
831  return IterateSegments( aOutline, aOutline, true );
832  }
833 
836  {
837  return CIterateSegments( 0, OutlineCount() - 1, true );
838  }
839 
842  {
843  return CIterateSegments( aOutline, aOutline, true );
844  }
845 
854  {
855  PM_FAST = true,
857  };
858 
861  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
862 
865  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
866 
869  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
870 
873  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
874  POLYGON_MODE aFastMode );
875 
878  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
879  POLYGON_MODE aFastMode );
880 
883  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
884  POLYGON_MODE aFastMode );
885 
887  {
895  };
897 
910  void Inflate( int aAmount, int aCircleSegmentsCount,
911  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
912 
913  void Deflate( int aAmount, int aCircleSegmentsCount,
914  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
915  {
916  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
917  }
918 
924  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
925 
929  void Fracture( POLYGON_MODE aFastMode );
930 
933  void Unfracture( POLYGON_MODE aFastMode );
934 
936  bool HasHoles() const;
937 
939  bool HasTouchingHoles() const;
940 
941 
944  void Simplify( POLYGON_MODE aFastMode );
945 
953  int NormalizeAreaOutlines();
954 
956  const std::string Format() const override;
957 
959  bool Parse( std::stringstream& aStream ) override;
960 
962  void Move( const VECTOR2I& aVector ) override;
963 
970  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
971 
978  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
979 
981  bool IsSolid() const override
982  {
983  return true;
984  }
985 
986  const BOX2I BBox( int aClearance = 0 ) const override;
987 
995  bool PointOnEdge( const VECTOR2I& aP ) const;
996 
1016  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr ) const override;
1017 
1038  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr ) const override;
1039 
1050  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1051  int aClearance = 0 ) const;
1052 
1063  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1064  int aClearance = 0 ) const;
1065 
1070  void BuildBBoxCaches();
1071 
1072  const BOX2I BBoxFromCaches() const;
1073 
1084  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1085  bool aUseBBoxCaches = false ) const;
1086 
1088  bool IsEmpty() const
1089  {
1090  return m_polys.size() == 0;
1091  }
1092 
1098  void RemoveVertex( int aGlobalIndex );
1099 
1105  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1106 
1108  void RemoveAllContours();
1109 
1118  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1119 
1125  int RemoveNullSegments();
1126 
1133  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1134 
1141  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1142 
1144  int TotalVertices() const;
1145 
1147  void DeletePolygon( int aIdx );
1148 
1157  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex,
1158  std::set<VECTOR2I>* aPreserveCorners );
1159 
1169  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex,
1170  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1171 
1179  SHAPE_POLY_SET Chamfer( int aDistance,
1180  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1181 
1190  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax,
1191  std::set<VECTOR2I>* aPreserveCorners = nullptr );
1192 
1201  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex ) const;
1202 
1215  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex ) const;
1216 
1225  SEG::ecoord SquaredDistance( VECTOR2I aPoint ) const;
1226 
1236  SEG::ecoord SquaredDistance( const SEG& aSegment ) const;
1237 
1244  bool IsVertexInHole( int aGlobalIdx );
1245 
1246  private:
1247  void fractureSingle( POLYGON& paths );
1248  void unfractureSingle ( POLYGON& path );
1249  void importTree( ClipperLib::PolyTree* tree );
1250 
1262  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1263  POLYGON_MODE aFastMode );
1264 
1265  void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1266  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1267 
1283  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1284  bool aUseBBoxCaches = false ) const;
1285 
1292  {
1295  };
1296 
1312  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1313  int aIndex, int aErrorMax,
1314  std::set<VECTOR2I>* aPreserveCorners );
1315 
1317  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1318 
1319  typedef std::vector<POLYGON> POLYSET;
1320 
1322 
1323  public:
1324 
1326 
1327  void CacheTriangulation();
1328  bool IsTriangulationUpToDate() const;
1329 
1330  MD5_HASH GetHash() const;
1331 
1332  private:
1333 
1334  MD5_HASH checksum() const;
1335 
1336  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1337  bool m_triangulationValid = false;
1339 
1340 };
1341 
1342 #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.
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
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
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
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...
T
enum T contains all this lexer's tokens.
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...
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)
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:74
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.
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.
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...
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.
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.
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
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.