KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 The 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 <atomic>
32#include <cstdio>
33#include <deque> // for deque
34#include <iosfwd> // for string, stringstream
35#include <memory>
36#include <mutex>
37#include <set> // for set
38#include <stdexcept> // for out_of_range
39#include <stdlib.h> // for abs
40#include <vector>
41
42#include <clipper2/clipper.h>
43#include <core/mirror.h> // for FLIP_DIRECTION
45#include <geometry/seg.h> // for SEG
46#include <geometry/shape.h>
48#include <math/box2.h> // for BOX2I
49#include <math/vector2d.h> // for VECTOR2I
50#include <hash_128.h>
51
52
67class SHAPE_POLY_SET : public SHAPE
68{
69public:
73 typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
74
76 {
77 public:
78 struct TRI : public SHAPE_LINE_CHAIN_BASE
79 {
80 TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
82 a( _a ),
83 b( _b ),
84 c( _c ),
85 parent( aParent )
86 {
87 }
88
89 virtual void Rotate( const EDA_ANGLE& aAngle,
90 const VECTOR2I& aCenter = { 0, 0 } ) override {};
91
92 virtual void Move( const VECTOR2I& aVector ) override {};
93
94 virtual bool IsSolid() const override { return true; }
95
96 virtual bool IsClosed() const override { return true; }
97
98 virtual const BOX2I BBox( int aClearance = 0 ) const override;
99
100 virtual const VECTOR2I GetPoint( int aIndex ) const override
101 {
102 switch(aIndex)
103 {
104 case 0: return parent->m_vertices[a];
105 case 1: return parent->m_vertices[b];
106 case 2: return parent->m_vertices[c];
107 default: wxCHECK( false, VECTOR2I() );
108 }
109 }
110
111 virtual const SEG GetSegment( int aIndex ) const override
112 {
113 switch(aIndex)
114 {
115 case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
116 case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
117 case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
118 default: wxCHECK( false, SEG() );
119 }
120 }
121
122 virtual size_t GetPointCount() const override { return 3; }
123 virtual size_t GetSegmentCount() const override { return 3; }
124
125 double Area() const
126 {
127 VECTOR2I& aa = parent->m_vertices[a];
128 VECTOR2I& bb = parent->m_vertices[b];
129 VECTOR2I& cc = parent->m_vertices[c];
130
131 VECTOR2D ba = bb - aa;
132 VECTOR2D cb = cc - bb;
133
134 return std::abs( cb.Cross( ba ) * 0.5 );
135 }
136
137 int a;
138 int b;
139 int c;
141 };
142
143 TRIANGULATED_POLYGON( int aSourceOutline );
146
147 void Clear()
148 {
149 m_vertices.clear();
150 m_triangles.clear();
151 }
152
153 void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
154 {
155 auto& tri = m_triangles[ index ];
156 a = m_vertices[ tri.a ];
157 b = m_vertices[ tri.b ];
158 c = m_vertices[ tri.c ];
159 }
160
162
163 void AddTriangle( int a, int b, int c );
164
165 void AddVertex( const VECTOR2I& aP )
166 {
167 m_vertices.push_back( aP );
168 }
169
170 size_t GetTriangleCount() const { return m_triangles.size(); }
171
173 void SetSourceOutlineIndex( int aIndex ) { m_sourceOutline = aIndex; }
174
175 const std::deque<TRI>& Triangles() const { return m_triangles; }
176 void SetTriangles( const std::deque<TRI>& aTriangles )
177 {
178 m_triangles.resize( aTriangles.size() );
179
180 for( size_t ii = 0; ii < aTriangles.size(); ii++ )
181 {
182 m_triangles[ii] = aTriangles[ii];
183 m_triangles[ii].parent = this;
184 }
185 }
186
187 const std::deque<VECTOR2I>& Vertices() const { return m_vertices; }
188 void SetVertices( const std::deque<VECTOR2I>& aVertices )
189 {
190 m_vertices = aVertices;
191 }
192
193 size_t GetVertexCount() const
194 {
195 return m_vertices.size();
196 }
197
198 void Move( const VECTOR2I& aVec )
199 {
200 for( VECTOR2I& vertex : m_vertices )
201 vertex += aVec;
202 }
203
204 private:
206 std::deque<TRI> m_triangles;
207 std::deque<VECTOR2I> m_vertices;
208 };
209
216 {
222 m_polygon(-1),
223 m_contour(-1),
224 m_vertex(-1)
225 {
226 }
227 };
228
232 template <class T>
234 {
235 public:
236
241 bool IsEndContour() const
242 {
243 return m_currentVertex + 1 ==
245 }
246
250 bool IsLastPolygon() const
251 {
253 }
254
255 operator bool() const
256 {
258 return true;
259
260 if( m_currentPolygon != m_poly->OutlineCount() - 1 )
261 return false;
262
263 const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
264
265 return m_currentContour < (int) currentPolygon.size() - 1
266 || m_currentVertex < currentPolygon[m_currentContour].PointCount();
267 }
268
273 void Advance()
274 {
275 // Advance vertex index
277
278 // Check whether the user wants to iterate through the vertices of the holes
279 // and behave accordingly
280 if( m_iterateHoles )
281 {
282 // If the last vertex of the contour was reached, advance the contour index
283 if( m_currentVertex >=
285 {
286 m_currentVertex = 0;
288
289 // If the last contour of the current polygon was reached, advance the
290 // outline index
291 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
292
293 if( m_currentContour >= totalContours )
294 {
297 }
298 }
299 }
300 else
301 {
302 // If the last vertex of the outline was reached, advance to the following polygon
303 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
304 {
305 m_currentVertex = 0;
307 }
308 }
309 }
310
311 void operator++( int dummy )
312 {
313 Advance();
314 }
315
317 {
318 Advance();
319 }
320
321 const T& Get()
322 {
324 }
325
326 const T& operator*()
327 {
328 return Get();
329 }
330
331 const T* operator->()
332 {
333 return &Get();
334 }
335
340 {
341 VERTEX_INDEX index;
342
346
347 return index;
348 }
349
350 private:
351 friend class SHAPE_POLY_SET;
352
359 };
360
364 template <class T>
366 {
367 public:
371 bool IsLastPolygon() const
372 {
374 }
375
376 operator bool() const
377 {
379 }
380
385 void Advance()
386 {
387 // Advance vertex index
389 int last;
390
391 // Check whether the user wants to iterate through the vertices of the holes
392 // and behave accordingly.
393 if( m_iterateHoles )
394 {
395 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
396
397 // If the last vertex of the contour was reached, advance the contour index.
398 if( m_currentSegment >= last )
399 {
402
403 // If the last contour of the current polygon was reached, advance the
404 // outline index.
405 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
406
407 if( m_currentContour >= totalContours )
408 {
411 }
412 }
413 }
414 else
415 {
416 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
417 // If the last vertex of the outline was reached, advance to the following
418 // polygon
419 if( m_currentSegment >= last )
420 {
423 }
424 }
425 }
426
427 void operator++( int dummy )
428 {
429 Advance();
430 }
431
433 {
434 Advance();
435 }
436
438 {
440 }
441
443 {
444 return Get();
445 }
446
451 {
452 VERTEX_INDEX index;
453
457
458 return index;
459 }
460
467 {
468 // Check that both iterators point to the same contour of the same polygon of the
469 // same polygon set.
470 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
472 {
473 // Compute the total number of segments.
474 int numSeg;
475 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
476
477 // Compute the difference of the segment indices. If it is exactly one, they
478 // are adjacent. The only missing case where they also are adjacent is when
479 // the segments are the first and last one, in which case the difference
480 // always equals the total number of segments minus one.
481 int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
482
483 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
484 }
485
486 return false;
487 }
488
489 private:
490 friend class SHAPE_POLY_SET;
491
498 };
499
500 // Iterator and const iterator types to visit polygon's points.
503
504 // Iterator and const iterator types to visit polygon's edges.
507
509
510 SHAPE_POLY_SET( const BOX2D& aRect );
511
517 SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
518
524 SHAPE_POLY_SET( const POLYGON& aPolygon );
525
532 SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
533
535
536 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
537
538 // Move assignment operator
540 {
541 if (this != &aOther)
542 {
543 SHAPE::operator=( aOther );
544
545 m_polys = std::move( aOther.m_polys );
546 m_triangulatedPolys = std::move( aOther.m_triangulatedPolys );
547
548 m_hash = aOther.m_hash;
549 m_hashValid = aOther.m_hashValid;
550 m_triangulationValid.store( aOther.m_triangulationValid );
551 }
552
553 return *this;
554 }
555
567 virtual void CacheTriangulation( bool aPartition = true, bool aSimplify = false )
568 {
569 cacheTriangulation( aPartition, aSimplify, nullptr );
570 }
571 bool IsTriangulationUpToDate() const;
572
573 HASH_128 GetHash() const;
574
575 virtual bool HasIndexableSubshapes() const override;
576
577 virtual size_t GetIndexableSubshapeCount() const override;
578
579 virtual void GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const override;
580
592 bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
593
603 bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
604
606 SHAPE* Clone() const override;
607
609
611 int NewOutline();
612
614 int NewHole( int aOutline = -1 );
615
617 int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
618
620 int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
621
623 int AddPolygon( const POLYGON& apolygon );
624
626 double Area();
627
629 int ArcCount() const;
630
632 void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
633
635 void ClearArcs();
636
638
650 int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
651
653 void Append( const SHAPE_POLY_SET& aSet );
654
656 void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
657
667 int Append( const SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1,
668 std::optional<int> aMaxError = {} );
669
677 void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
678
680 const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
681
683 const VECTOR2I& CVertex( int aGlobalIndex ) const;
684
686 const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
687
701 bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext ) const;
702
709 bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
710
716 bool IsSelfIntersecting() const;
717
719 unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
720
722 int OutlineCount() const { return m_polys.size(); }
723
725 int VertexCount( int aOutline = -1, int aHole = -1 ) const;
726
729 int FullPointCount() const;
730
732 int HoleCount( int aOutline ) const
733 {
734 if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
735 || ( m_polys[aOutline].size() < 2 ) )
736 return 0;
737
738 // the first polygon in m_polys[aOutline] is the main contour,
739 // only others are holes:
740 return m_polys[aOutline].size() - 1;
741 }
742
745 {
746 return m_polys[aIndex][0];
747 }
748
749 const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
750 {
751 return m_polys[aIndex][0];
752 }
753
763 SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
764
765 SHAPE_POLY_SET UnitSet( int aPolygonIndex )
766 {
767 return Subset( aPolygonIndex, aPolygonIndex + 1 );
768 }
769
771 SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
772 {
773 return m_polys[aOutline][aHole + 1];
774 }
775
777 POLYGON& Polygon( int aIndex )
778 {
779 return m_polys[aIndex];
780 }
781
782 const POLYGON& Polygon( int aIndex ) const
783 {
784 return m_polys[aIndex];
785 }
786
787 const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
788 {
789 return m_triangulatedPolys[aIndex].get();
790 }
791
792 const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
793 {
794 return m_polys[aIndex][0];
795 }
796
797 const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
798 {
799 return m_polys[aOutline][aHole + 1];
800 }
801
802 const POLYGON& CPolygon( int aIndex ) const
803 {
804 return m_polys[aIndex];
805 }
806
807 const std::vector<POLYGON>& CPolygons() const { return m_polys; }
808
819 ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
820 {
821 ITERATOR iter;
822
823 iter.m_poly = this;
824 iter.m_currentPolygon = aFirst;
825 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
826 iter.m_currentContour = 0;
827 iter.m_currentVertex = 0;
828 iter.m_iterateHoles = aIterateHoles;
829
830 return iter;
831 }
832
838 ITERATOR Iterate( int aOutline )
839 {
840 return Iterate( aOutline, aOutline );
841 }
842
849 {
850 return Iterate( aOutline, aOutline, true );
851 }
852
858 {
859 return Iterate( 0, OutlineCount() - 1 );
860 }
861
867 {
868 return Iterate( 0, OutlineCount() - 1, true );
869 }
870
871
872 CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
873 {
874 CONST_ITERATOR iter;
875
876 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
877 iter.m_currentPolygon = aFirst;
878 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
879 iter.m_currentContour = 0;
880 iter.m_currentVertex = 0;
881 iter.m_iterateHoles = aIterateHoles;
882
883 return iter;
884 }
885
886 CONST_ITERATOR CIterate( int aOutline ) const
887 {
888 return CIterate( aOutline, aOutline );
889 }
890
891 CONST_ITERATOR CIterateWithHoles( int aOutline ) const
892 {
893 return CIterate( aOutline, aOutline, true );
894 }
895
897 {
898 return CIterate( 0, OutlineCount() - 1 );
899 }
900
902 {
903 return CIterate( 0, OutlineCount() - 1, true );
904 }
905
907 {
908 // Build iterator
909 ITERATOR iter = IterateWithHoles();
910
911 // Get the relative indices of the globally indexed vertex
912 VERTEX_INDEX indices;
913
914 if( !GetRelativeIndices( aGlobalIdx, &indices ) )
915 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
916
917 // Adjust where the iterator is pointing
918 iter.m_currentPolygon = indices.m_polygon;
919 iter.m_currentContour = indices.m_contour;
920 iter.m_currentVertex = indices.m_vertex;
921
922 return iter;
923 }
924
927 SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
928 {
929 SEGMENT_ITERATOR iter;
930
931 iter.m_poly = this;
932 iter.m_currentPolygon = aFirst;
933 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
934 iter.m_currentContour = 0;
935 iter.m_currentSegment = 0;
936 iter.m_iterateHoles = aIterateHoles;
937
938 return iter;
939 }
940
944 bool aIterateHoles = false ) const
945 {
947
948 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
949 iter.m_currentPolygon = aFirst;
950 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
951 iter.m_currentContour = 0;
952 iter.m_currentSegment = 0;
953 iter.m_iterateHoles = aIterateHoles;
954
955 return iter;
956 }
957
960 {
961 return IterateSegments( aPolygonIdx, aPolygonIdx );
962 }
963
966 {
967 return CIterateSegments( aPolygonIdx, aPolygonIdx );
968 }
969
972 {
973 return IterateSegments( 0, OutlineCount() - 1 );
974 }
975
978 {
979 return CIterateSegments( 0, OutlineCount() - 1 );
980 }
981
984 {
985 return IterateSegments( 0, OutlineCount() - 1, true );
986 }
987
990 {
991 return IterateSegments( aOutline, aOutline, true );
992 }
993
996 {
997 return CIterateSegments( 0, OutlineCount() - 1, true );
998 }
999
1002 {
1003 return CIterateSegments( aOutline, aOutline, true );
1004 }
1005
1006
1008 void BooleanAdd( const SHAPE_POLY_SET& b );
1009
1011 void BooleanSubtract( const SHAPE_POLY_SET& b );
1012
1014 void BooleanIntersection( const SHAPE_POLY_SET& b );
1015
1017 void BooleanXor( const SHAPE_POLY_SET& b );
1018
1020 void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1021
1023 void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1024
1026 void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1027
1029 void BooleanXor( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1030
1036
1052 void Inflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
1053 bool aSimplify = false );
1054
1055 void Deflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError )
1056 {
1057 Inflate( -aAmount, aCornerStrategy, aMaxError );
1058 }
1059
1073 void OffsetLineChain( const SHAPE_LINE_CHAIN& aLine, int aAmount,
1074 CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify );
1075
1082 void InflateWithLinkedHoles( int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError );
1083
1086 void Fracture();
1087
1090 void Unfracture();
1091
1093 bool HasHoles() const;
1094
1096 bool HasTouchingHoles() const;
1097
1098
1100 void Simplify();
1101
1108 void SimplifyOutlines( int aMaxError = 0 );
1109
1119
1121 const std::string Format( bool aCplusPlus = true ) const override;
1122
1124 bool Parse( std::stringstream& aStream ) override;
1125
1127 void Move( const VECTOR2I& aVector ) override;
1128
1135 void Mirror( const VECTOR2I& aRef, FLIP_DIRECTION aFlipDirection );
1136
1143 void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1144
1146 bool IsSolid() const override
1147 {
1148 return true;
1149 }
1150
1151 const BOX2I BBox( int aClearance = 0 ) const override;
1152
1159 bool PointOnEdge( const VECTOR2I& aP, int aAccuracy = 0 ) const;
1160
1173 bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1174 VECTOR2I* aLocation = nullptr ) const override;
1175
1194 bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1195 VECTOR2I* aLocation = nullptr ) const override;
1196
1215 bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1216 VECTOR2I* aLocation = nullptr ) const override;
1217
1228 bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1229 int aClearance = 0 ) const;
1230
1241 bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1242 int aClearance = 0 ) const;
1243
1244 bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0,
1245 bool aUseBBoxCache = false ) const override;
1246
1253 void BuildBBoxCaches() const;
1254
1255 const BOX2I BBoxFromCaches() const;
1256
1267 bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1268 bool aUseBBoxCaches = false ) const;
1269
1271 bool IsEmpty() const
1272 {
1273 return m_polys.empty();
1274 }
1275
1281 void RemoveVertex( int aGlobalIndex );
1282
1288 void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1289
1291 void RemoveAllContours();
1292
1301 void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1302
1303
1309 void RemoveOutline( int aOutlineIdx );
1310
1316 int RemoveNullSegments();
1317
1324 void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1325
1334 void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1335
1337 int TotalVertices() const;
1338
1340 void DeletePolygon( int aIdx );
1341
1344 void DeletePolygonAndTriangulationData( int aIdx, bool aUpdateHash = true );
1345
1347
1355 POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1356
1365 POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1366
1373 SHAPE_POLY_SET Chamfer( int aDistance );
1374
1382 SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1383
1394 SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1395 VECTOR2I* aNearest ) const;
1396
1409 SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1410 VECTOR2I* aNearest) const;
1411
1422 SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly,
1423 VECTOR2I* aNearest ) const;
1424
1425 SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly = false ) const override
1426 {
1427 return SquaredDistance( aPoint, aOutlineOnly, nullptr );
1428 }
1429
1441 SEG::ecoord SquaredDistanceToSeg( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1442
1449 bool IsVertexInHole( int aGlobalIdx );
1450
1458 void BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
1459 bool aEvenOdd = false );
1460
1461 void TransformToPolygon( SHAPE_POLY_SET& aBuffer, int aError,
1462 ERROR_LOC aErrorLoc ) const override
1463 {
1464 aBuffer.Append( *this );
1465 }
1466
1467 const std::vector<SEG> GenerateHatchLines( const std::vector<double>& aSlopes, int aSpacing,
1468 int aLineLength ) const;
1469
1470protected:
1471 void cacheTriangulation( bool aPartition, bool aSimplify,
1472 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData );
1473
1474private:
1476
1478
1479 void fractureSingle( POLYGON& paths );
1480 void unfractureSingle ( POLYGON& path );
1481 void importTree( Clipper2Lib::PolyTree64& tree,
1482 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1483 const std::vector<SHAPE_ARC>& aArcBuffe );
1484 void importPaths( Clipper2Lib::Paths64& paths,
1485 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1486 const std::vector<SHAPE_ARC>& aArcBuffe );
1487 void importPolyPath( const std::unique_ptr<Clipper2Lib::PolyPath64>& aPolyPath,
1488 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1489 const std::vector<SHAPE_ARC>& aArcBuffer );
1490
1491 void inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
1492
1493 void inflateLine2( const SHAPE_LINE_CHAIN& aLine, int aAmount, int aCircleSegCount,
1494 CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
1495
1503 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape );
1504
1505 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
1506 const SHAPE_POLY_SET& aOtherShape );
1507
1522 bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1523 bool aUseBBoxCaches = false ) const;
1524
1531 {
1533 FILLETED
1535
1549 POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1550 int aIndex, int aErrorMax );
1551
1553 bool hasTouchingHoles( const POLYGON& aPoly ) const;
1554
1555 HASH_128 checksum() const;
1556
1557protected:
1558 std::vector<POLYGON> m_polys;
1559 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1560
1561 std::atomic<bool> m_triangulationValid = false;
1563
1564private:
1566 bool m_hashValid = false;
1567};
1568
1569#endif // __SHAPE_POLY_SET_H
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
Definition: approximation.h:32
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< VECTOR2I > & Vertices() const
void SetVertices(const std::deque< VECTOR2I > &aVertices)
const std::deque< TRI > & Triangles() const
void AddTriangle(int a, int b, int c)
void SetTriangles(const std::deque< TRI > &aTriangles)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
void Move(const VECTOR2I &aVec)
Represent a set of closed polygons.
std::mutex m_triangulationMutex
virtual bool HasIndexableSubshapes() const override
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
void RemoveAllContours()
Remove all outlines & holes (clears) the polygon set.
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
void RemoveOutline(int aOutlineIdx)
Delete the aOutlineIdx-th outline of the set including its contours and holes.
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.
HASH_128 GetHash() const
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const override
void BooleanXor(const SHAPE_POLY_SET &b)
Perform boolean polyset exclusive or.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes.
CONST_ITERATOR CIterateWithHoles() const
void BooleanAdd(const SHAPE_POLY_SET &b)
Perform boolean polyset union.
ITERATOR IterateWithHoles(int aOutline)
ITERATOR IterateWithHoles()
void ClearArcs()
Removes all arc references from all the outlines and holes in the polyset.
bool IsTriangulationUpToDate() const
void importPaths(Clipper2Lib::Paths64 &paths, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
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 outline to the set and returns its index.
virtual void CacheTriangulation(bool aPartition=true, bool aSimplify=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of vertices in a given outline/hole.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon from the set.
double Area()
Return the area of this poly set.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void Fracture()
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
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,...
void BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
ITERATOR Iterate(int aOutline)
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Return total number of vertices stored in the set.
CONST_ITERATOR CIterate(int aOutline) const
POLYGON & Polygon(int aIndex)
Return the aIndex-th subpolygon in the set.
int FullPointCount() const
Return the number of points in the shape poly set.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Appends all the arcs in this polyset to aArcBuffer.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
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)
void inflateLine2(const SHAPE_LINE_CHAIN &aLine, int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify=false)
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
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)
const POLYGON & Polygon(int aIndex) const
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
HASH_128 checksum() const
void Inflate(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify=false)
Perform outline inflation/deflation.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
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)
int AddPolygon(const POLYGON &apolygon)
Adds a polygon to the set.
const std::vector< SEG > GenerateHatchLines(const std::vector< double > &aSlopes, int aSpacing, int aLineLength) const
const std::string Format(bool aCplusPlus=true) const override
void Simplify()
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections)
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()
Return an iterator object, for all outlines in the set (no holes).
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 (no holes)
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
void inflate2(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify=false)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index.
SEG::ecoord SquaredDistance(const VECTOR2I &aPoint, bool aOutlineOnly, VECTOR2I *aNearest) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void Unfracture()
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int ArcCount() const
Count the number of arc shapes present.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext) const
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the reference to aHole-th hole in the aIndex-th outline.
bool IsSolid() const override
int NewOutline()
Creates a new empty polygon in the set and returns its index.
void SimplifyOutlines(int aMaxError=0)
Simplifies the lines in the polyset.
void booleanOp(Clipper2Lib::ClipType aType, const SHAPE_POLY_SET &aOtherShape)
This is the engine to execute all polygon boolean transforms (AND, OR, ... and polygon simplification...
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool hasTouchingHoles(const POLYGON &aPoly) const
Return true if the polygon set has any holes that touch share a vertex.
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
SEG::ecoord SquaredDistance(const VECTOR2I &aPoint, bool aOutlineOnly=false) const override
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of some of the outlines or 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)
Delete aIdx-th polygon and its triangulation data from the set.
unsigned int TriangulatedPolyCount() const
Return the number of triangulated polygons.
std::atomic< bool > m_triangulationValid
void Deflate(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError)
void UpdateTriangulationDataHash()
void BooleanIntersection(const SHAPE_POLY_SET &b)
Perform boolean polyset intersection.
int NewHole(int aOutline=-1)
Creates a new hole in a given outline.
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).
void cacheTriangulation(bool aPartition, bool aSimplify, std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > *aHintData)
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 between aFirst and aLast outline, with or without holes (def...
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
SEG::ecoord SquaredDistanceToSeg(const SEG &aSegment, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aSegment and all the polygons in the set.
void importPolyPath(const std::unique_ptr< Clipper2Lib::PolyPath64 > &aPolyPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
void RebuildHolesFromContours()
Extract all contours from this polygon set, then recreate polygons with holes.
void Mirror(const VECTOR2I &aRef, FLIP_DIRECTION aFlipDirection)
Mirror the line points about y or x (or both)
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
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 index-th vertex in a given hole outline within a given outline.
int OutlineCount() const
Return the number of outlines in the set.
void InflateWithLinkedHoles(int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError)
Perform outline inflation/deflation, using round corners.
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 & operator=(SHAPE_POLY_SET &&aOther) noexcept
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
Return true if the polygon set has any holes that share a vertex.
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
void TransformToPolygon(SHAPE_POLY_SET &aBuffer, int aError, ERROR_LOC aErrorLoc) const override
Fills a SHAPE_POLY_SET with a polygon representation of this shape.
void BooleanSubtract(const SHAPE_POLY_SET &b)
Perform boolean polyset difference.
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.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
const std::vector< POLYGON > & CPolygons() const
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
const BOX2I BBoxFromCaches() const
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
Return an iterator object, for the aOutline-th outline in the set (with holes).
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
void importTree(Clipper2Lib::PolyTree64 &tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
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:126
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:546
CORNER_STRATEGY
define how inflate transform build inflated polygon
FLIP_DIRECTION
Definition: mirror.h:27
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:400
@ SH_POLY_SET_TRIANGLE
a single triangle belonging to a POLY_SET triangulation
Definition: shape.h:56
std::vector< FAB_LAYER_COLOR > dummy
A storage class for 128-bit hash value.
Definition: hash_128.h:36
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< int32_t > VECTOR2I
Definition: vector2d.h:695