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