Horizon
Loading...
Searching...
No Matches
shape_poly_set.h
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 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8 * @author Alejandro García Montoro <alejandro.garciamontoro@gmail.com>
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 "router/clipper_kicad/clipper.hpp" // for ClipType, PolyTree (ptr only)
42#include <geometry/seg.h> // for SEG
43#include <geometry/shape.h>
44#include <geometry/shape_line_chain.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 ) :
78 SHAPE_LINE_CHAIN_BASE( SH_POLY_SET_TRIANGLE ),
79 a( _a ),
80 b( _b ),
81 c( _c ),
82 parent( aParent )
83 {
84 }
85
86 virtual void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override {};
87
88 virtual void Move( const VECTOR2I& aVector ) override {};
89
90 virtual bool IsSolid() const override { return true; }
91
92 virtual bool IsClosed() const override { return true; }
93
94 virtual const BOX2I BBox( int aClearance = 0 ) const override;
95
96 virtual const VECTOR2I GetPoint( int aIndex ) const override
97 {
98 switch(aIndex)
99 {
100 case 0: return parent->m_vertices[a];
101 case 1: return parent->m_vertices[b];
102 case 2: return parent->m_vertices[c];
103 default: assert(false);
104 }
105 return VECTOR2I(0, 0);
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: assert(false);
116 }
117 return SEG();
118 }
119
120 virtual size_t GetPointCount() const override { return 3; }
121 virtual size_t GetSegmentCount() const override { return 3; }
122
123
124 int a, b, c;
125 TRIANGULATED_POLYGON* parent;
126 };
127
128 TRIANGULATED_POLYGON();
129 TRIANGULATED_POLYGON( const TRIANGULATED_POLYGON& aOther );
130 ~TRIANGULATED_POLYGON();
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
146 TRIANGULATED_POLYGON& operator=( const TRIANGULATED_POLYGON& aOther );
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
156 {
157 return m_triangles.size();
158 }
159
160 std::deque<TRI>& Triangles()
161 {
162 return m_triangles;
163 }
164
165 size_t GetVertexCount() const
166 {
167 return m_vertices.size();
168 }
169
170 void Move( const VECTOR2I& aVec )
171 {
172 for( auto& vertex : m_vertices )
173 vertex += aVec;
174 }
175
176 private:
177 std::deque<TRI> m_triangles;
178 std::deque<VECTOR2I> m_vertices;
179 };
180
187 {
192 VERTEX_INDEX() :
193 m_polygon(-1),
194 m_contour(-1),
195 m_vertex(-1)
196 {
197 }
198 };
199
203 template <class T>
205 {
206 public:
207
212 bool IsEndContour() const
213 {
214 return m_currentVertex + 1 ==
215 m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
216 }
217
221 bool IsLastPolygon() const
222 {
223 return m_currentPolygon == m_lastPolygon;
224 }
225
226 operator bool() const
227 {
228 if( m_currentPolygon < m_lastPolygon )
229 return true;
230
231 if( m_currentPolygon != m_poly->OutlineCount() - 1 )
232 return false;
233
234 const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
235
236 return m_currentContour < (int) currentPolygon.size() - 1
237 || m_currentVertex < currentPolygon[m_currentContour].PointCount();
238 }
239
244 void Advance()
245 {
246 // Advance vertex index
247 m_currentVertex ++;
248
249 // Check whether the user wants to iterate through the vertices of the holes
250 // and behave accordingly
251 if( m_iterateHoles )
252 {
253 // If the last vertex of the contour was reached, advance the contour index
254 if( m_currentVertex >=
255 m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
256 {
257 m_currentVertex = 0;
258 m_currentContour++;
259
260 // If the last contour of the current polygon was reached, advance the
261 // outline index
262 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
263
264 if( m_currentContour >= totalContours )
265 {
266 m_currentContour = 0;
267 m_currentPolygon++;
268 }
269 }
270 }
271 else
272 {
273 // If the last vertex of the outline was reached, advance to the following polygon
274 if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
275 {
276 m_currentVertex = 0;
277 m_currentPolygon++;
278 }
279 }
280 }
281
282 void operator++( int dummy )
283 {
284 Advance();
285 }
286
287 void operator++()
288 {
289 Advance();
290 }
291
292 const T& Get()
293 {
294 return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint( m_currentVertex );
295 }
296
297 const T& operator*()
298 {
299 return Get();
300 }
301
302 const T* operator->()
303 {
304 return &Get();
305 }
306
311 {
312 VERTEX_INDEX index;
313
314 index.m_polygon = m_currentPolygon;
315 index.m_contour = m_currentContour;
316 index.m_vertex = m_currentVertex;
317
318 return index;
319 }
320
321 private:
322 friend class SHAPE_POLY_SET;
323
324 SHAPE_POLY_SET* m_poly;
325 int m_currentPolygon;
326 int m_currentContour;
327 int m_currentVertex;
328 int m_lastPolygon;
329 bool m_iterateHoles;
330 };
331
335 template <class T>
337 {
338 public:
342 bool IsLastPolygon() const
343 {
344 return m_currentPolygon == m_lastPolygon;
345 }
346
347 operator bool() const
348 {
349 return m_currentPolygon <= m_lastPolygon;
350 }
351
356 void Advance()
357 {
358 // Advance vertex index
359 m_currentSegment++;
360 int last;
361
362 // Check whether the user wants to iterate through the vertices of the holes
363 // and behave accordingly.
364 if( m_iterateHoles )
365 {
366 last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
367
368 // If the last vertex of the contour was reached, advance the contour index.
369 if( m_currentSegment >= last )
370 {
371 m_currentSegment = 0;
372 m_currentContour++;
373
374 // If the last contour of the current polygon was reached, advance the
375 // outline index.
376 int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
377
378 if( m_currentContour >= totalContours )
379 {
380 m_currentContour = 0;
381 m_currentPolygon++;
382 }
383 }
384 }
385 else
386 {
387 last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
388 // If the last vertex of the outline was reached, advance to the following
389 // polygon
390 if( m_currentSegment >= last )
391 {
392 m_currentSegment = 0;
393 m_currentPolygon++;
394 }
395 }
396 }
397
398 void operator++( int dummy )
399 {
400 Advance();
401 }
402
403 void operator++()
404 {
405 Advance();
406 }
407
408 T Get()
409 {
410 return m_poly->Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
411 }
412
413 T operator*()
414 {
415 return Get();
416 }
417
422 {
423 VERTEX_INDEX index;
424
425 index.m_polygon = m_currentPolygon;
426 index.m_contour = m_currentContour;
427 index.m_vertex = m_currentSegment;
428
429 return index;
430 }
431
438 {
439 // Check that both iterators point to the same contour of the same polygon of the
440 // same polygon set.
441 if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
442 m_currentContour == aOther.m_currentContour )
443 {
444 // Compute the total number of segments.
445 int numSeg;
446 numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
447
448 // Compute the difference of the segment indices. If it is exactly one, they
449 // are adjacent. The only missing case where they also are adjacent is when
450 // the segments are the first and last one, in which case the difference
451 // always equals the total number of segments minus one.
452 int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
453
454 return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
455 }
456
457 return false;
458 }
459
460 private:
461 friend class SHAPE_POLY_SET;
462
463 SHAPE_POLY_SET* m_poly;
464 int m_currentPolygon;
465 int m_currentContour;
466 int m_currentSegment;
467 int m_lastPolygon;
468 bool m_iterateHoles;
469 };
470
471 // Iterator and const iterator types to visit polygon's points.
472 typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR;
473 typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR;
474
475 // Iterator and const iterator types to visit polygon's edges.
476 typedef SEGMENT_ITERATOR_TEMPLATE<SEG> SEGMENT_ITERATOR;
477 typedef SEGMENT_ITERATOR_TEMPLATE<const SEG> CONST_SEGMENT_ITERATOR;
478
480
481 SHAPE_POLY_SET( const BOX2D& aRect );
482
488 SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
489
496 SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
497
499
500 SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
501
502 void CacheTriangulation( bool aPartition = true );
503 bool IsTriangulationUpToDate() const;
504
505 MD5_HASH GetHash() const;
506
507 virtual bool HasIndexableSubshapes() const override;
508
509 virtual size_t GetIndexableSubshapeCount() const override;
510
511 virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
512
524 bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
525
535 bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
536
538 SHAPE* Clone() const override;
539
541 int NewOutline();
542
544 int NewHole( int aOutline = -1 );
545
547 int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
548
550 int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
551
553 double Area();
554
556 int ArcCount() const;
557
559 void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
560
562 void ClearArcs();
563
565
577 int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
578
580 void Append( const SHAPE_POLY_SET& aSet );
581
583 void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
584
593 int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1 );
594
602 void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
603
605 const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
606
608 const VECTOR2I& CVertex( int aGlobalIndex ) const;
609
611 const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
612
626 bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
627
634 bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
635
641 bool IsSelfIntersecting() const;
642
644 unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
645
647 int OutlineCount() const { return m_polys.size(); }
648
650 int VertexCount( int aOutline = -1, int aHole = -1 ) const;
651
654 int FullPointCount() const;
655
657 int HoleCount( int aOutline ) const
658 {
659 if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
660 || ( m_polys[aOutline].size() < 2 ) )
661 return 0;
662
663 // the first polygon in m_polys[aOutline] is the main contour,
664 // only others are holes:
665 return m_polys[aOutline].size() - 1;
666 }
667
669 SHAPE_LINE_CHAIN& Outline( int aIndex )
670 {
671 return m_polys[aIndex][0];
672 }
673
674 const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
675 {
676 return m_polys[aIndex][0];
677 }
678
688 SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
689
690 SHAPE_POLY_SET UnitSet( int aPolygonIndex )
691 {
692 return Subset( aPolygonIndex, aPolygonIndex + 1 );
693 }
694
696 SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
697 {
698 return m_polys[aOutline][aHole + 1];
699 }
700
702 POLYGON& Polygon( int aIndex )
703 {
704 return m_polys[aIndex];
705 }
706
707 const POLYGON& Polygon( int aIndex ) const
708 {
709 return m_polys[aIndex];
710 }
711
712 const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
713 {
714 return m_triangulatedPolys[aIndex].get();
715 }
716
717 const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
718 {
719 return m_polys[aIndex][0];
720 }
721
722 const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
723 {
724 return m_polys[aOutline][aHole + 1];
725 }
726
727 const POLYGON& CPolygon( int aIndex ) const
728 {
729 return m_polys[aIndex];
730 }
731
742 ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
743 {
744 ITERATOR iter;
745
746 iter.m_poly = this;
747 iter.m_currentPolygon = aFirst;
748 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
749 iter.m_currentContour = 0;
750 iter.m_currentVertex = 0;
751 iter.m_iterateHoles = aIterateHoles;
752
753 return iter;
754 }
755
761 ITERATOR Iterate( int aOutline )
762 {
763 return Iterate( aOutline, aOutline );
764 }
765
772 {
773 return Iterate( aOutline, aOutline, true );
774 }
775
781 {
782 return Iterate( 0, OutlineCount() - 1 );
783 }
784
790 {
791 return Iterate( 0, OutlineCount() - 1, true );
792 }
793
794
795 CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
796 {
797 CONST_ITERATOR iter;
798
799 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
800 iter.m_currentPolygon = aFirst;
801 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
802 iter.m_currentContour = 0;
803 iter.m_currentVertex = 0;
804 iter.m_iterateHoles = aIterateHoles;
805
806 return iter;
807 }
808
809 CONST_ITERATOR CIterate( int aOutline ) const
810 {
811 return CIterate( aOutline, aOutline );
812 }
813
814 CONST_ITERATOR CIterateWithHoles( int aOutline ) const
815 {
816 return CIterate( aOutline, aOutline, true );
817 }
818
819 CONST_ITERATOR CIterate() const
820 {
821 return CIterate( 0, OutlineCount() - 1 );
822 }
823
824 CONST_ITERATOR CIterateWithHoles() const
825 {
826 return CIterate( 0, OutlineCount() - 1, true );
827 }
828
830 {
831 // Build iterator
832 ITERATOR iter = IterateWithHoles();
833
834 // Get the relative indices of the globally indexed vertex
835 VERTEX_INDEX indices;
836
837 if( !GetRelativeIndices( aGlobalIdx, &indices ) )
838 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
839
840 // Adjust where the iterator is pointing
841 iter.m_currentPolygon = indices.m_polygon;
842 iter.m_currentContour = indices.m_contour;
843 iter.m_currentVertex = indices.m_vertex;
844
845 return iter;
846 }
847
850 SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
851 {
852 SEGMENT_ITERATOR iter;
853
854 iter.m_poly = this;
855 iter.m_currentPolygon = aFirst;
856 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
857 iter.m_currentContour = 0;
858 iter.m_currentSegment = 0;
859 iter.m_iterateHoles = aIterateHoles;
860
861 return iter;
862 }
863
867 bool aIterateHoles = false ) const
868 {
870
871 iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
872 iter.m_currentPolygon = aFirst;
873 iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
874 iter.m_currentContour = 0;
875 iter.m_currentSegment = 0;
876 iter.m_iterateHoles = aIterateHoles;
877
878 return iter;
879 }
880
883 {
884 return IterateSegments( aPolygonIdx, aPolygonIdx );
885 }
886
889 {
890 return CIterateSegments( aPolygonIdx, aPolygonIdx );
891 }
892
895 {
896 return IterateSegments( 0, OutlineCount() - 1 );
897 }
898
901 {
902 return CIterateSegments( 0, OutlineCount() - 1 );
903 }
904
907 {
908 return IterateSegments( 0, OutlineCount() - 1, true );
909 }
910
913 {
914 return IterateSegments( aOutline, aOutline, true );
915 }
916
919 {
920 return CIterateSegments( 0, OutlineCount() - 1, true );
921 }
922
924 CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles( int aOutline ) const
925 {
926 return CIterateSegments( aOutline, aOutline, true );
927 }
928
938 {
939 PM_FAST = true,
940 PM_STRICTLY_SIMPLE = false
941 };
942
945 void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
946
949 void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
950
953 void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
954
957 void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
958 POLYGON_MODE aFastMode );
959
962 void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
963 POLYGON_MODE aFastMode );
964
967 void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
968 POLYGON_MODE aFastMode );
969
981
996 void Inflate( int aAmount, int aCircleSegCount,
997 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
998
999 void Deflate( int aAmount, int aCircleSegmentsCount,
1000 CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
1001 {
1002 Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1003 }
1004
1012 void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1013
1017 void Fracture( POLYGON_MODE aFastMode );
1018
1021 void Unfracture( POLYGON_MODE aFastMode );
1022
1024 bool HasHoles() const;
1025
1027 bool HasTouchingHoles() const;
1028
1029
1032 void Simplify( POLYGON_MODE aFastMode );
1033
1043
1045 const std::string Format() const override;
1046
1048 bool Parse( std::stringstream& aStream ) override;
1049
1051 void Move( const VECTOR2I& aVector ) override;
1052
1060 void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1061
1068 void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1069
1071 bool IsSolid() const override
1072 {
1073 return true;
1074 }
1075
1076 const BOX2I BBox( int aClearance = 0 ) const override;
1077
1084 bool PointOnEdge( const VECTOR2I& aP ) const;
1085
1098 bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1099 VECTOR2I* aLocation = nullptr ) const override;
1100
1119 bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1120 VECTOR2I* aLocation = nullptr ) const override;
1121
1140 bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1141 VECTOR2I* aLocation = nullptr ) const override;
1142
1153 bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1154 int aClearance = 0 ) const;
1155
1166 bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1167 int aClearance = 0 ) const;
1168
1175 void BuildBBoxCaches() const;
1176
1177 const BOX2I BBoxFromCaches() const;
1178
1189 bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1190 bool aUseBBoxCaches = false ) const;
1191
1193 bool IsEmpty() const
1194 {
1195 return m_polys.empty();
1196 }
1197
1203 void RemoveVertex( int aGlobalIndex );
1204
1210 void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1211
1213 void RemoveAllContours();
1214
1223 void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1224
1230 int RemoveNullSegments();
1231
1238 void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1239
1248 void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1249
1251 int TotalVertices() const;
1252
1254 void DeletePolygon( int aIdx );
1255
1263 POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1264
1273 POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1274
1281 SHAPE_POLY_SET Chamfer( int aDistance );
1282
1290 SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1291
1302 SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1303 VECTOR2I* aNearest ) const;
1304
1317 SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1318 VECTOR2I* aNearest) const;
1319
1330 SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1331
1343 SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1344
1351 bool IsVertexInHole( int aGlobalIdx );
1352
1361 static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths, bool aReverseOrientation = false, bool aEvenOdd = false );
1362
1363private:
1364 void fractureSingle( POLYGON& paths );
1365 void unfractureSingle ( POLYGON& path );
1366 void importTree( ClipperLibKiCad::PolyTree* tree,
1367 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1368 const std::vector<SHAPE_ARC>& aArcBuffe );
1369
1382 void booleanOp( ClipperLibKiCad::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1383 POLYGON_MODE aFastMode );
1384
1385 void booleanOp( ClipperLibKiCad::ClipType aType, const SHAPE_POLY_SET& aShape,
1386 const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1387
1402 bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1403 bool aUseBBoxCaches = false ) const;
1404
1410 enum CORNER_MODE
1411 {
1412 CHAMFERED,
1413 FILLETED
1414 };
1415
1429 POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1430 int aIndex, int aErrorMax );
1431
1433 bool hasTouchingHoles( const POLYGON& aPoly ) const;
1434
1435 MD5_HASH checksum() const;
1436
1437private:
1438 typedef std::vector<POLYGON> POLYSET;
1439
1440 POLYSET m_polys;
1441
1442 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1443
1444 bool m_triangulationValid = false;
1445 MD5_HASH m_hash;
1446};
1447
1448#endif // __SHAPE_POLY_SET_H
Definition clipper.hpp:193
Definition md5_hash.h:12
Definition seg.h:41
Definition shape_arc.h:36
Definition shape.h:241
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition shape_line_chain.h:81
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
Definition shape_poly_set.h:205
bool IsLastPolygon() const
Definition shape_poly_set.h:221
VERTEX_INDEX GetIndex()
Definition shape_poly_set.h:310
bool IsEndContour() const
Definition shape_poly_set.h:212
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Definition shape_poly_set.h:244
Base class for iterating over all segments in a given SHAPE_POLY_SET.
Definition shape_poly_set.h:337
bool IsLastPolygon() const
Definition shape_poly_set.h:342
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
Definition shape_poly_set.h:437
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Definition shape_poly_set.h:356
VERTEX_INDEX GetIndex() const
Definition shape_poly_set.h:421
Definition shape_poly_set.h:73
Represent a set of closed polygons.
Definition shape_poly_set.h:65
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.
Definition shape_poly_set.cpp:2531
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
Definition shape_poly_set.cpp:1956
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
Definition shape_poly_set.cpp:2019
const std::string Format() const override
Definition shape_poly_set.cpp:1299
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
Definition shape_poly_set.cpp:684
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
Definition shape_poly_set.cpp:1234
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
Definition shape_poly_set.cpp:1422
ITERATOR IterateWithHoles(int aOutline)
Definition shape_poly_set.h:771
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
Definition shape_poly_set.cpp:1063
ITERATOR IterateWithHoles()
Definition shape_poly_set.h:789
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
Definition shape_poly_set.cpp:556
POLYGON_MODE
Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
Definition shape_poly_set.h:938
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
Definition shape_poly_set.cpp:276
CORNER_STRATEGY
< define how inflate transform build inflated polygon
Definition shape_poly_set.h:971
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
Definition shape_poly_set.h:972
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
Definition shape_poly_set.h:973
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
Definition shape_poly_set.h:974
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
Definition shape_poly_set.h:975
@ ROUND_ALL_CORNERS
All angles are rounded.
Definition shape_poly_set.h:978
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
Definition shape_poly_set.cpp:480
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
Definition shape_poly_set.cpp:298
double Area()
Count the number of arc shapes present.
Definition shape_poly_set.cpp:513
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
Definition shape_poly_set.cpp:1784
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
Definition shape_poly_set.cpp:678
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,...
Definition shape_poly_set.cpp:1484
ITERATOR Iterate(int aOutline)
Definition shape_poly_set.h:761
bool Parse(std::stringstream &aStream) override
Definition shape_poly_set.cpp:1330
int TotalVertices() const
Delete aIdx-th polygon from the set.
Definition shape_poly_set.cpp:1856
int FullPointCount() const
Returns the number of holes in a given outline.
Definition shape_poly_set.cpp:323
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
Definition shape_poly_set.cpp:543
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
Definition shape_poly_set.cpp:2006
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
Definition shape_poly_set.cpp:726
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
Definition shape_poly_set.cpp:1266
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
Definition shape_poly_set.cpp:1755
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
Definition shape_poly_set.h:882
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
Definition shape_poly_set.cpp:1842
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,...
Definition shape_poly_set.cpp:690
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition shape_poly_set.h:912
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...
Definition shape_poly_set.cpp:122
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
Definition shape_poly_set.cpp:441
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
Definition shape_poly_set.cpp:344
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
Return the reference to aHole-th hole in the aIndex-th outline.
Definition shape_poly_set.h:690
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
Definition shape_poly_set.cpp:1583
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Definition shape_poly_set.h:657
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...
Definition shape_poly_set.cpp:230
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Definition shape_poly_set.h:70
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
Definition shape_poly_set.h:894
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...
Definition shape_poly_set.cpp:394
ITERATOR Iterate()
Definition shape_poly_set.h:780
CONST_SEGMENT_ITERATOR CIterateSegments() const
Returns an iterator object, for all outlines in the set (with holes)
Definition shape_poly_set.h:900
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
Definition shape_poly_set.cpp:494
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
Definition shape_poly_set.cpp:1573
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
Definition shape_poly_set.cpp:1829
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
Definition shape_poly_set.cpp:529
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.
Definition shape_poly_set.cpp:1249
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
Definition shape_poly_set.cpp:162
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
Definition shape_poly_set.h:696
bool IsSolid() const override
Definition shape_poly_set.h:1071
int NewOutline()
Creates a new hole in a given outline.
Definition shape_poly_set.cpp:201
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Return an iterator object, for all outlines in the set (no holes).
Definition shape_poly_set.h:888
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
Definition shape_poly_set.cpp:1693
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
Definition shape_poly_set.h:644
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
Definition shape_poly_set.cpp:213
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
Definition shape_poly_set.cpp:1883
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition shape_poly_set.h:918
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...
Definition shape_poly_set.h:850
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Return an object to iterate through the points of the polygons between aFirst and aLast.
Definition shape_poly_set.h:742
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
Definition shape_poly_set.h:866
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
Definition shape_poly_set.h:829
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
Definition shape_poly_set.cpp:1654
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
Definition shape_poly_set.cpp:1722
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
Definition shape_poly_set.cpp:1876
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the aGlobalIndex-th vertex in the poly set.
Definition shape_poly_set.cpp:357
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Definition shape_poly_set.h:647
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
Definition shape_poly_set.cpp:2030
void Move(const VECTOR2I &aVector) override
Definition shape_poly_set.cpp:1814
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
Definition shape_poly_set.cpp:2417
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
Definition shape_poly_set.cpp:116
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.
Definition shape_poly_set.cpp:1734
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
Definition shape_poly_set.cpp:717
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
Definition shape_poly_set.cpp:1870
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition shape_poly_set.h:906
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition shape_poly_set.cpp:1389
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
Definition shape_poly_set.cpp:468
An abstract shape on 2D plane.
Definition shape.h:117
Definition shape_poly_set.h:76
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition shape_poly_set.cpp:2479
virtual void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Definition shape_poly_set.h:86
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
Definition shape_poly_set.h:187
int m_vertex
Definition shape_poly_set.h:190
int m_polygon
Definition shape_poly_set.h:188
int m_contour
Definition shape_poly_set.h:189