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