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 // Move assignment operator.
165 {
166 if( this != &aOther )
167 {
168 m_sourceOutline = aOther.m_sourceOutline;
169 m_triangles = std::move( aOther.m_triangles );
170 m_vertices = std::move( aOther.m_vertices );
171
172 for( TRI& tri : m_triangles )
173 tri.parent = this;
174 }
175
176 return *this;
177 }
178
179 void AddTriangle( int a, int b, int c );
180
181 void AddVertex( const VECTOR2I& aP )
182 {
183 m_vertices.push_back( aP );
184 }
185
186 size_t GetTriangleCount() const { return m_triangles.size(); }
187
189 void SetSourceOutlineIndex( int aIndex ) { m_sourceOutline = aIndex; }
190
191 const std::deque<TRI>& Triangles() const { return m_triangles; }
192 void SetTriangles( const std::deque<TRI>& aTriangles )
193 {
194 m_triangles.resize( aTriangles.size() );
195
196 for( size_t ii = 0; ii < aTriangles.size(); ii++ )
197 {
198 m_triangles[ii] = aTriangles[ii];
199 m_triangles[ii].parent = this;
200 }
201 }
202
203 const std::deque<VECTOR2I>& Vertices() const { return m_vertices; }
204 void SetVertices( const std::deque<VECTOR2I>& aVertices )
205 {
206 m_vertices = aVertices;
207 }
208
209 size_t GetVertexCount() const
210 {
211 return m_vertices.size();
212 }
213
214 void Move( const VECTOR2I& aVec )
215 {
216 for( VECTOR2I& vertex : m_vertices )
217 vertex += aVec;
218 }
219
220 private:
222 std::deque<TRI> m_triangles;
223 std::deque<VECTOR2I> m_vertices;
224 };
225
232 {
236
238 m_polygon(-1),
239 m_contour(-1),
240 m_vertex(-1)
241 {
242 }
243 };
244
248 template <class T>
250 {
251 public:
252
257 bool IsEndContour() const
258 {
259 return m_currentVertex + 1 == m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
260 }
261
265 bool IsLastPolygon() const
266 {
268 }
269
270 operator bool() const
271 {
273 return true;
274
275 if( m_currentPolygon != m_poly->OutlineCount() - 1 )
276 return false;
277
278 const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
279
280 return m_currentContour < (int) currentPolygon.size() - 1
281 || m_currentVertex < currentPolygon[m_currentContour].PointCount();
282 }
283
288 void Advance()
289 {
290 // Advance vertex index
292
293 // Check whether the user wants to iterate through the vertices of the holes
294 // and behave accordingly
295 if( m_iterateHoles )
296 {
297 // If the last vertex of the contour was reached, advance the contour index
298 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
299 {
300 m_currentVertex = 0;
302
303 // If the last contour of the current polygon was reached, advance the
304 // outline index
305 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
306
307 if( m_currentContour >= totalContours )
308 {
311 }
312 }
313 }
314 else
315 {
316 // If the last vertex of the outline was reached, advance to the following polygon
317 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
318 {
319 m_currentVertex = 0;
321 }
322 }
323 }
324
325 void operator++( int dummy )
326 {
327 Advance();
328 }
329
331 {
332 Advance();
333 }
334
335 const T& Get()
336 {
337 return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint( m_currentVertex );
338 }
339
340 const T& operator*()
341 {
342 return Get();
343 }
344
345 const T* operator->()
346 {
347 return &Get();
348 }
349
354 {
355 VERTEX_INDEX index;
356
360
361 return index;
362 }
363
364 private:
365 friend class SHAPE_POLY_SET;
366
373 };
374
378 template <class T>
380 {
381 public:
385 bool IsLastPolygon() const
386 {
388 }
389
390 operator bool() const
391 {
393 }
394
399 void Advance()
400 {
401 // Advance vertex index
403 int last;
404
405 // Check whether the user wants to iterate through the vertices of the holes
406 // and behave accordingly.
407 if( m_iterateHoles )
408 {
409 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
410
411 // If the last vertex of the contour was reached, advance the contour index.
412 if( m_currentSegment >= last )
413 {
416
417 // If the last contour of the current polygon was reached, advance the
418 // outline index.
419 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
420
421 if( m_currentContour >= totalContours )
422 {
425 }
426 }
427 }
428 else
429 {
430 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
431 // If the last vertex of the outline was reached, advance to the following
432 // polygon
433 if( m_currentSegment >= last )
434 {
437 }
438 }
439 }
440
441 void operator++( int dummy )
442 {
443 Advance();
444 }
445
447 {
448 Advance();
449 }
450
452 {
453 return m_poly->Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
454 }
455
457 {
458 return Get();
459 }
460
465 {
466 VERTEX_INDEX index;
467
471
472 return index;
473 }
474
481 {
482 // Check that both iterators point to the same contour of the same polygon of the
483 // same polygon set.
484 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
486 {
487 // Compute the total number of segments.
488 int numSeg;
489 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
490
491 // Compute the difference of the segment indices. If it is exactly one, they
492 // are adjacent. The only missing case where they also are adjacent is when
493 // the segments are the first and last one, in which case the difference
494 // always equals the total number of segments minus one.
495 int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
496
497 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
498 }
499
500 return false;
501 }
502
503 private:
504 friend class SHAPE_POLY_SET;
505
512 };
513
514 // Iterator and const iterator types to visit polygon's points.
517
518 // Iterator and const iterator types to visit polygon's edges.
521
523
524 SHAPE_POLY_SET( const BOX2D& aRect );
525
531 SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
532
538 SHAPE_POLY_SET( const POLYGON& aPolygon );
539
546 SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
547
549
550 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
551
552 // Move assignment operator
554 {
555 if (this != &aOther)
556 {
557 SHAPE::operator=( aOther );
558
559 m_polys = std::move( aOther.m_polys );
560 m_triangulatedPolys = std::move( aOther.m_triangulatedPolys );
561
562 m_hash = aOther.m_hash;
563 m_hashValid = aOther.m_hashValid;
564 m_triangulationValid.store( aOther.m_triangulationValid );
565 }
566
567 return *this;
568 }
569
581 virtual void CacheTriangulation( bool aPartition = true, bool aSimplify = false )
582 {
583 cacheTriangulation( aPartition, aSimplify, nullptr );
584 }
585 bool IsTriangulationUpToDate() const;
586
587 HASH_128 GetHash() const;
588
589 virtual bool HasIndexableSubshapes() const override;
590
591 virtual size_t GetIndexableSubshapeCount() const override;
592
593 virtual void GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const override;
594
606 bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
607
617 bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
618
620 SHAPE* Clone() const override;
621
623
625 int NewOutline();
626
628 int NewHole( int aOutline = -1 );
629
631 int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
632
634 int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
635
637 int AddPolygon( const POLYGON& apolygon );
638
640 double Area();
641
643 int ArcCount() const;
644
646 void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
647
649 void ClearArcs();
650
652
664 int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
665
667 void Append( const SHAPE_POLY_SET& aSet );
668
670 void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
671
681 int Append( const SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1,
682 std::optional<int> aMaxError = {} );
683
691 void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
692
694 const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
695
697 const VECTOR2I& CVertex( int aGlobalIndex ) const;
698
700 const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
701
715 bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext ) const;
716
723 bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
724
730 bool IsSelfIntersecting() const;
731
733 unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
734
736 int OutlineCount() const { return m_polys.size(); }
737
739 int VertexCount( int aOutline = -1, int aHole = -1 ) const;
740
743 int FullPointCount() const;
744
746 int HoleCount( int aOutline ) const
747 {
748 if( aOutline < 0 || aOutline >= (int) m_polys.size() || m_polys[aOutline].size() < 2 )
749 return 0;
750
751 // the first polygon in m_polys[aOutline] is the main contour,
752 // only others are holes:
753 return m_polys[aOutline].size() - 1;
754 }
755
758 {
759 return m_polys[aIndex][0];
760 }
761
762 const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
763 {
764 return m_polys[aIndex][0];
765 }
766
776 SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
777
778 SHAPE_POLY_SET UnitSet( int aPolygonIndex )
779 {
780 return Subset( aPolygonIndex, aPolygonIndex + 1 );
781 }
782
784 SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
785 {
786 return m_polys[aOutline][aHole + 1];
787 }
788
790 POLYGON& Polygon( int aIndex )
791 {
792 return m_polys[aIndex];
793 }
794
795 const POLYGON& Polygon( int aIndex ) const
796 {
797 return m_polys[aIndex];
798 }
799
800 const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
801 {
802 return m_triangulatedPolys[aIndex].get();
803 }
804
805 const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
806 {
807 return m_polys[aIndex][0];
808 }
809
810 const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
811 {
812 return m_polys[aOutline][aHole + 1];
813 }
814
815 const POLYGON& CPolygon( int aIndex ) const
816 {
817 return m_polys[aIndex];
818 }
819
820 const std::vector<POLYGON>& CPolygons() const { return m_polys; }
821
832 ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
833 {
834 ITERATOR iter;
835
836 iter.m_poly = this;
837 iter.m_currentPolygon = aFirst;
838 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
839 iter.m_currentContour = 0;
840 iter.m_currentVertex = 0;
841 iter.m_iterateHoles = aIterateHoles;
842
843 return iter;
844 }
845
851 ITERATOR Iterate( int aOutline )
852 {
853 return Iterate( aOutline, aOutline );
854 }
855
862 {
863 return Iterate( aOutline, aOutline, true );
864 }
865
871 {
872 return Iterate( 0, OutlineCount() - 1 );
873 }
874
880 {
881 return Iterate( 0, OutlineCount() - 1, true );
882 }
883
884
885 CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
886 {
887 CONST_ITERATOR iter;
888
889 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
890 iter.m_currentPolygon = aFirst;
891 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
892 iter.m_currentContour = 0;
893 iter.m_currentVertex = 0;
894 iter.m_iterateHoles = aIterateHoles;
895
896 return iter;
897 }
898
899 CONST_ITERATOR CIterate( int aOutline ) const
900 {
901 return CIterate( aOutline, aOutline );
902 }
903
904 CONST_ITERATOR CIterateWithHoles( int aOutline ) const
905 {
906 return CIterate( aOutline, aOutline, true );
907 }
908
910 {
911 return CIterate( 0, OutlineCount() - 1 );
912 }
913
915 {
916 return CIterate( 0, OutlineCount() - 1, true );
917 }
918
920 {
921 // Build iterator
922 ITERATOR iter = IterateWithHoles();
923
924 // Get the relative indices of the globally indexed vertex
925 VERTEX_INDEX indices;
926
927 if( !GetRelativeIndices( aGlobalIdx, &indices ) )
928 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
929
930 // Adjust where the iterator is pointing
931 iter.m_currentPolygon = indices.m_polygon;
932 iter.m_currentContour = indices.m_contour;
933 iter.m_currentVertex = indices.m_vertex;
934
935 return iter;
936 }
937
940 SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
941 {
942 SEGMENT_ITERATOR iter;
943
944 iter.m_poly = this;
945 iter.m_currentPolygon = aFirst;
946 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
947 iter.m_currentContour = 0;
948 iter.m_currentSegment = 0;
949 iter.m_iterateHoles = aIterateHoles;
950
951 return iter;
952 }
953
957 bool aIterateHoles = false ) const
958 {
960
961 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
962 iter.m_currentPolygon = aFirst;
963 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
964 iter.m_currentContour = 0;
965 iter.m_currentSegment = 0;
966 iter.m_iterateHoles = aIterateHoles;
967
968 return iter;
969 }
970
973 {
974 return IterateSegments( aPolygonIdx, aPolygonIdx );
975 }
976
979 {
980 return CIterateSegments( aPolygonIdx, aPolygonIdx );
981 }
982
985 {
986 return IterateSegments( 0, OutlineCount() - 1 );
987 }
988
991 {
992 return CIterateSegments( 0, OutlineCount() - 1 );
993 }
994
997 {
998 return IterateSegments( 0, OutlineCount() - 1, true );
999 }
1000
1003 {
1004 return IterateSegments( aOutline, aOutline, true );
1005 }
1006
1009 {
1010 return CIterateSegments( 0, OutlineCount() - 1, true );
1011 }
1012
1015 {
1016 return CIterateSegments( aOutline, aOutline, true );
1017 }
1018
1019
1021 void BooleanAdd( const SHAPE_POLY_SET& b );
1022
1024 void BooleanSubtract( const SHAPE_POLY_SET& b );
1025
1027 void BooleanIntersection( const SHAPE_POLY_SET& b );
1028
1030 void BooleanXor( const SHAPE_POLY_SET& b );
1031
1033 void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1034
1036 void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1037
1039 void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1040
1042 void BooleanXor( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b );
1043
1049
1065 void Inflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
1066 bool aSimplify = false );
1067
1068 void Deflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError )
1069 {
1070 Inflate( -aAmount, aCornerStrategy, aMaxError );
1071 }
1072
1086 void OffsetLineChain( const SHAPE_LINE_CHAIN& aLine, int aAmount,
1087 CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify );
1088
1095 void InflateWithLinkedHoles( int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError );
1096
1099 void Fracture();
1100
1103 void Unfracture();
1104
1106 bool HasHoles() const;
1107
1109 bool HasTouchingHoles() const;
1110
1111
1113 void Simplify();
1114
1121 void SimplifyOutlines( int aMaxError = 0 );
1122
1132
1134 const std::string Format( bool aCplusPlus = true ) const override;
1135
1137 bool Parse( std::stringstream& aStream ) override;
1138
1140 void Move( const VECTOR2I& aVector ) override;
1141
1148 void Mirror( const VECTOR2I& aRef, FLIP_DIRECTION aFlipDirection );
1149
1156 void Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1157
1159 bool IsSolid() const override
1160 {
1161 return true;
1162 }
1163
1164 const BOX2I BBox( int aClearance = 0 ) const override;
1165
1172 bool PointOnEdge( const VECTOR2I& aP, int aAccuracy = 0 ) const;
1173
1186 bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1187 VECTOR2I* aLocation = nullptr ) const override;
1188
1207 bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1208 VECTOR2I* aLocation = nullptr ) const override;
1209
1228 bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1229 VECTOR2I* aLocation = nullptr ) const override;
1230
1241 bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1242 int aClearance = 0 ) const;
1243
1254 bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX* aClosestVertex = nullptr,
1255 int aClearance = 0 ) const;
1256
1257 bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0,
1258 bool aUseBBoxCache = false ) const override;
1259
1266 void BuildBBoxCaches() const;
1267
1268 const BOX2I BBoxFromCaches() const;
1269
1280 bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1281 bool aUseBBoxCaches = false ) const;
1282
1284 bool IsEmpty() const
1285 {
1286 return m_polys.empty();
1287 }
1288
1294 void RemoveVertex( int aGlobalIndex );
1295
1301 void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1302
1304 void RemoveAllContours();
1305
1314 void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1315
1316
1322 void RemoveOutline( int aOutlineIdx );
1323
1329 int RemoveNullSegments();
1330
1337 void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1338
1347 void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1348
1350 int TotalVertices() const;
1351
1353 void DeletePolygon( int aIdx );
1354
1357 void DeletePolygonAndTriangulationData( int aIdx, bool aUpdateHash = true );
1358
1360
1368 POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1369
1378 POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1379
1386 SHAPE_POLY_SET Chamfer( int aDistance );
1387
1395 SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1396
1407 SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1408 VECTOR2I* aNearest ) const;
1409
1422 SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1423 VECTOR2I* aNearest) const;
1424
1435 SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly,
1436 VECTOR2I* aNearest ) const;
1437
1438 SEG::ecoord SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly = false ) const override
1439 {
1440 return SquaredDistance( aPoint, aOutlineOnly, nullptr );
1441 }
1442
1454 SEG::ecoord SquaredDistanceToSeg( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1455
1462 bool IsVertexInHole( int aGlobalIdx );
1463
1471 void BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
1472 bool aEvenOdd = false );
1473
1474 void TransformToPolygon( SHAPE_POLY_SET& aBuffer, int aError,
1475 ERROR_LOC aErrorLoc ) const override
1476 {
1477 aBuffer.Append( *this );
1478 }
1479
1480 const std::vector<SEG> GenerateHatchLines( const std::vector<double>& aSlopes, int aSpacing,
1481 int aLineLength ) const;
1482
1483protected:
1484 void cacheTriangulation( bool aPartition, bool aSimplify,
1485 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData );
1486
1487private:
1489
1491
1492 void fractureSingle( POLYGON& paths );
1493 void unfractureSingle ( POLYGON& path );
1494 void importTree( Clipper2Lib::PolyTree64& tree,
1495 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1496 const std::vector<SHAPE_ARC>& aArcBuffe );
1497 void importPaths( Clipper2Lib::Paths64& paths,
1498 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1499 const std::vector<SHAPE_ARC>& aArcBuffe );
1500 void importPolyPath( const std::unique_ptr<Clipper2Lib::PolyPath64>& aPolyPath,
1501 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1502 const std::vector<SHAPE_ARC>& aArcBuffer );
1503
1504 void inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
1505
1506 void inflateLine2( const SHAPE_LINE_CHAIN& aLine, int aAmount, int aCircleSegCount,
1507 CORNER_STRATEGY aCornerStrategy, bool aSimplify = false );
1508
1510
1518 bool isExteriorWaist( const SEG& aSegA, const SEG& aSegB ) const;
1519
1527 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape );
1528
1529 void booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
1530 const SHAPE_POLY_SET& aOtherShape );
1531
1546 bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1547 bool aUseBBoxCaches = false ) const;
1548
1559
1573 POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1574 int aIndex, int aErrorMax );
1575
1577 bool hasTouchingHoles( const POLYGON& aPoly ) const;
1578
1579 HASH_128 checksum() const;
1580
1581protected:
1582 std::vector<POLYGON> m_polys;
1583 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1584
1585 std::atomic<bool> m_triangulationValid = false;
1587
1588private:
1590 bool m_hashValid = false;
1591};
1592
1593#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...
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
BOX2< VECTOR2D > BOX2D
Definition box2.h:923
Definition seg.h:42
VECTOR2I::extended_type ecoord
Definition seg.h:44
SHAPE_LINE_CHAIN_BASE(SHAPE_TYPE aType)
Definition shape.h:308
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
TRIANGULATED_POLYGON & operator=(TRIANGULATED_POLYGON &&aOther) noexcept
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.
bool isExteriorWaist(const SEG &aSegA, const SEG &aSegB) const
Check if two line segments are collinear and overlap.
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
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition shape.h:136
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
VECTOR2< double > VECTOR2D
Definition vector2d.h:694