KiCad PCB EDA Suite
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-2022 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 <type_traits> // for swap, move
42#include <unordered_set>
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
93 SHAPE( aOther ),
94 m_polys( aOther.m_polys )
95{
96 if( aOther.IsTriangulationUpToDate() )
97 {
98 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
99 {
100 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
101 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
102 }
103
104 m_hash = aOther.GetHash();
106 }
107 else
108 {
109 m_triangulationValid = false;
110 m_hash = MD5_HASH();
111 m_triangulatedPolys.clear();
112 }
113}
114
115
117 SHAPE( aOther ),
118 m_polys( aOther.m_polys )
119{
120 m_triangulationValid = false;
121 m_hash = MD5_HASH();
122 m_triangulatedPolys.clear();
123}
124
125
127{
128}
129
130
132{
133 return new SHAPE_POLY_SET( *this );
134}
135
136
138{
139 return SHAPE_POLY_SET( *this, DROP_TRIANGULATION_FLAG::SINGLETON );
140}
141
142
144 SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
145{
146 int polygonIdx = 0;
147 unsigned int contourIdx = 0;
148 int vertexIdx = 0;
149
150 int currentGlobalIdx = 0;
151
152 for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
153 {
154 const POLYGON& currentPolygon = CPolygon( polygonIdx );
155
156 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
157 {
158 const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
159 int totalPoints = currentContour.PointCount();
160
161 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
162 {
163 // Check if the current vertex is the globally indexed as aGlobalIdx
164 if( currentGlobalIdx == aGlobalIdx )
165 {
166 aRelativeIndices->m_polygon = polygonIdx;
167 aRelativeIndices->m_contour = contourIdx;
168 aRelativeIndices->m_vertex = vertexIdx;
169
170 return true;
171 }
172
173 // Advance
174 currentGlobalIdx++;
175 }
176 }
177 }
178
179 return false;
180}
181
182
184 int& aGlobalIdx ) const
185{
186 int selectedVertex = aRelativeIndices.m_vertex;
187 unsigned int selectedContour = aRelativeIndices.m_contour;
188 unsigned int selectedPolygon = aRelativeIndices.m_polygon;
189
190 // Check whether the vertex indices make sense in this poly set
191 if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
192 && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
193 {
194 POLYGON currentPolygon;
195
196 aGlobalIdx = 0;
197
198 for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
199 {
200 currentPolygon = Polygon( polygonIdx );
201
202 for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
203 aGlobalIdx += currentPolygon[contourIdx].PointCount();
204 }
205
206 currentPolygon = Polygon( selectedPolygon );
207
208 for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
209 aGlobalIdx += currentPolygon[contourIdx].PointCount();
210
211 aGlobalIdx += selectedVertex;
212
213 return true;
214 }
215 else
216 {
217 return false;
218 }
219}
220
221
223{
224 SHAPE_LINE_CHAIN empty_path;
225 POLYGON poly;
226
227 empty_path.SetClosed( true );
228 poly.push_back( empty_path );
229 m_polys.push_back( poly );
230 return m_polys.size() - 1;
231}
232
233
234int SHAPE_POLY_SET::NewHole( int aOutline )
235{
236 SHAPE_LINE_CHAIN empty_path;
237
238 empty_path.SetClosed( true );
239
240 // Default outline is the last one
241 if( aOutline < 0 )
242 aOutline += m_polys.size();
243
244 // Add hole to the selected outline
245 m_polys[aOutline].push_back( empty_path );
246
247 return m_polys.back().size() - 2;
248}
249
250
251int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
252{
253 assert( m_polys.size() );
254
255 if( aOutline < 0 )
256 aOutline += m_polys.size();
257
258 int idx;
259
260 if( aHole < 0 )
261 idx = 0;
262 else
263 idx = aHole + 1;
264
265 assert( aOutline < (int) m_polys.size() );
266 assert( idx < (int) m_polys[aOutline].size() );
267
268 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
269
270 return m_polys[aOutline][idx].PointCount();
271}
272
273
274int SHAPE_POLY_SET::Append( SHAPE_ARC& aArc, int aOutline, int aHole )
275{
276 assert( m_polys.size() );
277
278 if( aOutline < 0 )
279 aOutline += m_polys.size();
280
281 int idx;
282
283 if( aHole < 0 )
284 idx = 0;
285 else
286 idx = aHole + 1;
287
288 assert( aOutline < (int) m_polys.size() );
289 assert( idx < (int) m_polys[aOutline].size() );
290
291 m_polys[aOutline][idx].Append( aArc );
292
293 return m_polys[aOutline][idx].PointCount();
294}
295
296
297void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex )
298{
299 VERTEX_INDEX index;
300
301 if( aGlobalIndex < 0 )
302 aGlobalIndex = 0;
303
304 if( aGlobalIndex >= TotalVertices() )
305 {
306 Append( aNewVertex );
307 }
308 else
309 {
310 // Assure the position to be inserted exists; throw an exception otherwise
311 if( GetRelativeIndices( aGlobalIndex, &index ) )
312 m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
313 else
314 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
315 }
316}
317
318
319int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
320{
321 if( m_polys.size() == 0 ) // Empty poly set
322 return 0;
323
324 if( aOutline < 0 ) // Use last outline
325 aOutline += m_polys.size();
326
327 int idx;
328
329 if( aHole < 0 )
330 idx = 0;
331 else
332 idx = aHole + 1;
333
334 if( aOutline >= (int) m_polys.size() ) // not existing outline
335 return 0;
336
337 if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
338 return 0;
339
340 return m_polys[aOutline][idx].PointCount();
341}
342
343
345{
346 int full_count = 0;
347
348 if( m_polys.size() == 0 ) // Empty poly set
349 return full_count;
350
351 for( int ii = 0; ii < OutlineCount(); ii++ )
352 {
353 // the first polygon in m_polys[ii] is the main contour,
354 // only others are holes:
355 for( int idx = 0; idx <= HoleCount( ii ); idx++ )
356 {
357 full_count += m_polys[ii][idx].PointCount();
358 }
359 }
360
361 return full_count;
362}
363
364
365SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
366{
367 assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
368
369 SHAPE_POLY_SET newPolySet;
370
371 for( int index = aFirstPolygon; index < aLastPolygon; index++ )
372 newPolySet.m_polys.push_back( Polygon( index ) );
373
374 return newPolySet;
375}
376
377
378const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
379{
380 if( aOutline < 0 )
381 aOutline += m_polys.size();
382
383 int idx;
384
385 if( aHole < 0 )
386 idx = 0;
387 else
388 idx = aHole + 1;
389
390 assert( aOutline < (int) m_polys.size() );
391 assert( idx < (int) m_polys[aOutline].size() );
392
393 return m_polys[aOutline][idx].CPoint( aIndex );
394}
395
396
397const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
398{
400
401 // Assure the passed index references a legal position; abort otherwise
402 if( !GetRelativeIndices( aGlobalIndex, &index ) )
403 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
404
405 return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
406}
407
408
410{
411 return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
412}
413
414
415bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
416{
418
419 // If the edge does not exist, throw an exception, it is an illegal access memory error
420 if( !GetRelativeIndices( aGlobalIndex, &index ) )
421 return false;
422
423 // Calculate the previous and next index of aGlobalIndex, corresponding to
424 // the same contour;
425 VERTEX_INDEX inext = index;
426 int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
427
428 if( index.m_vertex == 0 )
429 {
430 index.m_vertex = lastpoint;
431 inext.m_vertex = 1;
432 }
433 else if( index.m_vertex == lastpoint )
434 {
435 index.m_vertex--;
436 inext.m_vertex = 0;
437 }
438 else
439 {
440 inext.m_vertex++;
441 index.m_vertex--;
442 }
443
444 if( aPrevious )
445 {
446 int previous;
447 GetGlobalIndex( index, previous );
448 *aPrevious = previous;
449 }
450
451 if( aNext )
452 {
453 int next;
454 GetGlobalIndex( inext, next );
455 *aNext = next;
456 }
457
458 return true;
459}
460
461
462bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
463{
464 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
465 CONST_SEGMENT_ITERATOR innerIterator;
466
467 for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
468 {
469 SEG firstSegment = *iterator;
470
471 // Iterate through all remaining segments.
472 innerIterator = iterator;
473
474 // Start in the next segment, we don't want to check collision between a segment and itself
475 for( innerIterator++; innerIterator; innerIterator++ )
476 {
477 SEG secondSegment = *innerIterator;
478
479 // Check whether the two segments built collide, only when they are not adjacent.
480 if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
481 return true;
482 }
483 }
484
485 return false;
486}
487
488
490{
491 for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
492 {
493 if( IsPolygonSelfIntersecting( polygon ) )
494 return true;
495 }
496
497 return false;
498}
499
500
502{
503 assert( aOutline.IsClosed() );
504
505 POLYGON poly;
506
507 poly.push_back( aOutline );
508
509 m_polys.push_back( poly );
510
511 return m_polys.size() - 1;
512}
513
514
515int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
516{
517 assert( m_polys.size() );
518
519 if( aOutline < 0 )
520 aOutline += m_polys.size();
521
522 assert( aOutline < (int)m_polys.size() );
523
524 POLYGON& poly = m_polys[aOutline];
525
526 assert( poly.size() );
527
528 poly.push_back( aHole );
529
530 return poly.size() - 2;
531}
532
533
535{
536 double area = 0.0;
537
538 for( int i = 0; i < OutlineCount(); i++ )
539 {
540 area += Outline( i ).Area();
541
542 for( int j = 0; j < HoleCount( i ); j++ )
543 area -= Hole( i, j ).Area();
544 }
545
546 return area;
547}
548
549
551{
552 int retval = 0;
553
554 for( const POLYGON& poly : m_polys )
555 {
556 for( size_t i = 0; i < poly.size(); i++ )
557 retval += poly[i].ArcCount();
558 }
559
560 return retval;
561}
562
563
564void SHAPE_POLY_SET::GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const
565{
566 for( const POLYGON& poly : m_polys )
567 {
568 for( size_t i = 0; i < poly.size(); i++ )
569 {
570 for( SHAPE_ARC arc : poly[i].m_arcs )
571 aArcBuffer.push_back( arc );
572 }
573 }
574}
575
576
578{
579 for( POLYGON& poly : m_polys )
580 {
581 for( size_t i = 0; i < poly.size(); i++ )
582 poly[i].ClearArcs();
583 }
584}
585
586
587void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
588 POLYGON_MODE aFastMode )
589{
590 booleanOp( aType, *this, aOtherShape, aFastMode );
591}
592
593
594void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aShape,
595 const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode )
596{
597 if( ( aShape.OutlineCount() > 1 || aOtherShape.OutlineCount() > 0 )
598 && ( aShape.ArcCount() > 0 || aOtherShape.ArcCount() > 0 ) )
599 {
600 wxFAIL_MSG( wxT( "Boolean ops on curved polygons are not supported. You should call "
601 "ClearArcs() before carrying out the boolean operation." ) );
602 }
603
604 ClipperLib::Clipper c;
605
606 c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
607
608 std::vector<CLIPPER_Z_VALUE> zValues;
609 std::vector<SHAPE_ARC> arcBuffer;
610 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
611
612 for( const POLYGON& poly : aShape.m_polys )
613 {
614 for( size_t i = 0; i < poly.size(); i++ )
615 {
616 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
617 ClipperLib::ptSubject, true );
618 }
619 }
620
621 for( const POLYGON& poly : aOtherShape.m_polys )
622 {
623 for( size_t i = 0; i < poly.size(); i++ )
624 {
625 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
626 ClipperLib::ptClip, true );
627 }
628 }
629
630 ClipperLib::PolyTree solution;
631
632 ClipperLib::ZFillCallback callback =
633 [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
634 ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
635 ClipperLib::IntPoint & pt )
636 {
637 auto arcIndex =
638 [&]( const ssize_t& aZvalue, const ssize_t& aCompareVal = -1 ) -> ssize_t
639 {
640 ssize_t retval;
641
642 retval = zValues.at( aZvalue ).m_SecondArcIdx;
643
644 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
645 retval = zValues.at( aZvalue ).m_FirstArcIdx;
646
647 return retval;
648 };
649
650 auto arcSegment =
651 [&]( const ssize_t& aBottomZ, const ssize_t aTopZ ) -> ssize_t
652 {
653 ssize_t retval = arcIndex( aBottomZ );
654
655 if( retval != -1 )
656 {
657 if( retval != arcIndex( aTopZ, retval ) )
658 retval = -1; // Not an arc segment as the two indices do not match
659 }
660
661 return retval;
662 };
663
664 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
665 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
666
667 CLIPPER_Z_VALUE newZval;
668
669 if( e1ArcSegmentIndex != -1 )
670 {
671 newZval.m_FirstArcIdx = e1ArcSegmentIndex;
672 newZval.m_SecondArcIdx = e2ArcSegmentIndex;
673 }
674 else
675 {
676 newZval.m_FirstArcIdx = e2ArcSegmentIndex;
677 newZval.m_SecondArcIdx = -1;
678 }
679
680 size_t z_value_ptr = zValues.size();
681 zValues.push_back( newZval );
682
683 // Only worry about arc segments for later processing
684 if( newZval.m_FirstArcIdx != -1 )
685 newIntersectPoints.insert( { VECTOR2I( pt.X, pt.Y ), newZval } );
686
687 pt.Z = z_value_ptr;
688 //@todo amend X,Y values to true intersection between arcs or arc and segment
689 };
690
691 c.ZFillFunction( callback ); // register callback
692
693 c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
694
695 importTree( &solution, zValues, arcBuffer );
696}
697
698
699void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aOtherShape )
700{
701 booleanOp( aType, *this, aOtherShape );
702}
703
704
705void SHAPE_POLY_SET::booleanOp( Clipper2Lib::ClipType aType, const SHAPE_POLY_SET& aShape,
706 const SHAPE_POLY_SET& aOtherShape )
707{
708 if( ( aShape.OutlineCount() > 1 || aOtherShape.OutlineCount() > 0 )
709 && ( aShape.ArcCount() > 0 || aOtherShape.ArcCount() > 0 ) )
710 {
711 wxFAIL_MSG( wxT( "Boolean ops on curved polygons are not supported. You should call "
712 "ClearArcs() before carrying out the boolean operation." ) );
713 }
714
715 Clipper2Lib::Clipper64 c;
716
717 std::vector<CLIPPER_Z_VALUE> zValues;
718 std::vector<SHAPE_ARC> arcBuffer;
719 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
720
721 Clipper2Lib::Paths64 paths;
722 Clipper2Lib::Paths64 clips;
723
724 for( const POLYGON& poly : aShape.m_polys )
725 {
726 for( size_t i = 0; i < poly.size(); i++ )
727 {
728 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
729 }
730 }
731
732 for( const POLYGON& poly : aOtherShape.m_polys )
733 {
734 for( size_t i = 0; i < poly.size(); i++ )
735 {
736 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
737 }
738 }
739
740 c.AddSubject( paths );
741 c.AddClip( clips );
742
743 Clipper2Lib::PolyTree64 solution;
744
745 Clipper2Lib::ZCallback64 callback =
746 [&]( const Clipper2Lib::Point64 & e1bot, const Clipper2Lib::Point64 & e1top,
747 const Clipper2Lib::Point64 & e2bot, const Clipper2Lib::Point64 & e2top,
748 Clipper2Lib::Point64 & pt )
749 {
750 auto arcIndex =
751 [&]( const ssize_t& aZvalue, const ssize_t& aCompareVal = -1 ) -> ssize_t
752 {
753 ssize_t retval;
754
755 retval = zValues.at( aZvalue ).m_SecondArcIdx;
756
757 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
758 retval = zValues.at( aZvalue ).m_FirstArcIdx;
759
760 return retval;
761 };
762
763 auto arcSegment =
764 [&]( const ssize_t& aBottomZ, const ssize_t aTopZ ) -> ssize_t
765 {
766 ssize_t retval = arcIndex( aBottomZ );
767
768 if( retval != -1 )
769 {
770 if( retval != arcIndex( aTopZ, retval ) )
771 retval = -1; // Not an arc segment as the two indices do not match
772 }
773
774 return retval;
775 };
776
777 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
778 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
779
780 CLIPPER_Z_VALUE newZval;
781
782 if( e1ArcSegmentIndex != -1 )
783 {
784 newZval.m_FirstArcIdx = e1ArcSegmentIndex;
785 newZval.m_SecondArcIdx = e2ArcSegmentIndex;
786 }
787 else
788 {
789 newZval.m_FirstArcIdx = e2ArcSegmentIndex;
790 newZval.m_SecondArcIdx = -1;
791 }
792
793 size_t z_value_ptr = zValues.size();
794 zValues.push_back( newZval );
795
796 // Only worry about arc segments for later processing
797 if( newZval.m_FirstArcIdx != -1 )
798 newIntersectPoints.insert( { VECTOR2I( pt.x, pt.y ), newZval } );
799
800 pt.z = z_value_ptr;
801 //@todo amend X,Y values to true intersection between arcs or arc and segment
802 };
803
804 c.SetZCallback( callback ); // register callback
805
806 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
807
808 importTree( solution, zValues, arcBuffer );
809}
810
811
813{
814 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
815 booleanOp( Clipper2Lib::ClipType::Union, b );
816 else
817 booleanOp( ClipperLib::ctUnion, b, aFastMode );
818}
819
820
822{
823 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
824 booleanOp( Clipper2Lib::ClipType::Difference, b );
825 else
826 booleanOp( ClipperLib::ctDifference, b, aFastMode );
827}
828
829
831{
832 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
833 booleanOp( Clipper2Lib::ClipType::Intersection, b );
834 else
835 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
836}
837
838
840 POLYGON_MODE aFastMode )
841{
842 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
843 booleanOp( Clipper2Lib::ClipType::Union, a, b );
844 else
845 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
846}
847
848
850 POLYGON_MODE aFastMode )
851{
852 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
853 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
854 else
855 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
856}
857
858
860 POLYGON_MODE aFastMode )
861{
862 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
863 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
864 else
865 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
866}
867
868
869void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
870 POLYGON_MODE aFastMode )
871{
872 Unfracture( aFastMode );
873 Inflate( aFactor, aCircleSegmentsCount );
874 Fracture( aFastMode );
875}
876
877
878void SHAPE_POLY_SET::inflate1( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy )
879{
880 using namespace ClipperLib;
881 // A static table to avoid repetitive calculations of the coefficient
882 // 1.0 - cos( M_PI / aCircleSegCount )
883 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
884 #define SEG_CNT_MAX 64
885 static double arc_tolerance_factor[SEG_CNT_MAX + 1];
886
887 ClipperOffset c;
888
889 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
890 // and are not what you'd think they are.
891 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
892 JoinType joinType = jtRound; // The way corners are offsetted
893 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
894 JoinType miterFallback = jtSquare;
895
896 switch( aCornerStrategy )
897 {
899 joinType = jtMiter;
900 miterLimit = 10; // Allows large spikes
901 miterFallback = jtSquare;
902 break;
903
904 case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
905 joinType = jtMiter;
906 miterFallback = jtRound;
907 break;
908
909 case ROUND_ACUTE_CORNERS: // Acute angles are rounded
910 joinType = jtMiter;
911 miterFallback = jtSquare;
912 break;
913
914 case CHAMFER_ALL_CORNERS: // All angles are chamfered.
915 joinType = jtSquare;
916 miterFallback = jtSquare;
917 break;
918
919 case ROUND_ALL_CORNERS: // All angles are rounded.
920 joinType = jtRound;
921 miterFallback = jtSquare;
922 break;
923 }
924
925 std::vector<CLIPPER_Z_VALUE> zValues;
926 std::vector<SHAPE_ARC> arcBuffer;
927
928 for( const POLYGON& poly : m_polys )
929 {
930 for( size_t i = 0; i < poly.size(); i++ )
931 {
932 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
933 joinType, etClosedPolygon );
934 }
935 }
936
937 PolyTree solution;
938
939 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
940 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
941 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
942
943 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
944 aCircleSegCount = 6;
945
946 double coeff;
947
948 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
949 {
950 coeff = 1.0 - cos( M_PI / aCircleSegCount );
951
952 if( aCircleSegCount <= SEG_CNT_MAX )
953 arc_tolerance_factor[aCircleSegCount] = coeff;
954 }
955 else
956 {
957 coeff = arc_tolerance_factor[aCircleSegCount];
958 }
959
960 c.ArcTolerance = std::abs( aAmount ) * coeff;
961 c.MiterLimit = miterLimit;
962 c.MiterFallback = miterFallback;
963 c.Execute( solution, aAmount );
964
965 importTree( &solution, zValues, arcBuffer );
966}
967
968
969void SHAPE_POLY_SET::inflate2( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy )
970{
971 using namespace Clipper2Lib;
972 // A static table to avoid repetitive calculations of the coefficient
973 // 1.0 - cos( M_PI / aCircleSegCount )
974 // aCircleSegCount is most of time <= 64 and usually 8, 12, 16, 32
975 #define SEG_CNT_MAX 64
976 static double arc_tolerance_factor[SEG_CNT_MAX + 1];
977
978 ClipperOffset c;
979
980 // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
981 // and are not what you'd think they are.
982 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
983 JoinType joinType = JoinType::Round; // The way corners are offsetted
984 double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
985 JoinType miterFallback = JoinType::Square;
986
987 switch( aCornerStrategy )
988 {
990 joinType = JoinType::Miter;
991 miterLimit = 10; // Allows large spikes
992 break;
993
994 case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
995 joinType = JoinType::Miter;
996 break;
997
998 case ROUND_ACUTE_CORNERS: // Acute angles are rounded
999 joinType = JoinType::Miter;
1000 break;
1001
1002 case CHAMFER_ALL_CORNERS: // All angles are chamfered.
1003 joinType = JoinType::Square;
1004 break;
1005
1006 case ROUND_ALL_CORNERS: // All angles are rounded.
1007 joinType = JoinType::Round;
1008 break;
1009 }
1010
1011 std::vector<CLIPPER_Z_VALUE> zValues;
1012 std::vector<SHAPE_ARC> arcBuffer;
1013
1014 for( const POLYGON& poly : m_polys )
1015 {
1016 Paths64 paths;
1017
1018 for( size_t i = 0; i < poly.size(); i++ )
1019 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1020
1021 c.AddPaths( paths, joinType, EndType::Polygon );
1022 }
1023
1024 // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
1025 // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
1026 // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
1027
1028 if( aCircleSegCount < 6 ) // avoid incorrect aCircleSegCount values
1029 aCircleSegCount = 6;
1030
1031 double coeff;
1032
1033 if( aCircleSegCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1034 {
1035 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1036
1037 if( aCircleSegCount <= SEG_CNT_MAX )
1038 arc_tolerance_factor[aCircleSegCount] = coeff;
1039 }
1040 else
1041 {
1042 coeff = arc_tolerance_factor[aCircleSegCount];
1043 }
1044
1045 c.ArcTolerance( std::abs( aAmount ) * coeff );
1046 c.MiterLimit( miterLimit );
1047 c.MergeGroups( true );
1048 Paths64 solution = c.Execute( aAmount );
1049
1050 // We get paths back but we need the tree to assign the holes to the correct
1051 // outlines
1052 Clipper64 c2;
1053 PolyTree64 tree;
1054 c2.PreserveCollinear = false;
1055 c2.ReverseSolution = false;
1056 c2.AddSubject( solution );
1057 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1058
1059 importTree( tree, zValues, arcBuffer );
1060}
1061
1062
1063void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy )
1064{
1065 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
1066 inflate2( aAmount, aCircleSegCount, aCornerStrategy );
1067 else
1068 inflate1( aAmount, aCircleSegCount, aCornerStrategy );
1069}
1070
1071
1072void SHAPE_POLY_SET::importTree( ClipperLib::PolyTree* tree,
1073 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1074 const std::vector<SHAPE_ARC>& aArcBuffer )
1075{
1076 m_polys.clear();
1077
1078 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
1079 {
1080 if( !n->IsHole() )
1081 {
1082 POLYGON paths;
1083 paths.reserve( n->Childs.size() + 1 );
1084
1085 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
1086
1087 for( unsigned int i = 0; i < n->Childs.size(); i++ )
1088 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
1089
1090 m_polys.push_back( paths );
1091 }
1092 }
1093}
1094
1095
1096void SHAPE_POLY_SET::importPolyPath( Clipper2Lib::PolyPath64* aPolyPath,
1097 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1098 const std::vector<SHAPE_ARC>& aArcBuffer )
1099{
1100 if( !aPolyPath->IsHole() )
1101 {
1102 POLYGON paths;
1103 paths.reserve( aPolyPath->Count() + 1 );
1104 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1105
1106 for( Clipper2Lib::PolyPath64* child : *aPolyPath )
1107 {
1108 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1109
1110 for( Clipper2Lib::PolyPath64* grandchild : *child )
1111 importPolyPath( grandchild, aZValueBuffer, aArcBuffer );
1112 }
1113
1114 m_polys.push_back( paths );
1115 }
1116}
1117
1118
1119void SHAPE_POLY_SET::importTree( Clipper2Lib::PolyTree64& tree,
1120 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1121 const std::vector<SHAPE_ARC>& aArcBuffer )
1122{
1123 m_polys.clear();
1124
1125 for( Clipper2Lib::PolyPath64* n : tree )
1126 importPolyPath( n, aZValueBuffer, aArcBuffer );
1127}
1128
1129
1130void SHAPE_POLY_SET::importPaths( Clipper2Lib::Paths64& aPath,
1131 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1132 const std::vector<SHAPE_ARC>& aArcBuffer )
1133{
1134 m_polys.clear();
1135 POLYGON path;
1136
1137 for( const Clipper2Lib::Path64& n : aPath )
1138 {
1139 if( Clipper2Lib::Area( n ) > 0 )
1140 {
1141 if( !path.empty() )
1142 m_polys.emplace_back( path );
1143
1144 path.clear();
1145 }
1146 else
1147 {
1148 wxCHECK2_MSG( !path.empty(), continue, wxT( "Cannot add a hole before an outline" ) );
1149 }
1150
1151 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1152 }
1153
1154 if( !path.empty() )
1155 m_polys.emplace_back( path );
1156}
1157
1158
1160{
1161 FractureEdge( int y = 0 ) :
1162 m_connected( false ),
1163 m_next( nullptr )
1164 {
1165 m_p1.x = m_p2.y = y;
1166 }
1167
1168 FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
1169 m_connected( connected ),
1170 m_p1( p1 ),
1171 m_p2( p2 ),
1172 m_next( nullptr )
1173 {
1174 }
1175
1176 bool matches( int y ) const
1177 {
1178 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
1179 }
1180
1185};
1186
1187
1188typedef std::vector<FractureEdge*> FractureEdgeSet;
1189
1190
1191static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
1192{
1193 int x = edge->m_p1.x;
1194 int y = edge->m_p1.y;
1195 int min_dist = std::numeric_limits<int>::max();
1196 int x_nearest = 0;
1197
1198 FractureEdge* e_nearest = nullptr;
1199
1200 for( FractureEdge* e : edges )
1201 {
1202 if( !e->matches( y ) )
1203 continue;
1204
1205 int x_intersect;
1206
1207 if( e->m_p1.y == e->m_p2.y ) // horizontal edge
1208 {
1209 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1210 }
1211 else
1212 {
1213 x_intersect = e->m_p1.x + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
1214 e->m_p2.y - e->m_p1.y );
1215 }
1216
1217 int dist = ( x - x_intersect );
1218
1219 if( dist >= 0 && dist < min_dist && e->m_connected )
1220 {
1221 min_dist = dist;
1222 x_nearest = x_intersect;
1223 e_nearest = e;
1224 }
1225 }
1226
1227 if( e_nearest && e_nearest->m_connected )
1228 {
1229 int count = 0;
1230
1231 FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
1232 FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
1233 FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
1234
1235 edges.push_back( split_2 );
1236 edges.push_back( lead1 );
1237 edges.push_back( lead2 );
1238
1239 FractureEdge* link = e_nearest->m_next;
1240
1241 e_nearest->m_p2 = VECTOR2I( x_nearest, y );
1242 e_nearest->m_next = lead1;
1243 lead1->m_next = edge;
1244
1245 FractureEdge* last;
1246
1247 for( last = edge; last->m_next != edge; last = last->m_next )
1248 {
1249 last->m_connected = true;
1250 count++;
1251 }
1252
1253 last->m_connected = true;
1254 last->m_next = lead2;
1255 lead2->m_next = split_2;
1256 split_2->m_next = link;
1257
1258 return count + 1;
1259 }
1260
1261 return 0;
1262}
1263
1264
1266{
1267 FractureEdgeSet edges;
1268 FractureEdgeSet border_edges;
1269 FractureEdge* root = nullptr;
1270
1271 bool first = true;
1272
1273 if( paths.size() == 1 )
1274 return;
1275
1276 int num_unconnected = 0;
1277
1278 for( const SHAPE_LINE_CHAIN& path : paths )
1279 {
1280 const std::vector<VECTOR2I>& points = path.CPoints();
1281 int pointCount = points.size();
1282
1283 FractureEdge* prev = nullptr, * first_edge = nullptr;
1284
1285 int x_min = std::numeric_limits<int>::max();
1286
1287 for( int i = 0; i < pointCount; i++ )
1288 {
1289 if( points[i].x < x_min )
1290 x_min = points[i].x;
1291
1292 // Do not use path.CPoint() here; open-coding it using the local variables "points"
1293 // and "pointCount" gives a non-trivial performance boost to zone fill times.
1294 FractureEdge* fe = new FractureEdge( first, points[ i ],
1295 points[ i+1 == pointCount ? 0 : i+1 ] );
1296
1297 if( !root )
1298 root = fe;
1299
1300 if( !first_edge )
1301 first_edge = fe;
1302
1303 if( prev )
1304 prev->m_next = fe;
1305
1306 if( i == pointCount - 1 )
1307 fe->m_next = first_edge;
1308
1309 prev = fe;
1310 edges.push_back( fe );
1311
1312 if( !first )
1313 {
1314 if( fe->m_p1.x == x_min )
1315 border_edges.push_back( fe );
1316 }
1317
1318 if( !fe->m_connected )
1319 num_unconnected++;
1320 }
1321
1322 first = false; // first path is always the outline
1323 }
1324
1325 // keep connecting holes to the main outline, until there's no holes left...
1326 while( num_unconnected > 0 )
1327 {
1328 int x_min = std::numeric_limits<int>::max();
1329 auto it = border_edges.begin();
1330
1331 FractureEdge* smallestX = nullptr;
1332
1333 // find the left-most hole edge and merge with the outline
1334 for( ; it != border_edges.end(); ++it )
1335 {
1336 FractureEdge* border_edge = *it;
1337 int xt = border_edge->m_p1.x;
1338
1339 if( ( xt <= x_min ) && !border_edge->m_connected )
1340 {
1341 x_min = xt;
1342 smallestX = border_edge;
1343 }
1344 }
1345
1346 int num_processed = processEdge( edges, smallestX );
1347
1348 // If we can't handle the edge, the zone is broken (maybe)
1349 if( !num_processed )
1350 {
1351 wxLogWarning( wxT( "Broken polygon, dropping path" ) );
1352
1353 for( FractureEdge* edge : edges )
1354 delete edge;
1355
1356 return;
1357 }
1358
1359 num_unconnected -= num_processed;
1360 }
1361
1362 paths.clear();
1363 SHAPE_LINE_CHAIN newPath;
1364
1365 newPath.SetClosed( true );
1366
1367 FractureEdge* e;
1368
1369 for( e = root; e->m_next != root; e = e->m_next )
1370 newPath.Append( e->m_p1 );
1371
1372 newPath.Append( e->m_p1 );
1373
1374 for( FractureEdge* edge : edges )
1375 delete edge;
1376
1377 paths.push_back( std::move( newPath ) );
1378}
1379
1380
1382{
1383 Simplify( aFastMode ); // remove overlapping holes/degeneracy
1384
1385 for( POLYGON& paths : m_polys )
1386 fractureSingle( paths );
1387}
1388
1389
1391{
1392 assert( aPoly.size() == 1 );
1393
1394 struct EDGE
1395 {
1396 int m_index = 0;
1397 SHAPE_LINE_CHAIN* m_poly = nullptr;
1398 bool m_duplicate = false;
1399
1400 EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
1401 m_index( aIndex ),
1402 m_poly( aPolygon )
1403 {}
1404
1405 bool compareSegs( const SEG& s1, const SEG& s2 ) const
1406 {
1407 return (s1.A == s2.B && s1.B == s2.A);
1408 }
1409
1410 bool operator==( const EDGE& aOther ) const
1411 {
1412 return compareSegs( m_poly->CSegment( m_index ),
1413 aOther.m_poly->CSegment( aOther.m_index ) );
1414 }
1415
1416 bool operator!=( const EDGE& aOther ) const
1417 {
1418 return !compareSegs( m_poly->CSegment( m_index ),
1419 aOther.m_poly->CSegment( aOther.m_index ) );
1420 }
1421
1422 struct HASH
1423 {
1424 std::size_t operator()( const EDGE& aEdge ) const
1425 {
1426 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1427 std::size_t seed = 0xa82de1c0;
1428 hash_combine( seed, a.A.x, a.B.x, a.A.y, a.B.y );
1429 return seed;
1430 }
1431 };
1432 };
1433
1434 struct EDGE_LIST_ENTRY
1435 {
1436 int index;
1437 EDGE_LIST_ENTRY* next;
1438 };
1439
1440 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1441
1442 SHAPE_LINE_CHAIN lc = aPoly[0];
1443 lc.Simplify();
1444
1445 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.SegmentCount() );
1446
1447 for( int i = 0; i < lc.SegmentCount(); i++ )
1448 {
1449 edgeList[i].index = i;
1450 edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
1451 }
1452
1453 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1454
1455 for( int i = 0; i < lc.SegmentCount(); i++ )
1456 {
1457 EDGE e( &lc, i );
1458 uniqueEdges.insert( e );
1459 }
1460
1461 for( int i = 0; i < lc.SegmentCount(); i++ )
1462 {
1463 EDGE e( &lc, i );
1464 auto it = uniqueEdges.find( e );
1465
1466 if( it != uniqueEdges.end() && it->m_index != i )
1467 {
1468 int e1 = it->m_index;
1469 int e2 = i;
1470
1471 if( e1 > e2 )
1472 std::swap( e1, e2 );
1473
1474 int e1_prev = e1 - 1;
1475
1476 if( e1_prev < 0 )
1477 e1_prev = lc.SegmentCount() - 1;
1478
1479 int e2_prev = e2 - 1;
1480
1481 if( e2_prev < 0 )
1482 e2_prev = lc.SegmentCount() - 1;
1483
1484 int e1_next = e1 + 1;
1485
1486 if( e1_next == lc.SegmentCount() )
1487 e1_next = 0;
1488
1489 int e2_next = e2 + 1;
1490
1491 if( e2_next == lc.SegmentCount() )
1492 e2_next = 0;
1493
1494 edgeList[e1_prev].next = &edgeList[ e2_next ];
1495 edgeList[e2_prev].next = &edgeList[ e1_next ];
1496 edgeList[i].next = nullptr;
1497 edgeList[it->m_index].next = nullptr;
1498 }
1499 }
1500
1501 for( int i = 0; i < lc.SegmentCount(); i++ )
1502 {
1503 if( edgeList[i].next )
1504 queue.insert( &edgeList[i] );
1505 }
1506
1507 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1508
1509 int n = 0;
1510 int outline = -1;
1511
1512 POLYGON result;
1513 double max_poly = 0.0;
1514
1515 while( queue.size() )
1516 {
1517 EDGE_LIST_ENTRY* e_first = *queue.begin();
1518 EDGE_LIST_ENTRY* e = e_first;
1519 int cnt = 0;
1520
1521 do
1522 {
1523 edgeBuf[cnt++] = e;
1524 e = e->next;
1525 } while( e && e != e_first );
1526
1527 SHAPE_LINE_CHAIN outl;
1528
1529 for( int i = 0; i < cnt; i++ )
1530 {
1531 VECTOR2I p = lc.CPoint( edgeBuf[i]->index );
1532 outl.Append( p );
1533 queue.erase( edgeBuf[i] );
1534 }
1535
1536 outl.SetClosed( true );
1537
1538 double area = std::fabs( outl.Area() );
1539
1540 if( area > max_poly )
1541 {
1542 outline = n;
1543 max_poly = area;
1544 }
1545
1546 result.push_back( outl );
1547 n++;
1548 }
1549
1550 if( outline > 0 )
1551 std::swap( result[0], result[outline] );
1552
1553 aPoly = result;
1554}
1555
1556
1558{
1559 // Iterate through all the polygons on the set
1560 for( const POLYGON& paths : m_polys )
1561 {
1562 // If any of them has more than one contour, it is a hole.
1563 if( paths.size() > 1 )
1564 return true;
1565 }
1566
1567 // Return false if and only if every polygon has just one outline, without holes.
1568 return false;
1569}
1570
1571
1573{
1574 for( POLYGON& path : m_polys )
1576
1577 Simplify( aFastMode ); // remove overlapping holes/degeneracy
1578}
1579
1580
1582{
1584
1585 if( ADVANCED_CFG::GetCfg().m_UseClipper2 )
1586 booleanOp( Clipper2Lib::ClipType::Union, empty );
1587 else
1588 booleanOp( ClipperLib::ctUnion, empty, aFastMode );
1589}
1590
1591
1593{
1594 // We are expecting only one main outline, but this main outline can have holes
1595 // if holes: combine holes and remove them from the main outline.
1596 // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1597 // calculations, but it is not mandatory. It is used mainly
1598 // because there is usually only very few vertices in area outlines
1599 SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1600 SHAPE_POLY_SET holesBuffer;
1601
1602 // Move holes stored in outline to holesBuffer:
1603 // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1604 while( outline.size() > 1 )
1605 {
1606 holesBuffer.AddOutline( outline.back() );
1607 outline.pop_back();
1608 }
1609
1611
1612 // If any hole, subtract it to main outline
1613 if( holesBuffer.OutlineCount() )
1614 {
1615 holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1617 }
1618
1619 // In degenerate cases, simplify might return no outlines
1620 if( OutlineCount() > 0 )
1622
1623 return OutlineCount();
1624}
1625
1626
1627const std::string SHAPE_POLY_SET::Format( bool aCplusPlus ) const
1628{
1629 std::stringstream ss;
1630
1631 ss << "SHAPE_LINE_CHAIN poly; \n";
1632
1633 for( unsigned i = 0; i < m_polys.size(); i++ )
1634 {
1635 for( unsigned j = 0; j < m_polys[i].size(); j++ )
1636 {
1637
1638 ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1639
1640 SHAPE_POLY_SET poly;
1641
1642 if( j == 0 )
1643 {
1644 ss << " poly.AddOutline(tmp); } \n";
1645 }
1646 else
1647 {
1648 ss << " poly.AddHole(tmp); } \n";
1649 }
1650
1651 }
1652 }
1653
1654 return ss.str();
1655}
1656
1657
1658bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1659{
1660 std::string tmp;
1661
1662 aStream >> tmp;
1663
1664 if( tmp != "polyset" )
1665 return false;
1666
1667 aStream >> tmp;
1668
1669 int n_polys = atoi( tmp.c_str() );
1670
1671 if( n_polys < 0 )
1672 return false;
1673
1674 for( int i = 0; i < n_polys; i++ )
1675 {
1676 POLYGON paths;
1677
1678 aStream >> tmp;
1679
1680 if( tmp != "poly" )
1681 return false;
1682
1683 aStream >> tmp;
1684 int n_outlines = atoi( tmp.c_str() );
1685
1686 if( n_outlines < 0 )
1687 return false;
1688
1689 for( int j = 0; j < n_outlines; j++ )
1690 {
1691 SHAPE_LINE_CHAIN outline;
1692
1693 outline.SetClosed( true );
1694
1695 aStream >> tmp;
1696 int n_vertices = atoi( tmp.c_str() );
1697
1698 for( int v = 0; v < n_vertices; v++ )
1699 {
1700 VECTOR2I p;
1701
1702 aStream >> tmp; p.x = atoi( tmp.c_str() );
1703 aStream >> tmp; p.y = atoi( tmp.c_str() );
1704 outline.Append( p );
1705 }
1706
1707 paths.push_back( outline );
1708 }
1709
1710 m_polys.push_back( paths );
1711 }
1712
1713 return true;
1714}
1715
1716
1717const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1718{
1719 BOX2I bb;
1720
1721 for( unsigned i = 0; i < m_polys.size(); i++ )
1722 {
1723 if( i == 0 )
1724 bb = m_polys[i][0].BBox();
1725 else
1726 bb.Merge( m_polys[i][0].BBox() );
1727 }
1728
1729 bb.Inflate( aClearance );
1730 return bb;
1731}
1732
1733
1735{
1736 BOX2I bb;
1737
1738 for( unsigned i = 0; i < m_polys.size(); i++ )
1739 {
1740 if( i == 0 )
1741 bb = *m_polys[i][0].GetCachedBBox();
1742 else
1743 bb.Merge( *m_polys[i][0].GetCachedBBox() );
1744 }
1745
1746 return bb;
1747}
1748
1749
1751{
1752 // Iterate through all the polygons in the set
1753 for( const POLYGON& polygon : m_polys )
1754 {
1755 // Iterate through all the line chains in the polygon
1756 for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1757 {
1758 if( lineChain.PointOnEdge( aP ) )
1759 return true;
1760 }
1761 }
1762
1763 return false;
1764}
1765
1766
1767bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance, int* aActual,
1768 VECTOR2I* aLocation ) const
1769{
1770 VECTOR2I nearest;
1771 ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1772
1773 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1774 {
1775 if( aLocation )
1776 *aLocation = nearest;
1777
1778 if( aActual )
1779 *aActual = sqrt( dist_sq );
1780
1781 return true;
1782 }
1783
1784 return false;
1785}
1786
1787
1788bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
1789 VECTOR2I* aLocation ) const
1790{
1791 if( IsEmpty() || VertexCount() == 0 )
1792 return false;
1793
1794 VECTOR2I nearest;
1795 ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1796
1797 if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1798 {
1799 if( aLocation )
1800 *aLocation = nearest;
1801
1802 if( aActual )
1803 *aActual = sqrt( dist_sq );
1804
1805 return true;
1806 }
1807
1808 return false;
1809}
1810
1811
1812bool SHAPE_POLY_SET::Collide( const SHAPE* aShape, int aClearance, int* aActual,
1813 VECTOR2I* aLocation ) const
1814{
1815 // A couple of simple cases are worth trying before we fall back on triangulation.
1816
1817 if( aShape->Type() == SH_SEGMENT )
1818 {
1819 const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1820 int extra = segment->GetWidth() / 2;
1821
1822 if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1823 {
1824 if( aActual )
1825 *aActual = std::max( 0, *aActual - extra );
1826
1827 return true;
1828 }
1829
1830 return false;
1831 }
1832
1833 if( aShape->Type() == SH_CIRCLE )
1834 {
1835 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1836 int extra = circle->GetRadius();
1837
1838 if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1839 {
1840 if( aActual )
1841 *aActual = std::max( 0, *aActual - extra );
1842
1843 return true;
1844 }
1845
1846 return false;
1847 }
1848
1849 const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( false );
1850
1851 int actual = INT_MAX;
1852 VECTOR2I location;
1853
1854 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
1855 {
1856 for( const TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
1857 {
1858 if( aActual || aLocation )
1859 {
1860 int triActual;
1861 VECTOR2I triLocation;
1862
1863 if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1864 {
1865 if( triActual < actual )
1866 {
1867 actual = triActual;
1868 location = triLocation;
1869 }
1870 }
1871 }
1872 else // A much faster version of above
1873 {
1874 if( aShape->Collide( &tri, aClearance ) )
1875 return true;
1876 }
1877 }
1878 }
1879
1880 if( actual < INT_MAX )
1881 {
1882 if( aActual )
1883 *aActual = std::max( 0, actual );
1884
1885 if( aLocation )
1886 *aLocation = location;
1887
1888 return true;
1889 }
1890
1891 return false;
1892}
1893
1894
1896{
1897 m_polys.clear();
1898}
1899
1900
1901void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1902{
1903 // Default polygon is the last one
1904 if( aPolygonIdx < 0 )
1905 aPolygonIdx += m_polys.size();
1906
1907 m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1908}
1909
1910
1912{
1913 int removed = 0;
1914
1915 ITERATOR iterator = IterateWithHoles();
1916
1917 VECTOR2I contourStart = *iterator;
1918 VECTOR2I segmentStart, segmentEnd;
1919
1920 VERTEX_INDEX indexStart;
1921 std::vector<VERTEX_INDEX> indices_to_remove;
1922
1923 while( iterator )
1924 {
1925 // Obtain first point and its index
1926 segmentStart = *iterator;
1927 indexStart = iterator.GetIndex();
1928
1929 // Obtain last point
1930 if( iterator.IsEndContour() )
1931 {
1932 segmentEnd = contourStart;
1933
1934 // Advance
1935 iterator++;
1936
1937 // If we have rolled into the next contour, remember its position
1938 // segmentStart and segmentEnd remain valid for comparison here
1939 if( iterator )
1940 contourStart = *iterator;
1941 }
1942 else
1943 {
1944 // Advance
1945 iterator++;
1946
1947 // If we have reached the end of the SHAPE_POLY_SET, something is broken here
1948 wxCHECK_MSG( iterator, removed, wxT( "Invalid polygon. Reached end without noticing. Please report this error" ) );
1949
1950 segmentEnd = *iterator;
1951 }
1952
1953 // Remove segment start if both points are equal
1954 if( segmentStart == segmentEnd )
1955 {
1956 indices_to_remove.push_back( indexStart );
1957 removed++;
1958 }
1959 }
1960
1961 // Proceed in reverse direction to remove the vertices because they are stored as absolute indices in a vector
1962 // Removing in reverse order preserves the remaining index values
1963 for( auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
1964 RemoveVertex( *it );
1965
1966 return removed;
1967}
1968
1969
1971{
1972 m_polys.erase( m_polys.begin() + aIdx );
1973}
1974
1975
1977{
1978 m_polys.erase( m_polys.begin() + aIdx );
1979
1981 {
1982 for( int ii = m_triangulatedPolys.size() - 1; ii >= 0; --ii )
1983 {
1984 std::unique_ptr<TRIANGULATED_POLYGON>& triangleSet = m_triangulatedPolys[ii];
1985
1986 if( triangleSet->GetSourceOutlineIndex() == aIdx )
1987 m_triangulatedPolys.erase( m_triangulatedPolys.begin() + ii );
1988 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
1989 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
1990 }
1991
1992 if( aUpdateHash )
1993 m_hash = checksum();
1994 }
1995}
1996
1997
1999{
2000 m_hash = checksum();
2001}
2002
2003
2005{
2006 m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
2007}
2008
2009
2010void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
2011{
2012 Append( aP.x, aP.y, aOutline, aHole );
2013}
2014
2015
2017 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
2018 int aClearance ) const
2019{
2020 // Shows whether there was a collision
2021 bool collision = false;
2022
2023 // Difference vector between each vertex and aPoint.
2025 ecoord distance_squared;
2026 ecoord clearance_squared = SEG::Square( aClearance );
2027
2028 for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
2029 {
2030 // Get the difference vector between current vertex and aPoint
2031 delta = *iterator - aPoint;
2032
2033 // Compute distance
2034 distance_squared = delta.SquaredEuclideanNorm();
2035
2036 // Check for collisions
2037 if( distance_squared <= clearance_squared )
2038 {
2039 if( !aClosestVertex )
2040 return true;
2041
2042 collision = true;
2043
2044 // Update clearance to look for closer vertices
2045 clearance_squared = distance_squared;
2046
2047 // Store the indices that identify the vertex
2048 *aClosestVertex = iterator.GetIndex();
2049 }
2050 }
2051
2052 return collision;
2053}
2054
2055
2057 SHAPE_POLY_SET::VERTEX_INDEX* aClosestVertex,
2058 int aClearance ) const
2059{
2060 // Shows whether there was a collision
2061 bool collision = false;
2062 ecoord clearance_squared = SEG::Square( aClearance );
2063
2064 for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
2065 {
2066 const SEG currentSegment = *iterator;
2067 ecoord distance_squared = currentSegment.SquaredDistance( aPoint );
2068
2069 // Check for collisions
2070 if( distance_squared <= clearance_squared )
2071 {
2072 if( !aClosestVertex )
2073 return true;
2074
2075 collision = true;
2076
2077 // Update clearance to look for closer edges
2078 clearance_squared = distance_squared;
2079
2080 // Store the indices that identify the vertex
2081 *aClosestVertex = iterator.GetIndex();
2082 }
2083 }
2084
2085 return collision;
2086}
2087
2088
2090{
2091 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
2092 {
2093 COutline( polygonIdx ).GenerateBBoxCache();
2094
2095 for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
2096 CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
2097 }
2098}
2099
2100
2101bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
2102 bool aUseBBoxCaches ) const
2103{
2104 if( m_polys.empty() )
2105 return false;
2106
2107 // If there is a polygon specified, check the condition against that polygon
2108 if( aSubpolyIndex >= 0 )
2109 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2110
2111 // In any other case, check it against all polygons in the set
2112 for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
2113 {
2114 if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2115 return true;
2116 }
2117
2118 return false;
2119}
2120
2121
2122void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
2123{
2124 VERTEX_INDEX index;
2125
2126 // Assure the to be removed vertex exists, abort otherwise
2127 if( GetRelativeIndices( aGlobalIndex, &index ) )
2128 RemoveVertex( index );
2129 else
2130 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
2131}
2132
2133
2135{
2136 m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
2137}
2138
2139
2140void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
2141{
2142 VERTEX_INDEX index;
2143
2144 if( GetRelativeIndices( aGlobalIndex, &index ) )
2145 SetVertex( index, aPos );
2146 else
2147 throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
2148}
2149
2150
2151void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
2152{
2153 m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
2154}
2155
2156
2157bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
2158 bool aUseBBoxCaches ) const
2159{
2160 // Check that the point is inside the outline
2161 if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
2162 {
2163 // Check that the point is not in any of the holes
2164 for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
2165 {
2166 const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
2167
2168 // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
2169 // here as it's meaning would be inverted.
2170 if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
2171 return false;
2172 }
2173
2174 return true;
2175 }
2176
2177 return false;
2178}
2179
2180
2181void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
2182{
2183 for( POLYGON& poly : m_polys )
2184 {
2185 for( SHAPE_LINE_CHAIN& path : poly )
2186 path.Move( aVector );
2187 }
2188
2189 for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
2190 tri->Move( aVector );
2191
2192 m_hash = checksum();
2193}
2194
2195
2196void SHAPE_POLY_SET::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
2197{
2198 for( POLYGON& poly : m_polys )
2199 {
2200 for( SHAPE_LINE_CHAIN& path : poly )
2201 path.Mirror( aX, aY, aRef );
2202 }
2203
2206}
2207
2208
2209void SHAPE_POLY_SET::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
2210{
2211 for( POLYGON& poly : m_polys )
2212 {
2213 for( SHAPE_LINE_CHAIN& path : poly )
2214 path.Rotate( aAngle, aCenter );
2215 }
2216
2217 // Don't re-cache if the triangulation is already invalid
2220}
2221
2222
2224{
2225 int c = 0;
2226
2227 for( const POLYGON& poly : m_polys )
2228 {
2229 for( const SHAPE_LINE_CHAIN& path : poly )
2230 c += path.PointCount();
2231 }
2232
2233 return c;
2234}
2235
2236
2237SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
2238{
2239 return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
2240}
2241
2242
2243SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
2244 int aIndex )
2245{
2246 return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
2247}
2248
2249
2251 VECTOR2I* aNearest ) const
2252{
2253 // We calculate the min dist between the segment and each outline segment. However, if the
2254 // segment to test is inside the outline, and does not cross any edge, it can be seen outside
2255 // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
2256 // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
2257 if( containsSingle( aPoint, aPolygonIndex, 1 ) )
2258 {
2259 if( aNearest )
2260 *aNearest = aPoint;
2261
2262 return 0;
2263 }
2264
2265 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
2266
2267 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2268
2269 for( iterator++; iterator && minDistance > 0; iterator++ )
2270 {
2271 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2272
2273 if( currentDistance < minDistance )
2274 {
2275 if( aNearest )
2276 *aNearest = (*iterator).NearestPoint( aPoint );
2277
2278 minDistance = currentDistance;
2279 }
2280 }
2281
2282 return minDistance;
2283}
2284
2285
2287 VECTOR2I* aNearest ) const
2288{
2289 // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
2290 if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
2291 containsSingle( aSegment.B, aPolygonIndex, 1 ) )
2292 {
2293 if( aNearest )
2294 *aNearest = ( aSegment.A + aSegment.B ) / 2;
2295
2296 return 0;
2297 }
2298
2299 CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
2300 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2301
2302 if( aNearest && minDistance == 0 )
2303 *aNearest = ( *iterator ).NearestPoint( aSegment );
2304
2305 for( iterator++; iterator && minDistance > 0; iterator++ )
2306 {
2307 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2308
2309 if( currentDistance < minDistance )
2310 {
2311 if( aNearest )
2312 *aNearest = (*iterator).NearestPoint( aSegment );
2313
2314 minDistance = currentDistance;
2315 }
2316 }
2317
2318 // Return the maximum of minDistance and zero
2319 return minDistance < 0 ? 0 : minDistance;
2320}
2321
2322
2324{
2325 SEG::ecoord currentDistance_sq;
2326 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2327 VECTOR2I nearest;
2328
2329 // Iterate through all the polygons and get the minimum distance.
2330 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2331 {
2332 currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
2333 aNearest ? &nearest : nullptr );
2334
2335 if( currentDistance_sq < minDistance_sq )
2336 {
2337 if( aNearest )
2338 *aNearest = nearest;
2339
2340 minDistance_sq = currentDistance_sq;
2341 }
2342 }
2343
2344 return minDistance_sq;
2345}
2346
2347
2348SEG::ecoord SHAPE_POLY_SET::SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest ) const
2349{
2350 SEG::ecoord currentDistance_sq;
2351 SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
2352 VECTOR2I nearest;
2353
2354 // Iterate through all the polygons and get the minimum distance.
2355 for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
2356 {
2357 currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
2358 aNearest ? &nearest : nullptr );
2359
2360 if( currentDistance_sq < minDistance_sq )
2361 {
2362 if( aNearest )
2363 *aNearest = nearest;
2364
2365 minDistance_sq = currentDistance_sq;
2366 }
2367 }
2368
2369 return minDistance_sq;
2370}
2371
2372
2374{
2375 VERTEX_INDEX index;
2376
2377 // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
2378 if( !GetRelativeIndices( aGlobalIdx, &index ) )
2379 return false;
2380
2381 // The contour is a hole if its index is greater than zero
2382 return index.m_contour > 0;
2383}
2384
2385
2387{
2388 SHAPE_POLY_SET chamfered;
2389
2390 for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
2391 chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
2392
2393 return chamfered;
2394}
2395
2396
2397SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
2398{
2399 SHAPE_POLY_SET filleted;
2400
2401 for( size_t idx = 0; idx < m_polys.size(); idx++ )
2402 filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
2403
2404 return filleted;
2405}
2406
2407
2409 unsigned int aDistance,
2410 int aIndex, int aErrorMax )
2411{
2412 // Null segments create serious issues in calculations. Remove them:
2414
2415 SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
2417
2418 // If the chamfering distance is zero, then the polygon remain intact.
2419 if( aDistance == 0 )
2420 {
2421 return currentPoly;
2422 }
2423
2424 // Iterate through all the contours (outline and holes) of the polygon.
2425 for( SHAPE_LINE_CHAIN& currContour : currentPoly )
2426 {
2427 // Generate a new contour in the new polygon
2428 SHAPE_LINE_CHAIN newContour;
2429
2430 // Iterate through the vertices of the contour
2431 for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2432 {
2433 // Current vertex
2434 int x1 = currContour.CPoint( currVertex ).x;
2435 int y1 = currContour.CPoint( currVertex ).y;
2436
2437 // Indices for previous and next vertices.
2438 int prevVertex;
2439 int nextVertex;
2440
2441 // Previous and next vertices indices computation. Necessary to manage the edge cases.
2442
2443 // Previous vertex is the last one if the current vertex is the first one
2444 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2445
2446 // next vertex is the first one if the current vertex is the last one.
2447 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2448
2449 // Previous vertex computation
2450 double xa = currContour.CPoint( prevVertex ).x - x1;
2451 double ya = currContour.CPoint( prevVertex ).y - y1;
2452
2453 // Next vertex computation
2454 double xb = currContour.CPoint( nextVertex ).x - x1;
2455 double yb = currContour.CPoint( nextVertex ).y - y1;
2456
2457 // Compute the new distances
2458 double lena = hypot( xa, ya );
2459 double lenb = hypot( xb, yb );
2460
2461 // Make the final computations depending on the mode selected, chamfered or filleted.
2462 if( aMode == CORNER_MODE::CHAMFERED )
2463 {
2464 double distance = aDistance;
2465
2466 // Chamfer one half of an edge at most
2467 if( 0.5 * lena < distance )
2468 distance = 0.5 * lena;
2469
2470 if( 0.5 * lenb < distance )
2471 distance = 0.5 * lenb;
2472
2473 int nx1 = KiROUND( distance * xa / lena );
2474 int ny1 = KiROUND( distance * ya / lena );
2475
2476 newContour.Append( x1 + nx1, y1 + ny1 );
2477
2478 int nx2 = KiROUND( distance * xb / lenb );
2479 int ny2 = KiROUND( distance * yb / lenb );
2480
2481 newContour.Append( x1 + nx2, y1 + ny2 );
2482 }
2483 else // CORNER_MODE = FILLETED
2484 {
2485 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2486
2487 double radius = aDistance;
2488 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2489
2490 // Do nothing in case of parallel edges
2491 if( std::isinf( denom ) )
2492 continue;
2493
2494 // Limit rounding distance to one half of an edge
2495 if( 0.5 * lena * denom < radius )
2496 radius = 0.5 * lena * denom;
2497
2498 if( 0.5 * lenb * denom < radius )
2499 radius = 0.5 * lenb * denom;
2500
2501 // Calculate fillet arc absolute center point (xc, yx)
2502 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2503 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2504 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2505 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2506 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2507
2508 // Calculate arc start and end vectors
2509 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2510 double xs = x1 + k * xa / lena - xc;
2511 double ys = y1 + k * ya / lena - yc;
2512 double xe = x1 + k * xb / lenb - xc;
2513 double ye = y1 + k * yb / lenb - yc;
2514
2515 // Cosine of arc angle
2516 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2517
2518 // Make sure the argument is in [-1,1], interval in which the acos function is
2519 // defined
2520 if( argument < -1 )
2521 argument = -1;
2522 else if( argument > 1 )
2523 argument = 1;
2524
2525 double arcAngle = acos( argument );
2526 int segments = GetArcToSegmentCount( radius, aErrorMax,
2527 EDA_ANGLE( arcAngle, RADIANS_T ) );
2528
2529 double deltaAngle = arcAngle / segments;
2530 double startAngle = atan2( -ys, xs );
2531
2532 // Flip arc for inner corners
2533 if( xa * yb - ya * xb <= 0 )
2534 deltaAngle *= -1;
2535
2536 double nx = xc + xs;
2537 double ny = yc + ys;
2538
2539 newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2540
2541 // Store the previous added corner to make a sanity check
2542 int prevX = KiROUND( nx );
2543 int prevY = KiROUND( ny );
2544
2545 for( int j = 0; j < segments; j++ )
2546 {
2547 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2548 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2549
2550 // Sanity check: the rounding can produce repeated corners; do not add them.
2551 if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
2552 {
2553 newContour.Append( KiROUND( nx ), KiROUND( ny ) );
2554 prevX = KiROUND( nx );
2555 prevY = KiROUND( ny );
2556 }
2557 }
2558 }
2559 }
2560
2561 // Close the current contour and add it the new polygon
2562 newContour.SetClosed( true );
2563 newPoly.push_back( newContour );
2564 }
2565
2566 return newPoly;
2567}
2568
2569
2571{
2572 static_cast<SHAPE&>(*this) = aOther;
2573 m_polys = aOther.m_polys;
2574
2575 m_triangulatedPolys.clear();
2576
2577 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2578 {
2579 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2580 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2581 }
2582
2583 m_hash = aOther.m_hash;
2585
2586 return *this;
2587}
2588
2589
2591{
2592 if( !m_hash.IsValid() )
2593 return checksum();
2594
2595 return m_hash;
2596}
2597
2598
2600{
2602 return false;
2603
2604 if( !m_hash.IsValid() )
2605 return false;
2606
2607 MD5_HASH hash = checksum();
2608
2609 return hash == m_hash;
2610}
2611
2612
2614{
2615 BOX2I bb = aPoly.BBox();
2616
2617 double w = bb.GetWidth();
2618 double h = bb.GetHeight();
2619
2620 if( w == 0.0 || h == 0.0 )
2621 return aPoly;
2622
2623 int n_cells_x, n_cells_y;
2624
2625 if( w > h )
2626 {
2627 n_cells_x = w / aSize;
2628 n_cells_y = floor( h / w * n_cells_x ) + 1;
2629 }
2630 else
2631 {
2632 n_cells_y = h / aSize;
2633 n_cells_x = floor( w / h * n_cells_y ) + 1;
2634 }
2635
2636 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2637
2638 for( int yy = 0; yy < n_cells_y; yy++ )
2639 {
2640 for( int xx = 0; xx < n_cells_x; xx++ )
2641 {
2642 VECTOR2I p;
2643
2644 p.x = bb.GetX() + w * xx / n_cells_x;
2645 p.y = bb.GetY() + h * yy / n_cells_y;
2646
2647 VECTOR2I p2;
2648
2649 p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
2650 p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
2651
2652
2653 SHAPE_LINE_CHAIN mask;
2654 mask.Append( VECTOR2I( p.x, p.y ) );
2655 mask.Append( VECTOR2I( p2.x, p.y ) );
2656 mask.Append( VECTOR2I( p2.x, p2.y ) );
2657 mask.Append( VECTOR2I( p.x, p2.y ) );
2658 mask.SetClosed( true );
2659
2660 if( ( xx ^ yy ) & 1 )
2661 maskSetOdd.AddOutline( mask );
2662 else
2663 maskSetEven.AddOutline( mask );
2664 }
2665 }
2666
2667 ps1.BooleanIntersection( maskSetOdd, SHAPE_POLY_SET::PM_FAST );
2668 ps2.BooleanIntersection( maskSetEven, SHAPE_POLY_SET::PM_FAST );
2669 ps1.Fracture( SHAPE_POLY_SET::PM_FAST );
2670 ps2.Fracture( SHAPE_POLY_SET::PM_FAST );
2671
2672 for( int i = 0; i < ps2.OutlineCount(); i++ )
2673 ps1.AddOutline( ps2.COutline( i ) );
2674
2675 if( ps1.OutlineCount() )
2676 return ps1;
2677 else
2678 return aPoly;
2679}
2680
2681
2683{
2684 bool recalculate = !m_hash.IsValid();
2685 MD5_HASH hash;
2686
2688 recalculate = true;
2689
2690 if( !recalculate )
2691 {
2692 hash = checksum();
2693
2694 if( m_hash != hash )
2695 {
2696 m_hash = hash;
2697 recalculate = true;
2698 }
2699 }
2700
2701 if( !recalculate )
2702 return;
2703
2704 auto triangulate =
2705 []( SHAPE_POLY_SET& polySet, int forOutline,
2706 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest )
2707 {
2708 bool triangulationValid = false;
2709 int pass = 0;
2710
2711 while( polySet.OutlineCount() > 0 )
2712 {
2713 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
2714 dest.erase( dest.end() - 1 );
2715
2716 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
2717 PolygonTriangulation tess( *dest.back() );
2718
2719 // If the tessellation fails, we re-fracture the polygon, which will
2720 // first simplify the system before fracturing and removing the holes
2721 // This may result in multiple, disjoint polygons.
2722 if( !tess.TesselatePolygon( polySet.Polygon( 0 ).front() ) )
2723 {
2724 ++pass;
2725
2726 if( pass == 1 )
2727 polySet.Fracture( PM_FAST );
2728 else if( pass == 2 )
2729 polySet.Fracture( PM_STRICTLY_SIMPLE );
2730 else
2731 break;
2732
2733 triangulationValid = false;
2734 continue;
2735 }
2736
2737 polySet.DeletePolygon( 0 );
2738 triangulationValid = true;
2739 }
2740
2741 return triangulationValid;
2742 };
2743
2744 m_triangulatedPolys.clear();
2745 m_triangulationValid = true;
2746
2747 if( aPartition )
2748 {
2749 for( int ii = 0; ii < OutlineCount(); ++ii )
2750 {
2751 // This partitions into regularly-sized grids (1cm in Pcbnew)
2752 SHAPE_POLY_SET flattened( Outline( ii ) );
2753 flattened.ClearArcs();
2754 SHAPE_POLY_SET partitions = partitionPolyIntoRegularCellGrid( flattened, 1e7 );
2755
2756 m_triangulationValid &= triangulate( partitions, ii, m_triangulatedPolys );
2757 }
2758 }
2759 else
2760 {
2761 SHAPE_POLY_SET tmpSet( *this );
2762
2763 if( tmpSet.HasHoles() )
2764 tmpSet.Fracture( PM_FAST );
2765
2766 m_triangulationValid = triangulate( tmpSet, -1, m_triangulatedPolys );
2767 }
2768
2770 m_hash = checksum();
2771}
2772
2773
2775{
2776 MD5_HASH hash;
2777
2778 hash.Hash( m_polys.size() );
2779
2780 for( const POLYGON& outline : m_polys )
2781 {
2782 hash.Hash( outline.size() );
2783
2784 for( const SHAPE_LINE_CHAIN& lc : outline )
2785 {
2786 hash.Hash( lc.PointCount() );
2787
2788 for( int i = 0; i < lc.PointCount(); i++ )
2789 {
2790 hash.Hash( lc.CPoint( i ).x );
2791 hash.Hash( lc.CPoint( i ).y );
2792 }
2793 }
2794 }
2795
2796 hash.Finalize();
2797
2798 return hash;
2799}
2800
2801
2803{
2804 for( int i = 0; i < OutlineCount(); i++ )
2805 {
2806 if( hasTouchingHoles( CPolygon( i ) ) )
2807 return true;
2808 }
2809
2810 return false;
2811}
2812
2813
2815{
2816 std::set<long long> ptHashes;
2817
2818 for( const SHAPE_LINE_CHAIN& lc : aPoly )
2819 {
2820 for( const VECTOR2I& pt : lc.CPoints() )
2821 {
2822 const long long ptHash = (long long) pt.x << 32 | pt.y;
2823
2824 if( ptHashes.count( ptHash ) > 0 )
2825 return true;
2826
2827 ptHashes.insert( ptHash );
2828 }
2829 }
2830
2831 return false;
2832}
2833
2834
2836{
2837 return IsTriangulationUpToDate();
2838}
2839
2840
2842{
2843 size_t n = 0;
2844
2845 for( const std::unique_ptr<TRIANGULATED_POLYGON>& t : m_triangulatedPolys )
2846 n += t->GetTriangleCount();
2847
2848 return n;
2849}
2850
2851
2852void SHAPE_POLY_SET::GetIndexableSubshapes( std::vector<const SHAPE*>& aSubshapes ) const
2853{
2854 aSubshapes.reserve( GetIndexableSubshapeCount() );
2855
2856 for( const std::unique_ptr<TRIANGULATED_POLYGON>& tpoly : m_triangulatedPolys )
2857 {
2858 for( TRIANGULATED_POLYGON::TRI& tri : tpoly->Triangles() )
2859 aSubshapes.push_back( &tri );
2860 }
2861}
2862
2863
2865{
2866 BOX2I bbox( parent->m_vertices[a] );
2867 bbox.Merge( parent->m_vertices[b] );
2868 bbox.Merge( parent->m_vertices[c] );
2869
2870 if( aClearance != 0 )
2871 bbox.Inflate( aClearance );
2872
2873 return bbox;
2874}
2875
2876
2878{
2879 m_triangles.emplace_back( a, b, c, this );
2880}
2881
2882
2884{
2886 m_vertices = aOther.m_vertices;
2887 m_triangles = aOther.m_triangles;
2888
2889 for( TRI& tri : m_triangles )
2890 tri.parent = this;
2891}
2892
2893
2895{
2897 m_vertices = aOther.m_vertices;
2898 m_triangles = aOther.m_triangles;
2899
2900 for( TRI& tri : m_triangles )
2901 tri.parent = this;
2902
2903 return *this;
2904}
2905
2906
2908 m_sourceOutline( aSourceOutline )
2909{
2910}
2911
2912
2914{
2915}
2916
2917
2918const SHAPE_POLY_SET
2919SHAPE_POLY_SET::BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths,
2920 bool aReverseOrientation, bool aEvenOdd )
2921{
2922 ClipperLib::Clipper clipper;
2923 ClipperLib::PolyTree tree;
2924
2925 // fixme: do we need aReverseOrientation?
2926
2927 for( const SHAPE_LINE_CHAIN& path : aPaths )
2928 {
2929 ClipperLib::Path lc;
2930
2931 for( int i = 0; i < path.PointCount(); i++ )
2932 {
2933 lc.emplace_back( path.CPoint( i ).x, path.CPoint( i ).y );
2934 }
2935
2936 clipper.AddPath( lc, ClipperLib::ptSubject, true );
2937 }
2938
2939 clipper.StrictlySimple( true );
2940 clipper.Execute( ClipperLib::ctUnion, tree,
2941 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
2942 ClipperLib::pftNonZero );
2943 SHAPE_POLY_SET result;
2944
2945 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
2946 {
2947 if( !n->IsHole() )
2948 {
2949 int outl = result.NewOutline();
2950
2951 for( unsigned int i = 0; i < n->Contour.size(); i++ )
2952 result.Outline( outl ).Append( n->Contour[i].X, n->Contour[i].Y );
2953
2954 for( unsigned int i = 0; i < n->Childs.size(); i++ )
2955 {
2956 int outh = result.NewHole( outl );
2957 for( unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
2958 {
2959 result.Hole( outl, outh )
2960 .Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
2961 }
2962 }
2963 }
2964 }
2965
2966 return result;
2967}
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
coord_type GetTop() const
Definition: box2.h:194
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetY() const
Definition: box2.h:181
coord_type GetWidth() const
Definition: box2.h:187
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetLeft() const
Definition: box2.h:193
coord_type GetBottom() const
Definition: box2.h:190
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
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
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
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
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:223
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:95
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
Check if point aP lies inside a polygon (any type) defined by the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
bool IsClosed() const override
void GenerateBBoxCache() const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
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.
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.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
void AddTriangle(int a, int b, int c)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
Represent a set of closed polygons.
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.
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
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 intersection For aFastMode meaning, see function booleanOp.
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CONST_ITERATOR CIterateWithHoles() const
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
ITERATOR IterateWithHoles()
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
bool IsTriangulationUpToDate() const
void inflate2(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy)
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_STRATEGY
< define how inflate transform build inflated polygon
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon and its triangulation data from the set.
double Area()
Count the number of arc shapes present.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference 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
Delete aIdx-th polygon from the set.
POLYGON & Polygon(int aIndex)
int FullPointCount() const
Returns the number of holes in a given outline.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
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 BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
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 CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
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.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
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...
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void Simplify(POLYGON_MODE aFastMode)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly 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
Appends all the arcs in this polyset to aArcBuffer.
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any 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.
SHAPE_LINE_CHAIN & Outline(int aIndex)
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
int NewOutline()
Creates a new hole in a given outline.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool hasTouchingHoles(const POLYGON &aPoly) const
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)
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
void UpdateTriangulationDataHash()
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
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).
virtual size_t GetIndexableSubshapeCount() const override
MD5_HASH checksum() const
void importPolyPath(Clipper2Lib::PolyPath64 *aPolyPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
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 aGlobalIndex-th vertex in the poly set.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
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
Creates a new empty polygon in the set and returns its index.
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
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.
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:123
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:178
VECTOR2I::extended_type ecoord
Definition: shape.h:249
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
static bool empty(const wxTextEntryBase *aCtrl)
@ RADIANS_T
Definition: eda_angle.h:32
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
const bool operator==(const COLOR4D &lhs, const COLOR4D &rhs)
Equality operator, are two colors equal.
Definition: color4d.cpp:268
const bool operator!=(const COLOR4D &lhs, const COLOR4D &rhs)
Not equality operator, are two colors not equal.
Definition: color4d.cpp:274
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
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:49
@ SH_CIRCLE
circle
Definition: shape.h:47
@ SH_SEGMENT
line segment
Definition: shape.h:45
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
#define SEG_CNT_MAX
static SHAPE_POLY_SET partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize)
std::vector< FractureEdge * > FractureEdgeSet
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
FractureEdge * m_next
bool matches(int y) const
FractureEdge(int y=0)
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:118
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618