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 <geometry/seg.h> // for SEG
43#include <geometry/shape.h>
45#include <math/box2.h> // for BOX2I
46#include <math/vector2d.h> // for VECTOR2I
47#include <md5_hash.h>
48
49
64class SHAPE_POLY_SET : public SHAPE
65{
66public:
70 typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
71
73 {
74 public:
75 struct TRI : public SHAPE_LINE_CHAIN_BASE
76 {
77 TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
79 a( _a ),
80 b( _b ),
81 c( _c ),
82 parent( aParent )
83 {
84 }
85
86 virtual void Rotate( const EDA_ANGLE& aAngle,
87 const VECTOR2I& aCenter = { 0, 0 } ) override {};
88
89 virtual void Move( const VECTOR2I& aVector ) override {};
90
91 virtual bool IsSolid() const override { return true; }
92
93 virtual bool IsClosed() const override { return true; }
94
95 virtual const BOX2I BBox( int aClearance = 0 ) const override;
96
97 virtual const VECTOR2I GetPoint( int aIndex ) const override
98 {
99 switch(aIndex)
100 {
101 case 0: return parent->m_vertices[a];
102 case 1: return parent->m_vertices[b];
103 case 2: return parent->m_vertices[c];
104 default: wxCHECK( false, VECTOR2I() );
105 }
106 }
107
108 virtual const SEG GetSegment( int aIndex ) const override
109 {
110 switch(aIndex)
111 {
112 case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
113 case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
114 case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
115 default: wxCHECK( false, SEG() );
116 }
117 }
118
119 virtual size_t GetPointCount() const override { return 3; }
120 virtual size_t GetSegmentCount() const override { return 3; }
121
122 int a;
123 int b;
124 int c;
126 };
127
128 TRIANGULATED_POLYGON( int aSourceOutline );
131
132 void Clear()
133 {
134 m_vertices.clear();
135 m_triangles.clear();
136 }
137
138 void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
139 {
140 auto tri = m_triangles[ index ];
141 a = m_vertices[ tri.a ];
142 b = m_vertices[ tri.b ];
143 c = m_vertices[ tri.c ];
144 }
145
147
148 void AddTriangle( int a, int b, int c );
149
150 void AddVertex( const VECTOR2I& aP )
151 {
152 m_vertices.push_back( aP );
153 }
154
155 size_t GetTriangleCount() const { return m_triangles.size(); }
156
158 void SetSourceOutlineIndex( int aIndex ) { m_sourceOutline = aIndex; }
159
160 std::deque<TRI>& Triangles() { return m_triangles; }
161 const std::deque<TRI>& Triangles() const { return m_triangles; }
162
163 size_t GetVertexCount() const
164 {
165 return m_vertices.size();
166 }
167
168 void Move( const VECTOR2I& aVec )
169 {
170 for( VECTOR2I& vertex : m_vertices )
171 vertex += aVec;
172 }
173
174 private:
176 std::deque<TRI> m_triangles;
177 std::deque<VECTOR2I> m_vertices;
178 };
179
186 {
192 m_polygon(-1),
193 m_contour(-1),
194 m_vertex(-1)
195 {
196 }
197 };
198
202 template <class T>
204 {
205 public:
206
211 bool IsEndContour() const
212 {
213 return m_currentVertex + 1 ==
215 }
216
220 bool IsLastPolygon() const
221 {
223 }
224
225 operator bool() const
226 {
228 return true;
229
230 if( m_currentPolygon != m_poly->OutlineCount() - 1 )
231 return false;
232
233 const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
234
235 return m_currentContour < (int) currentPolygon.size() - 1
236 || m_currentVertex < currentPolygon[m_currentContour].PointCount();
237 }
238
243 void Advance()
244 {
245 // Advance vertex index
247
248 // Check whether the user wants to iterate through the vertices of the holes
249 // and behave accordingly
250 if( m_iterateHoles )
251 {
252 // If the last vertex of the contour was reached, advance the contour index
253 if( m_currentVertex >=
255 {
256 m_currentVertex = 0;
258
259 // If the last contour of the current polygon was reached, advance the
260 // outline index
261 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
262
263 if( m_currentContour >= totalContours )
264 {
267 }
268 }
269 }
270 else
271 {
272 // If the last vertex of the outline was reached, advance to the following polygon
273 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
274 {
275 m_currentVertex = 0;
277 }
278 }
279 }
280
281 void operator++( int dummy )
282 {
283 Advance();
284 }
285
287 {
288 Advance();
289 }
290
291 const T& Get()
292 {
294 }
295
296 const T& operator*()
297 {
298 return Get();
299 }
300
301 const T* operator->()
302 {
303 return &Get();
304 }
305
310 {
311 VERTEX_INDEX index;
312
316
317 return index;
318 }
319
320 private:
321 friend class SHAPE_POLY_SET;
322
329 };
330
334 template <class T>
336 {
337 public:
341 bool IsLastPolygon() const
342 {
344 }
345
346 operator bool() const
347 {
349 }
350
355 void Advance()
356 {
357 // Advance vertex index
359 int last;
360
361 // Check whether the user wants to iterate through the vertices of the holes
362 // and behave accordingly.
363 if( m_iterateHoles )
364 {
365 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
366
367 // If the last vertex of the contour was reached, advance the contour index.
368 if( m_currentSegment >= last )
369 {
372
373 // If the last contour of the current polygon was reached, advance the
374 // outline index.
375 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
376
377 if( m_currentContour >= totalContours )
378 {
381 }
382 }
383 }
384 else
385 {
386 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
387 // If the last vertex of the outline was reached, advance to the following
388 // polygon
389 if( m_currentSegment >= last )
390 {
393 }
394 }
395 }
396
397 void operator++( int dummy )
398 {
399 Advance();
400 }
401
403 {
404 Advance();
405 }
406
407 T Get()
408 {
410 }
411
413 {
414 return Get();
415 }
416
421 {
422 VERTEX_INDEX index;
423
427
428 return index;
429 }
430
437 {
438 // Check that both iterators point to the same contour of the same polygon of the
439 // same polygon set.
440 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
442 {
443 // Compute the total number of segments.
444 int numSeg;
445 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
446
447 // Compute the difference of the segment indices. If it is exactly one, they
448 // are adjacent. The only missing case where they also are adjacent is when
449 // the segments are the first and last one, in which case the difference
450 // always equals the total number of segments minus one.
451 int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
452
453 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
454 }
455
456 return false;
457 }
458
459 private:
460 friend class SHAPE_POLY_SET;
461
468 };
469
470 // Iterator and const iterator types to visit polygon's points.
473
474 // Iterator and const iterator types to visit polygon's edges.
477
479
480 SHAPE_POLY_SET( const BOX2D& aRect );
481
487 SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
488
495 SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
496
498
499 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
500
511 void CacheTriangulation( bool aPartition = true );
512 bool IsTriangulationUpToDate() const;
513
514 MD5_HASH GetHash() const;
515
516 virtual bool HasIndexableSubshapes() const override;
517
518 virtual size_t GetIndexableSubshapeCount() const override;
519
520 virtual void GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const override;
521
533 bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
534
544 bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
545
547 SHAPE* Clone() const override;
548
550
552 int NewOutline();
553
555 int NewHole( int aOutline = -1 );
556
558 int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
559
561 int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
562
564 double Area();
565
567 int ArcCount() const;
568
570 void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
571
573 void ClearArcs();
574
576
588 int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
589
591 void Append( const SHAPE_POLY_SET& aSet );
592
594 void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
595
604 int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1 );
605
613 void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
614
616 const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
617
619 const VECTOR2I& CVertex( int aGlobalIndex ) const;
620
622 const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
623
637 bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
638
645 bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
646
652 bool IsSelfIntersecting() const;
653
655 unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
656
658 int OutlineCount() const { return m_polys.size(); }
659
661 int VertexCount( int aOutline = -1, int aHole = -1 ) const;
662
665 int FullPointCount() const;
666
668 int HoleCount( int aOutline ) const
669 {
670 if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
671 || ( m_polys[aOutline].size() < 2 ) )
672 return 0;
673
674 // the first polygon in m_polys[aOutline] is the main contour,
675 // only others are holes:
676 return m_polys[aOutline].size() - 1;
677 }
678
681 {
682 return m_polys[aIndex][0];
683 }
684
685 const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
686 {
687 return m_polys[aIndex][0];
688 }
689
699 SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
700
701 SHAPE_POLY_SET UnitSet( int aPolygonIndex )
702 {
703 return Subset( aPolygonIndex, aPolygonIndex + 1 );
704 }
705
707 SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
708 {
709 return m_polys[aOutline][aHole + 1];
710 }
711
713 POLYGON& Polygon( int aIndex )
714 {
715 return m_polys[aIndex];
716 }
717
718 const POLYGON& Polygon( int aIndex ) const
719 {
720 return m_polys[aIndex];
721 }
722
723 const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
724 {
725 return m_triangulatedPolys[aIndex].get();
726 }
727
728 const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
729 {
730 return m_polys[aIndex][0];
731 }
732
733 const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
734 {
735 return m_polys[aOutline][aHole + 1];
736 }
737
738 const POLYGON& CPolygon( int aIndex ) const
739 {
740 return m_polys[aIndex];
741 }
742
753 ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
754 {
755 ITERATOR iter;
756
757 iter.m_poly = this;
758 iter.m_currentPolygon = aFirst;
759 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
760 iter.m_currentContour = 0;
761 iter.m_currentVertex = 0;
762 iter.m_iterateHoles = aIterateHoles;
763
764 return iter;
765 }
766
772 ITERATOR Iterate( int aOutline )
773 {
774 return Iterate( aOutline, aOutline );
775 }
776
783 {
784 return Iterate( aOutline, aOutline, true );
785 }
786
792 {
793 return Iterate( 0, OutlineCount() - 1 );
794 }
795
801 {
802 return Iterate( 0, OutlineCount() - 1, true );
803 }
804
805
806 CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
807 {
808 CONST_ITERATOR iter;
809
810 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
811 iter.m_currentPolygon = aFirst;
812 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
813 iter.m_currentContour = 0;
814 iter.m_currentVertex = 0;
815 iter.m_iterateHoles = aIterateHoles;
816
817 return iter;
818 }
819
820 CONST_ITERATOR CIterate( int aOutline ) const
821 {
822 return CIterate( aOutline, aOutline );
823 }
824
825 CONST_ITERATOR CIterateWithHoles( int aOutline ) const
826 {
827 return CIterate( aOutline, aOutline, true );
828 }
829
831 {
832 return CIterate( 0, OutlineCount() - 1 );
833 }
834
836 {
837 return CIterate( 0, OutlineCount() - 1, true );
838 }
839
841 {
842 // Build iterator
843 ITERATOR iter = IterateWithHoles();
844
845 // Get the relative indices of the globally indexed vertex
846 VERTEX_INDEX indices;
847
848 if( !GetRelativeIndices( aGlobalIdx, &indices ) )
849 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
850
851 // Adjust where the iterator is pointing
852 iter.m_currentPolygon = indices.m_polygon;
853 iter.m_currentContour = indices.m_contour;
854 iter.m_currentVertex = indices.m_vertex;
855
856 return iter;
857 }
858
861 SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
862 {
863 SEGMENT_ITERATOR iter;
864
865 iter.m_poly = this;
866 iter.m_currentPolygon = aFirst;
867 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
868 iter.m_currentContour = 0;
869 iter.m_currentSegment = 0;
870 iter.m_iterateHoles = aIterateHoles;
871
872 return iter;
873 }
874
878 bool aIterateHoles = false ) const
879 {
881
882 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
883 iter.m_currentPolygon = aFirst;
884 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
885 iter.m_currentContour = 0;
886 iter.m_currentSegment = 0;
887 iter.m_iterateHoles = aIterateHoles;
888
889 return iter;
890 }
891
894 {
895 return IterateSegments( aPolygonIdx, aPolygonIdx );
896 }
897
900 {
901 return CIterateSegments( aPolygonIdx, aPolygonIdx );
902 }
903
906 {
907 return IterateSegments( 0, OutlineCount() - 1 );
908 }
909
912 {
913 return CIterateSegments( 0, OutlineCount() - 1 );
914 }
915
918 {
919 return IterateSegments( 0, OutlineCount() - 1, true );
920 }
921
924 {
925 return IterateSegments( aOutline, aOutline, true );
926 }
927
930 {
931 return CIterateSegments( 0, OutlineCount() - 1, true );
932 }
933
936 {
937 return CIterateSegments( aOutline, aOutline, true );
938 }
939
949 {
950 PM_FAST = true,
951 PM_STRICTLY_SIMPLE = false
952 };
953
956 void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
957
960 void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
961
964 void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
965
968 void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
969 POLYGON_MODE aFastMode );
970
973 void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
974 POLYGON_MODE aFastMode );
975
978 void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
979 POLYGON_MODE aFastMode );
980
982 {
991 };
992
1007 void Inflate( int aAmount, int aCircleSegCount,
1008 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
1009
1010 void Deflate( int aAmount, int aCircleSegmentsCount,
1011 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
1012 {
1013 Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1014 }
1015
1023 void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1024
1028 void Fracture( POLYGON_MODE aFastMode );
1029
1032 void Unfracture( POLYGON_MODE aFastMode );
1033
1035 bool HasHoles() const;
1036
1038 bool HasTouchingHoles() const;
1039
1040
1043 void Simplify( POLYGON_MODE aFastMode );
1044
1054
1056 const std::string Format() const override;
1057
1059 bool Parse( std::stringstream& aStream ) override;
1060
1062 void Move( const VECTOR2I& aVector ) override;
1063
1071 void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1072
1079 void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1080
1082 bool IsSolid() const override
1083 {
1084 return true;
1085 }
1086
1087 const BOX2I BBox( int aClearance = 0 ) const override;
1088
1095 bool PointOnEdge( const VECTOR2I& aP ) const;
1096
1109 bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1110 VECTOR2I* aLocation = nullptr ) const override;
1111
1130 bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1131 VECTOR2I* aLocation = nullptr ) const override;
1132
1151 bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1152 VECTOR2I* aLocation = nullptr ) const override;
1153
1164 bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1165 int aClearance = 0 ) const;
1166
1177 bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1178 int aClearance = 0 ) const;
1179
1186 void BuildBBoxCaches() const;
1187
1188 const BOX2I BBoxFromCaches() const;
1189
1200 bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1201 bool aUseBBoxCaches = false ) const;
1202
1204 bool IsEmpty() const
1205 {
1206 return m_polys.empty();
1207 }
1208
1214 void RemoveVertex( int aGlobalIndex );
1215
1221 void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1222
1224 void RemoveAllContours();
1225
1234 void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1235
1241 int RemoveNullSegments();
1242
1249 void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1250
1259 void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1260
1262 int TotalVertices() const;
1263
1265 void DeletePolygon( int aIdx );
1266
1269 void DeletePolygonAndTriangulationData( int aIdx, bool aUpdateHash = true );
1270
1272
1280 POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1281
1290 POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1291
1298 SHAPE_POLY_SET Chamfer( int aDistance );
1299
1307 SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1308
1319 SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1320 VECTOR2I* aNearest ) const;
1321
1334 SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1335 VECTOR2I* aNearest) const;
1336
1347 SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1348
1360 SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1361
1368 bool IsVertexInHole( int aGlobalIdx );
1369
1378 static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths, bool aReverseOrientation = false, bool aEvenOdd = false );
1379
1380private:
1382
1384
1385 void fractureSingle( POLYGON& paths );
1386 void unfractureSingle ( POLYGON& path );
1387 void importTree( ClipperLib::PolyTree* tree,
1388 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1389 const std::vector<SHAPE_ARC>& aArcBuffe );
1390
1403 void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1404 POLYGON_MODE aFastMode );
1405
1406 void booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
1407 const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1408
1423 bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1424 bool aUseBBoxCaches = false ) const;
1425
1432 {
1434 FILLETED
1436
1450 POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1451 int aIndex, int aErrorMax );
1452
1454 bool hasTouchingHoles( const POLYGON& aPoly ) const;
1455
1456 MD5_HASH checksum() const;
1457
1458private:
1459 std::vector<POLYGON> m_polys;
1460 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1461
1464};
1465
1466#endif // __SHAPE_POLY_SET_H
Definition: seg.h:42
VECTOR2I::extended_type ecoord
Definition: seg.h:44
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
const std::string Format() 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
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
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 CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
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...
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 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
static LIB_SYMBOL * dummy()
Used to draw a dummy shape when a LIB_SYMBOL is not found in library.
Definition: sch_symbol.cpp:74
@ SH_POLY_SET_TRIANGLE
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:53
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