KiCad PCB EDA Suite
Loading...
Searching...
No Matches
shape_poly_set.cpp
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 * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
11 * subject to Clipper library license.
12 *
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation; either version 2
16 * of the License, or (at your option) any later version.
17 *
18 * This program is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License
24 * along with this program. If not, see <https://www.gnu.org/licenses/>.
25 */
26
27#include <algorithm>
28#include <assert.h> // for assert
29#include <cmath> // for sqrt, cos, hypot, isinf
30#include <cstdio>
31#include <istream> // for operator<<, operator>>
32#include <limits> // for numeric_limits
33#include <map>
34#include <memory>
35#include <set>
36#include <string> // for char_traits, operator!=
37#include <unordered_map>
38#include <unordered_set>
39#include <thread>
40#include <utility> // for swap, move
41#include <vector>
42#include <array>
43
44#include <clipper2/clipper.h>
48#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
49#include <geometry/shape.h>
55#include <math/box2.h> // for BOX2I
56#include <math/util.h> // for KiROUND, rescale
57#include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
58#include <hash.h>
59#include <mmh3_hash.h>
63
64#include <wx/log.h>
65
66// ADVANCED_CFG::GetCfg() cannot be used on msys2/mingw builds (link failure)
67// So we use the ADVANCED_CFG default values
68#if defined( __MINGW32__ )
69 #define TRIANGULATESIMPLIFICATIONLEVEL 50
70 #define ENABLECACHEFRIENDLYFRACTURE true
71 #define ENABLEFRACTUREEDGEINDEX true
72#else
73 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
74 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
75 #define ENABLEFRACTUREEDGEINDEX ADVANCED_CFG::GetCfg().m_EnableFractureEdgeIndex
76#endif
77
78// Below this many elements a direct scan beats building and querying a spatial index.
79static constexpr int RTREE_THRESHOLD = 32;
80
81
86
87
90{
91 NewOutline();
92 Append( VECTOR2I( aRect.GetLeft(), aRect.GetTop() ) );
93 Append( VECTOR2I( aRect.GetRight(), aRect.GetTop() ) );
94 Append( VECTOR2I( aRect.GetRight(), aRect.GetBottom() ) );
95 Append( VECTOR2I( aRect.GetLeft(), aRect.GetBottom() ) );
96 Outline( 0 ).SetClosed( true );
97}
98
99
102{
103 AddOutline( aOutline );
104}
105
106
109{
110 AddPolygon( aPolygon );
111}
112
113
115 SHAPE( aOther ),
116 m_polys( aOther.m_polys )
117{
118 if( aOther.IsTriangulationUpToDate() )
119 {
120 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
121
122 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
123 {
124 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
125 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
126 }
127
128 m_hash = aOther.GetHash();
129 m_hashValid = true;
131 }
132 else
133 {
134 m_hash.Clear();
135 m_hashValid = false;
136 m_triangulationValid = false;
137 }
138
139 m_failedHash = aOther.m_failedHash;
140 m_failedHashValid.store( aOther.m_failedHashValid.load() );
141}
142
143
145 SHAPE( aOther ),
146 m_polys( aOther.m_polys )
147{
148 m_hash.Clear();
149 m_hashValid = false;
150 m_triangulationValid = false;
151}
152
153
157
158
160{
161 return new SHAPE_POLY_SET( *this );
162}
163
164
169
170
172 SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
173{
174 int polygonIdx = 0;
175 unsigned int contourIdx = 0;
176 int vertexIdx = 0;
177
178 int currentGlobalIdx = 0;
179
180 for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
181 {
182 const POLYGON& currentPolygon = CPolygon( polygonIdx );
183
184 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
185 {
186 const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
187 int totalPoints = currentContour.PointCount();
188
189 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
190 {
191 // Check if the current vertex is the globally indexed as aGlobalIdx
192 if( currentGlobalIdx == aGlobalIdx )
193 {
194 aRelativeIndices->m_polygon = polygonIdx;
195 aRelativeIndices->m_contour = contourIdx;
196 aRelativeIndices->m_vertex = vertexIdx;
197
198 return true;
199 }
200
201 // Advance
202 currentGlobalIdx++;
203 }
204 }
205 }
206
207 return false;
208}
209
210
212 int& aGlobalIdx ) const
213{
214 int selectedVertex = aRelativeIndices.m_vertex;
215 unsigned int selectedContour = aRelativeIndices.m_contour;
216 unsigned int selectedPolygon = aRelativeIndices.m_polygon;
217
218 // Check whether the vertex indices make sense in this poly set
219 if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
220 && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
221 {
222 POLYGON currentPolygon;
223
224 aGlobalIdx = 0;
225
226 for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
227 {
228 currentPolygon = Polygon( polygonIdx );
229
230 for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
231 aGlobalIdx += currentPolygon[contourIdx].PointCount();
232 }
233
234 currentPolygon = Polygon( selectedPolygon );
235
236 for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
237 aGlobalIdx += currentPolygon[contourIdx].PointCount();
238
239 aGlobalIdx += selectedVertex;
240
241 return true;
242 }
243 else
244 {
245 return false;
246 }
247}
248
249
251{
252 SHAPE_LINE_CHAIN empty_path;
253 POLYGON poly;
254
255 empty_path.SetClosed( true );
256 poly.push_back( empty_path );
257 m_polys.push_back( std::move( poly ) );
258 return m_polys.size() - 1;
259}
260
261
262int SHAPE_POLY_SET::NewHole( int aOutline )
263{
264 SHAPE_LINE_CHAIN empty_path;
265
266 empty_path.SetClosed( true );
267
268 // Default outline is the last one
269 if( aOutline < 0 )
270 aOutline += m_polys.size();
271
272 // Add hole to the selected outline
273 m_polys[aOutline].push_back( empty_path );
274
275 return m_polys.back().size() - 2;
276}
277
278
279int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
280{
281 assert( m_polys.size() );
282
283 if( aOutline < 0 )
284 aOutline += m_polys.size();
285
286 int idx;
287
288 if( aHole < 0 )
289 idx = 0;
290 else
291 idx = aHole + 1;
292
293 assert( aOutline < (int) m_polys.size() );
294 assert( idx < (int) m_polys[aOutline].size() );
295
296 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
297
298 return m_polys[aOutline][idx].PointCount();
299}
300
301
302int SHAPE_POLY_SET::Append( const SHAPE_ARC& aArc, int aOutline, int aHole,
303 std::optional<int> aMaxError )
304{
305 assert( m_polys.size() );
306
307 if( aOutline < 0 )
308 aOutline += m_polys.size();
309
310 int idx;
311
312 if( aHole < 0 )
313 idx = 0;
314 else
315 idx = aHole + 1;
316
317 assert( aOutline < (int) m_polys.size() );
318 assert( idx < (int) m_polys[aOutline].size() );
319
320 if( aMaxError.has_value() )
321 m_polys[aOutline][idx].Append( aArc, aMaxError.value() );
322 else
323 m_polys[aOutline][idx].Append( aArc );
324
325 return m_polys[aOutline][idx].PointCount();
326}
327
328
329void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex )
330{
332
333 if( aGlobalIndex < 0 )
334 aGlobalIndex = 0;
335
336 if( aGlobalIndex >= TotalVertices() )
337 {
338 Append( aNewVertex );
339 }
340 else
341 {
342 // Assure the position to be inserted exists; throw an exception otherwise
343 if( GetRelativeIndices( aGlobalIndex, &index ) )
344 m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
345 else
346 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
347 }
348}
349
350
351int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
352{
353 if( m_polys.size() == 0 ) // Empty poly set
354 return 0;
355
356 if( aOutline < 0 ) // Use last outline
357 aOutline += m_polys.size();
358
359 int idx;
360
361 if( aHole < 0 )
362 idx = 0;
363 else
364 idx = aHole + 1;
365
366 if( aOutline >= (int) m_polys.size() ) // not existing outline
367 return 0;
368
369 if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
370 return 0;
371
372 return m_polys[aOutline][idx].PointCount();
373}
374
375
377{
378 int full_count = 0;
379
380 if( m_polys.size() == 0 ) // Empty poly set
381 return full_count;
382
383 for( int ii = 0; ii < OutlineCount(); ii++ )
384 {
385 // the first polygon in m_polys[ii] is the main contour,
386 // only others are holes:
387 for( int idx = 0; idx <= HoleCount( ii ); idx++ )
388 {
389 full_count += m_polys[ii][idx].PointCount();
390 }
391 }
392
393 return full_count;
394}
395
396
397SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
398{
399 assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
400
401 SHAPE_POLY_SET newPolySet;
402
403 for( int index = aFirstPolygon; index < aLastPolygon; index++ )
404 newPolySet.m_polys.push_back( Polygon( index ) );
405
406 return newPolySet;
407}
408
409
410const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
411{
412 if( aOutline < 0 )
413 aOutline += m_polys.size();
414
415 int idx;
416
417 if( aHole < 0 )
418 idx = 0;
419 else
420 idx = aHole + 1;
421
422 assert( aOutline < (int) m_polys.size() );
423 assert( idx < (int) m_polys[aOutline].size() );
424
425 return m_polys[aOutline][idx].CPoint( aIndex );
426}
427
428
429const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
430{
432
433 // Assure the passed index references a legal position; abort otherwise
434 if( !GetRelativeIndices( aGlobalIndex, &index ) )
435 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
436
437 return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
438}
439
440
442{
443 return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
444}
445
446
447bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext ) const
448{
450
451 // If the edge does not exist, throw an exception, it is an illegal access memory error
452 if( !GetRelativeIndices( aGlobalIndex, &index ) )
453 return false;
454
455 // Calculate the previous and next index of aGlobalIndex, corresponding to
456 // the same contour;
457 VERTEX_INDEX inext = index;
458 int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
459
460 if( index.m_vertex == 0 )
461 {
462 index.m_vertex = lastpoint - 1;
463 inext.m_vertex = 1;
464 }
465 else if( index.m_vertex == lastpoint )
466 {
467 index.m_vertex--;
468 inext.m_vertex = 0;
469 }
470 else
471 {
472 inext.m_vertex++;
473 index.m_vertex--;
474
475 if( inext.m_vertex == lastpoint )
476 inext.m_vertex = 0;
477 }
478
479 if( aPrevious )
480 {
481 int previous;
482 GetGlobalIndex( index, previous );
483 *aPrevious = previous;
484 }
485
486 if( aNext )
487 {
488 int next;
489 GetGlobalIndex( inext, next );
490 *aNext = next;
491 }
492
493 return true;
494}
495
496
497bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
498{
499 // SEG::Index() counts within one contour, so adjacency needs the contour too
500 struct CONTOUR_SEG
501 {
502 SEG seg;
503 int contour;
504 };
505
506 std::vector<CONTOUR_SEG> segments;
507 segments.reserve( FullPointCount() );
508
509 for( CONST_SEGMENT_ITERATOR it = CIterateSegmentsWithHoles( aPolygonIndex ); it; it++ )
510 segments.push_back( { *it, it.GetIndex().m_contour } );
511
512 std::sort( segments.begin(), segments.end(), []( const CONTOUR_SEG& aA, const CONTOUR_SEG& aB )
513 {
514 const SEG& a = aA.seg;
515 const SEG& b = aB.seg;
516 int min_a_x = std::min( a.A.x, a.B.x );
517 int min_b_x = std::min( b.A.x, b.B.x );
518
519 return min_a_x < min_b_x || ( min_a_x == min_b_x && std::min( a.A.y, a.B.y ) < std::min( b.A.y, b.B.y ) );
520 } );
521
522 const POLYGON& polygon = m_polys[aPolygonIndex];
523
524 for( auto it = segments.begin(); it != segments.end(); ++it )
525 {
526 SEG& firstSegment = it->seg;
527
528 // Iterate through all remaining segments.
529 auto innerIterator = it;
530 int max_x = std::max( firstSegment.A.x, firstSegment.B.x );
531 int max_y = std::max( firstSegment.A.y, firstSegment.B.y );
532
533 // Start in the next segment, we don't want to check collision between a segment and itself
534 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
535 {
536 SEG& secondSegment = innerIterator->seg;
537 int min_x = std::min( secondSegment.A.x, secondSegment.B.x );
538 int min_y = std::min( secondSegment.A.y, secondSegment.B.y );
539
540 // We are ordered in minimum point order, so checking the static max (first segment) against
541 // the ordered min will tell us if any of the following segments are withing the BBox
542 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
543 break;
544
545 bool adjacent = false;
546
547 if( it->contour == innerIterator->contour )
548 {
549 int index_diff = std::abs( firstSegment.Index() - secondSegment.Index() );
550 adjacent = ( index_diff == 1 ) || ( index_diff == polygon[it->contour].SegmentCount() - 1 );
551 }
552
553 // Check whether the two segments built collide, only when they are not adjacent.
554 if( !adjacent && firstSegment.Collide( secondSegment, 0 ) )
555 return true;
556 }
557 }
558
559 return false;
560}
561
562
564{
565 for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
566 {
568 return true;
569 }
570
571 return false;
572}
573
574
576{
577 POLYGON poly;
578
579 poly.push_back( aOutline );
580
581 // This is an assertion because if it's generated by KiCad code, it probably
582 // indicates a bug elsewhere that should be fixed, but we also auto-fix it here
583 // for SWIG plugins that might mess it up
584 wxCHECK2_MSG( aOutline.IsClosed(), poly.back().SetClosed( true ),
585 "Warning: non-closed outline added to SHAPE_POLY_SET" );
586
587 m_polys.push_back( std::move( poly ) );
588
589 return (int) m_polys.size() - 1;
590}
591
592
593int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
594{
595 assert( m_polys.size() );
596
597 if( aOutline < 0 )
598 aOutline += (int) m_polys.size();
599
600 assert( aOutline < (int)m_polys.size() );
601
602 POLYGON& poly = m_polys[aOutline];
603
604 assert( poly.size() );
605
606 poly.push_back( aHole );
607
608 return (int) poly.size() - 2;
609}
610
611
613{
614 m_polys.push_back( apolygon );
615
616 return m_polys.size() - 1;
617}
618
619
621{
622 double area = 0.0;
623
624 for( int i = 0; i < OutlineCount(); i++ )
625 {
626 area += Outline( i ).Area( true );
627
628 for( int j = 0; j < HoleCount( i ); j++ )
629 area -= Hole( i, j ).Area( true );
630 }
631
632 return area;
633}
634
635
637{
638 int retval = 0;
639
640 for( const POLYGON& poly : m_polys )
641 {
642 for( size_t i = 0; i < poly.size(); i++ )
643 retval += poly[i].ArcCount();
644 }
645
646 return retval;
647}
648
649
650void SHAPE_POLY_SET::GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const
651{
652 for( const POLYGON& poly : m_polys )
653 {
654 for( size_t i = 0; i < poly.size(); i++ )
655 {
656 for( SHAPE_ARC arc : poly[i].m_arcs )
657 aArcBuffer.push_back( arc );
658 }
659 }
660}
661
662
664{
665 for( POLYGON& poly : m_polys )
666 {
667 for( size_t i = 0; i < poly.size(); i++ )
668 poly[i].ClearArcs();
669 }
670}
671
672
674{
675 std::vector<SHAPE_LINE_CHAIN> contours;
676
677 for( const POLYGON& poly : m_polys )
678 contours.insert( contours.end(), poly.begin(), poly.end() );
679
680 std::map<int, std::set<int>> parentToChildren;
681 std::map<int, std::set<int>> childToParents;
682
683 for( SHAPE_LINE_CHAIN& contour : contours )
684 contour.GenerateBBoxCache();
685
686 for( size_t i = 0; i < contours.size(); i++ )
687 {
688 const SHAPE_LINE_CHAIN& outline = contours[i];
689
690 for( size_t j = 0; j < contours.size(); j++ )
691 {
692 if( i == j )
693 continue;
694
695 const SHAPE_LINE_CHAIN& candidate = contours[j];
696 const VECTOR2I& pt0 = candidate.CPoint( 0 );
697
698 if( outline.PointInside( pt0, 0, true ) )
699 {
700 parentToChildren[i].emplace( j );
701 childToParents[j].emplace( i );
702 }
703 }
704 }
705
706 std::set<int> topLevelParents;
707
708 for( size_t i = 0; i < contours.size(); i++ )
709 {
710 if( childToParents[i].size() == 0 )
711 {
712 topLevelParents.emplace( i );
713 }
714 }
715
717
718 std::function<void( int, int, std::vector<int> )> process;
719
720 process =
721 [&]( int myId, int parentOutlineId, const std::vector<int>& path )
722 {
723 std::set<int> relParents = childToParents[myId];
724
725 for( int pathId : path )
726 {
727 int erased = relParents.erase( pathId );
728 wxASSERT( erased > 0 );
729 }
730
731 wxASSERT( relParents.size() == 0 );
732
733 int myOutline = -1;
734
735 bool isOutline = path.size() % 2 == 0;
736
737 if( isOutline )
738 {
739 int outlineId = result.AddOutline( contours[myId] );
740 myOutline = outlineId;
741 }
742 else
743 {
744 wxASSERT( parentOutlineId != -1 );
745 result.AddHole( contours[myId], parentOutlineId );
746 }
747
748 auto it = parentToChildren.find( myId );
749 if( it != parentToChildren.end() )
750 {
751 std::vector<int> thisPath = path;
752 thisPath.emplace_back( myId );
753
754 std::set<int> thisPathSet;
755 thisPathSet.insert( thisPath.begin(), thisPath.end() );
756
757 for( int childId : it->second )
758 {
759 const std::set<int>& childPathSet = childToParents[childId];
760
761 if( thisPathSet != childPathSet )
762 continue; // Only interested in immediate children
763
764 process( childId, myOutline, thisPath );
765 }
766 }
767 };
768
769 for( int topParentId : topLevelParents )
770 {
771 std::vector<int> path;
772 process( topParentId, -1, std::move( path ) );
773 }
774
775 *this = std::move( result );
776}
777
778
779void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape )
780{
781 booleanOp( aType, *this, aOtherShape );
782}
783
784
791static bool splitAtBridges( const SHAPE_LINE_CHAIN& aChain, std::vector<SHAPE_LINE_CHAIN>& aRings )
792{
793 struct DIRECTED_EDGE
794 {
795 VECTOR2I from;
796 VECTOR2I to;
797
798 bool operator==( const DIRECTED_EDGE& aOther ) const
799 {
800 return from == aOther.from && to == aOther.to;
801 }
802 };
803
804 struct DIRECTED_EDGE_HASH
805 {
806 std::size_t operator()( const DIRECTED_EDGE& aEdge ) const
807 {
808 std::size_t seed = 0x51ed27a3;
809 hash_combine( seed, aEdge.from.x, aEdge.from.y, aEdge.to.x, aEdge.to.y );
810 return seed;
811 }
812 };
813
814 const std::vector<VECTOR2I>& pts = aChain.CPoints();
815 const int count = static_cast<int>( pts.size() );
816
817 // A bucket per directed edge so repeated bridges along one line all find a partner
818 std::unordered_map<DIRECTED_EDGE, std::vector<int>, DIRECTED_EDGE_HASH> unpaired;
819 std::vector<int> partner( count, -1 );
820 bool hasBridge = false;
821
822 unpaired.reserve( count );
823
824 for( int ii = 0; ii < count; ++ii )
825 {
826 const VECTOR2I& a = pts[ii];
827 const VECTOR2I& b = pts[( ii + 1 ) % count];
828
829 if( a == b )
830 continue;
831
832 auto twin = unpaired.find( { b, a } );
833
834 if( twin != unpaired.end() )
835 {
836 const int jj = twin->second.back();
837
838 twin->second.pop_back();
839
840 if( twin->second.empty() )
841 unpaired.erase( twin );
842
843 partner[ii] = jj;
844 partner[jj] = ii;
845 hasBridge = true;
846 }
847 else
848 {
849 unpaired[{ a, b }].push_back( ii );
850 }
851 }
852
853 if( !hasBridge )
854 return false;
855
856 // The edge that continues from the end of aEdge once bridge pairs are skipped
857 auto nextEdge =
858 [&]( int aEdge ) -> int
859 {
860 int next = ( aEdge + 1 ) % count;
861
862 for( int guard = 0; partner[next] >= 0; ++guard )
863 {
864 if( guard > count )
865 return -1;
866
867 next = ( partner[next] + 1 ) % count;
868 }
869
870 return next;
871 };
872
873 std::vector<bool> visited( count, false );
874
875 for( int start = 0; start < count; ++start )
876 {
877 if( visited[start] || partner[start] >= 0 )
878 continue;
879
880 SHAPE_LINE_CHAIN ring;
881 int edge = start;
882
883 do
884 {
885 if( edge < 0 || visited[edge] )
886 {
887 aRings.clear();
888 return false;
889 }
890
891 visited[edge] = true;
892 ring.Append( pts[edge], true );
893 edge = nextEdge( edge );
894 } while( edge != start );
895
896 if( ring.PointCount() >= 3 )
897 {
898 ring.SetClosed( true );
899 aRings.push_back( std::move( ring ) );
900 }
901 }
902
903 return true;
904}
905
906
907bool SHAPE_POLY_SET::appendBridgeFreePaths( const SHAPE_LINE_CHAIN& aChain, Clipper2Lib::Paths64& aPaths,
908 std::vector<CLIPPER_Z_VALUE>& aZValues,
909 std::vector<SHAPE_ARC>& aArcBuffer )
910{
911 // Small rings are cheap for Clipper and dominate the boolean call count
912 constexpr int kMinPoints = 1024;
913
914 if( aChain.PointCount() < kMinPoints || aChain.ArcCount() > 0 )
915 return false;
916
917 std::vector<SHAPE_LINE_CHAIN> rings;
918
919 if( !splitAtBridges( aChain, rings ) )
920 return false;
921
922 // convertToClipper2() orients an outline by reversing the whole ring, so every piece of the
923 // ring follows the same flip to keep its winding relative to the others
924 const bool flip = aChain.Area( false ) < 0;
925
926 for( const SHAPE_LINE_CHAIN& ring : rings )
927 aPaths.push_back( ring.convertToClipper2( ( ring.Area( false ) >= 0 ) != flip, aZValues, aArcBuffer ) );
928
929 return true;
930}
931
932
933void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
934 const SHAPE_POLY_SET& aOtherShape )
935{
936 if( ( aShape.OutlineCount() > 1 || aOtherShape.OutlineCount() > 0 )
937 && ( aShape.ArcCount() > 0 || aOtherShape.ArcCount() > 0 ) )
938 {
939 wxFAIL_MSG( wxT( "Boolean ops on curved polygons are not supported. You should call "
940 "ClearArcs() before carrying out the boolean operation." ) );
941 }
942
943 Clipper2Lib::Clipper64 c;
944
945 std::vector<CLIPPER_Z_VALUE> zValues;
946 std::vector<SHAPE_ARC> arcBuffer;
947 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
948
949 Clipper2Lib::Paths64 paths;
950 Clipper2Lib::Paths64 clips;
951
952 for( const POLYGON& poly : aShape.m_polys )
953 {
954 if( poly.size() == 1 && appendBridgeFreePaths( poly[0], paths, zValues, arcBuffer ) )
955 continue;
956
957 for( size_t i = 0; i < poly.size(); i++ )
958 {
959 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
960 }
961 }
962
963 for( const POLYGON& poly : aOtherShape.m_polys )
964 {
965 if( poly.size() == 1 && appendBridgeFreePaths( poly[0], clips, zValues, arcBuffer ) )
966 continue;
967
968 for( size_t i = 0; i < poly.size(); i++ )
969 {
970 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
971 }
972 }
973
974 c.AddSubject( paths );
975 c.AddClip( clips );
976
977 Clipper2Lib::PolyTree64 solution;
978
979 Clipper2Lib::ZCallback64 callback =
980 [&]( const Clipper2Lib::Point64 & e1bot, const Clipper2Lib::Point64 & e1top,
981 const Clipper2Lib::Point64 & e2bot, const Clipper2Lib::Point64 & e2top,
982 Clipper2Lib::Point64 & pt )
983 {
984 auto arcIndex =
985 [&]( const ssize_t& aZvalue, const ssize_t& aCompareVal = -1 ) -> ssize_t
986 {
987 ssize_t retval;
988
989 retval = zValues.at( aZvalue ).m_SecondArcIdx;
990
991 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
992 retval = zValues.at( aZvalue ).m_FirstArcIdx;
993
994 return retval;
995 };
996
997 auto arcSegment =
998 [&]( const ssize_t& aBottomZ, const ssize_t aTopZ ) -> ssize_t
999 {
1000 ssize_t retval = arcIndex( aBottomZ );
1001
1002 if( retval != -1 )
1003 {
1004 if( retval != arcIndex( aTopZ, retval ) )
1005 retval = -1; // Not an arc segment as the two indices do not match
1006 }
1007
1008 return retval;
1009 };
1010
1011 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
1012 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
1013
1014 CLIPPER_Z_VALUE newZval;
1015
1016 if( e1ArcSegmentIndex != -1 )
1017 {
1018 newZval.m_FirstArcIdx = e1ArcSegmentIndex;
1019 newZval.m_SecondArcIdx = e2ArcSegmentIndex;
1020 }
1021 else
1022 {
1023 newZval.m_FirstArcIdx = e2ArcSegmentIndex;
1024 newZval.m_SecondArcIdx = -1;
1025 }
1026
1027 size_t z_value_ptr = zValues.size();
1028 zValues.push_back( newZval );
1029
1030 // Only worry about arc segments for later processing
1031 if( newZval.m_FirstArcIdx != -1 )
1032 newIntersectPoints.insert( { VECTOR2I( pt.x, pt.y ), newZval } );
1033
1034 pt.z = z_value_ptr;
1035 //@todo amend X,Y values to true intersection between arcs or arc and segment
1036 };
1037
1038 c.SetZCallback( std::move( callback ) ); // register callback
1039
1040 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
1041
1042 importTree( solution, zValues, arcBuffer );
1043 solution.Clear(); // Free used memory (not done in dtor)
1044}
1045
1046
1048{
1049 booleanOp( Clipper2Lib::ClipType::Union, b );
1050}
1051
1052
1054{
1055 booleanOp( Clipper2Lib::ClipType::Difference, b );
1056}
1057
1058
1060{
1061 booleanOp( Clipper2Lib::ClipType::Intersection, b );
1062}
1063
1064
1066{
1067 booleanOp( Clipper2Lib::ClipType::Xor, b );
1068}
1069
1070
1072{
1073 booleanOp( Clipper2Lib::ClipType::Union, a, b );
1074}
1075
1076
1078{
1079 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
1080}
1081
1082
1084{
1085 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
1086}
1087
1088
1090{
1091 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
1092}
1093
1094
1096 int aMaxError )
1097{
1098 Unfracture();
1099 Inflate( aFactor, aCornerStrategy, aMaxError );
1100 Fracture();
1101}
1102
1103
1104void SHAPE_POLY_SET::inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy,
1105 bool aSimplify )
1106{
1107 using namespace Clipper2Lib;
1108 // A thread-local table to avoid repetitive calculations of the coefficient
1109 // 1.0 - cos( M_PI / aCircleSegCount )
1110 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
1111 #define SEG_CNT_MAX 64
1112 static thread_local double arc_tolerance_factor[SEG_CNT_MAX + 1];
1113
1114 ClipperOffset c;
1115
1116 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
1117 // and are not what you'd think they are.
1118 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
1119 JoinType joinType = JoinType::Round; // The way corners are offsetted
1120 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
1121
1122 switch( aCornerStrategy )
1123 {
1125 joinType = JoinType::Miter;
1126 miterLimit = 10; // Allows large spikes
1127 break;
1128
1129 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
1130 joinType = JoinType::Miter;
1131 break;
1132
1133 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS: // Acute angles are rounded
1134 joinType = JoinType::Miter;
1135 break;
1136
1137 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS: // All angles are chamfered.
1138 joinType = JoinType::Square;
1139 break;
1140
1141 case CORNER_STRATEGY::ROUND_ALL_CORNERS: // All angles are rounded.
1142 joinType = JoinType::Round;
1143 break;
1144 }
1145
1146 std::vector<CLIPPER_Z_VALUE> zValues;
1147 std::vector<SHAPE_ARC> arcBuffer;
1148
1149 for( const POLYGON& poly : m_polys )
1150 {
1151 Paths64 paths;
1152
1153 for( size_t i = 0; i < poly.size(); i++ )
1154 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1155
1156 c.AddPaths( paths, joinType, EndType::Polygon );
1157 }
1158
1159 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
1160 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
1161 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
1162
1163 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
1164 aCircleSegCount = 6;
1165
1166 double coeff;
1167
1168 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1169 {
1170 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1171
1172 if( aCircleSegCount <= SEG_CNT_MAX )
1173 arc_tolerance_factor[aCircleSegCount] = coeff;
1174 }
1175 else
1176 {
1177 coeff = arc_tolerance_factor[aCircleSegCount];
1178 }
1179
1180 c.ArcTolerance( std::abs( aAmount ) * coeff );
1181 c.MiterLimit( miterLimit );
1182
1183 PolyTree64 tree;
1184
1185 if( aSimplify )
1186 {
1187 Paths64 paths;
1188 c.Execute( aAmount, paths );
1189
1190 Clipper2Lib::SimplifyPaths( paths, std::abs( aAmount ) * coeff, true );
1191
1192 Clipper64 c2;
1193 c2.PreserveCollinear( false );
1194 c2.ReverseSolution( false );
1195 c2.AddSubject( paths );
1196 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1197 }
1198 else
1199 {
1200 c.Execute( aAmount, tree );
1201 }
1202
1203 importTree( tree, zValues, arcBuffer );
1204 tree.Clear();
1205}
1206
1207
1208void SHAPE_POLY_SET::inflateLine2( const SHAPE_LINE_CHAIN& aLine, int aAmount, int aCircleSegCount,
1209 CORNER_STRATEGY aCornerStrategy, bool aSimplify )
1210{
1211 using namespace Clipper2Lib;
1212 // A thread-local table to avoid repetitive calculations of the coefficient
1213 // 1.0 - cos( M_PI / aCircleSegCount )
1214 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
1215 #define SEG_CNT_MAX 64
1216 static thread_local double arc_tolerance_factor[SEG_CNT_MAX + 1];
1217
1218 ClipperOffset c;
1219
1220 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
1221 // and are not what you'd think they are.
1222 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
1223 JoinType joinType = JoinType::Round; // The way corners are offsetted
1224 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
1225
1226 switch( aCornerStrategy )
1227 {
1229 joinType = JoinType::Miter;
1230 miterLimit = 10; // Allows large spikes
1231 break;
1232
1233 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
1234 joinType = JoinType::Miter;
1235 break;
1236
1237 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS: // Acute angles are rounded
1238 joinType = JoinType::Miter;
1239 break;
1240
1241 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS: // All angles are chamfered.
1242 joinType = JoinType::Square;
1243 break;
1244
1245 case CORNER_STRATEGY::ROUND_ALL_CORNERS: // All angles are rounded.
1246 joinType = JoinType::Round;
1247 break;
1248 }
1249
1250 std::vector<CLIPPER_Z_VALUE> zValues;
1251 std::vector<SHAPE_ARC> arcBuffer;
1252
1253 Path64 path = aLine.convertToClipper2( true, zValues, arcBuffer );
1254 c.AddPath( path, joinType, EndType::Butt );
1255
1256 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
1257 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
1258 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
1259
1260 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
1261 aCircleSegCount = 6;
1262
1263 double coeff;
1264
1265 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1266 {
1267 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1268
1269 if( aCircleSegCount <= SEG_CNT_MAX )
1270 arc_tolerance_factor[aCircleSegCount] = coeff;
1271 }
1272 else
1273 {
1274 coeff = arc_tolerance_factor[aCircleSegCount];
1275 }
1276
1277 c.ArcTolerance( std::abs( aAmount ) * coeff );
1278 c.MiterLimit( miterLimit );
1279
1280 PolyTree64 tree;
1281
1282 if( aSimplify )
1283 {
1284 Paths64 paths2;
1285 c.Execute( aAmount, paths2 );
1286
1287 Clipper2Lib::SimplifyPaths( paths2, std::abs( aAmount ) * coeff, false );
1288
1289 Clipper64 c2;
1290 c2.PreserveCollinear( false );
1291 c2.ReverseSolution( false );
1292 c2.AddSubject( paths2 );
1293 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1294 }
1295 else
1296 {
1297 c.Execute( aAmount, tree );
1298 }
1299
1300 importTree( tree, zValues, arcBuffer );
1301 tree.Clear();
1302}
1303
1304
1305void SHAPE_POLY_SET::Inflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
1306 bool aSimplify )
1307{
1308 int segCount = GetArcToSegmentCount( std::abs( aAmount ), aMaxError, FULL_CIRCLE );
1309
1310 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1311}
1312
1313
1315 CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify )
1316{
1317 int segCount = GetArcToSegmentCount( std::abs( aAmount ), aMaxError, FULL_CIRCLE );
1318
1319 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1320}
1321
1322
1323void SHAPE_POLY_SET::importPolyPath( const std::unique_ptr<Clipper2Lib::PolyPath64>& aPolyPath,
1324 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1325 const std::vector<SHAPE_ARC>& aArcBuffer )
1326{
1327 if( !aPolyPath->IsHole() )
1328 {
1329 POLYGON paths;
1330 paths.reserve( aPolyPath->Count() + 1 );
1331 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1332
1333 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1334 {
1335 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1336
1337 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1338 importPolyPath( grandchild, aZValueBuffer, aArcBuffer );
1339 }
1340
1341 m_polys.emplace_back( std::move( paths ) );
1342 }
1343}
1344
1345
1346void SHAPE_POLY_SET::importTree( Clipper2Lib::PolyTree64& tree,
1347 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1348 const std::vector<SHAPE_ARC>& aArcBuffer )
1349{
1350 m_polys.clear();
1351
1352 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1353 importPolyPath( n, aZValueBuffer, aArcBuffer );
1354}
1355
1356
1357void SHAPE_POLY_SET::importPaths( Clipper2Lib::Paths64& aPath,
1358 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1359 const std::vector<SHAPE_ARC>& aArcBuffer )
1360{
1361 m_polys.clear();
1362 POLYGON path;
1363
1364 for( const Clipper2Lib::Path64& n : aPath )
1365 {
1366 if( Clipper2Lib::Area( n ) > 0 )
1367 {
1368 if( !path.empty() )
1369 m_polys.emplace_back( path );
1370
1371 path.clear();
1372 }
1373 else
1374 {
1375 wxCHECK2_MSG( !path.empty(), continue, wxT( "Cannot add a hole before an outline" ) );
1376 }
1377
1378 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1379 }
1380
1381 if( !path.empty() )
1382 m_polys.emplace_back( std::move( path ) );
1383}
1384
1385
1387{
1388 using Index = int;
1389
1390 FractureEdge() = default;
1391
1392 FractureEdge( const VECTOR2I& p1, const VECTOR2I& p2, Index next ) :
1393 m_p1( p1 ),
1394 m_p2( p2 ),
1395 m_next( next )
1396 {
1397 }
1398
1399 bool matches( int y ) const
1400 {
1401 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
1402 }
1403
1407};
1408
1409
1410typedef std::vector<FractureEdge> FractureEdgeSet;
1411
1412
1414{
1415public:
1417
1418 struct NODE
1419 {
1420 uint32_t edge;
1421 uint32_t next;
1422 };
1423
1424 template <typename Originals>
1425 FRACTURE_EDGE_INDEX( FractureEdgeSet& aEdges, Originals&& aOriginals, int aMinY, int aMaxY,
1426 uint32_t aStripeCount, size_t aHoleCount ) :
1427 m_edges( aEdges ),
1428 m_minY( aMinY ),
1429 m_maxY( aMaxY ),
1430 m_stripeCount( aStripeCount ),
1431 m_maxNodes( ( KIGEOM::FRACTURE_INDEX::MAX_BUCKET_SPAN + 2 ) * aHoleCount ),
1432 m_budget( KIGEOM::FRACTURE_INDEX::CapacityBudget( aEdges.size(), sizeof( FractureEdge ) ) )
1433 {
1434 std::vector<uint32_t> counts( m_stripeCount );
1435 size_t bucketIds = 0;
1436 size_t longIds = 0;
1437
1438 aOriginals(
1439 [&]( uint32_t, uint32_t aFirst, uint32_t aLast )
1440 {
1441 if( aLast - aFirst + 1 > KIGEOM::FRACTURE_INDEX::MAX_BUCKET_SPAN )
1442 {
1443 ++longIds;
1444 }
1445 else
1446 {
1447 bucketIds += aLast - aFirst + 1;
1448
1449 for( uint32_t stripe = aFirst; stripe <= aLast; ++stripe )
1450 ++counts[stripe];
1451 }
1452 } );
1453
1454 if( !KIGEOM::FRACTURE_INDEX::CapacityFits( bucketIds, longIds, m_stripeCount, aHoleCount, sizeof( NODE ),
1455 m_budget ) )
1456 {
1457 return;
1458 }
1459
1460 m_offsets.resize( m_stripeCount + 1 );
1461
1462 for( uint32_t stripe = 0; stripe < m_stripeCount; ++stripe )
1463 m_offsets[stripe + 1] = m_offsets[stripe] + counts[stripe];
1464
1465 m_bucketIds.resize( bucketIds );
1466 m_longIds.reserve( longIds );
1467
1468 std::copy( m_offsets.begin(), m_offsets.end() - 1, counts.begin() );
1469
1470 aOriginals(
1471 [&]( uint32_t aEdge, uint32_t aFirst, uint32_t aLast )
1472 {
1473 if( aLast - aFirst + 1 > KIGEOM::FRACTURE_INDEX::MAX_BUCKET_SPAN )
1474 {
1475 m_longIds.push_back( aEdge );
1476 }
1477 else
1478 {
1479 for( uint32_t stripe = aFirst; stripe <= aLast; ++stripe )
1480 m_bucketIds[counts[stripe]++] = aEdge;
1481 }
1482 } );
1483
1484 m_heads.assign( m_stripeCount + 1, INVALID );
1485 m_nodes.reserve( m_maxNodes );
1486
1487 // The ascending order the Query breaks rely on, asserted once rather than per visit
1488#ifndef NDEBUG
1489 for( uint32_t stripe = 0; stripe < m_stripeCount; ++stripe )
1490 {
1491 for( uint32_t pos = m_offsets[stripe] + 1; pos < m_offsets[stripe + 1]; ++pos )
1492 assert( m_bucketIds[pos] >= m_bucketIds[pos - 1] );
1493 }
1494
1495 for( size_t pos = 1; pos < m_longIds.size(); ++pos )
1496 assert( m_longIds[pos] >= m_longIds[pos - 1] );
1497#endif
1498
1499 // The estimate prevents an over-budget allocation; this check catches allocator over-capacity.
1500 size_t allocated_bytes = 0;
1501
1503 m_offsets.capacity(), counts.capacity(), m_heads.capacity(),
1504 m_nodes.capacity(), sizeof( NODE ), m_budget,
1505 &allocated_bytes ) )
1506 {
1507 return;
1508 }
1509
1510 m_valid = true;
1511 logAccepted( aEdges.size(), aHoleCount, m_stripeCount, allocated_bytes );
1512 }
1513
1514 bool IsValid() const { return m_valid; }
1515
1516 template <typename Visitor>
1517 void Query( int aY, Index aProvokingIndex, Visitor&& aVisitor ) const
1518 {
1519 const uint32_t stripe = map( aY );
1520
1521 // Buckets and the long list are ascending, so the first out-of-range id ends the scan
1522 for( uint32_t pos = m_offsets[stripe]; pos < m_offsets[stripe + 1]; ++pos )
1523 {
1524 const uint32_t edge = m_bucketIds[pos];
1525
1526 if( edge >= static_cast<uint32_t>( aProvokingIndex ) )
1527 break;
1528
1529 aVisitor( static_cast<Index>( edge ) );
1530 }
1531
1532 for( uint32_t edge : m_longIds )
1533 {
1534 if( edge >= static_cast<uint32_t>( aProvokingIndex ) )
1535 break;
1536
1537 aVisitor( static_cast<Index>( edge ) );
1538 }
1539
1540 visitOverflow( m_heads[stripe], aProvokingIndex, aVisitor );
1541 visitOverflow( m_heads[m_stripeCount], aProvokingIndex, aVisitor );
1542 }
1543
1544 void InsertBridges( Index aFirst )
1545 {
1546 for( Index edge = aFirst; edge < aFirst + 3; ++edge )
1547 {
1548 const auto [first, last] = span( m_edges[edge] );
1549
1550 if( last - first + 1 > KIGEOM::FRACTURE_INDEX::MAX_BUCKET_SPAN )
1551 {
1552 insert( static_cast<uint32_t>( edge ), m_stripeCount );
1553 }
1554 else
1555 {
1556 for( uint32_t stripe = first; stripe <= last; ++stripe )
1557 insert( static_cast<uint32_t>( edge ), stripe );
1558 }
1559 }
1560 }
1561
1562private:
1563 static constexpr uint32_t INVALID = std::numeric_limits<uint32_t>::max();
1564
1565 uint32_t map( int aY ) const { return KIGEOM::FRACTURE_INDEX::MapYToStripe( aY, m_minY, m_maxY, m_stripeCount ); }
1566
1567 std::pair<uint32_t, uint32_t> span( const FractureEdge& aEdge ) const
1568 {
1570 }
1571
1572 template <typename Visitor>
1573 void visitOverflow( uint32_t aNode, Index aProvokingIndex, Visitor&& aVisitor ) const
1574 {
1575 // Bridges are only ever inserted for already processed holes, so the assert should hold,
1576 // but the filter keeps the release build honest if that ordering ever changes
1577 while( aNode != INVALID )
1578 {
1579 const NODE& node = m_nodes[aNode];
1580 assert( node.edge < static_cast<uint32_t>( aProvokingIndex ) );
1581
1582 if( node.edge < static_cast<uint32_t>( aProvokingIndex ) )
1583 aVisitor( static_cast<Index>( node.edge ) );
1584
1585 aNode = node.next;
1586 }
1587 }
1588
1589 void insert( uint32_t aEdge, uint32_t aHead )
1590 {
1591 assert( m_nodes.size() < m_maxNodes );
1592 m_nodes.push_back( { aEdge, m_heads[aHead] } );
1593 m_heads[aHead] = static_cast<uint32_t>( m_nodes.size() - 1 );
1594 }
1595
1596 static void logAccepted( size_t aEdges, size_t aHoles, uint32_t aStripes, size_t aBytes )
1597 {
1598 wxLogTrace( wxS( "KICAD_FRACTURE_INDEX" ),
1599 wxS( "Using fracture edge index: edges=%zu, holes=%zu, stripes=%u, allocated=%zu bytes" ),
1600 aEdges, aHoles, aStripes, aBytes );
1601 }
1602
1608 size_t m_budget;
1609 bool m_valid = false;
1610 std::vector<uint32_t> m_offsets;
1611 std::vector<uint32_t> m_bucketIds;
1612 std::vector<uint32_t> m_longIds;
1613 std::vector<uint32_t> m_heads;
1614 std::vector<NODE> m_nodes;
1615};
1616
1617
1618// Where a horizontal ray at aY crosses aEdge, valid only when aEdge.matches( aY )
1619static inline int fractureIntersectX( const FractureEdge& aEdge, int aY )
1620{
1621 if( aEdge.m_p1.y == aEdge.m_p2.y )
1622 return std::max( aEdge.m_p1.x, aEdge.m_p2.x );
1623
1624 return aEdge.m_p1.x
1625 + rescale( aEdge.m_p2.x - aEdge.m_p1.x, aY - aEdge.m_p1.y, aEdge.m_p2.y - aEdge.m_p1.y );
1626}
1627
1628
1630 FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex,
1631 FRACTURE_EDGE_INDEX* aIndex )
1632{
1633 FractureEdge& edge = edges[edgeIndex];
1634 int x = edge.m_p1.x;
1635 int y = edge.m_p1.y;
1636 int min_dist = std::numeric_limits<int>::max();
1637 int x_nearest = 0;
1638
1639 FractureEdge* e_nearest = nullptr;
1640
1641 // Since this function is run for all holes left to right, no need to
1642 // check for any edge beyond the provoking one because they will always be
1643 // further to the right, and unconnected to the outline anyway.
1644 if( aIndex )
1645 {
1646 FractureEdge::Index nearest_index = -1;
1647
1648 auto consider = [&]( FractureEdge::Index aCandidateIndex )
1649 {
1650 FractureEdge& candidate = edges[aCandidateIndex];
1651
1652 if( !candidate.matches( y ) )
1653 return;
1654
1655 int x_intersect = fractureIntersectX( candidate, y );
1656 int dist = x - x_intersect;
1657
1658 if( dist >= 0
1659 && ( dist < min_dist
1660 || ( nearest_index >= 0 && dist == min_dist && aCandidateIndex < nearest_index ) ) )
1661 {
1662 min_dist = dist;
1663 x_nearest = x_intersect;
1664 nearest_index = aCandidateIndex;
1665 }
1666 };
1667
1668 aIndex->Query( y, provokingIndex, consider );
1669
1670 if( nearest_index >= 0 )
1671 e_nearest = &edges[nearest_index];
1672 }
1673 else
1674 {
1675 for( FractureEdge::Index i = 0; i < provokingIndex; ++i )
1676 {
1677 FractureEdge& candidate = edges[i];
1678
1679 if( !candidate.matches( y ) )
1680 continue;
1681
1682 int x_intersect = fractureIntersectX( candidate, y );
1683 int dist = x - x_intersect;
1684
1685 if( dist >= 0 && dist < min_dist )
1686 {
1687 min_dist = dist;
1688 x_nearest = x_intersect;
1689 e_nearest = &candidate;
1690 }
1691 }
1692 }
1693
1694 if( e_nearest )
1695 {
1696 const FractureEdge::Index outline2hole_index = bridgeIndex;
1697 const FractureEdge::Index hole2outline_index = bridgeIndex + 1;
1698 const FractureEdge::Index split_index = bridgeIndex + 2;
1699 // Make an edge between the split outline edge and the hole...
1700 edges[outline2hole_index] = FractureEdge( VECTOR2I( x_nearest, y ), edge.m_p1, edgeIndex );
1701 // ...between the hole and the edge...
1702 edges[hole2outline_index] =
1703 FractureEdge( edge.m_p1, VECTOR2I( x_nearest, y ), split_index );
1704 // ...and between the split outline edge and the rest.
1705 edges[split_index] =
1706 FractureEdge( VECTOR2I( x_nearest, y ), e_nearest->m_p2, e_nearest->m_next );
1707
1708 // Perform the actual outline edge split
1709 // Existing stripe membership remains conservative because the selected y is inside the
1710 // edge's current interval, while newly initialized bridge edges are inserted below.
1711 e_nearest->m_p2 = VECTOR2I( x_nearest, y );
1712 e_nearest->m_next = outline2hole_index;
1713
1714 FractureEdge* last = &edge;
1715 for( ; last->m_next != edgeIndex; last = &edges[last->m_next] )
1716 ;
1717 last->m_next = hole2outline_index;
1718
1719 if( aIndex )
1720 aIndex->InsertBridges( bridgeIndex );
1721 }
1722
1723 return e_nearest;
1724}
1725
1726
1728{
1729 FractureEdgeSet edges;
1730 bool outline = true;
1731
1732 if( paths.size() == 1 )
1733 return;
1734
1735 size_t total_point_count = 0;
1736
1737 for( const SHAPE_LINE_CHAIN& path : paths )
1738 {
1739 total_point_count += path.PointCount();
1740 }
1741
1742 if( total_point_count > (size_t) std::numeric_limits<FractureEdge::Index>::max() )
1743 {
1744 wxLogWarning( wxT( "Polygon has more points than int limit" ) );
1745 return;
1746 }
1747
1748 // Reserve space in the edge set so pointers don't get invalidated during
1749 // the whole fracture process; one for each original edge, plus 3 per
1750 // path to join it to the outline.
1751 edges.reserve( total_point_count + paths.size() * 3 );
1752
1753 // Sort the paths by their lowest X bound before processing them.
1754 // This ensures the processing order for processEdge() is correct.
1755 struct PathInfo
1756 {
1757 int path_or_provoking_index;
1758 FractureEdge::Index leftmost;
1759 int x;
1760 int y_or_bridge;
1761 };
1762 std::vector<PathInfo> sorted_paths;
1763 const int paths_count = static_cast<int>( paths.size() );
1764 sorted_paths.reserve( paths_count );
1765
1766 for( int path_index = 0; path_index < paths_count; path_index++ )
1767 {
1768 const SHAPE_LINE_CHAIN& path = paths[path_index];
1769 const std::vector<VECTOR2I>& points = path.CPoints();
1770 const int point_count = static_cast<int>( points.size() );
1771 int x_min = std::numeric_limits<int>::max();
1772 int y_min = std::numeric_limits<int>::max();
1773 int leftmost = -1;
1774
1775 for( int point_index = 0; point_index < point_count; point_index++ )
1776 {
1777 const VECTOR2I& point = points[point_index];
1778 if( point.x < x_min )
1779 {
1780 x_min = point.x;
1781 leftmost = point_index;
1782 }
1783 if( point.y < y_min )
1784 y_min = point.y;
1785 }
1786
1787 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1788 }
1789
1790 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1791 []( const PathInfo& a, const PathInfo& b )
1792 {
1793 if( a.x == b.x )
1794 return a.y_or_bridge < b.y_or_bridge;
1795 return a.x < b.x;
1796 } );
1797
1798 FractureEdge::Index edge_index = 0;
1799
1800 for( PathInfo& path_info : sorted_paths )
1801 {
1802 const SHAPE_LINE_CHAIN& path = paths[path_info.path_or_provoking_index];
1803 const std::vector<VECTOR2I>& points = path.CPoints();
1804 const size_t point_count = points.size();
1805
1806 // Index of the provoking (first) edge for this path
1807 const FractureEdge::Index provoking_edge = edge_index;
1808
1809 for( size_t i = 0; i < point_count - 1; i++ )
1810 {
1811 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1812 edge_index++;
1813 }
1814
1815 // Create last edge looping back to the provoking one.
1816 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1817 edge_index++;
1818
1819 if( !outline )
1820 {
1821 // Repurpose the path sorting data structure to schedule the leftmost edge
1822 // for merging to the outline, which will in turn merge the rest of the path.
1823 path_info.path_or_provoking_index = provoking_edge;
1824 path_info.y_or_bridge = edge_index;
1825
1826 // Reserve 3 additional edges to bridge with the outline.
1827 edge_index += 3;
1828 edges.resize( edge_index );
1829 }
1830
1831 outline = false; // first path is always the outline
1832 }
1833
1834 assert( edges.size() == total_point_count + 3 * ( paths.size() - 1 ) );
1835#ifndef NDEBUG
1836 FractureEdge::Index expected_edge = paths[0].PointCount();
1837
1838 for( auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1839 {
1840 assert( it->path_or_provoking_index == expected_edge );
1841 expected_edge = it->y_or_bridge + 3;
1842 }
1843
1844 assert( expected_edge == static_cast<FractureEdge::Index>( edges.size() ) );
1845#endif
1846
1847 uint64_t estimated_visits = 0;
1848
1849 for( auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1850 estimated_visits += static_cast<uint64_t>( it->path_or_provoking_index );
1851
1852 std::unique_ptr<FRACTURE_EDGE_INDEX> index;
1853
1854 if( ENABLEFRACTUREEDGEINDEX && KIGEOM::FRACTURE_INDEX::ShouldIndex( estimated_visits, paths.size() - 1 ) )
1855 {
1856 int min_y = std::numeric_limits<int>::max();
1857 int max_y = std::numeric_limits<int>::min();
1858 const uint32_t stripe_count = KIGEOM::FRACTURE_INDEX::StripeCountFor( edges.size() );
1859
1860 for( const SHAPE_LINE_CHAIN& path : paths )
1861 {
1862 for( const VECTOR2I& point : path.CPoints() )
1863 {
1864 min_y = std::min( min_y, point.y );
1865 max_y = std::max( max_y, point.y );
1866 }
1867 }
1868
1869 auto visitOriginals = [&]( auto&& aVisitor )
1870 {
1871 auto visitRange = [&]( FractureEdge::Index aBegin, FractureEdge::Index aEnd )
1872 {
1873 for( FractureEdge::Index edge = aBegin; edge < aEnd; ++edge )
1874 {
1875 const FractureEdge& original = edges[edge];
1876 const auto [first, last] = KIGEOM::FRACTURE_INDEX::StripeSpan( original.m_p1.y, original.m_p2.y,
1877 min_y, max_y, stripe_count );
1878 aVisitor( static_cast<uint32_t>( edge ), first, last );
1879 }
1880 };
1881
1882 visitRange( 0, paths[0].PointCount() );
1883
1884 for( auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1885 visitRange( it->path_or_provoking_index, it->y_or_bridge );
1886 };
1887
1888 index = std::make_unique<FRACTURE_EDGE_INDEX>( edges, visitOriginals, min_y, max_y, stripe_count,
1889 paths.size() - 1 );
1890
1891 if( !index->IsValid() )
1892 index.reset();
1893 }
1894
1895 for( auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1896 {
1897 auto edge = processHole( edges, it->path_or_provoking_index, it->path_or_provoking_index + it->leftmost,
1898 it->y_or_bridge, index.get() );
1899
1900 // If we can't handle the hole, the zone is broken (maybe)
1901 if( !edge )
1902 {
1903 wxLogWarning( wxT( "Broken polygon, dropping path" ) );
1904
1905 return;
1906 }
1907 }
1908
1909 paths.resize( 1 );
1910 SHAPE_LINE_CHAIN& newPath = paths[0];
1911
1912 newPath.Clear();
1913 newPath.SetClosed( true );
1914
1915 // Root edge is always at index 0
1916 FractureEdge* e = &edges[0];
1917
1918 for( ; e->m_next != 0; e = &edges[e->m_next] )
1919 newPath.Append( e->m_p1 );
1920
1921 newPath.Append( e->m_p1 );
1922}
1923
1924
1926{
1927 FractureEdgeSlow( int y = 0 ) : m_connected( false ), m_next( nullptr ) { m_p1.x = m_p2.y = y; }
1928
1929 FractureEdgeSlow( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
1930 m_connected( connected ), m_p1( p1 ), m_p2( p2 ), m_next( nullptr )
1931 {
1932 }
1933
1934 bool matches( int y ) const
1935 {
1936 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
1937 }
1938
1943};
1944
1945
1946typedef std::vector<FractureEdgeSlow*> FractureEdgeSetSlow;
1947
1948
1950{
1951 int x = edge->m_p1.x;
1952 int y = edge->m_p1.y;
1953 int min_dist = std::numeric_limits<int>::max();
1954 int x_nearest = 0;
1955
1956 FractureEdgeSlow* e_nearest = nullptr;
1957
1958 for( FractureEdgeSlow* e : edges )
1959 {
1960 if( !e->matches( y ) )
1961 continue;
1962
1963 int x_intersect;
1964
1965 if( e->m_p1.y == e->m_p2.y ) // horizontal edge
1966 {
1967 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1968 }
1969 else
1970 {
1971 x_intersect = e->m_p1.x
1972 + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1973 }
1974
1975 int dist = ( x - x_intersect );
1976
1977 if( dist >= 0 && dist < min_dist && e->m_connected )
1978 {
1979 min_dist = dist;
1980 x_nearest = x_intersect;
1981 e_nearest = e;
1982 }
1983 }
1984
1985 if( e_nearest && e_nearest->m_connected )
1986 {
1987 int count = 0;
1988
1989 FractureEdgeSlow* lead1 =
1990 new FractureEdgeSlow( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
1991 FractureEdgeSlow* lead2 =
1992 new FractureEdgeSlow( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
1993 FractureEdgeSlow* split_2 =
1994 new FractureEdgeSlow( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
1995
1996 edges.push_back( split_2 );
1997 edges.push_back( lead1 );
1998 edges.push_back( lead2 );
1999
2000 FractureEdgeSlow* link = e_nearest->m_next;
2001
2002 e_nearest->m_p2 = VECTOR2I( x_nearest, y );
2003 e_nearest->m_next = lead1;
2004 lead1->m_next = edge;
2005
2006 FractureEdgeSlow* last;
2007
2008 for( last = edge; last->m_next != edge; last = last->m_next )
2009 {
2010 last->m_connected = true;
2011 count++;
2012 }
2013
2014 last->m_connected = true;
2015 last->m_next = lead2;
2016 lead2->m_next = split_2;
2017 split_2->m_next = link;
2018
2019 return count + 1;
2020 }
2021
2022 return 0;
2023}
2024
2025
2027{
2028 FractureEdgeSetSlow edges;
2029 FractureEdgeSetSlow border_edges;
2030 FractureEdgeSlow* root = nullptr;
2031
2032 bool first = true;
2033
2034 if( paths.size() == 1 )
2035 return;
2036
2037 int num_unconnected = 0;
2038
2039 for( const SHAPE_LINE_CHAIN& path : paths )
2040 {
2041 const std::vector<VECTOR2I>& points = path.CPoints();
2042 int pointCount = points.size();
2043
2044 FractureEdgeSlow *prev = nullptr, *first_edge = nullptr;
2045
2046 int x_min = std::numeric_limits<int>::max();
2047
2048 for( int i = 0; i < pointCount; i++ )
2049 {
2050 if( points[i].x < x_min )
2051 x_min = points[i].x;
2052
2053 // Do not use path.CPoint() here; open-coding it using the local variables "points"
2054 // and "pointCount" gives a non-trivial performance boost to zone fill times.
2055 FractureEdgeSlow* fe = new FractureEdgeSlow( first, points[i],
2056 points[i + 1 == pointCount ? 0 : i + 1] );
2057
2058 if( !root )
2059 root = fe;
2060
2061 if( !first_edge )
2062 first_edge = fe;
2063
2064 if( prev )
2065 prev->m_next = fe;
2066
2067 if( i == pointCount - 1 )
2068 fe->m_next = first_edge;
2069
2070 prev = fe;
2071 edges.push_back( fe );
2072
2073 if( !first )
2074 {
2075 if( fe->m_p1.x == x_min )
2076 border_edges.push_back( fe );
2077 }
2078
2079 if( !fe->m_connected )
2080 num_unconnected++;
2081 }
2082
2083 first = false; // first path is always the outline
2084 }
2085
2086 // keep connecting holes to the main outline, until there's no holes left...
2087 while( num_unconnected > 0 )
2088 {
2089 int x_min = std::numeric_limits<int>::max();
2090 auto it = border_edges.begin();
2091
2092 FractureEdgeSlow* smallestX = nullptr;
2093
2094 // find the left-most hole edge and merge with the outline
2095 for( ; it != border_edges.end(); ++it )
2096 {
2097 FractureEdgeSlow* border_edge = *it;
2098 int xt = border_edge->m_p1.x;
2099
2100 if( ( xt <= x_min ) && !border_edge->m_connected )
2101 {
2102 x_min = xt;
2103 smallestX = border_edge;
2104 }
2105 }
2106
2107 int num_processed = processEdge( edges, smallestX );
2108
2109 // If we can't handle the edge, the zone is broken (maybe)
2110 if( !num_processed )
2111 {
2112 wxLogWarning( wxT( "Broken polygon, dropping path" ) );
2113
2114 for( FractureEdgeSlow* edge : edges )
2115 delete edge;
2116
2117 return;
2118 }
2119
2120 num_unconnected -= num_processed;
2121 }
2122
2123 paths.clear();
2124 SHAPE_LINE_CHAIN newPath;
2125
2126 newPath.SetClosed( true );
2127
2129
2130 for( e = root; e->m_next != root; e = e->m_next )
2131 newPath.Append( e->m_p1 );
2132
2133 newPath.Append( e->m_p1 );
2134
2135 for( FractureEdgeSlow* edge : edges )
2136 delete edge;
2137
2138 paths.push_back( std::move( newPath ) );
2139}
2140
2141
2143{
2145 return fractureSingleCacheFriendly( paths );
2146 fractureSingleSlow( paths );
2147}
2148
2149
2150void SHAPE_POLY_SET::Fracture( bool aSimplify )
2151{
2152 if( aSimplify )
2153 Simplify(); // remove overlapping holes/degeneracy
2154
2155 for( POLYGON& paths : m_polys )
2156 fractureSingle( paths );
2157}
2158
2159
2161{
2162 assert( aPoly.size() == 1 );
2163
2164 SHAPE_LINE_CHAIN lc = aPoly[0];
2165 lc.Simplify();
2166
2167 // Rings are rebuilt from bare vertices, so arcs never survive unfracturing
2168 lc = SHAPE_LINE_CHAIN( lc.CPoints(), true );
2169
2170 std::vector<SHAPE_LINE_CHAIN> rings;
2171
2172 if( !splitAtBridges( lc, rings ) || rings.empty() )
2173 {
2174 aPoly[0] = std::move( lc );
2175 return;
2176 }
2177
2178 auto outline = std::max_element( rings.begin(), rings.end(),
2179 []( const SHAPE_LINE_CHAIN& aA, const SHAPE_LINE_CHAIN& aB )
2180 {
2181 return std::fabs( aA.Area() ) < std::fabs( aB.Area() );
2182 } );
2183
2184 std::iter_swap( rings.begin(), outline );
2185 aPoly = std::move( rings );
2186}
2187
2188
2190{
2191 // Iterate through all the polygons on the set
2192 for( const POLYGON& paths : m_polys )
2193 {
2194 // If any of them has more than one contour, it is a hole.
2195 if( paths.size() > 1 )
2196 return true;
2197 }
2198
2199 // Return false if and only if every polygon has just one outline, without holes.
2200 return false;
2201}
2202
2203
2205{
2206 for( POLYGON& path : m_polys )
2208
2209 Simplify(); // remove overlapping holes/degeneracy
2210}
2211
2212
2213bool SHAPE_POLY_SET::isExteriorWaist( const SEG& aSegA, const SEG& aSegB ) const
2214{
2215 const VECTOR2I da = aSegA.B - aSegA.A;
2216
2217 int axis = std::abs( da.x ) >= std::abs( da.y ) ? 0 : 1;
2218
2219 std::array<VECTOR2I,4> pts = { aSegA.A, aSegA.B, aSegB.A, aSegB.B };
2220
2221 std::sort( pts.begin(), pts.end(), [axis]( const VECTOR2I& p, const VECTOR2I& q )
2222 {
2223 if( axis == 0 )
2224 return p.x < q.x || ( p.x == q.x && p.y < q.y );
2225 else
2226 return p.y < q.y || ( p.y == q.y && p.x < q.x );
2227 } );
2228
2229 VECTOR2I s = pts[1];
2230 VECTOR2I e = pts[2];
2231
2232 // Check if there is polygon material on either side of the overlapping segments
2233 // Get the midpoint between s and e for testing
2234 VECTOR2I midpoint = ( s + e ) / 2;
2235
2236 // Create perpendicular offset vector to check both sides
2237 VECTOR2I segDir = e - s;
2238
2239 if( segDir.EuclideanNorm() > 25 )
2240 {
2241 VECTOR2I perp = segDir.Perpendicular().Resize( 10 );
2242
2243 // Both sides must be outside for this to be an exterior waist. Short-circuit if
2244 // either side is inside the polygon to avoid the second O(N) point-in-polygon test.
2245 if( !PointInside( midpoint + perp ) && !PointInside( midpoint - perp ) )
2246 {
2247 wxLogTrace( wxT( "collinear" ), wxT( "Found exterior waist between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)" ),
2248 aSegA.A.x, aSegA.A.y, aSegA.B.x, aSegA.B.y,
2249 aSegB.A.x, aSegB.A.y, aSegB.B.x, aSegB.B.y );
2250 return true;
2251 }
2252 }
2253
2254 return false;
2255}
2256
2257
2259{
2260 for( size_t polyIdx = 0; polyIdx < m_polys.size(); ++polyIdx )
2261 {
2262 bool changed = true;
2263
2264 while( changed )
2265 {
2266 changed = false;
2267
2268 SHAPE_LINE_CHAIN& outline = m_polys[polyIdx][0];
2269 intptr_t count = outline.PointCount();
2270
2271 std::vector<SEG> segs;
2272 segs.reserve( count );
2273
2274 for( intptr_t i = 0; i < count; ++i )
2275 segs.emplace_back( outline.CPoint( i ), outline.CPoint( ( i + 1 ) % count ) );
2276
2277 SEGMENT_INDEX index( std::move( segs ) );
2278
2279 bool found = false;
2280 int segA = -1;
2281 int segB = -1;
2282
2283 for( intptr_t i = 0; i < count && !found; ++i )
2284 {
2285 const VECTOR2I& a = outline.CPoint( i );
2286 const VECTOR2I& b = outline.CPoint( ( i + 1 ) % count );
2287 SEG seg( a, b );
2288
2289 auto visitor =
2290 [&]( int j ) -> bool
2291 {
2292 if( j == i || j == ( ( i + 1 ) % count ) || j == ( ( i + count - 1 ) % count ) )
2293 return true;
2294
2295 VECTOR2I oa = outline.CPoint( j );
2296 VECTOR2I ob = outline.CPoint( ( j + 1 ) % count );
2297 SEG other( oa, ob );
2298
2299 // Skip segments that share start/end points. This is the case for
2300 // fractured segments
2301 if( oa == a && ob == b )
2302 return true;
2303
2304 if( oa == b && ob == a )
2305 return true;
2306
2307 if( seg.ApproxCollinear( other, 10 ) && isExteriorWaist( seg, other ) )
2308 {
2309 segA = i;
2310 segB = j;
2311 found = true;
2312 return false;
2313 }
2314
2315 return true;
2316 };
2317
2318 index.VisitCandidates( seg, 0, visitor );
2319 }
2320
2321 if( !found )
2322 break;
2323
2324 int a0 = segA;
2325 int a1 = ( segA + 1 ) % outline.PointCount();
2326 int b0 = segB;
2327 int b1 = ( segB + 1 ) % outline.PointCount();
2328
2329 SHAPE_LINE_CHAIN lc1;
2330 int idx = a1;
2331 lc1.Append( outline.CPoint( idx ) );
2332
2333 while( idx != b0 )
2334 {
2335 idx = ( idx + 1 ) % outline.PointCount();
2336 lc1.Append( outline.CPoint( idx ) );
2337 }
2338
2339 lc1.SetClosed( true );
2340
2341 SHAPE_LINE_CHAIN lc2;
2342 idx = b1;
2343 lc2.Append( outline.CPoint( idx ) );
2344
2345 while( idx != a0 )
2346 {
2347 idx = ( idx + 1 ) % outline.PointCount();
2348 lc2.Append( outline.CPoint( idx ) );
2349 }
2350
2351 lc2.SetClosed( true );
2352
2353 m_polys[polyIdx][0] = std::move( lc1 );
2354
2355 POLYGON np;
2356 np.push_back( std::move( lc2 ) );
2357 m_polys.push_back( std::move( np ) );
2358
2359 changed = true;
2360 }
2361 }
2362}
2363
2364
2366{
2367 for( size_t polyIdx = 0; polyIdx < m_polys.size(); ++polyIdx )
2368 {
2369 bool changed = true;
2370
2371 while( changed )
2372 {
2373 changed = false;
2374
2375 SHAPE_LINE_CHAIN& outline = m_polys[polyIdx][0];
2376 const int count = outline.PointCount();
2377
2378 if( count < 4 )
2379 break;
2380
2381 // Prefix trapezoid terms (SHAPE_LINE_CHAIN::Area()) to sign a candidate's halves
2382 // in O(1). Built on demand; most outlines never produce a candidate.
2383 std::vector<double> prefix;
2384
2385 auto ringTerm =
2386 [&]( int aFrom, int aTo ) -> double
2387 {
2388 if( prefix.empty() )
2389 {
2390 prefix.resize( count + 1, 0.0 );
2391
2392 for( int ii = 0; ii < count; ++ii )
2393 {
2394 const VECTOR2I& a = outline.CPoint( ii );
2395 const VECTOR2I& b = outline.CPoint( ( ii + 1 ) % count );
2396
2397 prefix[ii + 1] = prefix[ii]
2398 + ( (double) a.x + b.x ) * ( (double) a.y - b.y );
2399 }
2400 }
2401
2402 double term = aFrom <= aTo ? prefix[aTo] - prefix[aFrom]
2403 : prefix[count] - prefix[aFrom] + prefix[aTo];
2404
2405 const VECTOR2I& last = outline.CPoint( aTo );
2406 const VECTOR2I& first = outline.CPoint( aFrom );
2407
2408 return term + ( (double) last.x + first.x ) * ( (double) last.y - first.y );
2409 };
2410
2411 auto ringSize =
2412 [&]( int aFrom, int aTo )
2413 {
2414 return aFrom <= aTo ? aTo - aFrom + 1 : count - aFrom + aTo + 1;
2415 };
2416
2417 // Both halves of a real self-touch keep the parent winding. An inverted half is a
2418 // Fracture() corridor; splitting there returns the hole ring as an outline.
2419 auto splittable =
2420 [&]( int aVertIdx, int aSegIdx )
2421 {
2422 const int start = ( aSegIdx + 1 ) % count;
2423
2424 if( ringSize( start, aVertIdx ) < 3 || ringSize( aVertIdx, aSegIdx ) < 3 )
2425 return false;
2426
2427 const bool sign = ringTerm( 0, count - 1 ) > 0;
2428 const double term1 = ringTerm( start, aVertIdx );
2429 const double term2 = ringTerm( aVertIdx, aSegIdx );
2430
2431 return term1 != 0.0 && term2 != 0.0 && ( term1 > 0 ) == sign
2432 && ( term2 > 0 ) == sign;
2433 };
2434
2435 int insertSegIdx = -1;
2436 int insertVertIdx = -1;
2437
2438 if( count < RTREE_THRESHOLD )
2439 {
2440 for( int vertIdx = 0; vertIdx < count && insertSegIdx < 0; ++vertIdx )
2441 {
2442 const VECTOR2I& pt = outline.CPoint( vertIdx );
2443 const int prevSeg = ( vertIdx + count - 1 ) % count;
2444
2445 for( int segIdx = 0; segIdx < count; ++segIdx )
2446 {
2447 // Skip adjacent segments
2448 if( segIdx == prevSeg || segIdx == vertIdx )
2449 continue;
2450
2451 const VECTOR2I& a = outline.CPoint( segIdx );
2452 const VECTOR2I& b = outline.CPoint( ( segIdx + 1 ) % count );
2453
2454 // SquaredDistance returns 0 only when pt lies exactly on the
2455 // segment. Clipper2 rounds corridor-cut vertices to integer
2456 // coordinates; they can land within 1nm of an endpoint but are
2457 // not true pinch points.
2458 if( pt != a && pt != b && SEG( a, b ).SquaredDistance( pt ) == 0
2459 && splittable( vertIdx, segIdx ) )
2460 {
2461 insertSegIdx = segIdx;
2462 insertVertIdx = vertIdx;
2463 break;
2464 }
2465 }
2466 }
2467 }
2468 else
2469 {
2470 std::vector<SEG> segs;
2471 segs.reserve( count );
2472
2473 for( int i = 0; i < count; ++i )
2474 segs.emplace_back( outline.CPoint( i ), outline.CPoint( ( i + 1 ) % count ) );
2475
2476 SEGMENT_INDEX index( std::move( segs ) );
2477
2478 for( int vertIdx = 0; vertIdx < count && insertSegIdx < 0; ++vertIdx )
2479 {
2480 const VECTOR2I& pt = outline.CPoint( vertIdx );
2481 const int prevSeg = ( vertIdx + count - 1 ) % count;
2482
2483 auto pinchVisitor =
2484 [&]( int segIdx ) -> bool
2485 {
2486 if( segIdx == prevSeg || segIdx == vertIdx )
2487 return true;
2488
2489 const VECTOR2I& a = outline.CPoint( segIdx );
2490 const VECTOR2I& b = outline.CPoint( ( segIdx + 1 ) % count );
2491
2492 // SquaredDistance returns 0 only when pt lies exactly on the
2493 // segment. Clipper2 rounds corridor-cut vertices to integer
2494 // coordinates; they can land within 1nm of an endpoint but
2495 // are not true pinch points.
2496 if( pt != a && pt != b && SEG( a, b ).SquaredDistance( pt ) == 0
2497 && splittable( vertIdx, segIdx ) )
2498 {
2499 insertSegIdx = segIdx;
2500 insertVertIdx = vertIdx;
2501 return false;
2502 }
2503
2504 return true;
2505 };
2506
2507 index.VisitCandidates( SEG( pt, pt ), 0, pinchVisitor );
2508 }
2509 }
2510
2511 if( insertSegIdx < 0 )
2512 break;
2513
2514 // Split the polygon at the pinch point into two separate polygons.
2515 // Polygon 1: vertices from (insertSegIdx+1) to insertVertIdx
2516 // Polygon 2: vertices from insertVertIdx to insertSegIdx
2517
2518 const int splitStart1 = ( insertSegIdx + 1 ) % count;
2519 const int size1 = ringSize( splitStart1, insertVertIdx );
2520 const int size2 = ringSize( insertVertIdx, insertSegIdx );
2521
2522 SHAPE_LINE_CHAIN poly1;
2523 SHAPE_LINE_CHAIN poly2;
2524 poly1.ReservePoints( size1 );
2525 poly2.ReservePoints( size2 );
2526
2527 int idx = splitStart1;
2528
2529 for( int i = 0; i < size1; ++i )
2530 {
2531 poly1.Append( outline.CPoint( idx ) );
2532 idx = ( idx + 1 ) % count;
2533 }
2534
2535 poly1.SetClosed( true );
2536
2537 idx = insertVertIdx;
2538
2539 for( int i = 0; i < size2; ++i )
2540 {
2541 poly2.Append( outline.CPoint( idx ) );
2542 idx = ( idx + 1 ) % count;
2543 }
2544
2545 poly2.SetClosed( true );
2546
2547 m_polys[polyIdx][0] = std::move( poly1 );
2548
2549 POLYGON np;
2550 np.push_back( std::move( poly2 ) );
2551 m_polys.push_back( std::move( np ) );
2552
2553 changed = true;
2554 }
2555 }
2556}
2557
2558
2560{
2562
2564
2565 booleanOp( Clipper2Lib::ClipType::Union, empty );
2566}
2567
2568
2570{
2571 for( POLYGON& paths : m_polys )
2572 {
2573 for( SHAPE_LINE_CHAIN& path : paths )
2574 {
2575 path.Simplify( aTolerance );
2576 }
2577 }
2578}
2579
2580
2582{
2583 // We are expecting only one main outline, but this main outline can have holes
2584 // if holes: combine holes and remove them from the main outline.
2585 // Note also we are usingin polygon
2586 // calculations, but it is not mandatory. It is used mainly
2587 // because there is usually only very few vertices in area outlines
2588 SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
2589 SHAPE_POLY_SET holesBuffer;
2590
2591 // Move holes stored in outline to holesBuffer:
2592 // The first SHAPE_LINE_CHAIN is the main outline, others are holes
2593 while( outline.size() > 1 )
2594 {
2595 holesBuffer.AddOutline( outline.back() );
2596 outline.pop_back();
2597 }
2598
2599 Simplify();
2600
2601 // If any hole, subtract it to main outline
2602 if( holesBuffer.OutlineCount() )
2603 {
2604 holesBuffer.Simplify();
2605 BooleanSubtract( holesBuffer );
2606 }
2607
2608 // In degenerate cases, simplify might return no outlines
2609 if( OutlineCount() > 0 )
2611
2612 return OutlineCount();
2613}
2614
2615
2616const std::string SHAPE_POLY_SET::Format( bool aCplusPlus ) const
2617{
2618 std::stringstream ss;
2619
2620 ss << "SHAPE_LINE_CHAIN poly; \n";
2621
2622 for( unsigned i = 0; i < m_polys.size(); i++ )
2623 {
2624 for( unsigned j = 0; j < m_polys[i].size(); j++ )
2625 {
2626
2627 ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
2628
2629 SHAPE_POLY_SET poly;
2630
2631 if( j == 0 )
2632 {
2633 ss << " poly.AddOutline(tmp); } \n";
2634 }
2635 else
2636 {
2637 ss << " poly.AddHole(tmp); } \n";
2638 }
2639
2640 }
2641 }
2642
2643 return ss.str();
2644}
2645
2646
2647bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
2648{
2649 std::string tmp;
2650
2651 aStream >> tmp;
2652
2653 if( tmp != "polyset" )
2654 return false;
2655
2656 aStream >> tmp;
2657
2658 int n_polys = atoi( tmp.c_str() );
2659
2660 if( n_polys < 0 )
2661 return false;
2662
2663 for( int i = 0; i < n_polys; i++ )
2664 {
2665 POLYGON paths;
2666
2667 aStream >> tmp;
2668
2669 if( tmp != "poly" )
2670 return false;
2671
2672 aStream >> tmp;
2673 int n_outlines = atoi( tmp.c_str() );
2674
2675 if( n_outlines < 0 )
2676 return false;
2677
2678 for( int j = 0; j < n_outlines; j++ )
2679 {
2680 SHAPE_LINE_CHAIN outline;
2681
2682 outline.SetClosed( true );
2683
2684 aStream >> tmp;
2685 int n_vertices = atoi( tmp.c_str() );
2686
2687 for( int v = 0; v < n_vertices; v++ )
2688 {
2689 VECTOR2I p;
2690
2691 aStream >> tmp; p.x = atoi( tmp.c_str() );
2692 aStream >> tmp; p.y = atoi( tmp.c_str() );
2693 outline.Append( p );
2694 }
2695
2696 paths.push_back( std::move( outline ) );
2697 }
2698
2699 m_polys.push_back( std::move( paths ) );
2700 }
2701
2702 return true;
2703}
2704
2705
2706const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
2707{
2708 BOX2I bb;
2709
2710 for( unsigned i = 0; i < m_polys.size(); i++ )
2711 {
2712 if( i == 0 )
2713 bb = m_polys[i][0].BBox();
2714 else
2715 bb.Merge( m_polys[i][0].BBox() );
2716 }
2717
2718 bb.Inflate( aClearance );
2719 return bb;
2720}
2721
2722
2724{
2725 BOX2I bb;
2726
2727 for( unsigned i = 0; i < m_polys.size(); i++ )
2728 {
2729 if( i == 0 )
2730 bb = *m_polys[i][0].GetCachedBBox();
2731 else
2732 bb.Merge( *m_polys[i][0].GetCachedBBox() );
2733 }
2734
2735 return bb;
2736}
2737
2738
2739bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP, int aAccuracy ) const
2740{
2741 // Iterate through all the polygons in the set
2742 for( const POLYGON& polygon : m_polys )
2743 {
2744 // Iterate through all the line chains in the polygon
2745 for( const SHAPE_LINE_CHAIN& lineChain : polygon )
2746 {
2747 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2748 return true;
2749 }
2750 }
2751
2752 return false;
2753}
2754
2755
2756bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance, int* aActual,
2757 VECTOR2I* aLocation ) const
2758{
2759 VECTOR2I nearest;
2760 ecoord dist_sq = SquaredDistanceToSeg( aSeg, aLocation ? &nearest : nullptr );
2761
2762 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
2763 {
2764 if( aLocation )
2765 *aLocation = nearest;
2766
2767 if( aActual )
2768 *aActual = sqrt( dist_sq );
2769
2770 return true;
2771 }
2772
2773 return false;
2774}
2775
2776
2777bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
2778 VECTOR2I* aLocation ) const
2779{
2780 if( IsEmpty() || VertexCount() == 0 )
2781 return false;
2782
2783 VECTOR2I nearest;
2784 ecoord dist_sq = SquaredDistance( aP, false, aLocation ? &nearest : nullptr );
2785
2786 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
2787 {
2788 if( aLocation )
2789 *aLocation = nearest;
2790
2791 if( aActual )
2792 *aActual = sqrt( dist_sq );
2793
2794 return true;
2795 }
2796
2797 return false;
2798}
2799
2800
2801bool SHAPE_POLY_SET::Collide( const SHAPE* aShape, int aClearance, int* aActual,
2802 VECTOR2I* aLocation ) const
2803{
2804 // A couple of simple cases are worth trying before we fall back on triangulation.
2805
2806 if( aShape->Type() == SH_SEGMENT )
2807 {
2808 const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
2809 int extra = segment->GetWidth() / 2;
2810
2811 if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
2812 {
2813 if( aActual )
2814 *aActual = std::max( 0, *aActual - extra );
2815
2816 return true;
2817 }
2818
2819 return false;
2820 }
2821
2822 if( aShape->Type() == SH_CIRCLE )
2823 {
2824 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
2825 int extra = circle->GetRadius();
2826
2827 if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
2828 {
2829 if( aActual )
2830 *aActual = std::max( 0, *aActual - extra );
2831
2832 return true;
2833 }
2834
2835 return false;
2836 }
2837
2838 const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( false, {}, true );
2839
2840 if( !aActual && !aLocation )
2841 return AnyTriangleHit( m_triIndex.get(), m_triangulatedPolys, aShape, aClearance );
2842
2843 int actual;
2845
2846 if( !AnyTriangleHit( m_triIndex.get(), m_triangulatedPolys, aShape, aClearance, &actual, &location ) )
2847 return false;
2848
2849 if( aActual )
2850 *aActual = std::max( 0, actual );
2851
2852 if( aLocation )
2853 *aLocation = location;
2854
2855 return true;
2856}
2857
2858
2860{
2861 m_triIndex.reset();
2862
2863 m_polys.clear();
2864 m_triangulatedPolys.clear();
2865 m_triangulationValid = false;
2866}
2867
2868
2869void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
2870{
2871 // Default polygon is the last one
2872 if( aPolygonIdx < 0 )
2873 aPolygonIdx += m_polys.size();
2874
2875 m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
2876}
2877
2878
2879void SHAPE_POLY_SET::RemoveOutline( int aOutlineIdx )
2880{
2881 m_polys.erase( m_polys.begin() + aOutlineIdx );
2882}
2883
2884
2886{
2887 int removed = 0;
2888
2889 ITERATOR iterator = IterateWithHoles();
2890
2891 VECTOR2I contourStart = *iterator;
2892 VECTOR2I segmentStart, segmentEnd;
2893
2894 VERTEX_INDEX indexStart;
2895 std::vector<VERTEX_INDEX> indices_to_remove;
2896
2897 while( iterator )
2898 {
2899 // Obtain first point and its index
2900 segmentStart = *iterator;
2901 indexStart = iterator.GetIndex();
2902
2903 // Obtain last point
2904 if( iterator.IsEndContour() )
2905 {
2906 segmentEnd = contourStart;
2907
2908 // Advance
2909 iterator++;
2910
2911 // If we have rolled into the next contour, remember its position
2912 // segmentStart and segmentEnd remain valid for comparison here
2913 if( iterator )
2914 contourStart = *iterator;
2915 }
2916 else
2917 {
2918 // Advance
2919 iterator++;
2920
2921 // If we have reached the end of the SHAPE_POLY_SET, something is broken here
2922 wxCHECK_MSG( iterator, removed, wxT( "Invalid polygon. Reached end without noticing. Please report this error" ) );
2923
2924 segmentEnd = *iterator;
2925 }
2926
2927 // Remove segment start if both points are equal
2928 if( segmentStart == segmentEnd )
2929 {
2930 indices_to_remove.push_back( indexStart );
2931 removed++;
2932 }
2933 }
2934
2935 // Proceed in reverse direction to remove the vertices because they are stored as absolute indices in a vector
2936 // Removing in reverse order preserves the remaining index values
2937 for( auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2938 RemoveVertex( *it );
2939
2940 return removed;
2941}
2942
2943
2945{
2946 m_polys.erase( m_polys.begin() + aIdx );
2947}
2948
2949
2951{
2952 m_triIndex.reset();
2953
2954 m_polys.erase( m_polys.begin() + aIdx );
2955
2957 {
2958 for( int ii = m_triangulatedPolys.size() - 1; ii >= 0; --ii )
2959 {
2960 std::unique_ptr<TRIANGULATED_POLYGON>& triangleSet = m_triangulatedPolys[ii];
2961
2962 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2963 m_triangulatedPolys.erase( m_triangulatedPolys.begin() + ii );
2964 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2965 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2966 }
2967
2968 if( aUpdateHash )
2969 {
2970 m_hash = checksum();
2971 m_hashValid = true;
2972 }
2973 }
2974}
2975
2976
2982
2983
2985{
2986 m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
2987}
2988
2989
2990void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
2991{
2992 Append( aP.x, aP.y, aOutline, aHole );
2993}
2994
2995
2997 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
2998 int aClearance ) const
2999{
3000 // Shows whether there was a collision
3001 bool collision = false;
3002
3003 // Difference vector between each vertex and aPoint.
3005 ecoord distance_squared;
3006 ecoord clearance_squared = SEG::Square( aClearance );
3007
3008 for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
3009 {
3010 // Get the difference vector between current vertex and aPoint
3011 delta = *iterator - aPoint;
3012
3013 // Compute distance
3014 distance_squared = delta.SquaredEuclideanNorm();
3015
3016 // Check for collisions
3017 if( distance_squared <= clearance_squared )
3018 {
3019 if( !aClosestVertex )
3020 return true;
3021
3022 collision = true;
3023
3024 // Update clearance to look for closer vertices
3025 clearance_squared = distance_squared;
3026
3027 // Store the indices that identify the vertex
3028 *aClosestVertex = iterator.GetIndex();
3029 }
3030 }
3031
3032 return collision;
3033}
3034
3035
3037 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
3038 int aClearance ) const
3039{
3040 // Shows whether there was a collision
3041 bool collision = false;
3042 ecoord clearance_squared = SEG::Square( aClearance );
3043
3044 for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
3045 {
3046 const SEG currentSegment = *iterator;
3047 ecoord distance_squared = currentSegment.SquaredDistance( aPoint );
3048
3049 // Check for collisions
3050 if( distance_squared <= clearance_squared )
3051 {
3052 if( !aClosestVertex )
3053 return true;
3054
3055 collision = true;
3056
3057 // Update clearance to look for closer edges
3058 clearance_squared = distance_squared;
3059
3060 // Store the indices that identify the vertex
3061 *aClosestVertex = iterator.GetIndex();
3062 }
3063 }
3064
3065 return collision;
3066}
3067
3068
3070{
3071 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
3072 {
3073 COutline( polygonIdx ).GenerateBBoxCache();
3074
3075 for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
3076 CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
3077 }
3078}
3079
3080
3081bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
3082 bool aUseBBoxCaches ) const
3083{
3084 if( m_polys.empty() )
3085 return false;
3086
3087 // If there is a polygon specified, check the condition against that polygon
3088 if( aSubpolyIndex >= 0 )
3089 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
3090
3091 // In any other case, check it against all polygons in the set
3092 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
3093 {
3094 if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
3095 return true;
3096 }
3097
3098 return false;
3099}
3100
3101
3102void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
3103{
3105
3106 // Assure the to be removed vertex exists, abort otherwise
3107 if( GetRelativeIndices( aGlobalIndex, &index ) )
3109 else
3110 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
3111}
3112
3113
3115{
3116 m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
3117}
3118
3119
3120void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
3121{
3123
3124 if( GetRelativeIndices( aGlobalIndex, &index ) )
3125 SetVertex( index, aPos );
3126 else
3127 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
3128}
3129
3130
3131void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
3132{
3133 m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
3134}
3135
3136
3137bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
3138 bool aUseBBoxCaches ) const
3139{
3140 // Check that the point is inside the outline
3141 if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
3142 {
3143 // Check that the point is not in any of the holes
3144 for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
3145 {
3146 const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
3147
3148 // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
3149 // here as it's meaning would be inverted.
3150 if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
3151 return false;
3152 }
3153
3154 return true;
3155 }
3156
3157 return false;
3158}
3159
3160
3161void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
3162{
3163 m_triIndex.reset();
3164
3165 for( POLYGON& poly : m_polys )
3166 {
3167 for( SHAPE_LINE_CHAIN& path : poly )
3168 path.Move( aVector );
3169 }
3170
3171 for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
3172 tri->Move( aVector );
3173
3174 m_hash = checksum();
3175 m_hashValid = true;
3176}
3177
3178
3179void SHAPE_POLY_SET::Mirror( const VECTOR2I& aRef, FLIP_DIRECTION aFlipDirection )
3180{
3181 for( POLYGON& poly : m_polys )
3182 {
3183 for( SHAPE_LINE_CHAIN& path : poly )
3184 path.Mirror( aRef, aFlipDirection );
3185 }
3186
3189}
3190
3191
3192void SHAPE_POLY_SET::Mirror( const SEG& aAxis )
3193{
3194 for( POLYGON& poly : m_polys )
3195 {
3196 for( SHAPE_LINE_CHAIN& path : poly )
3197 path.Mirror( aAxis );
3198 }
3199
3202}
3203
3204
3205void SHAPE_POLY_SET::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
3206{
3207 for( POLYGON& poly : m_polys )
3208 {
3209 for( SHAPE_LINE_CHAIN& path : poly )
3210 path.Rotate( aAngle, aCenter );
3211 }
3212
3213 // Don't re-cache if the triangulation is already invalid
3216}
3217
3218
3220{
3221 int c = 0;
3222
3223 for( const POLYGON& poly : m_polys )
3224 {
3225 for( const SHAPE_LINE_CHAIN& path : poly )
3226 c += path.PointCount();
3227 }
3228
3229 return c;
3230}
3231
3232
3233SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
3234{
3235 return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
3236}
3237
3238
3239SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
3240 int aIndex )
3241{
3242 return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
3243}
3244
3245
3247 VECTOR2I* aNearest ) const
3248{
3249 // We calculate the min dist between the segment and each outline segment. However, if the
3250 // segment to test is inside the outline, and does not cross any edge, it can be seen outside
3251 // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
3252 // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
3253 if( containsSingle( aPoint, aPolygonIndex, 1 ) )
3254 {
3255 if( aNearest )
3256 *aNearest = aPoint;
3257
3258 return 0;
3259 }
3260
3261 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
3262
3263 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
3264
3265 if( aNearest )
3266 *aNearest = ( *iterator ).NearestPoint( aPoint );
3267
3268 for( iterator++; iterator && minDistance > 0; iterator++ )
3269 {
3270 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
3271
3272 if( currentDistance < minDistance )
3273 {
3274 if( aNearest )
3275 *aNearest = (*iterator).NearestPoint( aPoint );
3276
3277 minDistance = currentDistance;
3278 }
3279 }
3280
3281 return minDistance;
3282}
3283
3284
3286 VECTOR2I* aNearest ) const
3287{
3288 // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
3289 if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
3290 containsSingle( aSegment.B, aPolygonIndex, 1 ) )
3291 {
3292 if( aNearest )
3293 *aNearest = ( aSegment.A + aSegment.B ) / 2;
3294
3295 return 0;
3296 }
3297
3298 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
3299 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
3300
3301 if( aNearest )
3302 *aNearest = ( *iterator ).NearestPoint( aSegment );
3303
3304 for( iterator++; iterator && minDistance > 0; iterator++ )
3305 {
3306 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
3307
3308 if( currentDistance < minDistance )
3309 {
3310 if( aNearest )
3311 *aNearest = (*iterator).NearestPoint( aSegment );
3312
3313 minDistance = currentDistance;
3314 }
3315 }
3316
3317 // Return the maximum of minDistance and zero
3318 return minDistance < 0 ? 0 : minDistance;
3319}
3320
3321
3322SEG::ecoord SHAPE_POLY_SET::SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly,
3323 VECTOR2I* aNearest ) const
3324{
3325 wxASSERT_MSG( !aOutlineOnly, wxT( "Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
3326 "support aOutlineOnly==true" ) );
3327
3328 SEG::ecoord currentDistance_sq;
3329 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
3330 VECTOR2I nearest;
3331
3332 // Iterate through all the polygons and get the minimum distance.
3333 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
3334 {
3335 currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
3336 aNearest ? &nearest : nullptr );
3337
3338 if( currentDistance_sq < minDistance_sq )
3339 {
3340 if( aNearest )
3341 *aNearest = nearest;
3342
3343 minDistance_sq = currentDistance_sq;
3344 }
3345 }
3346
3347 return minDistance_sq;
3348}
3349
3350
3352{
3353 SEG::ecoord currentDistance_sq;
3354 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
3355 VECTOR2I nearest;
3356
3357 // Iterate through all the polygons and get the minimum distance.
3358 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
3359 {
3360 currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
3361 aNearest ? &nearest : nullptr );
3362
3363 if( currentDistance_sq < minDistance_sq )
3364 {
3365 if( aNearest )
3366 *aNearest = nearest;
3367
3368 minDistance_sq = currentDistance_sq;
3369 }
3370 }
3371
3372 return minDistance_sq;
3373}
3374
3375
3377{
3379
3380 // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
3381 if( !GetRelativeIndices( aGlobalIdx, &index ) )
3382 return false;
3383
3384 // The contour is a hole if its index is greater than zero
3385 return index.m_contour > 0;
3386}
3387
3388
3390{
3391 SHAPE_POLY_SET chamfered;
3392
3393 for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
3394 chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
3395
3396 return chamfered;
3397}
3398
3399
3400SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
3401{
3402 SHAPE_POLY_SET filleted;
3403
3404 for( size_t idx = 0; idx < m_polys.size(); idx++ )
3405 filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
3406
3407 return filleted;
3408}
3409
3410
3412{
3413 if( this != &aOther )
3414 {
3415 SHAPE::operator=( aOther );
3416
3417 m_polys = std::move( aOther.m_polys );
3418 m_triangulatedPolys = std::move( aOther.m_triangulatedPolys );
3419
3420 m_triIndex = std::move( aOther.m_triIndex );
3421
3422 m_hash = aOther.m_hash;
3423 m_hashValid.store( aOther.m_hashValid.load() );
3424 m_triangulationValid.store( aOther.m_triangulationValid );
3425 }
3426
3427 return *this;
3428}
3429
3430
3432{
3433 m_triIndex.reset();
3434
3435 SHAPE::operator=( aOther );
3436 m_polys = aOther.m_polys;
3437
3438 m_triangulatedPolys.clear();
3439
3440 if( aOther.IsTriangulationUpToDate() )
3441 {
3442 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
3443
3444 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
3445 {
3446 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
3447 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
3448 }
3449
3450 m_hash = aOther.m_hash;
3451 m_hashValid.store( aOther.m_hashValid.load() );
3453 }
3454 else
3455 {
3456 m_hash.Clear();
3457 m_hashValid = false;
3458 m_triangulationValid = false;
3459 }
3460
3461 m_failedHash = aOther.m_failedHash;
3462 m_failedHashValid.store( aOther.m_failedHashValid.load() );
3463
3464 return *this;
3465}
3466
3467
3469{
3470 if( !m_hashValid )
3471 return checksum();
3472
3473 return m_hash;
3474}
3475
3476
3478{
3480 return false;
3481
3482 if( !m_hashValid )
3483 return false;
3484
3485 HASH_128 hash = checksum();
3486
3487 return hash == m_hash;
3488}
3489
3490
3491void SHAPE_POLY_SET::cacheTriangulation( bool aSimplify, std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData,
3492 const TASK_SUBMITTER& aSubmitter, bool aBuildIndexes )
3493{
3494 auto buildIndexes = [this]()
3495 {
3496 if( m_triIndex )
3497 return;
3498
3499 int triCount = 0;
3500
3501 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
3502 triCount += static_cast<int>( tpoly->GetTriangleCount() );
3503
3504 if( triCount < RTREE_THRESHOLD )
3505 return;
3506
3507 m_triIndex = std::make_unique<TRIANGULATION_INDEX>( m_triangulatedPolys );
3508 };
3509
3510 // if( m_triangulationValid && m_hashValid && m_hash == checksum() )
3511 // return;
3512 // if( m_failedHashValid && m_failedHash == checksum() )
3513 // return;
3514
3515 std::unique_lock<std::mutex> lock( m_triangulationMutex );
3516
3518 {
3519 if( aBuildIndexes )
3520 buildIndexes();
3521
3522 return;
3523 }
3525 return;
3526
3527 // Invalidate, in case anything goes wrong below
3528 m_triIndex.reset();
3529 m_triangulationValid = false;
3530 m_hashValid = false;
3531 m_failedHashValid = false;
3532
3533 auto triangulate =
3534 []( SHAPE_POLY_SET& polySet, int forOutline,
3535 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3536 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData,
3537 const TASK_SUBMITTER& taskSubmitter )
3538 {
3539 bool triangulationValid = false;
3540 int pass = 0;
3541 int index = 0;
3542
3543 if( hintData && hintData->size() != (unsigned) polySet.OutlineCount() )
3544 hintData = nullptr;
3545
3546 while( polySet.OutlineCount() > 0 )
3547 {
3548 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3549 dest.erase( dest.end() - 1 );
3550
3551 {
3552 const SHAPE_LINE_CHAIN& outline = polySet.Polygon( 0 ).front();
3553 TRIANGULATED_POLYGON partitionScratch( forOutline );
3554 POLYGON_TRIANGULATION partitioner( partitionScratch );
3555 size_t partitionLeaves = partitioner.suggestedPartitionLeafCount( outline );
3556
3557 if( partitionLeaves > 1 )
3558 {
3559 std::vector<SHAPE_LINE_CHAIN> partitions =
3560 partitioner.partitionPolygonBalanced( outline, partitionLeaves );
3561
3562 if( partitions.size() > 1 )
3563 {
3564 polySet.DeletePolygon( 0 );
3565
3566 if( taskSubmitter && partitions.size() > 2 )
3567 {
3568 size_t leafCount = partitions.size();
3569
3570 struct WorkStealState
3571 {
3572 std::unique_ptr<std::atomic<bool>[]> claimed;
3573 std::unique_ptr<std::atomic<bool>[]> done;
3574 std::unique_ptr<std::atomic<bool>[]> ok;
3575
3576 explicit WorkStealState( size_t n ) :
3577 claimed( new std::atomic<bool>[n] ),
3578 done( new std::atomic<bool>[n] ),
3579 ok( new std::atomic<bool>[n] )
3580 {
3581 for( size_t i = 0; i < n; ++i )
3582 {
3583 claimed[i].store( false );
3584 done[i].store( false );
3585 ok[i].store( false );
3586 }
3587 }
3588 };
3589
3590 auto state = std::make_shared<WorkStealState>( leafCount );
3591
3592 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> results( leafCount );
3593
3594 for( size_t i = 0; i < leafCount; ++i )
3595 {
3596 results[i] = std::make_unique<TRIANGULATED_POLYGON>( forOutline );
3597 }
3598
3599 for( size_t i = 0; i < leafCount; ++i )
3600 {
3601 auto* triPoly = results[i].get();
3602 auto* leaf = &partitions[i];
3603
3604 taskSubmitter( [state, i, triPoly, leaf]()
3605 {
3606 if( state->claimed[i].exchange( true ) )
3607 return;
3608
3609 POLYGON_TRIANGULATION tess( *triPoly );
3610 state->ok[i].store( tess.TesselatePolygon( *leaf, nullptr ) );
3611 state->done[i].store( true, std::memory_order_release );
3612 } );
3613 }
3614
3615 for( size_t i = 0; i < leafCount; ++i )
3616 {
3617 if( state->claimed[i].exchange( true ) )
3618 continue;
3619
3620 POLYGON_TRIANGULATION tess( *results[i] );
3621 state->ok[i].store( tess.TesselatePolygon( partitions[i], nullptr ) );
3622 state->done[i].store( true, std::memory_order_release );
3623 }
3624
3625 for( size_t i = 0; i < leafCount; ++i )
3626 {
3627 while( !state->done[i].load( std::memory_order_acquire ) )
3628 {
3629 std::this_thread::yield();
3630 }
3631 }
3632
3633 bool allOk = true;
3634
3635 for( size_t i = 0; i < leafCount; ++i )
3636 allOk = allOk && state->ok[i].load();
3637
3638 if( allOk )
3639 {
3640 for( auto& r : results )
3641 {
3642 if( r->GetTriangleCount() > 0 )
3643 dest.push_back( std::move( r ) );
3644 }
3645
3646 triangulationValid = true;
3647 hintData = nullptr;
3648 continue;
3649 }
3650
3651 }
3652
3653 for( auto it = partitions.rbegin(); it != partitions.rend(); ++it )
3654 polySet.AddOutline( *it );
3655
3656 hintData = nullptr;
3657 continue;
3658 }
3659 }
3660 }
3661
3662 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3663 POLYGON_TRIANGULATION tess( *dest.back() );
3664
3665 // If the tessellation fails, we re-fracture the polygon, which will
3666 // first simplify the system before fracturing and removing the holes
3667 // This may result in multiple, disjoint polygons.
3668 if( !tess.TesselatePolygon( polySet.Polygon( 0 ).front(),
3669 hintData ? hintData->at( index ).get() : nullptr ) )
3670 {
3671 ++pass;
3672
3673 if( pass == 1 )
3674 {
3676 }
3677 // In Clipper2, there is only one type of simplification
3678 else
3679 {
3680 break;
3681 }
3682
3683 triangulationValid = false;
3684 hintData = nullptr;
3685 continue;
3686 }
3687
3688 polySet.DeletePolygon( 0 );
3689 index++;
3690 triangulationValid = true;
3691 }
3692
3693 return triangulationValid;
3694 };
3695
3696 m_triangulatedPolys.clear();
3697
3698 const SHAPE_POLY_SET* srcSet = this;
3699 SHAPE_POLY_SET tmpSet;
3700
3701 if( ArcCount() > 0 || aSimplify )
3702 {
3703 tmpSet = SHAPE_POLY_SET( *this );
3704 tmpSet.ClearArcs();
3705
3706 if( aSimplify )
3707 tmpSet.Simplify();
3708
3709 srcSet = &tmpSet;
3710 }
3711
3712 bool directOk = true;
3713
3714 for( int ii = 0; ii < srcSet->OutlineCount() && directOk; ++ii )
3715 {
3716 const POLYGON& poly = srcSet->CPolygon( ii );
3717 size_t prevCount = m_triangulatedPolys.size();
3718
3719 if( poly.size() > 1 )
3720 {
3721 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( ii ) );
3723
3724 if( tess.TesselatePolygon( poly, nullptr ) )
3725 continue;
3726
3727 // Hole bridging failed; fracture to merge holes into the outline
3728 m_triangulatedPolys.resize( prevCount );
3729
3730 SHAPE_POLY_SET flatSet( poly.front() );
3731
3732 for( size_t jj = 1; jj < poly.size(); ++jj )
3733 flatSet.AddHole( poly[jj] );
3734
3735 flatSet.Fracture();
3736 flatSet.splitSelfTouchingOutlines();
3737
3738 if( triangulate( flatSet, ii, m_triangulatedPolys, nullptr, aSubmitter ) )
3739 continue;
3740
3741 m_triangulatedPolys.resize( prevCount );
3742 directOk = false;
3743 continue;
3744 }
3745
3746 {
3747 TRIANGULATED_POLYGON partScratch( -1 );
3748 POLYGON_TRIANGULATION partChecker( partScratch );
3749
3750 if( partChecker.suggestedPartitionLeafCount( poly.front() ) > 1 )
3751 {
3752 SHAPE_POLY_SET partSet;
3753 partSet.AddOutline( poly.front() );
3754
3755 if( triangulate( partSet, ii, m_triangulatedPolys, nullptr, aSubmitter ) )
3756 {
3757 continue;
3758 }
3759
3760 m_triangulatedPolys.resize( prevCount );
3761 }
3762 }
3763
3764 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( ii ) );
3766
3767 bool ok = tess.TesselatePolygon( poly.front(), nullptr );
3768
3769 // Self-touching outlines produce overlapping triangles; detect via area coverage
3770 if( ok )
3771 {
3772 double originalArea = std::abs( poly.front().Area() );
3773
3774 if( originalArea > 0.0 )
3775 {
3776 double triArea = 0.0;
3777
3778 for( const auto& tri : m_triangulatedPolys.back()->Triangles() )
3779 triArea += std::abs( tri.Area() );
3780
3781 double coverage = triArea / originalArea;
3782
3783 if( coverage > 1.01 || coverage < 0.99 )
3784 ok = false;
3785 }
3786 }
3787
3788 if( !ok )
3789 {
3790 m_triangulatedPolys.resize( prevCount );
3791
3792 SHAPE_POLY_SET splitSet;
3793 splitSet.AddOutline( poly[0] );
3794 splitSet.splitSelfTouchingOutlines();
3795
3796 bool splitOk = true;
3797
3798 for( int jj = 0; jj < splitSet.OutlineCount() && splitOk; ++jj )
3799 {
3800 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( ii ) );
3801 POLYGON_TRIANGULATION splitTess( *m_triangulatedPolys.back() );
3802 splitOk = splitTess.TesselatePolygon( splitSet.CPolygon( jj ).front(), nullptr );
3803 }
3804
3805 if( !splitOk )
3806 directOk = false;
3807 }
3808 }
3809
3810 if( !m_triangulatedPolys.empty() && m_triangulatedPolys.back()->GetTriangleCount() == 0 )
3811 m_triangulatedPolys.pop_back();
3812
3813 if( directOk && !m_triangulatedPolys.empty() )
3814 {
3815 m_hash = checksum();
3816 m_hashValid = true;
3817 m_triangulationValid = true;
3818 }
3819 else
3820 {
3821 // Fracture each outline individually to preserve source outline indices
3822 m_triangulatedPolys.clear();
3823 bool fallbackOk = true;
3824
3825 for( int ii = 0; ii < srcSet->OutlineCount() && fallbackOk; ++ii )
3826 {
3827 const POLYGON& poly = srcSet->CPolygon( ii );
3828 SHAPE_POLY_SET flatSet( poly.front() );
3829
3830 for( size_t jj = 1; jj < poly.size(); ++jj )
3831 flatSet.AddHole( poly[jj] );
3832
3833 flatSet.ClearArcs();
3834 flatSet.Fracture();
3835 flatSet.splitSelfTouchingOutlines();
3836
3837 if( !triangulate( flatSet, ii, m_triangulatedPolys, nullptr, aSubmitter ) )
3838 fallbackOk = false;
3839 }
3840
3841 if( !fallbackOk )
3842 {
3843 // Last resort: flatten everything together (loses outline indices)
3844 m_triangulatedPolys.clear();
3845 SHAPE_POLY_SET fallbackSet( *this );
3846 fallbackSet.ClearArcs();
3847 fallbackSet.Fracture();
3848 fallbackSet.splitSelfTouchingOutlines();
3849
3850 if( !triangulate( fallbackSet, -1, m_triangulatedPolys, aHintData, aSubmitter ) )
3851 {
3852 wxLogTrace( TRIANGULATE_TRACE, "Failed to triangulate polygon" );
3853 }
3854 else
3855 {
3856 m_triangulationValid = true;
3857 }
3858 }
3859 else
3860 {
3861 m_triangulationValid = true;
3862 }
3863
3865 {
3866 m_hash = checksum();
3867 m_hashValid = true;
3868 }
3869 else
3870 {
3872 m_failedHashValid = true;
3873 }
3874 }
3875
3876 if( aBuildIndexes && m_triangulationValid )
3877 buildIndexes();
3878}
3879
3880
3881
3883{
3884 MMH3_HASH hash( 0x68AF835D ); // Arbitrary seed
3885
3886 hash.add( m_polys.size() );
3887
3888 for( const POLYGON& outline : m_polys )
3889 {
3890 hash.add( outline.size() );
3891
3892 for( const SHAPE_LINE_CHAIN& lc : outline )
3893 {
3894 hash.add( lc.PointCount() );
3895
3896 for( int i = 0; i < lc.PointCount(); i++ )
3897 {
3898 VECTOR2I pt = lc.CPoint( i );
3899
3900 hash.add( pt.x );
3901 hash.add( pt.y );
3902 }
3903 }
3904 }
3905
3906 return hash.digest();
3907}
3908
3909
3911{
3912 for( int i = 0; i < OutlineCount(); i++ )
3913 {
3914 if( hasTouchingHoles( CPolygon( i ) ) )
3915 return true;
3916 }
3917
3918 return false;
3919}
3920
3921
3923{
3924 std::set<long long> ptHashes;
3925
3926 for( const SHAPE_LINE_CHAIN& lc : aPoly )
3927 {
3928 for( const VECTOR2I& pt : lc.CPoints() )
3929 {
3930 const long long ptHash = (long long) pt.x << 32 | pt.y;
3931
3932 if( ptHashes.count( ptHash ) > 0 )
3933 return true;
3934
3935 ptHashes.insert( ptHash );
3936 }
3937 }
3938
3939 return false;
3940}
3941
3942
3947
3948
3950{
3951 size_t n = 0;
3952
3953 for( const std::unique_ptr<TRIANGULATED_POLYGON>& t : m_triangulatedPolys )
3954 n += t->GetTriangleCount();
3955
3956 return n;
3957}
3958
3959
3960void SHAPE_POLY_SET::GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const
3961{
3962 aSubshapes.reserve( GetIndexableSubshapeCount() );
3963
3964 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
3965 {
3966 for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
3967 aSubshapes.push_back( &tri );
3968 }
3969}
3970
3971
3973{
3974 BOX2I bbox( parent->m_vertices[a] );
3975 bbox.Merge( parent->m_vertices[b] );
3976 bbox.Merge( parent->m_vertices[c] );
3977
3978 if( aClearance != 0 )
3979 bbox.Inflate( aClearance );
3980
3981 return bbox;
3982}
3983
3984
3986{
3987 m_triangles.emplace_back( a, b, c, this );
3988}
3989
3990
3992{
3994 m_vertices = aOther.m_vertices;
3995 m_triangles = aOther.m_triangles;
3996
3997 for( TRI& tri : m_triangles )
3998 tri.parent = this;
3999}
4000
4001
4003{
4005 m_vertices = aOther.m_vertices;
4006 m_triangles = aOther.m_triangles;
4007
4008 for( TRI& tri : m_triangles )
4009 tri.parent = this;
4010
4011 return *this;
4012}
4013
4014
4016{
4017 const size_t triCount = m_triangles.size();
4018
4019 // Indices are int; skip an implausibly huge mesh rather than overflow.
4020 if( triCount < 2 || triCount > static_cast<size_t>( std::numeric_limits<int>::max() ) / 6 )
4021 return;
4022
4023 const int halfEdgeCount = static_cast<int>( 3 * triCount );
4024
4025 // heVertex[3k+j] is vertex j of triangle k.
4026 std::vector<int> heVertex( halfEdgeCount );
4027
4028 for( size_t k = 0; k < triCount; k++ )
4029 {
4030 heVertex[3 * k + 0] = m_triangles[k].a;
4031 heVertex[3 * k + 1] = m_triangles[k].b;
4032 heVertex[3 * k + 2] = m_triangles[k].c;
4033 }
4034
4035 auto nextInTriangle = []( int aEdge ) { return aEdge - aEdge % 3 + ( aEdge + 1 ) % 3; };
4036
4037 // An untwinned edge is a polygon boundary and must never flip. Slots are never tombstoned so
4038 // probe chains stay intact.
4039 std::vector<int> twin( halfEdgeCount, -1 );
4040
4041 int tableSize = 1;
4042
4043 while( tableSize < halfEdgeCount * 2 )
4044 tableSize <<= 1;
4045
4046 const uint32_t tableMask = static_cast<uint32_t>( tableSize - 1 );
4047 std::vector<int> slotEdge( tableSize, -1 );
4048
4049 // A non-manifold edge (three or more triangles, e.g. a hole-bridge pinch) is retired so no
4050 // triangle straddling it can flip.
4051 std::vector<char> retired( tableSize, 0 );
4052 std::vector<int> toVisit;
4053 std::vector<char> queued( halfEdgeCount, 0 );
4054
4055 for( int edge = 0; edge < halfEdgeCount; edge++ )
4056 {
4057 int from = heVertex[edge];
4058 int to = heVertex[nextInTriangle( edge )];
4059 uint32_t keyLow = static_cast<uint32_t>( from < to ? from : to );
4060 uint32_t keyHigh = static_cast<uint32_t>( from < to ? to : from );
4061 uint32_t slot = ( ( keyLow * 0x9e3779b1u ) ^ ( keyHigh * 0x85ebca6bu ) ) & tableMask;
4062 bool handled = false;
4063
4064 while( slotEdge[slot] != -1 )
4065 {
4066 int other = slotEdge[slot];
4067 int otherFrom = heVertex[other];
4068 int otherTo = heVertex[nextInTriangle( other )];
4069 uint32_t otherLow = static_cast<uint32_t>( otherFrom < otherTo ? otherFrom : otherTo );
4070 uint32_t otherHigh = static_cast<uint32_t>( otherFrom < otherTo ? otherTo : otherFrom );
4071
4072 if( otherLow == keyLow && otherHigh == keyHigh )
4073 {
4074 if( retired[slot] )
4075 {
4076 // Non-manifold; stays a boundary.
4077 }
4078 else if( twin[other] == -1 )
4079 {
4080 twin[edge] = other;
4081 twin[other] = edge;
4082 queued[other] = 1;
4083 toVisit.push_back( other );
4084 }
4085 else
4086 {
4087 // Third half-edge here: retire the edge and unlink the pair already formed.
4088 int mate = twin[other];
4089 twin[other] = -1;
4090 twin[mate] = -1;
4091 retired[slot] = 1;
4092 }
4093
4094 handled = true;
4095 break;
4096 }
4097
4098 slot = ( slot + 1 ) & tableMask;
4099 }
4100
4101 if( !handled )
4102 slotEdge[slot] = edge;
4103 }
4104
4105 while( !toVisit.empty() )
4106 {
4107 int edge = toVisit.back();
4108 toVisit.pop_back();
4109 queued[edge] = 0;
4110
4111 int twinEdge = twin[edge];
4112
4113 if( twinEdge == -1 )
4114 continue;
4115
4116 int tri = edge - edge % 3;
4117 int twinTri = twinEdge - twinEdge % 3;
4118
4119 int apexAEdge = tri + ( edge + 2 ) % 3;
4120 int sharedEndEdge = tri + ( edge + 1 ) % 3;
4121 int apexBEdge = twinTri + ( twinEdge + 2 ) % 3;
4122 int twinSharedEdge = twinTri + ( twinEdge + 1 ) % 3;
4123
4124 int apexA = heVertex[apexAEdge];
4125 int sharedFrom = heVertex[edge];
4126 int sharedTo = heVertex[sharedEndEdge];
4127 int apexB = heVertex[apexBEdge];
4128
4129 const VECTOR2I& apexAPt = m_vertices[apexA];
4130 const VECTOR2I& sharedFromPt = m_vertices[sharedFrom];
4131 const VECTOR2I& sharedToPt = m_vertices[sharedTo];
4132 const VECTOR2I& apexBPt = m_vertices[apexB];
4133
4134 // A non-convex quad would flip a triangle outside the polygon.
4135 if( KIGEOM::OrientationSign( apexAPt, sharedFromPt, apexBPt ) <= 0 )
4136 continue;
4137
4138 if( KIGEOM::OrientationSign( apexAPt, apexBPt, sharedToPt ) <= 0 )
4139 continue;
4140
4141 // Prefer the diagonal with fewer slivers, Delaunay breaks ties. Each flip lowers
4142 // (slivers, then -min-angle) lexicographically, so the loop terminates.
4143 bool legal = KIGEOM::InCircleDelaunayLegal( apexAPt, sharedFromPt, sharedToPt, apexBPt );
4144
4145 int curSlivers = KIGEOM::IsSliverTriangle( apexAPt, sharedFromPt, sharedToPt )
4146 + KIGEOM::IsSliverTriangle( apexBPt, sharedToPt, sharedFromPt );
4147
4148 // Nothing to gain when already Delaunay and neither triangle is a sliver.
4149 if( legal && curSlivers == 0 )
4150 continue;
4151
4152 int flipSlivers = KIGEOM::IsSliverTriangle( apexAPt, sharedFromPt, apexBPt )
4153 + KIGEOM::IsSliverTriangle( apexAPt, apexBPt, sharedToPt );
4154
4155 bool doFlip = ( flipSlivers != curSlivers ) ? ( flipSlivers < curSlivers ) : !legal;
4156
4157 if( !doFlip )
4158 continue;
4159
4160 heVertex[edge] = apexB;
4161 heVertex[twinEdge] = apexA;
4162
4163 int apexBOuterTwin = twin[apexBEdge];
4164 int apexAOuterTwin = twin[apexAEdge];
4165
4166 twin[edge] = apexBOuterTwin;
4167
4168 if( apexBOuterTwin != -1 )
4169 twin[apexBOuterTwin] = edge;
4170
4171 twin[twinEdge] = apexAOuterTwin;
4172
4173 if( apexAOuterTwin != -1 )
4174 twin[apexAOuterTwin] = twinEdge;
4175
4176 twin[apexAEdge] = apexBEdge;
4177 twin[apexBEdge] = apexAEdge;
4178
4179 // The flip may have made the quad's four outer edges illegal.
4180 for( int outer : { edge, twinEdge, sharedEndEdge, twinSharedEdge } )
4181 {
4182 if( twin[outer] != -1 && !queued[outer] )
4183 {
4184 queued[outer] = 1;
4185 toVisit.push_back( outer );
4186 }
4187 }
4188 }
4189
4190 std::deque<TRI> refined;
4191
4192 for( size_t i = 0; i < triCount; i++ )
4193 refined.emplace_back( heVertex[3 * i + 0], heVertex[3 * i + 1], heVertex[3 * i + 2], this );
4194
4195 m_triangles = std::move( refined );
4196}
4197
4198
4200 m_sourceOutline( aSourceOutline )
4201{
4202}
4203
4204
4208
4209
4210void SHAPE_POLY_SET::Scale( double aScaleFactorX, double aScaleFactorY, const VECTOR2I& aCenter )
4211{
4212 for( POLYGON& poly : m_polys )
4213 {
4214 for( SHAPE_LINE_CHAIN& path : poly )
4215 {
4216 for( int i = 0; i < path.PointCount(); i++ )
4217 {
4218 VECTOR2I pt = path.CPoint( i );
4219 VECTOR2D vec;
4220 vec.x = ( pt.x - aCenter.x ) * aScaleFactorX;
4221 vec.y = ( pt.y - aCenter.y ) * aScaleFactorY;
4222 pt.x = KiROUND<double, int>( aCenter.x + vec.x );
4223 pt.y = KiROUND<double, int>( aCenter.y + vec.y );
4224 path.SetPoint( i, pt );
4225 }
4226 }
4227 }
4228
4231}
4232
4233
4234void
4235SHAPE_POLY_SET::BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
4236 bool aEvenOdd )
4237{
4238 Clipper2Lib::Clipper64 clipper;
4239 Clipper2Lib::PolyTree64 tree;
4240 Clipper2Lib::Paths64 paths;
4241
4242 for( const SHAPE_LINE_CHAIN& path : aPaths )
4243 {
4244 Clipper2Lib::Path64 lc;
4245 lc.reserve( path.PointCount() );
4246
4247 for( int i = 0; i < path.PointCount(); i++ )
4248 lc.emplace_back( path.CPoint( i ).x, path.CPoint( i ).y );
4249
4250 paths.push_back( std::move( lc ) );
4251 }
4252
4253 clipper.AddSubject( paths );
4254 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
4255 : Clipper2Lib::FillRule::NonZero, tree );
4256
4257 std::vector<CLIPPER_Z_VALUE> zValues;
4258 std::vector<SHAPE_ARC> arcBuffer;
4259
4260 importTree( tree, zValues, arcBuffer );
4261 tree.Clear(); // Free used memory (not done in dtor)
4262}
4263
4264
4265bool SHAPE_POLY_SET::PointInside( const VECTOR2I& aPt, int aAccuracy, bool aUseBBoxCache ) const
4266{
4267 for( int idx = 0; idx < OutlineCount(); idx++ )
4268 {
4269 if( COutline( idx ).PointInside( aPt, aAccuracy, aUseBBoxCache ) )
4270 return true;
4271 }
4272
4273 return false;
4274}
4275
4276
4277const std::vector<SEG> SHAPE_POLY_SET::GenerateHatchLines( const std::vector<double>& aSlopes,
4278 int aSpacing, int aLineLength ) const
4279{
4280 std::vector<SEG> hatchLines;
4281
4282 if( OutlineCount() == 0 || TotalVertices() == 0 )
4283 return hatchLines;
4284
4285 // define range for hatch lines
4286 int min_x = CVertex( 0 ).x;
4287 int max_x = CVertex( 0 ).x;
4288 int min_y = CVertex( 0 ).y;
4289 int max_y = CVertex( 0 ).y;
4290
4291 for( auto iterator = CIterateWithHoles(); iterator; iterator++ )
4292 {
4293 if( iterator->x < min_x )
4294 min_x = iterator->x;
4295
4296 if( iterator->x > max_x )
4297 max_x = iterator->x;
4298
4299 if( iterator->y < min_y )
4300 min_y = iterator->y;
4301
4302 if( iterator->y > max_y )
4303 max_y = iterator->y;
4304 }
4305
4306 auto sortEndsByDescendingX =
4307 []( const VECTOR2I& ref, const VECTOR2I& tst )
4308 {
4309 return tst.x < ref.x;
4310 };
4311
4312 for( double slope : aSlopes )
4313 {
4314 int64_t max_a, min_a;
4315
4316 if( slope > 0 )
4317 {
4318 max_a = KiROUND<double, int64_t>( max_y - slope * min_x );
4319 min_a = KiROUND<double, int64_t>( min_y - slope * max_x );
4320 }
4321 else
4322 {
4323 max_a = KiROUND<double, int64_t>( max_y - slope * max_x );
4324 min_a = KiROUND<double, int64_t>( min_y - slope * min_x );
4325 }
4326
4327 min_a = ( min_a / aSpacing ) * aSpacing;
4328
4329 // loop through hatch lines
4330 std::vector<VECTOR2I> pointbuffer;
4331 pointbuffer.reserve( 256 );
4332
4333 for( int64_t a = min_a; a < max_a; a += aSpacing )
4334 {
4335 pointbuffer.clear();
4336
4337 // Iterate through all vertices
4338 for( auto iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
4339 {
4340 const SEG seg = *iterator;
4341 VECTOR2I pt;
4342
4343 if( seg.IntersectsLine( slope, a, pt ) )
4344 {
4345 // If the intersection point is outside the polygon, skip it
4346 if( pt.x < min_x || pt.x > max_x || pt.y < min_y || pt.y > max_y )
4347 continue;
4348
4349 // Add the intersection point to the buffer
4350 pointbuffer.emplace_back( KiROUND( pt.x ), KiROUND( pt.y ) );
4351 }
4352 }
4353
4354 // sort points in order of descending x (if more than 2) to
4355 // ensure the starting point and the ending point of the same segment
4356 // are stored one just after the other.
4357 if( pointbuffer.size() > 2 )
4358 sort( pointbuffer.begin(), pointbuffer.end(), sortEndsByDescendingX );
4359
4360 // creates lines or short segments inside the complex polygon
4361 for( size_t ip = 0; ip + 1 < pointbuffer.size(); ip++ )
4362 {
4363 const VECTOR2I& p1 = pointbuffer[ip];
4364 const VECTOR2I& p2 = pointbuffer[ip + 1];
4365
4366 // Avoid duplicated intersections or segments
4367 if( p1 == p2 )
4368 continue;
4369
4370 SEG candidate( p1, p2 );
4371
4372 VECTOR2I mid( ( candidate.A.x + candidate.B.x ) / 2, ( candidate.A.y + candidate.B.y ) / 2 );
4373
4374 // Check if segment is inside the polygon by checking its middle point
4375 if( Contains( mid, -1, 1, true ) )
4376 {
4377 int dx = p2.x - p1.x;
4378
4379 // Push only one line for diagonal hatch or for small lines < twice
4380 // the line length; else push 2 small lines
4381 if( aLineLength == -1 || std::abs( dx ) < 2 * aLineLength )
4382 {
4383 hatchLines.emplace_back( candidate );
4384 }
4385 else
4386 {
4387 double dy = p2.y - p1.y;
4388 slope = dy / dx;
4389
4390 if( dx > 0 )
4391 dx = aLineLength;
4392 else
4393 dx = -aLineLength;
4394
4395 int x1 = KiROUND( p1.x + dx );
4396 int x2 = KiROUND( p2.x - dx );
4397 int y1 = KiROUND( p1.y + dx * slope );
4398 int y2 = KiROUND( p2.y - dx * slope );
4399
4400 hatchLines.emplace_back( SEG( p1.x, p1.y, x1, y1 ) );
4401
4402 hatchLines.emplace_back( SEG( p2.x, p2.y, x2, y2 ) );
4403 }
4404 }
4405 }
4406 }
4407 }
4408
4409 return hatchLines;
4410}
int index
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition box2.h:985
BOX2< VECTOR2D > BOX2D
Definition box2.h:918
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition box2.h:556
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:597
constexpr coord_type GetLeft() const
Definition box2.h:231
constexpr coord_type GetRight() const
Definition box2.h:220
constexpr coord_type GetTop() const
Definition box2.h:232
constexpr coord_type GetBottom() const
Definition box2.h:225
void InsertBridges(Index aFirst)
void insert(uint32_t aEdge, uint32_t aHead)
std::vector< NODE > m_nodes
std::vector< uint32_t > m_bucketIds
FractureEdge::Index Index
void Query(int aY, Index aProvokingIndex, Visitor &&aVisitor) const
std::vector< uint32_t > m_longIds
std::vector< uint32_t > m_offsets
static void logAccepted(size_t aEdges, size_t aHoles, uint32_t aStripes, size_t aBytes)
std::pair< uint32_t, uint32_t > span(const FractureEdge &aEdge) const
FRACTURE_EDGE_INDEX(FractureEdgeSet &aEdges, Originals &&aOriginals, int aMinY, int aMaxY, uint32_t aStripeCount, size_t aHoleCount)
uint32_t map(int aY) const
static constexpr uint32_t INVALID
void visitOverflow(uint32_t aNode, Index aProvokingIndex, Visitor &&aVisitor) const
FractureEdgeSet & m_edges
std::vector< uint32_t > m_heads
A streaming C++ equivalent for MurmurHash3_x64_128.
Definition mmh3_hash.h:61
FORCE_INLINE void add(const std::string &input)
Definition mmh3_hash.h:138
FORCE_INLINE HASH_128 digest()
Definition mmh3_hash.h:157
bool TesselatePolygon(const SHAPE_POLY_SET::POLYGON &aPolygon, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
Triangulate a polygon with holes by bridging holes directly into the outer ring's VERTEX linked list,...
std::vector< SHAPE_LINE_CHAIN > partitionPolygonBalanced(const SHAPE_LINE_CHAIN &aPoly, size_t aTargetLeaves) const
size_t suggestedPartitionLeafCount(const SHAPE_LINE_CHAIN &aPoly) const
Immutable owning spatial snapshot of straight segments.
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:35
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
Definition seg.cpp:412
VECTOR2I::extended_type ecoord
Definition seg.h:40
VECTOR2I B
Definition seg.h:46
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition seg.h:379
static SEG::ecoord Square(int a)
Definition seg.h:119
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition seg.cpp:497
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:759
SHAPE_TYPE Type() const
Return the type of the shape.
Definition shape.h:96
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
void GenerateBBoxCache() const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void ReservePoints(size_t aSize)
Allocate a number of points all at once (for performance).
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Clipper2Lib::Path64 convertToClipper2(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation.
size_t ArcCount() const
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< VECTOR2I > & CPoints() const
void Refine()
Refine this triangulation in place with boundary-preserving Lawson edge flips, minimizing the number ...
void AddTriangle(int a, int b, int c)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
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.
void Scale(double aScaleFactorX, double aScaleFactorY, const VECTOR2I &aCenter)
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.
void cacheTriangulation(bool aSimplify, std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > *aHintData, const TASK_SUBMITTER &aSubmitter={}, bool aBuildIndexes=false)
CONST_ITERATOR CIterateWithHoles() const
void BooleanAdd(const SHAPE_POLY_SET &b)
Perform boolean polyset union.
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.
std::atomic< bool > m_failedHashValid
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
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)
virtual void CacheTriangulation(bool aSimplify=false, const TASK_SUBMITTER &aSubmitter={}, bool aBuildIndexes=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
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.
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Return total number of vertices stored in the set.
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).
static bool appendBridgeFreePaths(const SHAPE_LINE_CHAIN &aChain, Clipper2Lib::Paths64 &aPaths, std::vector< CLIPPER_Z_VALUE > &aZValues, std::vector< SHAPE_ARC > &aArcBuffer)
Append the rings left after cutting the fracture bridges out of aChain.
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)
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.
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
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...
std::unique_ptr< TRIANGULATION_INDEX > m_triIndex
One index over every triangle of every polygon above.
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.
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.
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.
std::atomic< bool > m_hashValid
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 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).
virtual size_t GetIndexableSubshapeCount() const override
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
void splitSelfTouchingOutlines()
Split outline segments at vertices that lie on them (self-touching polygons).
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.
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
void Move(const VECTOR2I &aVector) override
bool HasTouchingHoles() const
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.
void Fracture(bool aSimplify=true)
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
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
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 SHAPE_LINE_CHAIN & COutline(int aIndex) const
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
std::function< void(std::function< void()>)> TASK_SUBMITTER
Callback that submits a unit of work for asynchronous execution.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
const BOX2I BBoxFromCaches() const
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.
const SEG & GetSeg() const
int GetWidth() const override
VECTOR2I::extended_type ecoord
Definition shape.h:311
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition shape.h:134
static constexpr extended_type ECOORD_MAX
Definition vector2d.h:72
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition vector2d.h:281
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition vector2d.h:335
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:406
CORNER_STRATEGY
define how inflate transform build inflated polygon
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
static bool empty(const wxTextEntryBase *aCtrl)
static constexpr EDA_ANGLE FULL_CIRCLE
Definition eda_angle.h:470
Exact orientation and in-circle predicates over integer coordinates.
a few functions useful in geometry calculations.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
static constexpr void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
Definition hash.h:28
FLIP_DIRECTION
Definition mirror.h:26
std::pair< uint32_t, uint32_t > StripeSpan(int aY1, int aY2, int aMinY, int aMaxY, uint32_t aStripeCount)
bool ActualCapacityFits(size_t aBucketIds, size_t aLongIds, size_t aOffsets, size_t aScratch, size_t aHeads, size_t aNodes, size_t aNodeSize, size_t aBudget, size_t *aBytes=nullptr)
bool ShouldIndex(uint64_t aEstimatedVisits, size_t aHoleCount)
bool CapacityFits(size_t aBucketIds, size_t aLongIds, size_t aStripeCount, size_t aHoleCount, size_t aNodeSize, size_t aBudget)
uint32_t MapYToStripe(int aY, int aMinY, int aMaxY, uint32_t aStripeCount)
uint32_t StripeCountFor(size_t aEdgeCount)
Construction helpers for the interactive arc drawing modes.
int OrientationSign(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c)
Orientation of triangle (a, b, c): +1 counter-clockwise, -1 clockwise, 0 collinear.
bool InCircleDelaunayLegal(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c, const VECTOR2I &p)
True when p is outside the circumcircle of CCW triangle (a, b, c): the shared edge is already Delauna...
bool IsSliverTriangle(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c)
A triangle is a sliver when its longest edge exceeds ten times its shortest.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:461
static PGM_BASE * process
#define TRIANGULATE_TRACE
#define TRIANGULATESIMPLIFICATIONLEVEL
CITER next(CITER it)
Definition ptree.cpp:120
@ SH_POLY_SET
set of polygons (with holes, etc.)
Definition shape.h:48
@ SH_CIRCLE
circle
Definition shape.h:46
@ SH_SEGMENT
line segment
Definition shape.h:44
static void fractureSingleCacheFriendly(SHAPE_POLY_SET::POLYGON &paths)
static constexpr int RTREE_THRESHOLD
static void fractureSingleSlow(SHAPE_POLY_SET::POLYGON &paths)
static int fractureIntersectX(const FractureEdge &aEdge, int aY)
std::vector< FractureEdge > FractureEdgeSet
std::vector< FractureEdgeSlow * > FractureEdgeSetSlow
#define ENABLEFRACTUREEDGEINDEX
static bool splitAtBridges(const SHAPE_LINE_CHAIN &aChain, std::vector< SHAPE_LINE_CHAIN > &aRings)
Split a closed ring into the rings left once pairs of coincident opposite edges are removed.
#define SEG_CNT_MAX
#define ENABLECACHEFRIENDLYFRACTURE
static FractureEdge * processHole(FractureEdgeSet &edges, FractureEdge::Index provokingIndex, FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex, FRACTURE_EDGE_INDEX *aIndex)
static int processEdge(FractureEdgeSetSlow &edges, FractureEdgeSlow *edge)
bool AnyTriangleHit(const TRIANGULATION_INDEX *aIndex, const std::vector< std::unique_ptr< SHAPE_POLY_SET::TRIANGULATED_POLYGON > > &aPolys, const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr)
Return true if any candidate triangle collides with aShape within aClearance.
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
FractureEdgeSlow * m_next
bool matches(int y) const
FractureEdgeSlow(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
FractureEdge(const VECTOR2I &p1, const VECTOR2I &p2, Index next)
FractureEdge()=default
bool matches(int y) const
A storage class for 128-bit hash value.
Definition hash_128.h:33
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
std::string path
KIBIS_PIN * partner
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
VECTOR2I location
int actual
wxString result
Test unit parsing edge cases and error handling.
int delta
#define M_PI
constexpr int sign(T val)
Definition util.h:167
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition util.h:161
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708
VECTOR2< double > VECTOR2D
Definition vector2d.h:707
static PIECE polygon(std::vector< VIA_CROSS_SECTION_GEOMETRY::POINT > aPoints, bool aMixed=false)