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