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