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