KiCad PCB EDA Suite
shape_poly_set.h
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2015-2019 CERN
5 * Copyright (C) 2021-2022 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 * @author Alejandro García Montoro <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28#ifndef __SHAPE_POLY_SET_H
29#define __SHAPE_POLY_SET_H
30
31#include <cstdio>
32#include <deque> // for deque
33#include <vector> // for vector
34#include <iosfwd> // for string, stringstream
35#include <memory>
36#include <set> // for set
37#include <stdexcept> // for out_of_range
38#include <stdlib.h> // for abs
39#include <vector>
40
41#include <clipper.hpp> // for ClipType, PolyTree (ptr only)
42#include <clipper2/clipper.h>
43#include <geometry/seg.h> // for SEG
44#include <geometry/shape.h>
46#include <math/box2.h> // for BOX2I
47#include <math/vector2d.h> // for VECTOR2I
48#include <md5_hash.h>
49
50
65class SHAPE_POLY_SET : public SHAPE
66{
67public:
71 typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
72
74 {
75 public:
76 struct TRI : public SHAPE_LINE_CHAIN_BASE
77 {
78 TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
80 a( _a ),
81 b( _b ),
82 c( _c ),
83 parent( aParent )
84 {
85 }
86
87 virtual void Rotate( const EDA_ANGLE& aAngle,
88 const VECTOR2I& aCenter = { 0, 0 } ) override {};
89
90 virtual void Move( const VECTOR2I& aVector ) override {};
91
92 virtual bool IsSolid() const override { return true; }
93
94 virtual bool IsClosed() const override { return true; }
95
96 virtual const BOX2I BBox( int aClearance = 0 ) const override;
97
98 virtual const VECTOR2I GetPoint( int aIndex ) const override
99 {
100 switch(aIndex)
101 {
102 case 0: return parent->m_vertices[a];
103 case 1: return parent->m_vertices[b];
104 case 2: return parent->m_vertices[c];
105 default: wxCHECK( false, VECTOR2I() );
106 }
107 }
108
109 virtual const SEG GetSegment( int aIndex ) const override
110 {
111 switch(aIndex)
112 {
113 case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
114 case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
115 case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
116 default: wxCHECK( false, SEG() );
117 }
118 }
119
120 virtual size_t GetPointCount() const override { return 3; }
121 virtual size_t GetSegmentCount() const override { return 3; }
122
123 int a;
124 int b;
125 int c;
127 };
128
129 TRIANGULATED_POLYGON( int aSourceOutline );
132
133 void Clear()
134 {
135 m_vertices.clear();
136 m_triangles.clear();
137 }
138
139 void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
140 {
141 auto tri = m_triangles[ index ];
142 a = m_vertices[ tri.a ];
143 b = m_vertices[ tri.b ];
144 c = m_vertices[ tri.c ];
145 }
146
148
149 void AddTriangle( int a, int b, int c );
150
151 void AddVertex( const VECTOR2I& aP )
152 {
153 m_vertices.push_back( aP );
154 }
155
156 size_t GetTriangleCount() const { return m_triangles.size(); }
157
159 void SetSourceOutlineIndex( int aIndex ) { m_sourceOutline = aIndex; }
160
161 std::deque<TRI>& Triangles() { return m_triangles; }
162 const std::deque<TRI>& Triangles() const { return m_triangles; }
163
164 size_t GetVertexCount() const
165 {
166 return m_vertices.size();
167 }
168
169 void Move( const VECTOR2I& aVec )
170 {
171 for( VECTOR2I& vertex : m_vertices )
172 vertex += aVec;
173 }
174
175 private:
177 std::deque<TRI> m_triangles;
178 std::deque<VECTOR2I> m_vertices;
179 };
180
187 {
193 m_polygon(-1),
194 m_contour(-1),
195 m_vertex(-1)
196 {
197 }
198 };
199
203 template <class T>
205 {
206 public:
207
212 bool IsEndContour() const
213 {
214 return m_currentVertex + 1 ==
216 }
217
221 bool IsLastPolygon() const
222 {
224 }
225
226 operator bool() const
227 {
229 return true;
230
231 if( m_currentPolygon != m_poly->OutlineCount() - 1 )
232 return false;
233
234 const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
235
236 return m_currentContour < (int) currentPolygon.size() - 1
237 || m_currentVertex < currentPolygon[m_currentContour].PointCount();
238 }
239
244 void Advance()
245 {
246 // Advance vertex index
248
249 // Check whether the user wants to iterate through the vertices of the holes
250 // and behave accordingly
251 if( m_iterateHoles )
252 {
253 // If the last vertex of the contour was reached, advance the contour index
254 if( m_currentVertex >=
256 {
257 m_currentVertex = 0;
259
260 // If the last contour of the current polygon was reached, advance the
261 // outline index
262 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
263
264 if( m_currentContour >= totalContours )
265 {
268 }
269 }
270 }
271 else
272 {
273 // If the last vertex of the outline was reached, advance to the following polygon
274 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
275 {
276 m_currentVertex = 0;
278 }
279 }
280 }
281
282 void operator++( int dummy )
283 {
284 Advance();
285 }
286
288 {
289 Advance();
290 }
291
292 const T& Get()
293 {
295 }
296
297 const T& operator*()
298 {
299 return Get();
300 }
301
302 const T* operator->()
303 {
304 return &Get();
305 }
306
311 {
312 VERTEX_INDEX index;
313
317
318 return index;
319 }
320
321 private:
322 friend class SHAPE_POLY_SET;
323
330 };
331
335 template <class T>
337 {
338 public:
342 bool IsLastPolygon() const
343 {
345 }
346
347 operator bool() const
348 {
350 }
351
356 void Advance()
357 {
358 // Advance vertex index
360 int last;
361
362 // Check whether the user wants to iterate through the vertices of the holes
363 // and behave accordingly.
364 if( m_iterateHoles )
365 {
366 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
367
368 // If the last vertex of the contour was reached, advance the contour index.
369 if( m_currentSegment >= last )
370 {
373
374 // If the last contour of the current polygon was reached, advance the
375 // outline index.
376 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
377
378 if( m_currentContour >= totalContours )
379 {
382 }
383 }
384 }
385 else
386 {
387 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
388 // If the last vertex of the outline was reached, advance to the following
389 // polygon
390 if( m_currentSegment >= last )
391 {
394 }
395 }
396 }
397
398 void operator++( int dummy )
399 {
400 Advance();
401 }
402
404 {
405 Advance();
406 }
407
408 T Get()
409 {
411 }
412
414 {
415 return Get();
416 }
417
422 {
423 VERTEX_INDEX index;
424
428
429 return index;
430 }
431
438 {
439 // Check that both iterators point to the same contour of the same polygon of the
440 // same polygon set.
441 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
443 {
444 // Compute the total number of segments.
445 int numSeg;
446 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
447
448 // Compute the difference of the segment indices. If it is exactly one, they
449 // are adjacent. The only missing case where they also are adjacent is when
450 // the segments are the first and last one, in which case the difference
451 // always equals the total number of segments minus one.
452 int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
453
454 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
455 }
456
457 return false;
458 }
459
460 private:
461 friend class SHAPE_POLY_SET;
462
469 };
470
471 // Iterator and const iterator types to visit polygon's points.
474
475 // Iterator and const iterator types to visit polygon's edges.
478
480
481 SHAPE_POLY_SET( const BOX2D& aRect );
482
488 SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
489
496 SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
497
499
500 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
501
513 void CacheTriangulation( bool aPartition = true, bool aSimplify = false );
514 bool IsTriangulationUpToDate() const;
515
516 MD5_HASH GetHash() const;
517
518 virtual bool HasIndexableSubshapes() const override;
519
520 virtual size_t GetIndexableSubshapeCount() const override;
521
522 virtual void GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const override;
523
535 bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
536
546 bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
547
549 SHAPE* Clone() const override;
550
552
554 int NewOutline();
555
557 int NewHole( int aOutline = -1 );
558
560 int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
561
563 int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
564
566 double Area();
567
569 int ArcCount() const;
570
572 void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
573
575 void ClearArcs();
576
578
590 int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
591
593 void Append( const SHAPE_POLY_SET& aSet );
594
596 void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
597
607 int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1,
608 double aAccuracy = SHAPE_ARC::DefaultAccuracyForPCB() );
609
617 void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
618
620 const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
621
623 const VECTOR2I& CVertex( int aGlobalIndex ) const;
624
626 const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
627
641 bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
642
649 bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
650
656 bool IsSelfIntersecting() const;
657
659 unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
660
662 int OutlineCount() const { return m_polys.size(); }
663
665 int VertexCount( int aOutline = -1, int aHole = -1 ) const;
666
669 int FullPointCount() const;
670
672 int HoleCount( int aOutline ) const
673 {
674 if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
675 || ( m_polys[aOutline].size() < 2 ) )
676 return 0;
677
678 // the first polygon in m_polys[aOutline] is the main contour,
679 // only others are holes:
680 return m_polys[aOutline].size() - 1;
681 }
682
685 {
686 return m_polys[aIndex][0];
687 }
688
689 const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
690 {
691 return m_polys[aIndex][0];
692 }
693
703 SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
704
705 SHAPE_POLY_SET UnitSet( int aPolygonIndex )
706 {
707 return Subset( aPolygonIndex, aPolygonIndex + 1 );
708 }
709
711 SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
712 {
713 return m_polys[aOutline][aHole + 1];
714 }
715
717 POLYGON& Polygon( int aIndex )
718 {
719 return m_polys[aIndex];
720 }
721
722 const POLYGON& Polygon( int aIndex ) const
723 {
724 return m_polys[aIndex];
725 }
726
727 const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
728 {
729 return m_triangulatedPolys[aIndex].get();
730 }
731
732 const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
733 {
734 return m_polys[aIndex][0];
735 }
736
737 const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
738 {
739 return m_polys[aOutline][aHole + 1];
740 }
741
742 const POLYGON& CPolygon( int aIndex ) const
743 {
744 return m_polys[aIndex];
745 }
746
757 ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
758 {
759 ITERATOR iter;
760
761 iter.m_poly = this;
762 iter.m_currentPolygon = aFirst;
763 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
764 iter.m_currentContour = 0;
765 iter.m_currentVertex = 0;
766 iter.m_iterateHoles = aIterateHoles;
767
768 return iter;
769 }
770
776 ITERATOR Iterate( int aOutline )
777 {
778 return Iterate( aOutline, aOutline );
779 }
780
787 {
788 return Iterate( aOutline, aOutline, true );
789 }
790
796 {
797 return Iterate( 0, OutlineCount() - 1 );
798 }
799
805 {
806 return Iterate( 0, OutlineCount() - 1, true );
807 }
808
809
810 CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
811 {
812 CONST_ITERATOR iter;
813
814 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
815 iter.m_currentPolygon = aFirst;
816 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
817 iter.m_currentContour = 0;
818 iter.m_currentVertex = 0;
819 iter.m_iterateHoles = aIterateHoles;
820
821 return iter;
822 }
823
824 CONST_ITERATOR CIterate( int aOutline ) const
825 {
826 return CIterate( aOutline, aOutline );
827 }
828
829 CONST_ITERATOR CIterateWithHoles( int aOutline ) const
830 {
831 return CIterate( aOutline, aOutline, true );
832 }
833
835 {
836 return CIterate( 0, OutlineCount() - 1 );
837 }
838
840 {
841 return CIterate( 0, OutlineCount() - 1, true );
842 }
843
845 {
846 // Build iterator
847 ITERATOR iter = IterateWithHoles();
848
849 // Get the relative indices of the globally indexed vertex
850 VERTEX_INDEX indices;
851
852 if( !GetRelativeIndices( aGlobalIdx, &indices ) )
853 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
854
855 // Adjust where the iterator is pointing
856 iter.m_currentPolygon = indices.m_polygon;
857 iter.m_currentContour = indices.m_contour;
858 iter.m_currentVertex = indices.m_vertex;
859
860 return iter;
861 }
862
865 SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
866 {
867 SEGMENT_ITERATOR iter;
868
869 iter.m_poly = this;
870 iter.m_currentPolygon = aFirst;
871 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
872 iter.m_currentContour = 0;
873 iter.m_currentSegment = 0;
874 iter.m_iterateHoles = aIterateHoles;
875
876 return iter;
877 }
878
882 bool aIterateHoles = false ) const
883 {
885
886 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
887 iter.m_currentPolygon = aFirst;
888 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
889 iter.m_currentContour = 0;
890 iter.m_currentSegment = 0;
891 iter.m_iterateHoles = aIterateHoles;
892
893 return iter;
894 }
895
898 {
899 return IterateSegments( aPolygonIdx, aPolygonIdx );
900 }
901
904 {
905 return CIterateSegments( aPolygonIdx, aPolygonIdx );
906 }
907
910 {
911 return IterateSegments( 0, OutlineCount() - 1 );
912 }
913
916 {
917 return CIterateSegments( 0, OutlineCount() - 1 );
918 }
919
922 {
923 return IterateSegments( 0, OutlineCount() - 1, true );
924 }
925
928 {
929 return IterateSegments( aOutline, aOutline, true );
930 }
931
934 {
935 return CIterateSegments( 0, OutlineCount() - 1, true );
936 }
937
940 {
941 return CIterateSegments( aOutline, aOutline, true );
942 }
943
953 {
954 PM_FAST = true,
955 PM_STRICTLY_SIMPLE = false
956 };
957
960 void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
961
964 void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
965
968 void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
969
972 void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
973 POLYGON_MODE aFastMode );
974
977 void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
978 POLYGON_MODE aFastMode );
979
982 void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
983 POLYGON_MODE aFastMode );
984
986 {
995 };
996
1011 void Inflate( int aAmount, int aCircleSegCount,
1012 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
1013
1014 void Deflate( int aAmount, int aCircleSegmentsCount,
1015 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
1016 {
1017 Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1018 }
1019
1027 void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1028
1032 void Fracture( POLYGON_MODE aFastMode );
1033
1036 void Unfracture( POLYGON_MODE aFastMode );
1037
1039 bool HasHoles() const;
1040
1042 bool HasTouchingHoles() const;
1043
1044
1047 void Simplify( POLYGON_MODE aFastMode );
1048
1058
1060 const std::string Format( bool aCplusPlus = true ) const override;
1061
1063 bool Parse( std::stringstream& aStream ) override;
1064
1066 void Move( const VECTOR2I& aVector ) override;
1067
1075 void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1076
1083 void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1084
1086 bool IsSolid() const override
1087 {
1088 return true;
1089 }
1090
1091 const BOX2I BBox( int aClearance = 0 ) const override;
1092
1099 bool PointOnEdge( const VECTOR2I& aP ) const;
1100
1113 bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1114 VECTOR2I* aLocation = nullptr ) const override;
1115
1134 bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1135 VECTOR2I* aLocation = nullptr ) const override;
1136
1155 bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1156 VECTOR2I* aLocation = nullptr ) const override;
1157
1168 bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1169 int aClearance = 0 ) const;
1170
1181 bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1182 int aClearance = 0 ) const;
1183
1190 void BuildBBoxCaches() const;
1191
1192 const BOX2I BBoxFromCaches() const;
1193
1204 bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1205 bool aUseBBoxCaches = false ) const;
1206
1208 bool IsEmpty() const
1209 {
1210 return m_polys.empty();
1211 }
1212
1218 void RemoveVertex( int aGlobalIndex );
1219
1225 void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1226
1228 void RemoveAllContours();
1229
1238 void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1239
1245 int RemoveNullSegments();
1246
1253 void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1254
1263 void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1264
1266 int TotalVertices() const;
1267
1269 void DeletePolygon( int aIdx );
1270
1273 void DeletePolygonAndTriangulationData( int aIdx, bool aUpdateHash = true );
1274
1276
1284 POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1285
1294 POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1295
1302 SHAPE_POLY_SET Chamfer( int aDistance );
1303
1311 SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1312
1323 SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1324 VECTOR2I* aNearest ) const;
1325
1338 SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1339 VECTOR2I* aNearest) const;
1340
1351 SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1352
1364 SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1365
1372 bool IsVertexInHole( int aGlobalIdx );
1373
1382 static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths, bool aReverseOrientation = false, bool aEvenOdd = false );
1383
1384private:
1386
1388
1389 void fractureSingle( POLYGON& paths );
1390 void unfractureSingle ( POLYGON& path );
1391 void importTree( ClipperLib::PolyTree* tree,
1392 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1393 const std::vector<SHAPE_ARC>& aArcBuffe );
1394 void importTree( Clipper2Lib::PolyTree64& tree,
1395 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1396 const std::vector<SHAPE_ARC>& aArcBuffe );
1397 void importPaths( Clipper2Lib::Paths64& paths,
1398 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1399 const std::vector<SHAPE_ARC>& aArcBuffe );
1400 void importPolyPath( Clipper2Lib::PolyPath64* aPolyPath,
1401 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1402 const std::vector<SHAPE_ARC>& aArcBuffer );
1403
1404 void inflate1( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy );
1405 void inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy );
1406
1419 void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1420 POLYGON_MODE aFastMode );
1421
1422 void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1423 const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1424
1425 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape );
1426
1427 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
1428 const SHAPE_POLY_SET& aOtherShape );
1429
1444 bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1445 bool aUseBBoxCaches = false ) const;
1446
1453 {
1455 FILLETED
1457
1471 POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1472 int aIndex, int aErrorMax );
1473
1475 bool hasTouchingHoles( const POLYGON& aPoly ) const;
1476
1477 MD5_HASH checksum() const;
1478
1479private:
1480 std::vector<POLYGON> m_polys;
1481 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1482
1485};
1486
1487#endif // __SHAPE_POLY_SET_H
Definition: seg.h:42
VECTOR2I::extended_type ecoord
Definition: seg.h:44
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:221
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Base class for iterating over all segments in a given SHAPE_POLY_SET.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
void AddVertex(const VECTOR2I &aP)
void GetTriangle(int index, VECTOR2I &a, VECTOR2I &b, VECTOR2I &c) const
const std::deque< TRI > & Triangles() const
void AddTriangle(int a, int b, int c)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
void Move(const VECTOR2I &aVec)
Represent a set of closed polygons.
virtual bool HasIndexableSubshapes() const override
static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aReverseOrientation=false, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const override
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CONST_ITERATOR CIterateWithHoles() const
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
ITERATOR IterateWithHoles(int aOutline)
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
ITERATOR IterateWithHoles()
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
bool IsTriangulationUpToDate() const
void inflate2(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy)
void importPaths(Clipper2Lib::Paths64 &paths, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
POLYGON_MODE
Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
CONST_ITERATOR CIterate() const
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon and its triangulation data from the set.
double Area()
Count the number of arc shapes present.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
void Deflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void CacheTriangulation(bool aPartition=true, bool aSimplify=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
ITERATOR Iterate(int aOutline)
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Delete aIdx-th polygon from the set.
CONST_ITERATOR CIterate(int aOutline) const
POLYGON & Polygon(int aIndex)
int FullPointCount() const
Returns the number of holes in a given outline.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
void unfractureSingle(POLYGON &path)
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Return an iterator object, for the aOutline-th outline in the set (with holes).
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
Return the reference to aHole-th hole in the aIndex-th outline.
void inflate1(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy)
MD5_HASH GetHash() const
const POLYGON & Polygon(int aIndex) const
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
const std::string Format(bool aCplusPlus=true) const override
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ... and polygon simplification...
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void Simplify(POLYGON_MODE aFastMode)
ITERATOR Iterate()
const SHAPE_LINE_CHAIN & Outline(int aIndex) const
CONST_SEGMENT_ITERATOR CIterateSegments() const
Returns an iterator object, for all outlines in the set (with holes)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
SHAPE_LINE_CHAIN & Outline(int aIndex)
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
bool IsSolid() const override
int NewOutline()
Creates a new hole in a given outline.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool hasTouchingHoles(const POLYGON &aPoly) const
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Return an iterator object, for all outlines in the set (no holes).
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
void DeletePolygonAndTriangulationData(int aIdx, bool aUpdateHash=true)
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
void UpdateTriangulationDataHash()
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
virtual size_t GetIndexableSubshapeCount() const override
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Return an object to iterate through the points of the polygons between aFirst and aLast.
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
MD5_HASH checksum() const
void importPolyPath(Clipper2Lib::PolyPath64 *aPolyPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
std::vector< POLYGON > m_polys
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the aGlobalIndex-th vertex in the poly set.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SEGMENT_ITERATOR_TEMPLATE< SEG > SEGMENT_ITERATOR
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
void Move(const VECTOR2I &aVector) override
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &aOther)
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
SHAPE_POLY_SET CloneDropTriangulation() const
Creates a new empty polygon in the set and returns its index.
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
const POLYGON & CPolygon(int aIndex) const
CONST_ITERATOR CIterateWithHoles(int aOutline) const
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
const BOX2I BBoxFromCaches() const
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
An abstract shape on 2D plane.
Definition: shape.h:123
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
@ SH_POLY_SET_TRIANGLE
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:53
std::vector< FAB_LAYER_COLOR > dummy
virtual bool IsClosed() const override
TRI(int _a=0, int _b=0, int _c=0, TRIANGULATED_POLYGON *aParent=nullptr)
virtual bool IsSolid() const override
virtual void Move(const VECTOR2I &aVector) override
virtual void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
virtual size_t GetPointCount() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
virtual size_t GetSegmentCount() const override
virtual const SEG GetSegment(int aIndex) const override
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618