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, you may find one here:
25 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
26 * or you may search the http://www.gnu.org website for the version 2 license,
27 * or you may write to the Free Software Foundation, Inc.,
28 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
29 */
30
31#include <algorithm>
32#include <assert.h> // for assert
33#include <cmath> // for sqrt, cos, hypot, isinf
34#include <cstdio>
35#include <istream> // for operator<<, operator>>
36#include <limits> // for numeric_limits
37#include <map>
38#include <memory>
39#include <set>
40#include <string> // for char_traits, operator!=
41#include <unordered_set>
42#include <utility> // for swap, move
43#include <vector>
44#include <array>
45
46#include <clipper2/clipper.h>
49#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
50#include <geometry/shape.h>
53#include <geometry/rtree.h>
54#include <math/box2.h> // for BOX2I
55#include <math/util.h> // for KiROUND, rescale
56#include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
57#include <hash.h>
58#include <mmh3_hash.h>
61
62#include <wx/log.h>
63
64// ADVANCED_CFG::GetCfg() cannot be used on msys2/mingw builds (link failure)
65// So we use the ADVANCED_CFG default values
66#if defined( __MINGW32__ )
67 #define TRIANGULATESIMPLIFICATIONLEVEL 50
68 #define ENABLECACHEFRIENDLYFRACTURE true
69#else
70 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
71 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
72#endif
73
78
79
82{
83 NewOutline();
84 Append( VECTOR2I( aRect.GetLeft(), aRect.GetTop() ) );
85 Append( VECTOR2I( aRect.GetRight(), aRect.GetTop() ) );
86 Append( VECTOR2I( aRect.GetRight(), aRect.GetBottom() ) );
87 Append( VECTOR2I( aRect.GetLeft(), aRect.GetBottom() ) );
88 Outline( 0 ).SetClosed( true );
89}
90
91
94{
95 AddOutline( aOutline );
96}
97
98
101{
102 AddPolygon( aPolygon );
103}
104
105
107 SHAPE( aOther ),
108 m_polys( aOther.m_polys )
109{
110 if( aOther.IsTriangulationUpToDate() )
111 {
112 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
113
114 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
115 {
116 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
117 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
118 }
119
120 m_hash = aOther.GetHash();
121 m_hashValid = true;
123 }
124 else
125 {
126 m_hash.Clear();
127 m_hashValid = false;
128 m_triangulationValid = false;
129 }
130}
131
132
134 SHAPE( aOther ),
135 m_polys( aOther.m_polys )
136{
137 m_hash.Clear();
138 m_hashValid = false;
139 m_triangulationValid = false;
140}
141
142
146
147
149{
150 return new SHAPE_POLY_SET( *this );
151}
152
153
158
159
161 SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
162{
163 int polygonIdx = 0;
164 unsigned int contourIdx = 0;
165 int vertexIdx = 0;
166
167 int currentGlobalIdx = 0;
168
169 for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
170 {
171 const POLYGON& currentPolygon = CPolygon( polygonIdx );
172
173 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
174 {
175 const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
176 int totalPoints = currentContour.PointCount();
177
178 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
179 {
180 // Check if the current vertex is the globally indexed as aGlobalIdx
181 if( currentGlobalIdx == aGlobalIdx )
182 {
183 aRelativeIndices->m_polygon = polygonIdx;
184 aRelativeIndices->m_contour = contourIdx;
185 aRelativeIndices->m_vertex = vertexIdx;
186
187 return true;
188 }
189
190 // Advance
191 currentGlobalIdx++;
192 }
193 }
194 }
195
196 return false;
197}
198
199
201 int& aGlobalIdx ) const
202{
203 int selectedVertex = aRelativeIndices.m_vertex;
204 unsigned int selectedContour = aRelativeIndices.m_contour;
205 unsigned int selectedPolygon = aRelativeIndices.m_polygon;
206
207 // Check whether the vertex indices make sense in this poly set
208 if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
209 && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
210 {
211 POLYGON currentPolygon;
212
213 aGlobalIdx = 0;
214
215 for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
216 {
217 currentPolygon = Polygon( polygonIdx );
218
219 for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
220 aGlobalIdx += currentPolygon[contourIdx].PointCount();
221 }
222
223 currentPolygon = Polygon( selectedPolygon );
224
225 for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
226 aGlobalIdx += currentPolygon[contourIdx].PointCount();
227
228 aGlobalIdx += selectedVertex;
229
230 return true;
231 }
232 else
233 {
234 return false;
235 }
236}
237
238
240{
241 SHAPE_LINE_CHAIN empty_path;
242 POLYGON poly;
243
244 empty_path.SetClosed( true );
245 poly.push_back( empty_path );
246 m_polys.push_back( std::move( poly ) );
247 return m_polys.size() - 1;
248}
249
250
251int SHAPE_POLY_SET::NewHole( int aOutline )
252{
253 SHAPE_LINE_CHAIN empty_path;
254
255 empty_path.SetClosed( true );
256
257 // Default outline is the last one
258 if( aOutline < 0 )
259 aOutline += m_polys.size();
260
261 // Add hole to the selected outline
262 m_polys[aOutline].push_back( empty_path );
263
264 return m_polys.back().size() - 2;
265}
266
267
268int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
269{
270 assert( m_polys.size() );
271
272 if( aOutline < 0 )
273 aOutline += m_polys.size();
274
275 int idx;
276
277 if( aHole < 0 )
278 idx = 0;
279 else
280 idx = aHole + 1;
281
282 assert( aOutline < (int) m_polys.size() );
283 assert( idx < (int) m_polys[aOutline].size() );
284
285 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
286
287 return m_polys[aOutline][idx].PointCount();
288}
289
290
291int SHAPE_POLY_SET::Append( const SHAPE_ARC& aArc, int aOutline, int aHole,
292 std::optional<int> aMaxError )
293{
294 assert( m_polys.size() );
295
296 if( aOutline < 0 )
297 aOutline += m_polys.size();
298
299 int idx;
300
301 if( aHole < 0 )
302 idx = 0;
303 else
304 idx = aHole + 1;
305
306 assert( aOutline < (int) m_polys.size() );
307 assert( idx < (int) m_polys[aOutline].size() );
308
309 if( aMaxError.has_value() )
310 m_polys[aOutline][idx].Append( aArc, aMaxError.value() );
311 else
312 m_polys[aOutline][idx].Append( aArc );
313
314 return m_polys[aOutline][idx].PointCount();
315}
316
317
318void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex )
319{
320 VERTEX_INDEX index;
321
322 if( aGlobalIndex < 0 )
323 aGlobalIndex = 0;
324
325 if( aGlobalIndex >= TotalVertices() )
326 {
327 Append( aNewVertex );
328 }
329 else
330 {
331 // Assure the position to be inserted exists; throw an exception otherwise
332 if( GetRelativeIndices( aGlobalIndex, &index ) )
333 m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
334 else
335 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
336 }
337}
338
339
340int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
341{
342 if( m_polys.size() == 0 ) // Empty poly set
343 return 0;
344
345 if( aOutline < 0 ) // Use last outline
346 aOutline += m_polys.size();
347
348 int idx;
349
350 if( aHole < 0 )
351 idx = 0;
352 else
353 idx = aHole + 1;
354
355 if( aOutline >= (int) m_polys.size() ) // not existing outline
356 return 0;
357
358 if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
359 return 0;
360
361 return m_polys[aOutline][idx].PointCount();
362}
363
364
366{
367 int full_count = 0;
368
369 if( m_polys.size() == 0 ) // Empty poly set
370 return full_count;
371
372 for( int ii = 0; ii < OutlineCount(); ii++ )
373 {
374 // the first polygon in m_polys[ii] is the main contour,
375 // only others are holes:
376 for( int idx = 0; idx <= HoleCount( ii ); idx++ )
377 {
378 full_count += m_polys[ii][idx].PointCount();
379 }
380 }
381
382 return full_count;
383}
384
385
386SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
387{
388 assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
389
390 SHAPE_POLY_SET newPolySet;
391
392 for( int index = aFirstPolygon; index < aLastPolygon; index++ )
393 newPolySet.m_polys.push_back( Polygon( index ) );
394
395 return newPolySet;
396}
397
398
399const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
400{
401 if( aOutline < 0 )
402 aOutline += m_polys.size();
403
404 int idx;
405
406 if( aHole < 0 )
407 idx = 0;
408 else
409 idx = aHole + 1;
410
411 assert( aOutline < (int) m_polys.size() );
412 assert( idx < (int) m_polys[aOutline].size() );
413
414 return m_polys[aOutline][idx].CPoint( aIndex );
415}
416
417
418const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
419{
421
422 // Assure the passed index references a legal position; abort otherwise
423 if( !GetRelativeIndices( aGlobalIndex, &index ) )
424 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
425
426 return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
427}
428
429
431{
432 return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
433}
434
435
436bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext ) const
437{
439
440 // If the edge does not exist, throw an exception, it is an illegal access memory error
441 if( !GetRelativeIndices( aGlobalIndex, &index ) )
442 return false;
443
444 // Calculate the previous and next index of aGlobalIndex, corresponding to
445 // the same contour;
446 VERTEX_INDEX inext = index;
447 int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
448
449 if( index.m_vertex == 0 )
450 {
451 index.m_vertex = lastpoint - 1;
452 inext.m_vertex = 1;
453 }
454 else if( index.m_vertex == lastpoint )
455 {
456 index.m_vertex--;
457 inext.m_vertex = 0;
458 }
459 else
460 {
461 inext.m_vertex++;
462 index.m_vertex--;
463
464 if( inext.m_vertex == lastpoint )
465 inext.m_vertex = 0;
466 }
467
468 if( aPrevious )
469 {
470 int previous;
471 GetGlobalIndex( index, previous );
472 *aPrevious = previous;
473 }
474
475 if( aNext )
476 {
477 int next;
478 GetGlobalIndex( inext, next );
479 *aNext = next;
480 }
481
482 return true;
483}
484
485
486bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
487{
488 std::vector<SEG> segments;
489 segments.reserve( FullPointCount() );
490
491 for( CONST_SEGMENT_ITERATOR it = CIterateSegmentsWithHoles( aPolygonIndex ); it; it++ )
492 segments.emplace_back( *it );
493
494 std::sort( segments.begin(), segments.end(), []( const SEG& a, const SEG& b )
495 {
496 int min_a_x = std::min( a.A.x, a.B.x );
497 int min_b_x = std::min( b.A.x, b.B.x );
498
499 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 ) );
500 } );
501
502 for( auto it = segments.begin(); it != segments.end(); ++it )
503 {
504 SEG& firstSegment = *it;
505
506 // Iterate through all remaining segments.
507 auto innerIterator = it;
508 int max_x = std::max( firstSegment.A.x, firstSegment.B.x );
509 int max_y = std::max( firstSegment.A.y, firstSegment.B.y );
510
511 // Start in the next segment, we don't want to check collision between a segment and itself
512 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
513 {
514 SEG& secondSegment = *innerIterator;
515 int min_x = std::min( secondSegment.A.x, secondSegment.B.x );
516 int min_y = std::min( secondSegment.A.y, secondSegment.B.y );
517
518 // We are ordered in minimum point order, so checking the static max (first segment) against
519 // the ordered min will tell us if any of the following segments are withing the BBox
520 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
521 break;
522
523 int index_diff = std::abs( firstSegment.Index() - secondSegment.Index() );
524 bool adjacent = ( index_diff == 1) || (index_diff == ((int)segments.size() - 1) );
525
526 // Check whether the two segments built collide, only when they are not adjacent.
527 if( !adjacent && firstSegment.Collide( secondSegment, 0 ) )
528 return true;
529 }
530 }
531
532 return false;
533}
534
535
537{
538 for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
539 {
540 if( IsPolygonSelfIntersecting( polygon ) )
541 return true;
542 }
543
544 return false;
545}
546
547
549{
550 POLYGON poly;
551
552 poly.push_back( aOutline );
553
554 // This is an assertion because if it's generated by KiCad code, it probably
555 // indicates a bug elsewhere that should be fixed, but we also auto-fix it here
556 // for SWIG plugins that might mess it up
557 wxCHECK2_MSG( aOutline.IsClosed(), poly.back().SetClosed( true ),
558 "Warning: non-closed outline added to SHAPE_POLY_SET" );
559
560 m_polys.push_back( std::move( poly ) );
561
562 return (int) m_polys.size() - 1;
563}
564
565
566int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
567{
568 assert( m_polys.size() );
569
570 if( aOutline < 0 )
571 aOutline += (int) m_polys.size();
572
573 assert( aOutline < (int)m_polys.size() );
574
575 POLYGON& poly = m_polys[aOutline];
576
577 assert( poly.size() );
578
579 poly.push_back( aHole );
580
581 return (int) poly.size() - 2;
582}
583
584
586{
587 m_polys.push_back( apolygon );
588
589 return m_polys.size() - 1;
590}
591
592
594{
595 double area = 0.0;
596
597 for( int i = 0; i < OutlineCount(); i++ )
598 {
599 area += Outline( i ).Area( true );
600
601 for( int j = 0; j < HoleCount( i ); j++ )
602 area -= Hole( i, j ).Area( true );
603 }
604
605 return area;
606}
607
608
610{
611 int retval = 0;
612
613 for( const POLYGON& poly : m_polys )
614 {
615 for( size_t i = 0; i < poly.size(); i++ )
616 retval += poly[i].ArcCount();
617 }
618
619 return retval;
620}
621
622
623void SHAPE_POLY_SET::GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const
624{
625 for( const POLYGON& poly : m_polys )
626 {
627 for( size_t i = 0; i < poly.size(); i++ )
628 {
629 for( SHAPE_ARC arc : poly[i].m_arcs )
630 aArcBuffer.push_back( arc );
631 }
632 }
633}
634
635
637{
638 for( POLYGON& poly : m_polys )
639 {
640 for( size_t i = 0; i < poly.size(); i++ )
641 poly[i].ClearArcs();
642 }
643}
644
645
647{
648 std::vector<SHAPE_LINE_CHAIN> contours;
649
650 for( const POLYGON& poly : m_polys )
651 contours.insert( contours.end(), poly.begin(), poly.end() );
652
653 std::map<int, std::set<int>> parentToChildren;
654 std::map<int, std::set<int>> childToParents;
655
656 for( SHAPE_LINE_CHAIN& contour : contours )
657 contour.GenerateBBoxCache();
658
659 for( size_t i = 0; i < contours.size(); i++ )
660 {
661 const SHAPE_LINE_CHAIN& outline = contours[i];
662
663 for( size_t j = 0; j < contours.size(); j++ )
664 {
665 if( i == j )
666 continue;
667
668 const SHAPE_LINE_CHAIN& candidate = contours[j];
669 const VECTOR2I& pt0 = candidate.CPoint( 0 );
670
671 if( outline.PointInside( pt0, 0, true ) )
672 {
673 parentToChildren[i].emplace( j );
674 childToParents[j].emplace( i );
675 }
676 }
677 }
678
679 std::set<int> topLevelParents;
680
681 for( size_t i = 0; i < contours.size(); i++ )
682 {
683 if( childToParents[i].size() == 0 )
684 {
685 topLevelParents.emplace( i );
686 }
687 }
688
690
691 std::function<void( int, int, std::vector<int> )> process;
692
693 process =
694 [&]( int myId, int parentOutlineId, const std::vector<int>& path )
695 {
696 std::set<int> relParents = childToParents[myId];
697
698 for( int pathId : path )
699 {
700 int erased = relParents.erase( pathId );
701 wxASSERT( erased > 0 );
702 }
703
704 wxASSERT( relParents.size() == 0 );
705
706 int myOutline = -1;
707
708 bool isOutline = path.size() % 2 == 0;
709
710 if( isOutline )
711 {
712 int outlineId = result.AddOutline( contours[myId] );
713 myOutline = outlineId;
714 }
715 else
716 {
717 wxASSERT( parentOutlineId != -1 );
718 result.AddHole( contours[myId], parentOutlineId );
719 }
720
721 auto it = parentToChildren.find( myId );
722 if( it != parentToChildren.end() )
723 {
724 std::vector<int> thisPath = path;
725 thisPath.emplace_back( myId );
726
727 std::set<int> thisPathSet;
728 thisPathSet.insert( thisPath.begin(), thisPath.end() );
729
730 for( int childId : it->second )
731 {
732 const std::set<int>& childPathSet = childToParents[childId];
733
734 if( thisPathSet != childPathSet )
735 continue; // Only interested in immediate children
736
737 process( childId, myOutline, thisPath );
738 }
739 }
740 };
741
742 for( int topParentId : topLevelParents )
743 {
744 std::vector<int> path;
745 process( topParentId, -1, std::move( path ) );
746 }
747
748 *this = std::move( result );
749}
750
751
752void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape )
753{
754 booleanOp( aType, *this, aOtherShape );
755}
756
757
758void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
759 const SHAPE_POLY_SET& aOtherShape )
760{
761 if( ( aShape.OutlineCount() > 1 || aOtherShape.OutlineCount() > 0 )
762 && ( aShape.ArcCount() > 0 || aOtherShape.ArcCount() > 0 ) )
763 {
764 wxFAIL_MSG( wxT( "Boolean ops on curved polygons are not supported. You should call "
765 "ClearArcs() before carrying out the boolean operation." ) );
766 }
767
768 Clipper2Lib::Clipper64 c;
769
770 std::vector<CLIPPER_Z_VALUE> zValues;
771 std::vector<SHAPE_ARC> arcBuffer;
772 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
773
774 Clipper2Lib::Paths64 paths;
775 Clipper2Lib::Paths64 clips;
776
777 for( const POLYGON& poly : aShape.m_polys )
778 {
779 for( size_t i = 0; i < poly.size(); i++ )
780 {
781 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
782 }
783 }
784
785 for( const POLYGON& poly : aOtherShape.m_polys )
786 {
787 for( size_t i = 0; i < poly.size(); i++ )
788 {
789 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
790 }
791 }
792
793 c.AddSubject( paths );
794 c.AddClip( clips );
795
796 Clipper2Lib::PolyTree64 solution;
797
798 Clipper2Lib::ZCallback64 callback =
799 [&]( const Clipper2Lib::Point64 & e1bot, const Clipper2Lib::Point64 & e1top,
800 const Clipper2Lib::Point64 & e2bot, const Clipper2Lib::Point64 & e2top,
801 Clipper2Lib::Point64 & pt )
802 {
803 auto arcIndex =
804 [&]( const ssize_t& aZvalue, const ssize_t& aCompareVal = -1 ) -> ssize_t
805 {
806 ssize_t retval;
807
808 retval = zValues.at( aZvalue ).m_SecondArcIdx;
809
810 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
811 retval = zValues.at( aZvalue ).m_FirstArcIdx;
812
813 return retval;
814 };
815
816 auto arcSegment =
817 [&]( const ssize_t& aBottomZ, const ssize_t aTopZ ) -> ssize_t
818 {
819 ssize_t retval = arcIndex( aBottomZ );
820
821 if( retval != -1 )
822 {
823 if( retval != arcIndex( aTopZ, retval ) )
824 retval = -1; // Not an arc segment as the two indices do not match
825 }
826
827 return retval;
828 };
829
830 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
831 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
832
833 CLIPPER_Z_VALUE newZval;
834
835 if( e1ArcSegmentIndex != -1 )
836 {
837 newZval.m_FirstArcIdx = e1ArcSegmentIndex;
838 newZval.m_SecondArcIdx = e2ArcSegmentIndex;
839 }
840 else
841 {
842 newZval.m_FirstArcIdx = e2ArcSegmentIndex;
843 newZval.m_SecondArcIdx = -1;
844 }
845
846 size_t z_value_ptr = zValues.size();
847 zValues.push_back( newZval );
848
849 // Only worry about arc segments for later processing
850 if( newZval.m_FirstArcIdx != -1 )
851 newIntersectPoints.insert( { VECTOR2I( pt.x, pt.y ), newZval } );
852
853 pt.z = z_value_ptr;
854 //@todo amend X,Y values to true intersection between arcs or arc and segment
855 };
856
857 c.SetZCallback( std::move( callback ) ); // register callback
858
859 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
860
861 importTree( solution, zValues, arcBuffer );
862 solution.Clear(); // Free used memory (not done in dtor)
863}
864
865
867{
868 booleanOp( Clipper2Lib::ClipType::Union, b );
869}
870
871
873{
874 booleanOp( Clipper2Lib::ClipType::Difference, b );
875}
876
877
879{
880 booleanOp( Clipper2Lib::ClipType::Intersection, b );
881}
882
883
885{
886 booleanOp( Clipper2Lib::ClipType::Xor, b );
887}
888
889
891{
892 booleanOp( Clipper2Lib::ClipType::Union, a, b );
893}
894
895
897{
898 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
899}
900
901
903{
904 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
905}
906
907
909{
910 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
911}
912
913
915 int aMaxError )
916{
917 Unfracture();
918 Inflate( aFactor, aCornerStrategy, aMaxError );
919 Fracture();
920}
921
922
923void SHAPE_POLY_SET::inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy,
924 bool aSimplify )
925{
926 using namespace Clipper2Lib;
927 // A static table to avoid repetitive calculations of the coefficient
928 // 1.0 - cos( M_PI / aCircleSegCount )
929 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
930 #define SEG_CNT_MAX 64
931 static double arc_tolerance_factor[SEG_CNT_MAX + 1];
932
933 ClipperOffset c;
934
935 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
936 // and are not what you'd think they are.
937 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
938 JoinType joinType = JoinType::Round; // The way corners are offsetted
939 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
940
941 switch( aCornerStrategy )
942 {
944 joinType = JoinType::Miter;
945 miterLimit = 10; // Allows large spikes
946 break;
947
948 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
949 joinType = JoinType::Miter;
950 break;
951
952 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS: // Acute angles are rounded
953 joinType = JoinType::Miter;
954 break;
955
956 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS: // All angles are chamfered.
957 joinType = JoinType::Square;
958 break;
959
960 case CORNER_STRATEGY::ROUND_ALL_CORNERS: // All angles are rounded.
961 joinType = JoinType::Round;
962 break;
963 }
964
965 std::vector<CLIPPER_Z_VALUE> zValues;
966 std::vector<SHAPE_ARC> arcBuffer;
967
968 for( const POLYGON& poly : m_polys )
969 {
970 Paths64 paths;
971
972 for( size_t i = 0; i < poly.size(); i++ )
973 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
974
975 c.AddPaths( paths, joinType, EndType::Polygon );
976 }
977
978 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
979 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
980 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
981
982 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
983 aCircleSegCount = 6;
984
985 double coeff;
986
987 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
988 {
989 coeff = 1.0 - cos( M_PI / aCircleSegCount );
990
991 if( aCircleSegCount <= SEG_CNT_MAX )
992 arc_tolerance_factor[aCircleSegCount] = coeff;
993 }
994 else
995 {
996 coeff = arc_tolerance_factor[aCircleSegCount];
997 }
998
999 c.ArcTolerance( std::abs( aAmount ) * coeff );
1000 c.MiterLimit( miterLimit );
1001
1002 PolyTree64 tree;
1003
1004 if( aSimplify )
1005 {
1006 Paths64 paths;
1007 c.Execute( aAmount, paths );
1008
1009 Clipper2Lib::SimplifyPaths( paths, std::abs( aAmount ) * coeff, true );
1010
1011 Clipper64 c2;
1012 c2.PreserveCollinear( false );
1013 c2.ReverseSolution( false );
1014 c2.AddSubject( paths );
1015 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1016 }
1017 else
1018 {
1019 c.Execute( aAmount, tree );
1020 }
1021
1022 importTree( tree, zValues, arcBuffer );
1023 tree.Clear();
1024}
1025
1026
1027void SHAPE_POLY_SET::inflateLine2( const SHAPE_LINE_CHAIN& aLine, int aAmount, int aCircleSegCount,
1028 CORNER_STRATEGY aCornerStrategy, bool aSimplify )
1029{
1030 using namespace Clipper2Lib;
1031 // A static table to avoid repetitive calculations of the coefficient
1032 // 1.0 - cos( M_PI / aCircleSegCount )
1033 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
1034 #define SEG_CNT_MAX 64
1035 static double arc_tolerance_factor[SEG_CNT_MAX + 1];
1036
1037 ClipperOffset c;
1038
1039 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
1040 // and are not what you'd think they are.
1041 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
1042 JoinType joinType = JoinType::Round; // The way corners are offsetted
1043 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
1044
1045 switch( aCornerStrategy )
1046 {
1048 joinType = JoinType::Miter;
1049 miterLimit = 10; // Allows large spikes
1050 break;
1051
1052 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
1053 joinType = JoinType::Miter;
1054 break;
1055
1056 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS: // Acute angles are rounded
1057 joinType = JoinType::Miter;
1058 break;
1059
1060 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS: // All angles are chamfered.
1061 joinType = JoinType::Square;
1062 break;
1063
1064 case CORNER_STRATEGY::ROUND_ALL_CORNERS: // All angles are rounded.
1065 joinType = JoinType::Round;
1066 break;
1067 }
1068
1069 std::vector<CLIPPER_Z_VALUE> zValues;
1070 std::vector<SHAPE_ARC> arcBuffer;
1071
1072 Path64 path = aLine.convertToClipper2( true, zValues, arcBuffer );
1073 c.AddPath( path, joinType, EndType::Butt );
1074
1075 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
1076 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
1077 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
1078
1079 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
1080 aCircleSegCount = 6;
1081
1082 double coeff;
1083
1084 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1085 {
1086 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1087
1088 if( aCircleSegCount <= SEG_CNT_MAX )
1089 arc_tolerance_factor[aCircleSegCount] = coeff;
1090 }
1091 else
1092 {
1093 coeff = arc_tolerance_factor[aCircleSegCount];
1094 }
1095
1096 c.ArcTolerance( std::abs( aAmount ) * coeff );
1097 c.MiterLimit( miterLimit );
1098
1099 PolyTree64 tree;
1100
1101 if( aSimplify )
1102 {
1103 Paths64 paths2;
1104 c.Execute( aAmount, paths2 );
1105
1106 Clipper2Lib::SimplifyPaths( paths2, std::abs( aAmount ) * coeff, false );
1107
1108 Clipper64 c2;
1109 c2.PreserveCollinear( false );
1110 c2.ReverseSolution( false );
1111 c2.AddSubject( paths2 );
1112 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1113 }
1114 else
1115 {
1116 c.Execute( aAmount, tree );
1117 }
1118
1119 importTree( tree, zValues, arcBuffer );
1120 tree.Clear();
1121}
1122
1123
1124void SHAPE_POLY_SET::Inflate( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
1125 bool aSimplify )
1126{
1127 int segCount = GetArcToSegmentCount( std::abs( aAmount ), aMaxError, FULL_CIRCLE );
1128
1129 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1130}
1131
1132
1134 CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify )
1135{
1136 int segCount = GetArcToSegmentCount( std::abs( aAmount ), aMaxError, FULL_CIRCLE );
1137
1138 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1139}
1140
1141
1142void SHAPE_POLY_SET::importPolyPath( const std::unique_ptr<Clipper2Lib::PolyPath64>& aPolyPath,
1143 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1144 const std::vector<SHAPE_ARC>& aArcBuffer )
1145{
1146 if( !aPolyPath->IsHole() )
1147 {
1148 POLYGON paths;
1149 paths.reserve( aPolyPath->Count() + 1 );
1150 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1151
1152 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1153 {
1154 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1155
1156 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1157 importPolyPath( grandchild, aZValueBuffer, aArcBuffer );
1158 }
1159
1160 m_polys.emplace_back( std::move( paths ) );
1161 }
1162}
1163
1164
1165void SHAPE_POLY_SET::importTree( Clipper2Lib::PolyTree64& tree,
1166 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1167 const std::vector<SHAPE_ARC>& aArcBuffer )
1168{
1169 m_polys.clear();
1170
1171 for( const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1172 importPolyPath( n, aZValueBuffer, aArcBuffer );
1173}
1174
1175
1176void SHAPE_POLY_SET::importPaths( Clipper2Lib::Paths64& aPath,
1177 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1178 const std::vector<SHAPE_ARC>& aArcBuffer )
1179{
1180 m_polys.clear();
1181 POLYGON path;
1182
1183 for( const Clipper2Lib::Path64& n : aPath )
1184 {
1185 if( Clipper2Lib::Area( n ) > 0 )
1186 {
1187 if( !path.empty() )
1188 m_polys.emplace_back( path );
1189
1190 path.clear();
1191 }
1192 else
1193 {
1194 wxCHECK2_MSG( !path.empty(), continue, wxT( "Cannot add a hole before an outline" ) );
1195 }
1196
1197 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1198 }
1199
1200 if( !path.empty() )
1201 m_polys.emplace_back( std::move( path ) );
1202}
1203
1204
1206{
1207 using Index = int;
1208
1209 FractureEdge() = default;
1210
1211 FractureEdge( const VECTOR2I& p1, const VECTOR2I& p2, Index next ) :
1212 m_p1( p1 ),
1213 m_p2( p2 ),
1214 m_next( next )
1215 {
1216 }
1217
1218 bool matches( int y ) const
1219 {
1220 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
1221 }
1222
1226};
1227
1228
1229typedef std::vector<FractureEdge> FractureEdgeSet;
1230
1231
1233 FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex )
1234{
1235 FractureEdge& edge = edges[edgeIndex];
1236 int x = edge.m_p1.x;
1237 int y = edge.m_p1.y;
1238 int min_dist = std::numeric_limits<int>::max();
1239 int x_nearest = 0;
1240
1241 FractureEdge* e_nearest = nullptr;
1242
1243 // Since this function is run for all holes left to right, no need to
1244 // check for any edge beyond the provoking one because they will always be
1245 // further to the right, and unconnected to the outline anyway.
1246 for( FractureEdge::Index i = 0; i < provokingIndex; i++ )
1247 {
1248 FractureEdge& e = edges[i];
1249 // Don't consider this edge if it can't be bridged to, or faces left.
1250 if( !e.matches( y ) )
1251 continue;
1252
1253 int x_intersect;
1254
1255 if( e.m_p1.y == e.m_p2.y ) // horizontal edge
1256 {
1257 x_intersect = std::max( e.m_p1.x, e.m_p2.x );
1258 }
1259 else
1260 {
1261 x_intersect =
1262 e.m_p1.x + rescale( e.m_p2.x - e.m_p1.x, y - e.m_p1.y, e.m_p2.y - e.m_p1.y );
1263 }
1264
1265 int dist = ( x - x_intersect );
1266
1267 if( dist >= 0 && dist < min_dist )
1268 {
1269 min_dist = dist;
1270 x_nearest = x_intersect;
1271 e_nearest = &e;
1272 }
1273 }
1274
1275 if( e_nearest )
1276 {
1277 const FractureEdge::Index outline2hole_index = bridgeIndex;
1278 const FractureEdge::Index hole2outline_index = bridgeIndex + 1;
1279 const FractureEdge::Index split_index = bridgeIndex + 2;
1280 // Make an edge between the split outline edge and the hole...
1281 edges[outline2hole_index] = FractureEdge( VECTOR2I( x_nearest, y ), edge.m_p1, edgeIndex );
1282 // ...between the hole and the edge...
1283 edges[hole2outline_index] =
1284 FractureEdge( edge.m_p1, VECTOR2I( x_nearest, y ), split_index );
1285 // ...and between the split outline edge and the rest.
1286 edges[split_index] =
1287 FractureEdge( VECTOR2I( x_nearest, y ), e_nearest->m_p2, e_nearest->m_next );
1288
1289 // Perform the actual outline edge split
1290 e_nearest->m_p2 = VECTOR2I( x_nearest, y );
1291 e_nearest->m_next = outline2hole_index;
1292
1293 FractureEdge* last = &edge;
1294 for( ; last->m_next != edgeIndex; last = &edges[last->m_next] )
1295 ;
1296 last->m_next = hole2outline_index;
1297 }
1298
1299 return e_nearest;
1300}
1301
1302
1304{
1305 FractureEdgeSet edges;
1306 bool outline = true;
1307
1308 if( paths.size() == 1 )
1309 return;
1310
1311 size_t total_point_count = 0;
1312
1313 for( const SHAPE_LINE_CHAIN& path : paths )
1314 {
1315 total_point_count += path.PointCount();
1316 }
1317
1318 if( total_point_count > (size_t) std::numeric_limits<FractureEdge::Index>::max() )
1319 {
1320 wxLogWarning( wxT( "Polygon has more points than int limit" ) );
1321 return;
1322 }
1323
1324 // Reserve space in the edge set so pointers don't get invalidated during
1325 // the whole fracture process; one for each original edge, plus 3 per
1326 // path to join it to the outline.
1327 edges.reserve( total_point_count + paths.size() * 3 );
1328
1329 // Sort the paths by their lowest X bound before processing them.
1330 // This ensures the processing order for processEdge() is correct.
1331 struct PathInfo
1332 {
1333 int path_or_provoking_index;
1334 FractureEdge::Index leftmost;
1335 int x;
1336 int y_or_bridge;
1337 };
1338 std::vector<PathInfo> sorted_paths;
1339 const int paths_count = static_cast<int>( paths.size() );
1340 sorted_paths.reserve( paths_count );
1341
1342 for( int path_index = 0; path_index < paths_count; path_index++ )
1343 {
1344 const SHAPE_LINE_CHAIN& path = paths[path_index];
1345 const std::vector<VECTOR2I>& points = path.CPoints();
1346 const int point_count = static_cast<int>( points.size() );
1347 int x_min = std::numeric_limits<int>::max();
1348 int y_min = std::numeric_limits<int>::max();
1349 int leftmost = -1;
1350
1351 for( int point_index = 0; point_index < point_count; point_index++ )
1352 {
1353 const VECTOR2I& point = points[point_index];
1354 if( point.x < x_min )
1355 {
1356 x_min = point.x;
1357 leftmost = point_index;
1358 }
1359 if( point.y < y_min )
1360 y_min = point.y;
1361 }
1362
1363 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1364 }
1365
1366 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1367 []( const PathInfo& a, const PathInfo& b )
1368 {
1369 if( a.x == b.x )
1370 return a.y_or_bridge < b.y_or_bridge;
1371 return a.x < b.x;
1372 } );
1373
1374 FractureEdge::Index edge_index = 0;
1375
1376 for( PathInfo& path_info : sorted_paths )
1377 {
1378 const SHAPE_LINE_CHAIN& path = paths[path_info.path_or_provoking_index];
1379 const std::vector<VECTOR2I>& points = path.CPoints();
1380 const size_t point_count = points.size();
1381
1382 // Index of the provoking (first) edge for this path
1383 const FractureEdge::Index provoking_edge = edge_index;
1384
1385 for( size_t i = 0; i < point_count - 1; i++ )
1386 {
1387 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1388 edge_index++;
1389 }
1390
1391 // Create last edge looping back to the provoking one.
1392 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1393 edge_index++;
1394
1395 if( !outline )
1396 {
1397 // Repurpose the path sorting data structure to schedule the leftmost edge
1398 // for merging to the outline, which will in turn merge the rest of the path.
1399 path_info.path_or_provoking_index = provoking_edge;
1400 path_info.y_or_bridge = edge_index;
1401
1402 // Reserve 3 additional edges to bridge with the outline.
1403 edge_index += 3;
1404 edges.resize( edge_index );
1405 }
1406
1407 outline = false; // first path is always the outline
1408 }
1409
1410 for( auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1411 {
1412 auto edge = processHole( edges, it->path_or_provoking_index,
1413 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1414
1415 // If we can't handle the hole, the zone is broken (maybe)
1416 if( !edge )
1417 {
1418 wxLogWarning( wxT( "Broken polygon, dropping path" ) );
1419
1420 return;
1421 }
1422 }
1423
1424 paths.resize( 1 );
1425 SHAPE_LINE_CHAIN& newPath = paths[0];
1426
1427 newPath.Clear();
1428 newPath.SetClosed( true );
1429
1430 // Root edge is always at index 0
1431 FractureEdge* e = &edges[0];
1432
1433 for( ; e->m_next != 0; e = &edges[e->m_next] )
1434 newPath.Append( e->m_p1 );
1435
1436 newPath.Append( e->m_p1 );
1437}
1438
1439
1441{
1442 FractureEdgeSlow( int y = 0 ) : m_connected( false ), m_next( nullptr ) { m_p1.x = m_p2.y = y; }
1443
1444 FractureEdgeSlow( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
1445 m_connected( connected ), m_p1( p1 ), m_p2( p2 ), m_next( nullptr )
1446 {
1447 }
1448
1449 bool matches( int y ) const
1450 {
1451 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
1452 }
1453
1458};
1459
1460
1461typedef std::vector<FractureEdgeSlow*> FractureEdgeSetSlow;
1462
1463
1465{
1466 int x = edge->m_p1.x;
1467 int y = edge->m_p1.y;
1468 int min_dist = std::numeric_limits<int>::max();
1469 int x_nearest = 0;
1470
1471 FractureEdgeSlow* e_nearest = nullptr;
1472
1473 for( FractureEdgeSlow* e : edges )
1474 {
1475 if( !e->matches( y ) )
1476 continue;
1477
1478 int x_intersect;
1479
1480 if( e->m_p1.y == e->m_p2.y ) // horizontal edge
1481 {
1482 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1483 }
1484 else
1485 {
1486 x_intersect = e->m_p1.x
1487 + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1488 }
1489
1490 int dist = ( x - x_intersect );
1491
1492 if( dist >= 0 && dist < min_dist && e->m_connected )
1493 {
1494 min_dist = dist;
1495 x_nearest = x_intersect;
1496 e_nearest = e;
1497 }
1498 }
1499
1500 if( e_nearest && e_nearest->m_connected )
1501 {
1502 int count = 0;
1503
1504 FractureEdgeSlow* lead1 =
1505 new FractureEdgeSlow( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
1506 FractureEdgeSlow* lead2 =
1507 new FractureEdgeSlow( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
1508 FractureEdgeSlow* split_2 =
1509 new FractureEdgeSlow( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
1510
1511 edges.push_back( split_2 );
1512 edges.push_back( lead1 );
1513 edges.push_back( lead2 );
1514
1515 FractureEdgeSlow* link = e_nearest->m_next;
1516
1517 e_nearest->m_p2 = VECTOR2I( x_nearest, y );
1518 e_nearest->m_next = lead1;
1519 lead1->m_next = edge;
1520
1521 FractureEdgeSlow* last;
1522
1523 for( last = edge; last->m_next != edge; last = last->m_next )
1524 {
1525 last->m_connected = true;
1526 count++;
1527 }
1528
1529 last->m_connected = true;
1530 last->m_next = lead2;
1531 lead2->m_next = split_2;
1532 split_2->m_next = link;
1533
1534 return count + 1;
1535 }
1536
1537 return 0;
1538}
1539
1540
1542{
1543 FractureEdgeSetSlow edges;
1544 FractureEdgeSetSlow border_edges;
1545 FractureEdgeSlow* root = nullptr;
1546
1547 bool first = true;
1548
1549 if( paths.size() == 1 )
1550 return;
1551
1552 int num_unconnected = 0;
1553
1554 for( const SHAPE_LINE_CHAIN& path : paths )
1555 {
1556 const std::vector<VECTOR2I>& points = path.CPoints();
1557 int pointCount = points.size();
1558
1559 FractureEdgeSlow *prev = nullptr, *first_edge = nullptr;
1560
1561 int x_min = std::numeric_limits<int>::max();
1562
1563 for( int i = 0; i < pointCount; i++ )
1564 {
1565 if( points[i].x < x_min )
1566 x_min = points[i].x;
1567
1568 // Do not use path.CPoint() here; open-coding it using the local variables "points"
1569 // and "pointCount" gives a non-trivial performance boost to zone fill times.
1570 FractureEdgeSlow* fe = new FractureEdgeSlow( first, points[i],
1571 points[i + 1 == pointCount ? 0 : i + 1] );
1572
1573 if( !root )
1574 root = fe;
1575
1576 if( !first_edge )
1577 first_edge = fe;
1578
1579 if( prev )
1580 prev->m_next = fe;
1581
1582 if( i == pointCount - 1 )
1583 fe->m_next = first_edge;
1584
1585 prev = fe;
1586 edges.push_back( fe );
1587
1588 if( !first )
1589 {
1590 if( fe->m_p1.x == x_min )
1591 border_edges.push_back( fe );
1592 }
1593
1594 if( !fe->m_connected )
1595 num_unconnected++;
1596 }
1597
1598 first = false; // first path is always the outline
1599 }
1600
1601 // keep connecting holes to the main outline, until there's no holes left...
1602 while( num_unconnected > 0 )
1603 {
1604 int x_min = std::numeric_limits<int>::max();
1605 auto it = border_edges.begin();
1606
1607 FractureEdgeSlow* smallestX = nullptr;
1608
1609 // find the left-most hole edge and merge with the outline
1610 for( ; it != border_edges.end(); ++it )
1611 {
1612 FractureEdgeSlow* border_edge = *it;
1613 int xt = border_edge->m_p1.x;
1614
1615 if( ( xt <= x_min ) && !border_edge->m_connected )
1616 {
1617 x_min = xt;
1618 smallestX = border_edge;
1619 }
1620 }
1621
1622 int num_processed = processEdge( edges, smallestX );
1623
1624 // If we can't handle the edge, the zone is broken (maybe)
1625 if( !num_processed )
1626 {
1627 wxLogWarning( wxT( "Broken polygon, dropping path" ) );
1628
1629 for( FractureEdgeSlow* edge : edges )
1630 delete edge;
1631
1632 return;
1633 }
1634
1635 num_unconnected -= num_processed;
1636 }
1637
1638 paths.clear();
1639 SHAPE_LINE_CHAIN newPath;
1640
1641 newPath.SetClosed( true );
1642
1644
1645 for( e = root; e->m_next != root; e = e->m_next )
1646 newPath.Append( e->m_p1 );
1647
1648 newPath.Append( e->m_p1 );
1649
1650 for( FractureEdgeSlow* edge : edges )
1651 delete edge;
1652
1653 paths.push_back( std::move( newPath ) );
1654}
1655
1656
1658{
1660 return fractureSingleCacheFriendly( paths );
1661 fractureSingleSlow( paths );
1662}
1663
1664
1666{
1667 Simplify(); // remove overlapping holes/degeneracy
1668
1669 for( POLYGON& paths : m_polys )
1670 fractureSingle( paths );
1671}
1672
1673
1675{
1676 assert( aPoly.size() == 1 );
1677
1678 struct EDGE
1679 {
1680 int m_index = 0;
1681 SHAPE_LINE_CHAIN* m_poly = nullptr;
1682 bool m_duplicate = false;
1683
1684 EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
1685 m_index( aIndex ),
1686 m_poly( aPolygon )
1687 {}
1688
1689 bool compareSegs( const SEG& s1, const SEG& s2 ) const
1690 {
1691 return (s1.A == s2.B && s1.B == s2.A);
1692 }
1693
1694 bool operator==( const EDGE& aOther ) const
1695 {
1696 return compareSegs( m_poly->CSegment( m_index ),
1697 aOther.m_poly->CSegment( aOther.m_index ) );
1698 }
1699
1700 bool operator!=( const EDGE& aOther ) const
1701 {
1702 return !compareSegs( m_poly->CSegment( m_index ),
1703 aOther.m_poly->CSegment( aOther.m_index ) );
1704 }
1705
1706 struct HASH
1707 {
1708 std::size_t operator()( const EDGE& aEdge ) const
1709 {
1710 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1711 std::size_t seed = 0xa82de1c0;
1712 hash_combine( seed, a.A.x, a.B.x, a.A.y, a.B.y );
1713 return seed;
1714 }
1715 };
1716 };
1717
1718 struct EDGE_LIST_ENTRY
1719 {
1720 int index;
1721 EDGE_LIST_ENTRY* next;
1722 };
1723
1724 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1725
1726 SHAPE_LINE_CHAIN lc = aPoly[0];
1727 lc.Simplify();
1728
1729 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.SegmentCount() );
1730
1731 for( int i = 0; i < lc.SegmentCount(); i++ )
1732 {
1733 edgeList[i].index = i;
1734 edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
1735 }
1736
1737 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1738
1739 for( int i = 0; i < lc.SegmentCount(); i++ )
1740 {
1741 EDGE e( &lc, i );
1742 uniqueEdges.insert( e );
1743 }
1744
1745 for( int i = 0; i < lc.SegmentCount(); i++ )
1746 {
1747 EDGE e( &lc, i );
1748 auto it = uniqueEdges.find( e );
1749
1750 if( it != uniqueEdges.end() && it->m_index != i )
1751 {
1752 int e1 = it->m_index;
1753 int e2 = i;
1754
1755 if( e1 > e2 )
1756 std::swap( e1, e2 );
1757
1758 int e1_prev = e1 - 1;
1759
1760 if( e1_prev < 0 )
1761 e1_prev = lc.SegmentCount() - 1;
1762
1763 int e2_prev = e2 - 1;
1764
1765 if( e2_prev < 0 )
1766 e2_prev = lc.SegmentCount() - 1;
1767
1768 int e1_next = e1 + 1;
1769
1770 if( e1_next == lc.SegmentCount() )
1771 e1_next = 0;
1772
1773 int e2_next = e2 + 1;
1774
1775 if( e2_next == lc.SegmentCount() )
1776 e2_next = 0;
1777
1778 edgeList[e1_prev].next = &edgeList[ e2_next ];
1779 edgeList[e2_prev].next = &edgeList[ e1_next ];
1780 edgeList[i].next = nullptr;
1781 edgeList[it->m_index].next = nullptr;
1782 }
1783 }
1784
1785 for( int i = 0; i < lc.SegmentCount(); i++ )
1786 {
1787 if( edgeList[i].next )
1788 queue.insert( &edgeList[i] );
1789 }
1790
1791 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1792
1793 int n = 0;
1794 int outline = -1;
1795
1797 double max_poly = 0.0;
1798
1799 while( queue.size() )
1800 {
1801 EDGE_LIST_ENTRY* e_first = *queue.begin();
1802 EDGE_LIST_ENTRY* e = e_first;
1803 int cnt = 0;
1804
1805 do
1806 {
1807 edgeBuf[cnt++] = e;
1808 e = e->next;
1809 } while( e && e != e_first );
1810
1811 SHAPE_LINE_CHAIN outl;
1812
1813 for( int i = 0; i < cnt; i++ )
1814 {
1815 VECTOR2I p = lc.CPoint( edgeBuf[i]->index );
1816 outl.Append( p );
1817 queue.erase( edgeBuf[i] );
1818 }
1819
1820 outl.SetClosed( true );
1821
1822 double area = std::fabs( outl.Area() );
1823
1824 if( area > max_poly )
1825 {
1826 outline = n;
1827 max_poly = area;
1828 }
1829
1830 result.push_back( outl );
1831 n++;
1832 }
1833
1834 if( outline > 0 )
1835 std::swap( result[0], result[outline] );
1836
1837 aPoly = std::move( result );
1838}
1839
1840
1842{
1843 // Iterate through all the polygons on the set
1844 for( const POLYGON& paths : m_polys )
1845 {
1846 // If any of them has more than one contour, it is a hole.
1847 if( paths.size() > 1 )
1848 return true;
1849 }
1850
1851 // Return false if and only if every polygon has just one outline, without holes.
1852 return false;
1853}
1854
1855
1857{
1858 for( POLYGON& path : m_polys )
1860
1861 Simplify(); // remove overlapping holes/degeneracy
1862}
1863
1864
1865bool SHAPE_POLY_SET::isExteriorWaist( const SEG& aSegA, const SEG& aSegB ) const
1866{
1867 const VECTOR2I da = aSegA.B - aSegA.A;
1868
1869 int axis = std::abs( da.x ) >= std::abs( da.y ) ? 0 : 1;
1870
1871 std::array<VECTOR2I,4> pts = { aSegA.A, aSegA.B, aSegB.A, aSegB.B };
1872
1873 std::sort( pts.begin(), pts.end(), [axis]( const VECTOR2I& p, const VECTOR2I& q )
1874 {
1875 if( axis == 0 )
1876 return p.x < q.x || ( p.x == q.x && p.y < q.y );
1877 else
1878 return p.y < q.y || ( p.y == q.y && p.x < q.x );
1879 } );
1880
1881 VECTOR2I s = pts[1];
1882 VECTOR2I e = pts[2];
1883
1884 // Check if there is polygon material on either side of the overlapping segments
1885 // Get the midpoint between s and e for testing
1886 VECTOR2I midpoint = ( s + e ) / 2;
1887
1888 // Create perpendicular offset vector to check both sides
1889 VECTOR2I segDir = e - s;
1890
1891 if( segDir.EuclideanNorm() > 0 )
1892 {
1893 VECTOR2I perp = segDir.Perpendicular().Resize( 10 );
1894
1895 // Test points on both sides of the overlapping segment
1896 bool side1 = PointInside( midpoint + perp );
1897 bool side2 = PointInside( midpoint - perp );
1898
1899 // Only return true if both sides are outside the polygon
1900 // This is the case for non-fractured segments
1901 if( !side1 && !side2 )
1902 return true;
1903 }
1904
1905 return false;
1906}
1907
1908
1910{
1911 for( size_t polyIdx = 0; polyIdx < m_polys.size(); ++polyIdx )
1912 {
1913 bool changed = true;
1914
1915 while( changed )
1916 {
1917 changed = false;
1918
1919 SHAPE_LINE_CHAIN& outline = m_polys[polyIdx][0];
1920 intptr_t count = outline.PointCount();
1921
1922 RTree<intptr_t, intptr_t, 2, intptr_t> rtree;
1923
1924 for( intptr_t i = 0; i < count; ++i )
1925 {
1926 const VECTOR2I& a = outline.CPoint( i );
1927 const VECTOR2I& b = outline.CPoint( ( i + 1 ) % count );
1928 intptr_t min[2] = { std::min( a.x, b.x ), std::min( a.y, b.y ) };
1929 intptr_t max[2] = { std::max( a.x, b.x ), std::max( a.y, b.y ) };
1930 rtree.Insert( min, max, i );
1931 }
1932
1933 bool found = false;
1934 int segA = -1;
1935 int segB = -1;
1936
1937 for( intptr_t i = 0; i < count && !found; ++i )
1938 {
1939 const VECTOR2I& a = outline.CPoint( i );
1940 const VECTOR2I& b = outline.CPoint( ( i + 1 ) % count );
1941 SEG seg( a, b );
1942 intptr_t min[2] = { std::min( a.x, b.x ), std::min( a.y, b.y ) };
1943 intptr_t max[2] = { std::max( a.x, b.x ), std::max( a.y, b.y ) };
1944
1945 auto visitor =
1946 [&]( const int& j ) -> bool
1947 {
1948 if( j == i || j == ( ( i + 1 ) % count ) || j == ( ( i + count - 1 ) % count ) )
1949 return true;
1950
1951 VECTOR2I oa = outline.CPoint( j );
1952 VECTOR2I ob = outline.CPoint( ( j + 1 ) % count );
1953 SEG other( oa, ob );
1954
1955 // Skip segments that share start/end points. This is the case for
1956 // fractured segments
1957 if( oa == a && ob == b )
1958 return true;
1959
1960 if( oa == b && ob == a )
1961 return true;
1962
1963 if( seg.ApproxCollinear( other, 10 ) && isExteriorWaist( seg, other ) )
1964 {
1965 segA = i;
1966 segB = j;
1967 found = true;
1968 return false;
1969 }
1970
1971 return true;
1972 };
1973
1974 rtree.Search( min, max, visitor );
1975 }
1976
1977 if( !found )
1978 break;
1979
1980 int a0 = segA;
1981 int a1 = ( segA + 1 ) % outline.PointCount();
1982 int b0 = segB;
1983 int b1 = ( segB + 1 ) % outline.PointCount();
1984
1985 SHAPE_LINE_CHAIN lc1;
1986 int idx = a1;
1987 lc1.Append( outline.CPoint( idx ) );
1988
1989 while( idx != b0 )
1990 {
1991 idx = ( idx + 1 ) % outline.PointCount();
1992 lc1.Append( outline.CPoint( idx ) );
1993 }
1994
1995 lc1.SetClosed( true );
1996
1997 SHAPE_LINE_CHAIN lc2;
1998 idx = b1;
1999 lc2.Append( outline.CPoint( idx ) );
2000
2001 while( idx != a0 )
2002 {
2003 idx = ( idx + 1 ) % outline.PointCount();
2004 lc2.Append( outline.CPoint( idx ) );
2005 }
2006
2007 lc2.SetClosed( true );
2008
2009 m_polys[polyIdx][0] = std::move( lc1 );
2010
2011 POLYGON np;
2012 np.push_back( std::move( lc2 ) );
2013 m_polys.push_back( std::move( np ) );
2014
2015 changed = true;
2016 }
2017 }
2018}
2019
2020
2022{
2024
2026
2027 booleanOp( Clipper2Lib::ClipType::Union, empty );
2028}
2029
2030
2032{
2033 for( POLYGON& paths : m_polys )
2034 {
2035 for( SHAPE_LINE_CHAIN& path : paths )
2036 {
2037 path.Simplify( aTolerance );
2038 }
2039 }
2040}
2041
2042
2044{
2045 // We are expecting only one main outline, but this main outline can have holes
2046 // if holes: combine holes and remove them from the main outline.
2047 // Note also we are usingin polygon
2048 // calculations, but it is not mandatory. It is used mainly
2049 // because there is usually only very few vertices in area outlines
2050 SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
2051 SHAPE_POLY_SET holesBuffer;
2052
2053 // Move holes stored in outline to holesBuffer:
2054 // The first SHAPE_LINE_CHAIN is the main outline, others are holes
2055 while( outline.size() > 1 )
2056 {
2057 holesBuffer.AddOutline( outline.back() );
2058 outline.pop_back();
2059 }
2060
2061 Simplify();
2062
2063 // If any hole, subtract it to main outline
2064 if( holesBuffer.OutlineCount() )
2065 {
2066 holesBuffer.Simplify();
2067 BooleanSubtract( holesBuffer );
2068 }
2069
2070 // In degenerate cases, simplify might return no outlines
2071 if( OutlineCount() > 0 )
2073
2074 return OutlineCount();
2075}
2076
2077
2078const std::string SHAPE_POLY_SET::Format( bool aCplusPlus ) const
2079{
2080 std::stringstream ss;
2081
2082 ss << "SHAPE_LINE_CHAIN poly; \n";
2083
2084 for( unsigned i = 0; i < m_polys.size(); i++ )
2085 {
2086 for( unsigned j = 0; j < m_polys[i].size(); j++ )
2087 {
2088
2089 ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
2090
2091 SHAPE_POLY_SET poly;
2092
2093 if( j == 0 )
2094 {
2095 ss << " poly.AddOutline(tmp); } \n";
2096 }
2097 else
2098 {
2099 ss << " poly.AddHole(tmp); } \n";
2100 }
2101
2102 }
2103 }
2104
2105 return ss.str();
2106}
2107
2108
2109bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
2110{
2111 std::string tmp;
2112
2113 aStream >> tmp;
2114
2115 if( tmp != "polyset" )
2116 return false;
2117
2118 aStream >> tmp;
2119
2120 int n_polys = atoi( tmp.c_str() );
2121
2122 if( n_polys < 0 )
2123 return false;
2124
2125 for( int i = 0; i < n_polys; i++ )
2126 {
2127 POLYGON paths;
2128
2129 aStream >> tmp;
2130
2131 if( tmp != "poly" )
2132 return false;
2133
2134 aStream >> tmp;
2135 int n_outlines = atoi( tmp.c_str() );
2136
2137 if( n_outlines < 0 )
2138 return false;
2139
2140 for( int j = 0; j < n_outlines; j++ )
2141 {
2142 SHAPE_LINE_CHAIN outline;
2143
2144 outline.SetClosed( true );
2145
2146 aStream >> tmp;
2147 int n_vertices = atoi( tmp.c_str() );
2148
2149 for( int v = 0; v < n_vertices; v++ )
2150 {
2151 VECTOR2I p;
2152
2153 aStream >> tmp; p.x = atoi( tmp.c_str() );
2154 aStream >> tmp; p.y = atoi( tmp.c_str() );
2155 outline.Append( p );
2156 }
2157
2158 paths.push_back( std::move( outline ) );
2159 }
2160
2161 m_polys.push_back( std::move( paths ) );
2162 }
2163
2164 return true;
2165}
2166
2167
2168const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
2169{
2170 BOX2I bb;
2171
2172 for( unsigned i = 0; i < m_polys.size(); i++ )
2173 {
2174 if( i == 0 )
2175 bb = m_polys[i][0].BBox();
2176 else
2177 bb.Merge( m_polys[i][0].BBox() );
2178 }
2179
2180 bb.Inflate( aClearance );
2181 return bb;
2182}
2183
2184
2186{
2187 BOX2I bb;
2188
2189 for( unsigned i = 0; i < m_polys.size(); i++ )
2190 {
2191 if( i == 0 )
2192 bb = *m_polys[i][0].GetCachedBBox();
2193 else
2194 bb.Merge( *m_polys[i][0].GetCachedBBox() );
2195 }
2196
2197 return bb;
2198}
2199
2200
2201bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP, int aAccuracy ) const
2202{
2203 // Iterate through all the polygons in the set
2204 for( const POLYGON& polygon : m_polys )
2205 {
2206 // Iterate through all the line chains in the polygon
2207 for( const SHAPE_LINE_CHAIN& lineChain : polygon )
2208 {
2209 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2210 return true;
2211 }
2212 }
2213
2214 return false;
2215}
2216
2217
2218bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance, int* aActual,
2219 VECTOR2I* aLocation ) const
2220{
2221 VECTOR2I nearest;
2222 ecoord dist_sq = SquaredDistanceToSeg( aSeg, aLocation ? &nearest : nullptr );
2223
2224 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
2225 {
2226 if( aLocation )
2227 *aLocation = nearest;
2228
2229 if( aActual )
2230 *aActual = sqrt( dist_sq );
2231
2232 return true;
2233 }
2234
2235 return false;
2236}
2237
2238
2239bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
2240 VECTOR2I* aLocation ) const
2241{
2242 if( IsEmpty() || VertexCount() == 0 )
2243 return false;
2244
2245 VECTOR2I nearest;
2246 ecoord dist_sq = SquaredDistance( aP, false, aLocation ? &nearest : nullptr );
2247
2248 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
2249 {
2250 if( aLocation )
2251 *aLocation = nearest;
2252
2253 if( aActual )
2254 *aActual = sqrt( dist_sq );
2255
2256 return true;
2257 }
2258
2259 return false;
2260}
2261
2262
2263bool SHAPE_POLY_SET::Collide( const SHAPE* aShape, int aClearance, int* aActual,
2264 VECTOR2I* aLocation ) const
2265{
2266 // A couple of simple cases are worth trying before we fall back on triangulation.
2267
2268 if( aShape->Type() == SH_SEGMENT )
2269 {
2270 const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
2271 int extra = segment->GetWidth() / 2;
2272
2273 if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
2274 {
2275 if( aActual )
2276 *aActual = std::max( 0, *aActual - extra );
2277
2278 return true;
2279 }
2280
2281 return false;
2282 }
2283
2284 if( aShape->Type() == SH_CIRCLE )
2285 {
2286 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
2287 int extra = circle->GetRadius();
2288
2289 if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
2290 {
2291 if( aActual )
2292 *aActual = std::max( 0, *aActual - extra );
2293
2294 return true;
2295 }
2296
2297 return false;
2298 }
2299
2300 const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( false );
2301
2302 int actual = INT_MAX;
2304
2305 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
2306 {
2307 for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
2308 {
2309 if( aActual || aLocation )
2310 {
2311 int triActual;
2312 VECTOR2I triLocation;
2313
2314 if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
2315 {
2316 if( triActual < actual )
2317 {
2318 actual = triActual;
2319 location = triLocation;
2320 }
2321 }
2322 }
2323 else // A much faster version of above
2324 {
2325 if( aShape->Collide( &tri, aClearance ) )
2326 return true;
2327 }
2328 }
2329 }
2330
2331 if( actual < INT_MAX )
2332 {
2333 if( aActual )
2334 *aActual = std::max( 0, actual );
2335
2336 if( aLocation )
2337 *aLocation = location;
2338
2339 return true;
2340 }
2341
2342 return false;
2343}
2344
2345
2347{
2348 m_polys.clear();
2349 m_triangulatedPolys.clear();
2350 m_triangulationValid = false;
2351}
2352
2353
2354void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
2355{
2356 // Default polygon is the last one
2357 if( aPolygonIdx < 0 )
2358 aPolygonIdx += m_polys.size();
2359
2360 m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
2361}
2362
2363
2364void SHAPE_POLY_SET::RemoveOutline( int aOutlineIdx )
2365{
2366 m_polys.erase( m_polys.begin() + aOutlineIdx );
2367}
2368
2369
2371{
2372 int removed = 0;
2373
2374 ITERATOR iterator = IterateWithHoles();
2375
2376 VECTOR2I contourStart = *iterator;
2377 VECTOR2I segmentStart, segmentEnd;
2378
2379 VERTEX_INDEX indexStart;
2380 std::vector<VERTEX_INDEX> indices_to_remove;
2381
2382 while( iterator )
2383 {
2384 // Obtain first point and its index
2385 segmentStart = *iterator;
2386 indexStart = iterator.GetIndex();
2387
2388 // Obtain last point
2389 if( iterator.IsEndContour() )
2390 {
2391 segmentEnd = contourStart;
2392
2393 // Advance
2394 iterator++;
2395
2396 // If we have rolled into the next contour, remember its position
2397 // segmentStart and segmentEnd remain valid for comparison here
2398 if( iterator )
2399 contourStart = *iterator;
2400 }
2401 else
2402 {
2403 // Advance
2404 iterator++;
2405
2406 // If we have reached the end of the SHAPE_POLY_SET, something is broken here
2407 wxCHECK_MSG( iterator, removed, wxT( "Invalid polygon. Reached end without noticing. Please report this error" ) );
2408
2409 segmentEnd = *iterator;
2410 }
2411
2412 // Remove segment start if both points are equal
2413 if( segmentStart == segmentEnd )
2414 {
2415 indices_to_remove.push_back( indexStart );
2416 removed++;
2417 }
2418 }
2419
2420 // Proceed in reverse direction to remove the vertices because they are stored as absolute indices in a vector
2421 // Removing in reverse order preserves the remaining index values
2422 for( auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2423 RemoveVertex( *it );
2424
2425 return removed;
2426}
2427
2428
2430{
2431 m_polys.erase( m_polys.begin() + aIdx );
2432}
2433
2434
2436{
2437 m_polys.erase( m_polys.begin() + aIdx );
2438
2440 {
2441 for( int ii = m_triangulatedPolys.size() - 1; ii >= 0; --ii )
2442 {
2443 std::unique_ptr<TRIANGULATED_POLYGON>& triangleSet = m_triangulatedPolys[ii];
2444
2445 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2446 m_triangulatedPolys.erase( m_triangulatedPolys.begin() + ii );
2447 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2448 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2449 }
2450
2451 if( aUpdateHash )
2452 {
2453 m_hash = checksum();
2454 m_hashValid = true;
2455 }
2456 }
2457}
2458
2459
2465
2466
2468{
2469 m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
2470}
2471
2472
2473void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
2474{
2475 Append( aP.x, aP.y, aOutline, aHole );
2476}
2477
2478
2480 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
2481 int aClearance ) const
2482{
2483 // Shows whether there was a collision
2484 bool collision = false;
2485
2486 // Difference vector between each vertex and aPoint.
2488 ecoord distance_squared;
2489 ecoord clearance_squared = SEG::Square( aClearance );
2490
2491 for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
2492 {
2493 // Get the difference vector between current vertex and aPoint
2494 delta = *iterator - aPoint;
2495
2496 // Compute distance
2497 distance_squared = delta.SquaredEuclideanNorm();
2498
2499 // Check for collisions
2500 if( distance_squared <= clearance_squared )
2501 {
2502 if( !aClosestVertex )
2503 return true;
2504
2505 collision = true;
2506
2507 // Update clearance to look for closer vertices
2508 clearance_squared = distance_squared;
2509
2510 // Store the indices that identify the vertex
2511 *aClosestVertex = iterator.GetIndex();
2512 }
2513 }
2514
2515 return collision;
2516}
2517
2518
2520 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
2521 int aClearance ) const
2522{
2523 // Shows whether there was a collision
2524 bool collision = false;
2525 ecoord clearance_squared = SEG::Square( aClearance );
2526
2527 for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
2528 {
2529 const SEG currentSegment = *iterator;
2530 ecoord distance_squared = currentSegment.SquaredDistance( aPoint );
2531
2532 // Check for collisions
2533 if( distance_squared <= clearance_squared )
2534 {
2535 if( !aClosestVertex )
2536 return true;
2537
2538 collision = true;
2539
2540 // Update clearance to look for closer edges
2541 clearance_squared = distance_squared;
2542
2543 // Store the indices that identify the vertex
2544 *aClosestVertex = iterator.GetIndex();
2545 }
2546 }
2547
2548 return collision;
2549}
2550
2551
2553{
2554 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
2555 {
2556 COutline( polygonIdx ).GenerateBBoxCache();
2557
2558 for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
2559 CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
2560 }
2561}
2562
2563
2564bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
2565 bool aUseBBoxCaches ) const
2566{
2567 if( m_polys.empty() )
2568 return false;
2569
2570 // If there is a polygon specified, check the condition against that polygon
2571 if( aSubpolyIndex >= 0 )
2572 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2573
2574 // In any other case, check it against all polygons in the set
2575 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
2576 {
2577 if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2578 return true;
2579 }
2580
2581 return false;
2582}
2583
2584
2585void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
2586{
2587 VERTEX_INDEX index;
2588
2589 // Assure the to be removed vertex exists, abort otherwise
2590 if( GetRelativeIndices( aGlobalIndex, &index ) )
2591 RemoveVertex( index );
2592 else
2593 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
2594}
2595
2596
2598{
2599 m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
2600}
2601
2602
2603void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
2604{
2605 VERTEX_INDEX index;
2606
2607 if( GetRelativeIndices( aGlobalIndex, &index ) )
2608 SetVertex( index, aPos );
2609 else
2610 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
2611}
2612
2613
2614void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
2615{
2616 m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
2617}
2618
2619
2620bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
2621 bool aUseBBoxCaches ) const
2622{
2623 // Check that the point is inside the outline
2624 if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
2625 {
2626 // Check that the point is not in any of the holes
2627 for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
2628 {
2629 const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
2630
2631 // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
2632 // here as it's meaning would be inverted.
2633 if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
2634 return false;
2635 }
2636
2637 return true;
2638 }
2639
2640 return false;
2641}
2642
2643
2644void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
2645{
2646 for( POLYGON& poly : m_polys )
2647 {
2648 for( SHAPE_LINE_CHAIN& path : poly )
2649 path.Move( aVector );
2650 }
2651
2652 for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
2653 tri->Move( aVector );
2654
2655 m_hash = checksum();
2656 m_hashValid = true;
2657}
2658
2659
2660void SHAPE_POLY_SET::Mirror( const VECTOR2I& aRef, FLIP_DIRECTION aFlipDirection )
2661{
2662 for( POLYGON& poly : m_polys )
2663 {
2664 for( SHAPE_LINE_CHAIN& path : poly )
2665 path.Mirror( aRef, aFlipDirection );
2666 }
2667
2670}
2671
2672
2673void SHAPE_POLY_SET::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
2674{
2675 for( POLYGON& poly : m_polys )
2676 {
2677 for( SHAPE_LINE_CHAIN& path : poly )
2678 path.Rotate( aAngle, aCenter );
2679 }
2680
2681 // Don't re-cache if the triangulation is already invalid
2684}
2685
2686
2688{
2689 int c = 0;
2690
2691 for( const POLYGON& poly : m_polys )
2692 {
2693 for( const SHAPE_LINE_CHAIN& path : poly )
2694 c += path.PointCount();
2695 }
2696
2697 return c;
2698}
2699
2700
2701SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
2702{
2703 return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
2704}
2705
2706
2707SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
2708 int aIndex )
2709{
2710 return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
2711}
2712
2713
2715 VECTOR2I* aNearest ) const
2716{
2717 // We calculate the min dist between the segment and each outline segment. However, if the
2718 // segment to test is inside the outline, and does not cross any edge, it can be seen outside
2719 // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
2720 // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
2721 if( containsSingle( aPoint, aPolygonIndex, 1 ) )
2722 {
2723 if( aNearest )
2724 *aNearest = aPoint;
2725
2726 return 0;
2727 }
2728
2729 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
2730
2731 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2732
2733 for( iterator++; iterator && minDistance > 0; iterator++ )
2734 {
2735 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2736
2737 if( currentDistance < minDistance )
2738 {
2739 if( aNearest )
2740 *aNearest = (*iterator).NearestPoint( aPoint );
2741
2742 minDistance = currentDistance;
2743 }
2744 }
2745
2746 return minDistance;
2747}
2748
2749
2751 VECTOR2I* aNearest ) const
2752{
2753 // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
2754 if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
2755 containsSingle( aSegment.B, aPolygonIndex, 1 ) )
2756 {
2757 if( aNearest )
2758 *aNearest = ( aSegment.A + aSegment.B ) / 2;
2759
2760 return 0;
2761 }
2762
2763 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
2764 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2765
2766 if( aNearest && minDistance == 0 )
2767 *aNearest = ( *iterator ).NearestPoint( aSegment );
2768
2769 for( iterator++; iterator && minDistance > 0; iterator++ )
2770 {
2771 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2772
2773 if( currentDistance < minDistance )
2774 {
2775 if( aNearest )
2776 *aNearest = (*iterator).NearestPoint( aSegment );
2777
2778 minDistance = currentDistance;
2779 }
2780 }
2781
2782 // Return the maximum of minDistance and zero
2783 return minDistance < 0 ? 0 : minDistance;
2784}
2785
2786
2787SEG::ecoord SHAPE_POLY_SET::SquaredDistance( const VECTOR2I& aPoint, bool aOutlineOnly,
2788 VECTOR2I* aNearest ) const
2789{
2790 wxASSERT_MSG( !aOutlineOnly, wxT( "Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2791 "support aOutlineOnly==true" ) );
2792
2793 SEG::ecoord currentDistance_sq;
2794 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2795 VECTOR2I nearest;
2796
2797 // Iterate through all the polygons and get the minimum distance.
2798 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2799 {
2800 currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
2801 aNearest ? &nearest : nullptr );
2802
2803 if( currentDistance_sq < minDistance_sq )
2804 {
2805 if( aNearest )
2806 *aNearest = nearest;
2807
2808 minDistance_sq = currentDistance_sq;
2809 }
2810 }
2811
2812 return minDistance_sq;
2813}
2814
2815
2817{
2818 SEG::ecoord currentDistance_sq;
2819 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2820 VECTOR2I nearest;
2821
2822 // Iterate through all the polygons and get the minimum distance.
2823 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2824 {
2825 currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
2826 aNearest ? &nearest : nullptr );
2827
2828 if( currentDistance_sq < minDistance_sq )
2829 {
2830 if( aNearest )
2831 *aNearest = nearest;
2832
2833 minDistance_sq = currentDistance_sq;
2834 }
2835 }
2836
2837 return minDistance_sq;
2838}
2839
2840
2842{
2843 VERTEX_INDEX index;
2844
2845 // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
2846 if( !GetRelativeIndices( aGlobalIdx, &index ) )
2847 return false;
2848
2849 // The contour is a hole if its index is greater than zero
2850 return index.m_contour > 0;
2851}
2852
2853
2855{
2856 SHAPE_POLY_SET chamfered;
2857
2858 for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
2859 chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
2860
2861 return chamfered;
2862}
2863
2864
2865SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
2866{
2867 SHAPE_POLY_SET filleted;
2868
2869 for( size_t idx = 0; idx < m_polys.size(); idx++ )
2870 filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
2871
2872 return filleted;
2873}
2874
2875
2877{
2878 SHAPE::operator=( aOther );
2879 m_polys = aOther.m_polys;
2880
2881 m_triangulatedPolys.clear();
2882
2883 if( aOther.IsTriangulationUpToDate() )
2884 {
2885 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
2886
2887 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2888 {
2889 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2890 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2891 }
2892
2893 m_hash = aOther.m_hash;
2894 m_hashValid = aOther.m_hashValid;
2896 }
2897 else
2898 {
2899 m_hash.Clear();
2900 m_hashValid = false;
2901 m_triangulationValid = false;
2902 }
2903
2904 return *this;
2905}
2906
2907
2909{
2910 if( !m_hashValid )
2911 return checksum();
2912
2913 return m_hash;
2914}
2915
2916
2918{
2920 return false;
2921
2922 if( !m_hashValid )
2923 return false;
2924
2925 HASH_128 hash = checksum();
2926
2927 return hash == m_hash;
2928}
2929
2930
2932{
2933 BOX2I bb = aPoly.BBox();
2934
2935 double w = bb.GetWidth();
2936 double h = bb.GetHeight();
2937
2938 if( w == 0.0 || h == 0.0 )
2939 return aPoly;
2940
2941 int n_cells_x, n_cells_y;
2942
2943 if( w > h )
2944 {
2945 n_cells_x = w / aSize;
2946 n_cells_y = floor( h / w * n_cells_x ) + 1;
2947 }
2948 else
2949 {
2950 n_cells_y = h / aSize;
2951 n_cells_x = floor( w / h * n_cells_y ) + 1;
2952 }
2953
2954 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2955
2956 for( int yy = 0; yy < n_cells_y; yy++ )
2957 {
2958 for( int xx = 0; xx < n_cells_x; xx++ )
2959 {
2960 VECTOR2I p;
2961
2962 p.x = bb.GetX() + w * xx / n_cells_x;
2963 p.y = bb.GetY() + h * yy / n_cells_y;
2964
2965 VECTOR2I p2;
2966
2967 p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
2968 p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
2969
2970
2971 SHAPE_LINE_CHAIN mask;
2972 mask.Append( VECTOR2I( p.x, p.y ) );
2973 mask.Append( VECTOR2I( p2.x, p.y ) );
2974 mask.Append( VECTOR2I( p2.x, p2.y ) );
2975 mask.Append( VECTOR2I( p.x, p2.y ) );
2976 mask.SetClosed( true );
2977
2978 if( ( xx ^ yy ) & 1 )
2979 maskSetOdd.AddOutline( mask );
2980 else
2981 maskSetEven.AddOutline( mask );
2982 }
2983 }
2984
2985 ps1.BooleanIntersection( maskSetOdd );
2986 ps2.BooleanIntersection( maskSetEven );
2987 ps1.Fracture();
2988 ps2.Fracture();
2989
2990 for( int i = 0; i < ps2.OutlineCount(); i++ )
2991 ps1.AddOutline( ps2.COutline( i ) );
2992
2993 if( ps1.OutlineCount() )
2994 return ps1;
2995 else
2996 return aPoly;
2997}
2998
2999
3000void SHAPE_POLY_SET::cacheTriangulation( bool aPartition, bool aSimplify,
3001 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3002{
3003 std::unique_lock<std::mutex> lock( m_triangulationMutex );
3004
3006 {
3007 if( m_hash == checksum() )
3008 return;
3009 }
3010
3011 // Invalidate, in case anything goes wrong below
3012 m_triangulationValid = false;
3013 m_hashValid = false;
3014
3015 auto triangulate =
3016 []( SHAPE_POLY_SET& polySet, int forOutline,
3017 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3018 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3019 {
3020 bool triangulationValid = false;
3021 int pass = 0;
3022 int index = 0;
3023
3024 if( hintData && hintData->size() != (unsigned) polySet.OutlineCount() )
3025 hintData = nullptr;
3026
3027 while( polySet.OutlineCount() > 0 )
3028 {
3029 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3030 dest.erase( dest.end() - 1 );
3031
3032 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3033 POLYGON_TRIANGULATION tess( *dest.back() );
3034
3035 // If the tessellation fails, we re-fracture the polygon, which will
3036 // first simplify the system before fracturing and removing the holes
3037 // This may result in multiple, disjoint polygons.
3038 if( !tess.TesselatePolygon( polySet.Polygon( 0 ).front(),
3039 hintData ? hintData->at( index ).get() : nullptr ) )
3040 {
3041 ++pass;
3042
3043 if( pass == 1 )
3044 {
3046 }
3047 // In Clipper2, there is only one type of simplification
3048 else
3049 {
3050 break;
3051 }
3052
3053 triangulationValid = false;
3054 hintData = nullptr;
3055 continue;
3056 }
3057
3058 polySet.DeletePolygon( 0 );
3059 index++;
3060 triangulationValid = true;
3061 }
3062
3063 return triangulationValid;
3064 };
3065
3066 m_triangulatedPolys.clear();
3067
3068 if( aPartition )
3069 {
3070 for( int ii = 0; ii < OutlineCount(); ++ii )
3071 {
3072 // This partitions into regularly-sized grids (1cm in Pcbnew)
3073 SHAPE_POLY_SET flattened( Outline( ii ) );
3074
3075 for( int jj = 0; jj < HoleCount( ii ); ++jj )
3076 flattened.AddHole( Hole( ii, jj ) );
3077
3078 flattened.ClearArcs();
3079
3080 if( flattened.HasHoles() || flattened.IsSelfIntersecting() )
3081 flattened.Fracture();
3082 else if( aSimplify )
3083 flattened.Simplify();
3084
3085 SHAPE_POLY_SET partitions = partitionPolyIntoRegularCellGrid( flattened, 1e7 );
3086
3087 // This pushes the triangulation for all polys in partitions
3088 // to be referenced to the ii-th polygon
3089 if( !triangulate( partitions, ii , m_triangulatedPolys, aHintData ) )
3090 {
3091 wxLogTrace( TRIANGULATE_TRACE, "Failed to triangulate partitioned polygon %d", ii );
3092 }
3093 else
3094 {
3095 m_hash = checksum();
3096 m_hashValid = true;
3097 // Set valid flag only after everything has been updated
3098 m_triangulationValid = true;
3099 }
3100 }
3101 }
3102 else
3103 {
3104 SHAPE_POLY_SET tmpSet( *this );
3105
3106 tmpSet.ClearArcs();
3107 tmpSet.Fracture();
3108
3109 if( !triangulate( tmpSet, -1, m_triangulatedPolys, aHintData ) )
3110 {
3111 wxLogTrace( TRIANGULATE_TRACE, "Failed to triangulate polygon" );
3112 }
3113 else
3114 {
3115 m_hash = checksum();
3116 m_hashValid = true;
3117 // Set valid flag only after everything has been updated
3118 m_triangulationValid = true;
3119 }
3120 }
3121}
3122
3123
3125{
3126 MMH3_HASH hash( 0x68AF835D ); // Arbitrary seed
3127
3128 hash.add( m_polys.size() );
3129
3130 for( const POLYGON& outline : m_polys )
3131 {
3132 hash.add( outline.size() );
3133
3134 for( const SHAPE_LINE_CHAIN& lc : outline )
3135 {
3136 hash.add( lc.PointCount() );
3137
3138 for( int i = 0; i < lc.PointCount(); i++ )
3139 {
3140 VECTOR2I pt = lc.CPoint( i );
3141
3142 hash.add( pt.x );
3143 hash.add( pt.y );
3144 }
3145 }
3146 }
3147
3148 return hash.digest();
3149}
3150
3151
3153{
3154 for( int i = 0; i < OutlineCount(); i++ )
3155 {
3156 if( hasTouchingHoles( CPolygon( i ) ) )
3157 return true;
3158 }
3159
3160 return false;
3161}
3162
3163
3165{
3166 std::set<long long> ptHashes;
3167
3168 for( const SHAPE_LINE_CHAIN& lc : aPoly )
3169 {
3170 for( const VECTOR2I& pt : lc.CPoints() )
3171 {
3172 const long long ptHash = (long long) pt.x << 32 | pt.y;
3173
3174 if( ptHashes.count( ptHash ) > 0 )
3175 return true;
3176
3177 ptHashes.insert( ptHash );
3178 }
3179 }
3180
3181 return false;
3182}
3183
3184
3189
3190
3192{
3193 size_t n = 0;
3194
3195 for( const std::unique_ptr<TRIANGULATED_POLYGON>& t : m_triangulatedPolys )
3196 n += t->GetTriangleCount();
3197
3198 return n;
3199}
3200
3201
3202void SHAPE_POLY_SET::GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const
3203{
3204 aSubshapes.reserve( GetIndexableSubshapeCount() );
3205
3206 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
3207 {
3208 for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
3209 aSubshapes.push_back( &tri );
3210 }
3211}
3212
3213
3215{
3216 BOX2I bbox( parent->m_vertices[a] );
3217 bbox.Merge( parent->m_vertices[b] );
3218 bbox.Merge( parent->m_vertices[c] );
3219
3220 if( aClearance != 0 )
3221 bbox.Inflate( aClearance );
3222
3223 return bbox;
3224}
3225
3226
3228{
3229 m_triangles.emplace_back( a, b, c, this );
3230}
3231
3232
3234{
3236 m_vertices = aOther.m_vertices;
3237 m_triangles = aOther.m_triangles;
3238
3239 for( TRI& tri : m_triangles )
3240 tri.parent = this;
3241}
3242
3243
3245{
3247 m_vertices = aOther.m_vertices;
3248 m_triangles = aOther.m_triangles;
3249
3250 for( TRI& tri : m_triangles )
3251 tri.parent = this;
3252
3253 return *this;
3254}
3255
3256
3258 m_sourceOutline( aSourceOutline )
3259{
3260}
3261
3262
3266
3267
3268void
3269SHAPE_POLY_SET::BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
3270 bool aEvenOdd )
3271{
3272 Clipper2Lib::Clipper64 clipper;
3273 Clipper2Lib::PolyTree64 tree;
3274 Clipper2Lib::Paths64 paths;
3275
3276 for( const SHAPE_LINE_CHAIN& path : aPaths )
3277 {
3278 Clipper2Lib::Path64 lc;
3279 lc.reserve( path.PointCount() );
3280
3281 for( int i = 0; i < path.PointCount(); i++ )
3282 lc.emplace_back( path.CPoint( i ).x, path.CPoint( i ).y );
3283
3284 paths.push_back( std::move( lc ) );
3285 }
3286
3287 clipper.AddSubject( paths );
3288 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
3289 : Clipper2Lib::FillRule::NonZero, tree );
3290
3291 std::vector<CLIPPER_Z_VALUE> zValues;
3292 std::vector<SHAPE_ARC> arcBuffer;
3293
3294 importTree( tree, zValues, arcBuffer );
3295 tree.Clear(); // Free used memory (not done in dtor)
3296}
3297
3298
3299bool SHAPE_POLY_SET::PointInside( const VECTOR2I& aPt, int aAccuracy, bool aUseBBoxCache ) const
3300{
3301 for( int idx = 0; idx < OutlineCount(); idx++ )
3302 {
3303 if( COutline( idx ).PointInside( aPt, aAccuracy, aUseBBoxCache ) )
3304 return true;
3305 }
3306
3307 return false;
3308}
3309
3310
3311const std::vector<SEG> SHAPE_POLY_SET::GenerateHatchLines( const std::vector<double>& aSlopes,
3312 int aSpacing, int aLineLength ) const
3313{
3314 std::vector<SEG> hatchLines;
3315
3316 // define range for hatch lines
3317 int min_x = CVertex( 0 ).x;
3318 int max_x = CVertex( 0 ).x;
3319 int min_y = CVertex( 0 ).y;
3320 int max_y = CVertex( 0 ).y;
3321
3322 for( auto iterator = CIterateWithHoles(); iterator; iterator++ )
3323 {
3324 if( iterator->x < min_x )
3325 min_x = iterator->x;
3326
3327 if( iterator->x > max_x )
3328 max_x = iterator->x;
3329
3330 if( iterator->y < min_y )
3331 min_y = iterator->y;
3332
3333 if( iterator->y > max_y )
3334 max_y = iterator->y;
3335 }
3336
3337 auto sortEndsByDescendingX =
3338 []( const VECTOR2I& ref, const VECTOR2I& tst )
3339 {
3340 return tst.x < ref.x;
3341 };
3342
3343 for( double slope : aSlopes )
3344 {
3345 int64_t max_a, min_a;
3346
3347 if( slope > 0 )
3348 {
3349 max_a = KiROUND<double, int64_t>( max_y - slope * min_x );
3350 min_a = KiROUND<double, int64_t>( min_y - slope * max_x );
3351 }
3352 else
3353 {
3354 max_a = KiROUND<double, int64_t>( max_y - slope * max_x );
3355 min_a = KiROUND<double, int64_t>( min_y - slope * min_x );
3356 }
3357
3358 min_a = ( min_a / aSpacing ) * aSpacing;
3359
3360 // loop through hatch lines
3361 std::vector<VECTOR2I> pointbuffer;
3362 pointbuffer.reserve( 256 );
3363
3364 for( int64_t a = min_a; a < max_a; a += aSpacing )
3365 {
3366 pointbuffer.clear();
3367
3368 // Iterate through all vertices
3369 for( auto iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
3370 {
3371 const SEG seg = *iterator;
3372 VECTOR2I pt;
3373
3374 if( seg.IntersectsLine( slope, a, pt ) )
3375 {
3376 // If the intersection point is outside the polygon, skip it
3377 if( pt.x < min_x || pt.x > max_x || pt.y < min_y || pt.y > max_y )
3378 continue;
3379
3380 // Add the intersection point to the buffer
3381 pointbuffer.emplace_back( KiROUND( pt.x ), KiROUND( pt.y ) );
3382 }
3383 }
3384
3385 // sort points in order of descending x (if more than 2) to
3386 // ensure the starting point and the ending point of the same segment
3387 // are stored one just after the other.
3388 if( pointbuffer.size() > 2 )
3389 sort( pointbuffer.begin(), pointbuffer.end(), sortEndsByDescendingX );
3390
3391 // creates lines or short segments inside the complex polygon
3392 for( size_t ip = 0; ip + 1 < pointbuffer.size(); ip++ )
3393 {
3394 const VECTOR2I& p1 = pointbuffer[ip];
3395 const VECTOR2I& p2 = pointbuffer[ip + 1];
3396
3397 // Avoid duplicated intersections or segments
3398 if( p1 == p2 )
3399 continue;
3400
3401 SEG candidate( p1, p2 );
3402
3403 VECTOR2I mid( ( candidate.A.x + candidate.B.x ) / 2, ( candidate.A.y + candidate.B.y ) / 2 );
3404
3405 // Check if segment is inside the polygon by checking its middle point
3406 if( containsSingle( mid, 0, 1, true ) )
3407 {
3408 int dx = p2.x - p1.x;
3409
3410 // Push only one line for diagonal hatch or for small lines < twice
3411 // the line length; else push 2 small lines
3412 if( aLineLength == -1 || std::abs( dx ) < 2 * aLineLength )
3413 {
3414 hatchLines.emplace_back( candidate );
3415 }
3416 else
3417 {
3418 double dy = p2.y - p1.y;
3419 slope = dy / dx;
3420
3421 if( dx > 0 )
3422 dx = aLineLength;
3423 else
3424 dx = -aLineLength;
3425
3426 int x1 = KiROUND( p1.x + dx );
3427 int x2 = KiROUND( p2.x - dx );
3428 int y1 = KiROUND( p1.y + dx * slope );
3429 int y2 = KiROUND( p2.y - dx * slope );
3430
3431 hatchLines.emplace_back( SEG( p1.x, p1.y, x1, y1 ) );
3432
3433 hatchLines.emplace_back( SEG( p2.x, p2.y, x2, y2 ) );
3434 }
3435 }
3436 }
3437 }
3438 }
3439
3440 return hatchLines;
3441}
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
bool operator!=(const BOM_FIELD &lhs, const BOM_FIELD &rhs)
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition box2.h:990
BOX2< VECTOR2D > BOX2D
Definition box2.h:923
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition box2.h:558
constexpr coord_type GetY() const
Definition box2.h:208
constexpr size_type GetWidth() const
Definition box2.h:214
constexpr coord_type GetX() const
Definition box2.h:207
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:658
constexpr size_type GetHeight() const
Definition box2.h:215
constexpr coord_type GetLeft() const
Definition box2.h:228
constexpr coord_type GetRight() const
Definition box2.h:217
constexpr coord_type GetTop() const
Definition box2.h:229
constexpr coord_type GetBottom() const
Definition box2.h:222
A streaming C++ equivalent for MurmurHash3_x64_128.
Definition mmh3_hash.h:60
FORCE_INLINE void add(const std::string &input)
Definition mmh3_hash.h:95
FORCE_INLINE HASH_128 digest()
Definition mmh3_hash.h:114
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
Definition seg.h:42
VECTOR2I A
Definition seg.h:49
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:80
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:448
VECTOR2I::extended_type ecoord
Definition seg.h:44
VECTOR2I B
Definition seg.h:50
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition seg.h:361
static SEG::ecoord Square(int a)
Definition seg.h:123
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition seg.cpp:536
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:766
SHAPE_TYPE Type() const
Return the type of the shape.
Definition shape.h:98
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
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 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.
int SegmentCount() const
Return the number of segments in this 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.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
void AddTriangle(int a, int b, int c)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
Represent a set of closed polygons.
std::mutex m_triangulationMutex
virtual bool HasIndexableSubshapes() const override
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
void RemoveAllContours()
Remove all outlines & holes (clears) the polygon set.
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
void RemoveOutline(int aOutlineIdx)
Delete the aOutlineIdx-th outline of the set including its contours and holes.
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
HASH_128 GetHash() const
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const override
void BooleanXor(const SHAPE_POLY_SET &b)
Perform boolean polyset exclusive or.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes.
CONST_ITERATOR CIterateWithHoles() const
void BooleanAdd(const SHAPE_POLY_SET &b)
Perform boolean polyset union.
ITERATOR IterateWithHoles()
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.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
virtual void CacheTriangulation(bool aPartition=true, bool aSimplify=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of vertices in a given outline/hole.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon from the set.
double Area()
Return the area of this poly set.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
void Fracture()
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
void BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
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).
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...
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.
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).
void cacheTriangulation(bool aPartition, bool aSimplify, std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > *aHintData)
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
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.
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.
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
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition shape.h:181
VECTOR2I::extended_type ecoord
Definition shape.h:301
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
Definition shape.h:136
static constexpr extended_type ECOORD_MAX
Definition vector2d.h:76
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition vector2d.h:283
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition vector2d.h:314
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:385
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:409
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:32
FLIP_DIRECTION
Definition mirror.h:27
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:400
static PGM_BASE * process
Definition pgm_base.cpp:910
#define TRIANGULATE_TRACE
#define TRIANGULATESIMPLIFICATIONLEVEL
CITER next(CITER it)
Definition ptree.cpp:124
@ SH_POLY_SET
set of polygons (with holes, etc.)
Definition shape.h:52
@ SH_CIRCLE
circle
Definition shape.h:50
@ SH_SEGMENT
line segment
Definition shape.h:48
static void fractureSingleCacheFriendly(SHAPE_POLY_SET::POLYGON &paths)
static void fractureSingleSlow(SHAPE_POLY_SET::POLYGON &paths)
static FractureEdge * processHole(FractureEdgeSet &edges, FractureEdge::Index provokingIndex, FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex)
std::vector< FractureEdge > FractureEdgeSet
std::vector< FractureEdgeSlow * > FractureEdgeSetSlow
#define SEG_CNT_MAX
static SHAPE_POLY_SET partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize)
#define ENABLECACHEFRIENDLYFRACTURE
static int processEdge(FractureEdgeSetSlow &edges, FractureEdgeSlow *edge)
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:36
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...
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
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition util.h:139
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695
VECTOR2< double > VECTOR2D
Definition vector2d.h:694