41#include <unordered_set>
45#include <clipper2/clipper.h>
64#if defined( __MINGW32__ )
65 #define TRIANGULATESIMPLIFICATIONLEVEL 50
66 #define ENABLECACHEFRIENDLYFRACTURE true
68 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
69 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
106 m_polys( aOther.m_polys )
133 m_polys( aOther.m_polys )
162 unsigned int contourIdx = 0;
165 int currentGlobalIdx = 0;
167 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
171 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
174 int totalPoints = currentContour.
PointCount();
176 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
179 if( currentGlobalIdx == aGlobalIdx )
181 aRelativeIndices->
m_polygon = polygonIdx;
182 aRelativeIndices->
m_contour = contourIdx;
183 aRelativeIndices->
m_vertex = vertexIdx;
199 int& aGlobalIdx )
const
201 int selectedVertex = aRelativeIndices.
m_vertex;
202 unsigned int selectedContour = aRelativeIndices.
m_contour;
203 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
206 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
207 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
213 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
215 currentPolygon =
Polygon( polygonIdx );
217 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
218 aGlobalIdx += currentPolygon[contourIdx].PointCount();
221 currentPolygon =
Polygon( selectedPolygon );
223 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
224 aGlobalIdx += currentPolygon[contourIdx].PointCount();
226 aGlobalIdx += selectedVertex;
243 poly.push_back( empty_path );
244 m_polys.push_back( std::move( poly ) );
260 m_polys[aOutline].push_back( empty_path );
262 return m_polys.back().size() - 2;
280 assert( aOutline < (
int)
m_polys.size() );
281 assert( idx < (
int)
m_polys[aOutline].size() );
283 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
285 return m_polys[aOutline][idx].PointCount();
290 std::optional<int> aMaxError )
304 assert( aOutline < (
int)
m_polys.size() );
305 assert( idx < (
int)
m_polys[aOutline].size() );
307 if( aMaxError.has_value() )
308 m_polys[aOutline][idx].Append( aArc, aMaxError.value() );
310 m_polys[aOutline][idx].Append( aArc );
312 return m_polys[aOutline][idx].PointCount();
320 if( aGlobalIndex < 0 )
333 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
353 if( aOutline >= (
int)
m_polys.size() )
356 if( idx >= (
int)
m_polys[aOutline].size() )
359 return m_polys[aOutline][idx].PointCount();
374 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
376 full_count +=
m_polys[ii][idx].PointCount();
386 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
390 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
409 assert( aOutline < (
int)
m_polys.size() );
410 assert( idx < (
int)
m_polys[aOutline].size() );
412 return m_polys[aOutline][idx].CPoint( aIndex );
422 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
452 else if( index.
m_vertex == lastpoint )
470 *aPrevious = previous;
486 std::vector<SEG> segments;
490 segments.emplace_back( *it );
492 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
494 int min_a_x = std::min( a.A.x, a.B.x );
495 int min_b_x = std::min( b.A.x, b.B.x );
497 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 ) );
500 for(
auto it = segments.begin(); it != segments.end(); ++it )
502 SEG& firstSegment = *it;
505 auto innerIterator = it;
506 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
507 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
510 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
512 SEG& secondSegment = *innerIterator;
513 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
514 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
518 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
522 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
525 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
536 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
550 poly.push_back( aOutline );
555 wxCHECK2_MSG( aOutline.
IsClosed(), poly.back().SetClosed(
true ),
556 "Warning: non-closed outline added to SHAPE_POLY_SET" );
558 m_polys.push_back( std::move( poly ) );
560 return (
int)
m_polys.size() - 1;
569 aOutline += (int)
m_polys.size();
571 assert( aOutline < (
int)
m_polys.size() );
575 assert( poly.size() );
577 poly.push_back( aHole );
579 return (
int) poly.size() - 2;
599 for(
int j = 0; j <
HoleCount( i ); j++ )
613 for(
size_t i = 0; i < poly.size(); i++ )
625 for(
size_t i = 0; i < poly.size(); i++ )
628 aArcBuffer.push_back( arc );
638 for(
size_t i = 0; i < poly.size(); i++ )
646 std::vector<SHAPE_LINE_CHAIN> contours;
649 contours.insert( contours.end(), poly.begin(), poly.end() );
651 std::map<int, std::set<int>> parentToChildren;
652 std::map<int, std::set<int>> childToParents;
655 contour.GenerateBBoxCache();
657 for(
size_t i = 0; i < contours.size(); i++ )
661 for(
size_t j = 0; j < contours.size(); j++ )
671 parentToChildren[i].emplace( j );
672 childToParents[j].emplace( i );
677 std::set<int> topLevelParents;
679 for(
size_t i = 0; i < contours.size(); i++ )
681 if( childToParents[i].size() == 0 )
683 topLevelParents.emplace( i );
689 std::function<void(
int,
int, std::vector<int> )>
process;
692 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
694 std::set<int> relParents = childToParents[myId];
696 for(
int pathId :
path )
698 int erased = relParents.erase( pathId );
699 wxASSERT( erased > 0 );
702 wxASSERT( relParents.size() == 0 );
706 bool isOutline =
path.size() % 2 == 0;
710 int outlineId = result.
AddOutline( contours[myId] );
711 myOutline = outlineId;
715 wxASSERT( parentOutlineId != -1 );
716 result.
AddHole( contours[myId], parentOutlineId );
719 auto it = parentToChildren.find( myId );
720 if( it != parentToChildren.end() )
722 std::vector<int> thisPath =
path;
723 thisPath.emplace_back( myId );
725 std::set<int> thisPathSet;
726 thisPathSet.insert( thisPath.begin(), thisPath.end() );
728 for(
int childId : it->second )
730 const std::set<int>& childPathSet = childToParents[childId];
732 if( thisPathSet != childPathSet )
735 process( childId, myOutline, thisPath );
740 for(
int topParentId : topLevelParents )
742 std::vector<int>
path;
746 *
this = std::move( result );
762 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
763 "ClearArcs() before carrying out the boolean operation." ) );
766 Clipper2Lib::Clipper64 c;
768 std::vector<CLIPPER_Z_VALUE> zValues;
769 std::vector<SHAPE_ARC> arcBuffer;
770 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
772 Clipper2Lib::Paths64 paths;
773 Clipper2Lib::Paths64 clips;
777 for(
size_t i = 0; i < poly.size(); i++ )
779 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
785 for(
size_t i = 0; i < poly.size(); i++ )
787 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
791 c.AddSubject( paths );
794 Clipper2Lib::PolyTree64 solution;
796 Clipper2Lib::ZCallback64 callback =
797 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
798 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
799 Clipper2Lib::Point64 & pt )
802 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
806 retval = zValues.at( aZvalue ).m_SecondArcIdx;
808 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
809 retval = zValues.at( aZvalue ).m_FirstArcIdx;
815 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
817 ssize_t retval = arcIndex( aBottomZ );
821 if( retval != arcIndex( aTopZ, retval ) )
828 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
829 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
833 if( e1ArcSegmentIndex != -1 )
844 size_t z_value_ptr = zValues.size();
845 zValues.push_back( newZval );
849 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
855 c.SetZCallback( std::move( callback ) );
857 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
866 booleanOp( Clipper2Lib::ClipType::Union, b );
872 booleanOp( Clipper2Lib::ClipType::Difference, b );
878 booleanOp( Clipper2Lib::ClipType::Intersection, b );
884 booleanOp( Clipper2Lib::ClipType::Xor, b );
890 booleanOp( Clipper2Lib::ClipType::Union, a, b );
896 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
902 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
908 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
916 Inflate( aFactor, aCornerStrategy, aMaxError );
924 using namespace Clipper2Lib;
928 #define SEG_CNT_MAX 64
929 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
936 JoinType joinType = JoinType::Round;
937 double miterLimit = 2.0;
939 switch( aCornerStrategy )
941 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
942 joinType = JoinType::Miter;
946 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
947 joinType = JoinType::Miter;
950 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
951 joinType = JoinType::Miter;
954 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
955 joinType = JoinType::Square;
958 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
959 joinType = JoinType::Round;
963 std::vector<CLIPPER_Z_VALUE> zValues;
964 std::vector<SHAPE_ARC> arcBuffer;
970 for(
size_t i = 0; i < poly.size(); i++ )
971 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
973 c.AddPaths( paths, joinType, EndType::Polygon );
980 if( aCircleSegCount < 6 )
985 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
987 coeff = 1.0 - cos( M_PI / aCircleSegCount );
990 arc_tolerance_factor[aCircleSegCount] = coeff;
994 coeff = arc_tolerance_factor[aCircleSegCount];
997 c.ArcTolerance(
std::abs( aAmount ) * coeff );
998 c.MiterLimit( miterLimit );
1005 c.Execute( aAmount, paths );
1007 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1010 c2.PreserveCollinear(
false );
1011 c2.ReverseSolution(
false );
1012 c2.AddSubject( paths );
1013 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1017 c.Execute( aAmount, tree );
1028 using namespace Clipper2Lib;
1032 #define SEG_CNT_MAX 64
1033 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1040 JoinType joinType = JoinType::Round;
1041 double miterLimit = 2.0;
1043 switch( aCornerStrategy )
1045 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1046 joinType = JoinType::Miter;
1050 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1051 joinType = JoinType::Miter;
1054 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1055 joinType = JoinType::Miter;
1058 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1059 joinType = JoinType::Square;
1062 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1063 joinType = JoinType::Round;
1067 std::vector<CLIPPER_Z_VALUE> zValues;
1068 std::vector<SHAPE_ARC> arcBuffer;
1071 c.AddPath(
path, joinType, EndType::Butt );
1077 if( aCircleSegCount < 6 )
1078 aCircleSegCount = 6;
1082 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1084 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1087 arc_tolerance_factor[aCircleSegCount] = coeff;
1091 coeff = arc_tolerance_factor[aCircleSegCount];
1094 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1095 c.MiterLimit( miterLimit );
1102 c.Execute( aAmount, paths2 );
1104 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1107 c2.PreserveCollinear(
false );
1108 c2.ReverseSolution(
false );
1109 c2.AddSubject( paths2 );
1110 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1114 c.Execute( aAmount, tree );
1127 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1136 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1141 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1142 const std::vector<SHAPE_ARC>& aArcBuffer )
1144 if( !aPolyPath->IsHole() )
1147 paths.reserve( aPolyPath->Count() + 1 );
1148 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1150 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1152 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1154 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1158 m_polys.emplace_back( std::move( paths ) );
1164 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1165 const std::vector<SHAPE_ARC>& aArcBuffer )
1169 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1175 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1176 const std::vector<SHAPE_ARC>& aArcBuffer )
1181 for(
const Clipper2Lib::Path64& n : aPath )
1183 if( Clipper2Lib::Area( n ) > 0 )
1192 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1195 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1234 int x = edge.
m_p1.
x;
1235 int y = edge.
m_p1.
y;
1236 int min_dist = std::numeric_limits<int>::max();
1255 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1263 int dist = ( x - x_intersect );
1265 if( dist >= 0 && dist < min_dist )
1268 x_nearest = x_intersect;
1281 edges[hole2outline_index] =
1284 edges[split_index] =
1289 e_nearest->
m_next = outline2hole_index;
1292 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1294 last->
m_next = hole2outline_index;
1304 bool outline =
true;
1306 if( paths.size() == 1 )
1309 size_t total_point_count = 0;
1313 total_point_count +=
path.PointCount();
1316 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1318 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1325 edges.reserve( total_point_count + paths.size() * 3 );
1331 int path_or_provoking_index;
1336 std::vector<PathInfo> sorted_paths;
1337 const int paths_count =
static_cast<int>( paths.size() );
1338 sorted_paths.reserve( paths_count );
1340 for(
int path_index = 0; path_index < paths_count; path_index++ )
1343 const std::vector<VECTOR2I>& points =
path.CPoints();
1344 const int point_count =
static_cast<int>( points.size() );
1345 int x_min = std::numeric_limits<int>::max();
1346 int y_min = std::numeric_limits<int>::max();
1349 for(
int point_index = 0; point_index < point_count; point_index++ )
1351 const VECTOR2I& point = points[point_index];
1352 if( point.
x < x_min )
1355 leftmost = point_index;
1357 if( point.
y < y_min )
1361 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1364 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1365 [](
const PathInfo& a,
const PathInfo& b )
1368 return a.y_or_bridge < b.y_or_bridge;
1374 for( PathInfo& path_info : sorted_paths )
1377 const std::vector<VECTOR2I>& points =
path.CPoints();
1378 const size_t point_count = points.size();
1383 for(
size_t i = 0; i < point_count - 1; i++ )
1385 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1390 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1397 path_info.path_or_provoking_index = provoking_edge;
1398 path_info.y_or_bridge = edge_index;
1402 edges.resize( edge_index );
1408 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1410 auto edge =
processHole( edges, it->path_or_provoking_index,
1411 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1416 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1464 int x = edge->
m_p1.
x;
1465 int y = edge->
m_p1.
y;
1466 int min_dist = std::numeric_limits<int>::max();
1473 if( !e->matches( y ) )
1478 if( e->m_p1.y == e->m_p2.y )
1480 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1484 x_intersect = e->m_p1.x
1485 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1488 int dist = ( x - x_intersect );
1490 if( dist >= 0 && dist < min_dist && e->m_connected )
1493 x_nearest = x_intersect;
1509 edges.push_back( split_2 );
1510 edges.push_back( lead1 );
1511 edges.push_back( lead2 );
1516 e_nearest->
m_next = lead1;
1521 for( last = edge; last->
m_next != edge; last = last->
m_next )
1547 if( paths.size() == 1 )
1550 int num_unconnected = 0;
1554 const std::vector<VECTOR2I>& points =
path.CPoints();
1555 int pointCount = points.size();
1559 int x_min = std::numeric_limits<int>::max();
1561 for(
int i = 0; i < pointCount; i++ )
1563 if( points[i].x < x_min )
1564 x_min = points[i].x;
1569 points[i + 1 == pointCount ? 0 : i + 1] );
1580 if( i == pointCount - 1 )
1584 edges.push_back( fe );
1588 if( fe->
m_p1.
x == x_min )
1589 border_edges.push_back( fe );
1600 while( num_unconnected > 0 )
1602 int x_min = std::numeric_limits<int>::max();
1603 auto it = border_edges.begin();
1608 for( ; it != border_edges.end(); ++it )
1611 int xt = border_edge->
m_p1.
x;
1613 if( ( xt <= x_min ) && !border_edge->
m_connected )
1616 smallestX = border_edge;
1620 int num_processed =
processEdge( edges, smallestX );
1623 if( !num_processed )
1625 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1633 num_unconnected -= num_processed;
1651 paths.push_back( std::move( newPath ) );
1674 assert( aPoly.size() == 1 );
1680 bool m_duplicate =
false;
1687 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1689 return (s1.
A == s2.
B && s1.
B == s2.
A);
1694 return compareSegs( m_poly->
CSegment( m_index ),
1695 aOther.m_poly->CSegment( aOther.m_index ) );
1700 return !compareSegs( m_poly->
CSegment( m_index ),
1701 aOther.m_poly->CSegment( aOther.m_index ) );
1706 std::size_t operator()(
const EDGE& aEdge )
const
1708 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1709 std::size_t seed = 0xa82de1c0;
1716 struct EDGE_LIST_ENTRY
1719 EDGE_LIST_ENTRY*
next;
1722 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1727 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1731 edgeList[i].index = i;
1732 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1735 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1740 uniqueEdges.insert( e );
1746 auto it = uniqueEdges.find( e );
1748 if( it != uniqueEdges.end() && it->m_index != i )
1750 int e1 = it->m_index;
1754 std::swap( e1, e2 );
1756 int e1_prev = e1 - 1;
1761 int e2_prev = e2 - 1;
1766 int e1_next = e1 + 1;
1771 int e2_next = e2 + 1;
1776 edgeList[e1_prev].next = &edgeList[ e2_next ];
1777 edgeList[e2_prev].next = &edgeList[ e1_next ];
1778 edgeList[i].next =
nullptr;
1779 edgeList[it->m_index].next =
nullptr;
1785 if( edgeList[i].
next )
1786 queue.insert( &edgeList[i] );
1789 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1795 double max_poly = 0.0;
1797 while( queue.size() )
1799 EDGE_LIST_ENTRY* e_first = *queue.begin();
1800 EDGE_LIST_ENTRY* e = e_first;
1807 }
while( e && e != e_first );
1811 for(
int i = 0; i < cnt; i++ )
1815 queue.erase( edgeBuf[i] );
1820 double area = std::fabs( outl.
Area() );
1822 if( area > max_poly )
1828 result.push_back( outl );
1833 std::swap( result[0], result[outline] );
1835 aPoly = std::move( result );
1845 if( paths.size() > 1 )
1877 path.Simplify( aTolerance );
1895 while( outline.size() > 1 )
1920 std::stringstream ss;
1922 ss <<
"SHAPE_LINE_CHAIN poly; \n";
1924 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1926 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
1929 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
1935 ss <<
" poly.AddOutline(tmp); } \n";
1939 ss <<
" poly.AddHole(tmp); } \n";
1955 if( tmp !=
"polyset" )
1960 int n_polys = atoi( tmp.c_str() );
1965 for(
int i = 0; i < n_polys; i++ )
1975 int n_outlines = atoi( tmp.c_str() );
1977 if( n_outlines < 0 )
1980 for(
int j = 0; j < n_outlines; j++ )
1987 int n_vertices = atoi( tmp.c_str() );
1989 for(
int v = 0; v < n_vertices; v++ )
1993 aStream >> tmp; p.
x = atoi( tmp.c_str() );
1994 aStream >> tmp; p.
y = atoi( tmp.c_str() );
1998 paths.push_back( std::move( outline ) );
2001 m_polys.push_back( std::move( paths ) );
2012 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2029 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2032 bb = *
m_polys[i][0].GetCachedBBox();
2049 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2064 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2067 *aLocation = nearest;
2070 *aActual = sqrt( dist_sq );
2088 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2091 *aLocation = nearest;
2094 *aActual = sqrt( dist_sq );
2111 int extra = segment->
GetWidth() / 2;
2113 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2116 *aActual = std::max( 0, *aActual - extra );
2132 *aActual = std::max( 0, *aActual - extra );
2149 if( aActual || aLocation )
2154 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2165 if( aShape->
Collide( &tri, aClearance ) )
2174 *aActual = std::max( 0,
actual );
2195 if( aPolygonIdx < 0 )
2196 aPolygonIdx +=
m_polys.size();
2198 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2218 std::vector<VERTEX_INDEX> indices_to_remove;
2223 segmentStart = *iterator;
2229 segmentEnd = contourStart;
2237 contourStart = *iterator;
2245 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2247 segmentEnd = *iterator;
2251 if( segmentStart == segmentEnd )
2253 indices_to_remove.push_back( indexStart );
2260 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2283 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2285 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2286 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2313 Append( aP.
x, aP.
y, aOutline, aHole );
2319 int aClearance )
const
2322 bool collision =
false;
2332 delta = *iterator - aPoint;
2335 distance_squared =
delta.SquaredEuclideanNorm();
2338 if( distance_squared <= clearance_squared )
2340 if( !aClosestVertex )
2346 clearance_squared = distance_squared;
2349 *aClosestVertex = iterator.GetIndex();
2359 int aClearance )
const
2362 bool collision =
false;
2367 const SEG currentSegment = *iterator;
2371 if( distance_squared <= clearance_squared )
2373 if( !aClosestVertex )
2379 clearance_squared = distance_squared;
2382 *aClosestVertex = iterator.GetIndex();
2392 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2396 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2403 bool aUseBBoxCaches )
const
2409 if( aSubpolyIndex >= 0 )
2410 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2413 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2415 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2431 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2448 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2459 bool aUseBBoxCaches )
const
2465 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2487 path.Move( aVector );
2491 tri->Move( aVector );
2503 path.Mirror( aRef, aFlipDirection );
2516 path.Rotate( aAngle, aCenter );
2532 c +=
path.PointCount();
2569 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2571 for( iterator++; iterator && minDistance > 0; iterator++ )
2573 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2575 if( currentDistance < minDistance )
2578 *aNearest = (*iterator).NearestPoint( aPoint );
2580 minDistance = currentDistance;
2596 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2602 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2604 if( aNearest && minDistance == 0 )
2605 *aNearest = ( *iterator ).NearestPoint( aSegment );
2607 for( iterator++; iterator && minDistance > 0; iterator++ )
2611 if( currentDistance < minDistance )
2614 *aNearest = (*iterator).NearestPoint( aSegment );
2616 minDistance = currentDistance;
2621 return minDistance < 0 ? 0 : minDistance;
2628 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2629 "support aOutlineOnly==true" ) );
2636 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2639 aNearest ? &nearest :
nullptr );
2641 if( currentDistance_sq < minDistance_sq )
2644 *aNearest = nearest;
2646 minDistance_sq = currentDistance_sq;
2650 return minDistance_sq;
2661 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2664 aNearest ? &nearest :
nullptr );
2666 if( currentDistance_sq < minDistance_sq )
2669 *aNearest = nearest;
2671 minDistance_sq = currentDistance_sq;
2675 return minDistance_sq;
2696 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2707 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2716 SHAPE::operator=( aOther );
2776 if( w == 0.0 || h == 0.0 )
2779 int n_cells_x, n_cells_y;
2783 n_cells_x = w / aSize;
2784 n_cells_y = floor( h / w * n_cells_x ) + 1;
2788 n_cells_y = h / aSize;
2789 n_cells_x = floor( w / h * n_cells_y ) + 1;
2792 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2794 for(
int yy = 0; yy < n_cells_y; yy++ )
2796 for(
int xx = 0; xx < n_cells_x; xx++ )
2800 p.
x = bb.
GetX() + w * xx / n_cells_x;
2801 p.
y = bb.
GetY() + h * yy / n_cells_y;
2805 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2806 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2814 mask.SetClosed(
true );
2816 if( ( xx ^ yy ) & 1 )
2823 ps1.BooleanIntersection( maskSetOdd );
2824 ps2.BooleanIntersection( maskSetEven );
2828 for(
int i = 0; i < ps2.OutlineCount(); i++ )
2829 ps1.AddOutline( ps2.COutline( i ) );
2831 if( ps1.OutlineCount() )
2839 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
2855 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
2856 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
2858 bool triangulationValid =
false;
2862 if( hintData && hintData->size() != (unsigned) polySet.
OutlineCount() )
2867 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
2868 dest.erase( dest.end() - 1 );
2870 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
2877 hintData ? hintData->at( index ).get() :
nullptr ) )
2891 triangulationValid =
false;
2898 triangulationValid =
true;
2901 return triangulationValid;
2913 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
2920 else if( aSimplify )
2929 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
2970 hash.
add( outline.size() );
2974 hash.
add( lc.PointCount() );
2976 for(
int i = 0; i < lc.PointCount(); i++ )
3004 std::set<long long> ptHashes;
3008 for(
const VECTOR2I& pt : lc.CPoints() )
3010 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3012 if( ptHashes.count( ptHash ) > 0 )
3015 ptHashes.insert( ptHash );
3034 n += t->GetTriangleCount();
3047 aSubshapes.push_back( &tri );
3058 if( aClearance != 0 )
3110 Clipper2Lib::Clipper64 clipper;
3111 Clipper2Lib::PolyTree64 tree;
3112 Clipper2Lib::Paths64 paths;
3116 Clipper2Lib::Path64 lc;
3117 lc.reserve(
path.PointCount() );
3119 for(
int i = 0; i <
path.PointCount(); i++ )
3120 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3122 paths.push_back( std::move( lc ) );
3125 clipper.AddSubject( paths );
3126 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
3127 : Clipper2Lib::FillRule::NonZero, tree );
3129 std::vector<CLIPPER_Z_VALUE> zValues;
3130 std::vector<SHAPE_ARC> arcBuffer;
3150 int aSpacing,
int aLineLength )
const
3152 std::vector<SEG> hatchLines;
3162 if( iterator->x < min_x )
3163 min_x = iterator->x;
3165 if( iterator->x > max_x )
3166 max_x = iterator->x;
3168 if( iterator->y < min_y )
3169 min_y = iterator->y;
3171 if( iterator->y > max_y )
3172 max_y = iterator->y;
3175 auto sortEndsByDescendingX =
3178 return tst.x < ref.
x;
3181 for(
double slope : aSlopes )
3183 int64_t max_a, min_a;
3187 max_a = KiROUND<double, int64_t>( max_y - slope * min_x );
3188 min_a = KiROUND<double, int64_t>( min_y - slope * max_x );
3192 max_a = KiROUND<double, int64_t>( max_y - slope * max_x );
3193 min_a = KiROUND<double, int64_t>( min_y - slope * min_x );
3196 min_a = ( min_a / aSpacing ) * aSpacing;
3199 std::vector<VECTOR2I> pointbuffer;
3200 pointbuffer.reserve( 256 );
3202 for( int64_t a = min_a; a < max_a; a += aSpacing )
3204 pointbuffer.clear();
3210 const SEG seg = *iterator;
3216 if( pt.
x < min_x || pt.
x > max_x || pt.
y < min_y || pt.
y > max_y )
3227 if( pointbuffer.size() > 2 )
3228 sort( pointbuffer.begin(), pointbuffer.end(), sortEndsByDescendingX );
3231 for(
size_t ip = 0; ip + 1 < pointbuffer.size(); ip += 2 )
3233 int dx = pointbuffer[ip + 1].x - pointbuffer[ip].x;
3237 if( aLineLength == -1 ||
std::abs( dx ) < 2 * aLineLength )
3239 hatchLines.emplace_back(
SEG( pointbuffer[ip], pointbuffer[ ip + 1] ) );
3243 double dy = pointbuffer[ip + 1].y - pointbuffer[ip].y;
3251 int x1 =
KiROUND( pointbuffer[ip].x + dx );
3252 int x2 =
KiROUND( pointbuffer[ip + 1].x - dx );
3253 int y1 =
KiROUND( pointbuffer[ip].y + dx * slope );
3254 int y2 =
KiROUND( pointbuffer[ip + 1].y - dx * slope );
3256 hatchLines.emplace_back(
SEG( pointbuffer[ip].x, pointbuffer[ip].y, x1, y1 ) );
3258 hatchLines.emplace_back(
SEG( pointbuffer[ip+1].x, pointbuffer[ip+1].y, x2,
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
bool operator!=(const BOM_FIELD &lhs, const BOM_FIELD &rhs)
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr coord_type GetY() const
constexpr size_type GetWidth() const
constexpr coord_type GetX() const
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr size_type GetHeight() const
constexpr coord_type GetLeft() const
constexpr coord_type GetRight() const
constexpr coord_type GetTop() const
constexpr coord_type GetBottom() const
A streaming C++ equivalent for MurmurHash3_x64_128.
FORCE_INLINE void add(const std::string &input)
FORCE_INLINE HASH_128 digest()
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
ecoord SquaredDistance(const SEG &aSeg) const
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
VECTOR2I::extended_type ecoord
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
static SEG::ecoord Square(int a)
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
SHAPE_TYPE Type() const
Return the type of the shape.
const VECTOR2I GetCenter() const
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.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
bool IsEndContour() const
Base class for iterating over all segments in a given SHAPE_POLY_SET.
TRIANGULATED_POLYGON(int aSourceOutline)
std::deque< TRI > m_triangles
std::deque< VECTOR2I > m_vertices
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.
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.
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::vector< SEG > GenerateHatchLines(const std::vector< double > &aSlopes, int aSpacing, int aLineLength) const
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
An abstract shape on 2D plane.
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,...
VECTOR2I::extended_type ecoord
constexpr extended_type SquaredDistance(const VECTOR2< T > &aVector) const
Compute the squared distance between two vectors.
static constexpr extended_type ECOORD_MAX
CORNER_STRATEGY
define how inflate transform build inflated polygon
static bool empty(const wxTextEntryBase *aCtrl)
static constexpr EDA_ANGLE FULL_CIRCLE
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.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
static PGM_BASE * process
#define TRIANGULATE_TRACE
#define TRIANGULATESIMPLIFICATIONLEVEL
@ SH_POLY_SET
set of polygons (with holes, etc.)
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
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(int y=0)
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)
bool matches(int y) const
A storage class for 128-bit hash value.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
TRIANGULATED_POLYGON * parent
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I