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