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