41#include <unordered_set>
45#include <clipper2/clipper.h>
67#if defined( __MINGW32__ )
68 #define TRIANGULATESIMPLIFICATIONLEVEL 50
69 #define ENABLECACHEFRIENDLYFRACTURE true
71 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
72 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
109 m_polys( aOther.m_polys )
137 m_polys( aOther.m_polys )
167 unsigned int contourIdx = 0;
170 int currentGlobalIdx = 0;
172 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
176 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
179 int totalPoints = currentContour.
PointCount();
181 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
184 if( currentGlobalIdx == aGlobalIdx )
186 aRelativeIndices->
m_polygon = polygonIdx;
187 aRelativeIndices->
m_contour = contourIdx;
188 aRelativeIndices->
m_vertex = vertexIdx;
204 int& aGlobalIdx )
const
206 int selectedVertex = aRelativeIndices.
m_vertex;
207 unsigned int selectedContour = aRelativeIndices.
m_contour;
208 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
211 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
212 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
218 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
220 currentPolygon =
Polygon( polygonIdx );
222 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
223 aGlobalIdx += currentPolygon[contourIdx].PointCount();
226 currentPolygon =
Polygon( selectedPolygon );
228 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
229 aGlobalIdx += currentPolygon[contourIdx].PointCount();
231 aGlobalIdx += selectedVertex;
248 poly.push_back( empty_path );
265 m_polys[aOutline].push_back( empty_path );
267 return m_polys.back().size() - 2;
285 assert( aOutline < (
int)
m_polys.size() );
286 assert( idx < (
int)
m_polys[aOutline].size() );
288 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
290 return m_polys[aOutline][idx].PointCount();
308 assert( aOutline < (
int)
m_polys.size() );
309 assert( idx < (
int)
m_polys[aOutline].size() );
311 m_polys[aOutline][idx].Append( aArc, aAccuracy );
313 return m_polys[aOutline][idx].PointCount();
321 if( aGlobalIndex < 0 )
334 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
354 if( aOutline >= (
int)
m_polys.size() )
357 if( idx >= (
int)
m_polys[aOutline].size() )
360 return m_polys[aOutline][idx].PointCount();
375 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
377 full_count +=
m_polys[ii][idx].PointCount();
387 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
391 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
410 assert( aOutline < (
int)
m_polys.size() );
411 assert( idx < (
int)
m_polys[aOutline].size() );
413 return m_polys[aOutline][idx].CPoint( aIndex );
423 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
453 else if( index.
m_vertex == lastpoint )
471 *aPrevious = previous;
487 std::vector<SEG> segments;
491 segments.emplace_back( *it );
493 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
495 int min_a_x = std::min( a.A.x, a.B.x );
496 int min_b_x = std::min( b.A.x, b.B.x );
498 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 ) );
501 for(
auto it = segments.begin(); it != segments.end(); ++it )
503 SEG& firstSegment = *it;
506 auto innerIterator = it;
507 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
508 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
511 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
513 SEG& secondSegment = *innerIterator;
514 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
515 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
519 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
523 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
526 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
537 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
551 poly.push_back( aOutline );
556 wxCHECK2_MSG( aOutline.
IsClosed(), poly.back().SetClosed(
true ),
557 "Warning: non-closed outline added to SHAPE_POLY_SET" );
572 assert( aOutline < (
int)
m_polys.size() );
576 assert( poly.size() );
578 poly.push_back( aHole );
580 return poly.size() - 2;
600 for(
int j = 0; j <
HoleCount( i ); j++ )
614 for(
size_t i = 0; i < poly.size(); i++ )
626 for(
size_t i = 0; i < poly.size(); i++ )
629 aArcBuffer.push_back( arc );
639 for(
size_t i = 0; i < poly.size(); i++ )
647 std::vector<SHAPE_LINE_CHAIN> contours;
650 contours.insert( contours.end(), poly.begin(), poly.end() );
652 std::map<int, std::set<int>> parentToChildren;
653 std::map<int, std::set<int>> childToParents;
656 contour.GenerateBBoxCache();
658 for(
size_t i = 0; i < contours.size(); i++ )
662 for(
size_t j = 0; j < contours.size(); j++ )
672 parentToChildren[i].emplace( j );
673 childToParents[j].emplace( i );
678 std::set<int> topLevelParents;
680 for(
size_t i = 0; i < contours.size(); i++ )
682 if( childToParents[i].size() == 0 )
684 topLevelParents.emplace( i );
690 std::function<void(
int,
int, std::vector<int> )>
process;
693 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
695 std::set<int> relParents = childToParents[myId];
697 for(
int pathId :
path )
699 int erased = relParents.erase( pathId );
700 wxASSERT( erased > 0 );
703 wxASSERT( relParents.size() == 0 );
707 bool isOutline =
path.size() % 2 == 0;
711 int outlineId = result.
AddOutline( contours[myId] );
712 myOutline = outlineId;
716 wxASSERT( parentOutlineId != -1 );
717 result.
AddHole( contours[myId], parentOutlineId );
720 auto it = parentToChildren.find( myId );
721 if( it != parentToChildren.end() )
723 std::vector<int> thisPath =
path;
724 thisPath.emplace_back( myId );
726 std::set<int> thisPathSet;
727 thisPathSet.insert( thisPath.begin(), thisPath.end() );
729 for(
int childId : it->second )
731 const std::set<int>& childPathSet = childToParents[childId];
733 if( thisPathSet != childPathSet )
736 process( childId, myOutline, thisPath );
741 for(
int topParentId : topLevelParents )
743 std::vector<int>
path;
763 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
764 "ClearArcs() before carrying out the boolean operation." ) );
767 Clipper2Lib::Clipper64 c;
769 std::vector<CLIPPER_Z_VALUE> zValues;
770 std::vector<SHAPE_ARC> arcBuffer;
771 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
773 Clipper2Lib::Paths64 paths;
774 Clipper2Lib::Paths64 clips;
778 for(
size_t i = 0; i < poly.size(); i++ )
780 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
786 for(
size_t i = 0; i < poly.size(); i++ )
788 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
792 c.AddSubject( paths );
795 Clipper2Lib::PolyTree64 solution;
797 Clipper2Lib::ZCallback64 callback =
798 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
799 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
800 Clipper2Lib::Point64 & pt )
803 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
807 retval = zValues.at( aZvalue ).m_SecondArcIdx;
809 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
810 retval = zValues.at( aZvalue ).m_FirstArcIdx;
816 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
818 ssize_t retval = arcIndex( aBottomZ );
822 if( retval != arcIndex( aTopZ, retval ) )
829 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
830 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
834 if( e1ArcSegmentIndex != -1 )
845 size_t z_value_ptr = zValues.size();
846 zValues.push_back( newZval );
850 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
856 c.SetZCallback( std::move( callback ) );
858 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
867 booleanOp( Clipper2Lib::ClipType::Union, b );
873 booleanOp( Clipper2Lib::ClipType::Difference, b );
879 booleanOp( Clipper2Lib::ClipType::Intersection, b );
885 booleanOp( Clipper2Lib::ClipType::Xor, b );
891 booleanOp( Clipper2Lib::ClipType::Union, a, b );
897 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
903 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
909 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
917 Inflate( aFactor, aCornerStrategy, aMaxError );
925 using namespace Clipper2Lib;
929 #define SEG_CNT_MAX 64
930 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
937 JoinType joinType = JoinType::Round;
938 double miterLimit = 2.0;
940 switch( aCornerStrategy )
942 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
943 joinType = JoinType::Miter;
947 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
948 joinType = JoinType::Miter;
951 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
952 joinType = JoinType::Miter;
955 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
956 joinType = JoinType::Square;
959 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
960 joinType = JoinType::Round;
964 std::vector<CLIPPER_Z_VALUE> zValues;
965 std::vector<SHAPE_ARC> arcBuffer;
971 for(
size_t i = 0; i < poly.size(); i++ )
972 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
974 c.AddPaths( paths, joinType, EndType::Polygon );
981 if( aCircleSegCount < 6 )
986 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
988 coeff = 1.0 - cos( M_PI / aCircleSegCount );
991 arc_tolerance_factor[aCircleSegCount] = coeff;
995 coeff = arc_tolerance_factor[aCircleSegCount];
998 c.ArcTolerance(
std::abs( aAmount ) * coeff );
999 c.MiterLimit( miterLimit );
1006 c.Execute( aAmount, paths );
1008 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1011 c2.PreserveCollinear(
false );
1012 c2.ReverseSolution(
false );
1013 c2.AddSubject( paths );
1014 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1018 c.Execute( aAmount, tree );
1029 using namespace Clipper2Lib;
1033 #define SEG_CNT_MAX 64
1034 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1041 JoinType joinType = JoinType::Round;
1042 double miterLimit = 2.0;
1044 switch( aCornerStrategy )
1046 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1047 joinType = JoinType::Miter;
1051 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1052 joinType = JoinType::Miter;
1055 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1056 joinType = JoinType::Miter;
1059 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1060 joinType = JoinType::Square;
1063 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1064 joinType = JoinType::Round;
1068 std::vector<CLIPPER_Z_VALUE> zValues;
1069 std::vector<SHAPE_ARC> arcBuffer;
1072 c.AddPath(
path, joinType, EndType::Butt );
1078 if( aCircleSegCount < 6 )
1079 aCircleSegCount = 6;
1083 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1085 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1088 arc_tolerance_factor[aCircleSegCount] = coeff;
1092 coeff = arc_tolerance_factor[aCircleSegCount];
1095 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1096 c.MiterLimit( miterLimit );
1103 c.Execute( aAmount, paths2 );
1105 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1108 c2.PreserveCollinear(
false );
1109 c2.ReverseSolution(
false );
1110 c2.AddSubject( paths2 );
1111 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1115 c.Execute( aAmount, tree );
1128 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1137 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1142 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1143 const std::vector<SHAPE_ARC>& aArcBuffer )
1145 if( !aPolyPath->IsHole() )
1148 paths.reserve( aPolyPath->Count() + 1 );
1149 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1151 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1153 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1155 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1165 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1166 const std::vector<SHAPE_ARC>& aArcBuffer )
1170 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1176 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1177 const std::vector<SHAPE_ARC>& aArcBuffer )
1182 for(
const Clipper2Lib::Path64& n : aPath )
1184 if( Clipper2Lib::Area( n ) > 0 )
1193 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1196 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1233 int x = edge.
m_p1.
x;
1234 int y = edge.
m_p1.
y;
1235 int min_dist = std::numeric_limits<int>::max();
1254 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1262 int dist = ( x - x_intersect );
1264 if( dist >= 0 && dist < min_dist )
1267 x_nearest = x_intersect;
1280 edges[hole2outline_index] =
1283 edges[split_index] =
1288 e_nearest->
m_next = outline2hole_index;
1291 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1293 last->
m_next = hole2outline_index;
1303 bool outline =
true;
1305 if( paths.size() == 1 )
1308 size_t total_point_count = 0;
1312 total_point_count +=
path.PointCount();
1315 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1317 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1324 edges.reserve( total_point_count + paths.size() * 3 );
1330 int path_or_provoking_index;
1335 std::vector<PathInfo> sorted_paths;
1336 const int paths_count =
static_cast<int>( paths.size() );
1337 sorted_paths.reserve( paths_count );
1339 for(
int path_index = 0; path_index < paths_count; path_index++ )
1342 const std::vector<VECTOR2I>& points =
path.CPoints();
1343 const int point_count =
static_cast<int>( points.size() );
1344 int x_min = std::numeric_limits<int>::max();
1345 int y_min = std::numeric_limits<int>::max();
1348 for(
int point_index = 0; point_index < point_count; point_index++ )
1350 const VECTOR2I& point = points[point_index];
1351 if( point.
x < x_min )
1354 leftmost = point_index;
1356 if( point.
y < y_min )
1360 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1363 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1364 [](
const PathInfo& a,
const PathInfo& b )
1367 return a.y_or_bridge < b.y_or_bridge;
1373 for( PathInfo& path_info : sorted_paths )
1376 const std::vector<VECTOR2I>& points =
path.CPoints();
1377 const size_t point_count = points.size();
1382 for(
size_t i = 0; i < point_count - 1; i++ )
1384 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1389 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1396 path_info.path_or_provoking_index = provoking_edge;
1397 path_info.y_or_bridge = edge_index;
1401 edges.resize( edge_index );
1407 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1409 auto edge =
processHole( edges, it->path_or_provoking_index,
1410 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1415 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1463 int x = edge->
m_p1.
x;
1464 int y = edge->
m_p1.
y;
1465 int min_dist = std::numeric_limits<int>::max();
1472 if( !e->matches( y ) )
1477 if( e->m_p1.y == e->m_p2.y )
1479 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1483 x_intersect = e->m_p1.x
1484 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1487 int dist = ( x - x_intersect );
1489 if( dist >= 0 && dist < min_dist && e->m_connected )
1492 x_nearest = x_intersect;
1508 edges.push_back( split_2 );
1509 edges.push_back( lead1 );
1510 edges.push_back( lead2 );
1515 e_nearest->
m_next = lead1;
1520 for( last = edge; last->
m_next != edge; last = last->
m_next )
1546 if( paths.size() == 1 )
1549 int num_unconnected = 0;
1553 const std::vector<VECTOR2I>& points =
path.CPoints();
1554 int pointCount = points.size();
1558 int x_min = std::numeric_limits<int>::max();
1560 for(
int i = 0; i < pointCount; i++ )
1562 if( points[i].x < x_min )
1563 x_min = points[i].x;
1568 points[i + 1 == pointCount ? 0 : i + 1] );
1579 if( i == pointCount - 1 )
1583 edges.push_back( fe );
1587 if( fe->
m_p1.
x == x_min )
1588 border_edges.push_back( fe );
1599 while( num_unconnected > 0 )
1601 int x_min = std::numeric_limits<int>::max();
1602 auto it = border_edges.begin();
1607 for( ; it != border_edges.end(); ++it )
1610 int xt = border_edge->
m_p1.
x;
1612 if( ( xt <= x_min ) && !border_edge->
m_connected )
1615 smallestX = border_edge;
1619 int num_processed =
processEdge( edges, smallestX );
1622 if( !num_processed )
1624 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1632 num_unconnected -= num_processed;
1650 paths.push_back( std::move( newPath ) );
1673 assert( aPoly.size() == 1 );
1679 bool m_duplicate =
false;
1686 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1688 return (s1.
A == s2.
B && s1.
B == s2.
A);
1693 return compareSegs( m_poly->
CSegment( m_index ),
1694 aOther.m_poly->CSegment( aOther.m_index ) );
1699 return !compareSegs( m_poly->
CSegment( m_index ),
1700 aOther.m_poly->CSegment( aOther.m_index ) );
1705 std::size_t operator()(
const EDGE& aEdge )
const
1707 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1708 std::size_t seed = 0xa82de1c0;
1715 struct EDGE_LIST_ENTRY
1718 EDGE_LIST_ENTRY*
next;
1721 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1726 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1730 edgeList[i].index = i;
1731 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1734 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1739 uniqueEdges.insert( e );
1745 auto it = uniqueEdges.find( e );
1747 if( it != uniqueEdges.end() && it->m_index != i )
1749 int e1 = it->m_index;
1753 std::swap( e1, e2 );
1755 int e1_prev = e1 - 1;
1760 int e2_prev = e2 - 1;
1765 int e1_next = e1 + 1;
1770 int e2_next = e2 + 1;
1775 edgeList[e1_prev].next = &edgeList[ e2_next ];
1776 edgeList[e2_prev].next = &edgeList[ e1_next ];
1777 edgeList[i].next =
nullptr;
1778 edgeList[it->m_index].next =
nullptr;
1784 if( edgeList[i].
next )
1785 queue.insert( &edgeList[i] );
1788 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1794 double max_poly = 0.0;
1796 while( queue.size() )
1798 EDGE_LIST_ENTRY* e_first = *queue.begin();
1799 EDGE_LIST_ENTRY* e = e_first;
1806 }
while( e && e != e_first );
1810 for(
int i = 0; i < cnt; i++ )
1814 queue.erase( edgeBuf[i] );
1819 double area = std::fabs( outl.
Area() );
1821 if( area > max_poly )
1827 result.push_back( outl );
1832 std::swap( result[0], result[outline] );
1844 if( paths.size() > 1 )
1876 path.Simplify( aMaxError );
1894 while( outline.size() > 1 )
1919 std::stringstream ss;
1921 ss <<
"SHAPE_LINE_CHAIN poly; \n";
1923 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1925 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
1928 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
1934 ss <<
" poly.AddOutline(tmp); } \n";
1938 ss <<
" poly.AddHole(tmp); } \n";
1954 if( tmp !=
"polyset" )
1959 int n_polys = atoi( tmp.c_str() );
1964 for(
int i = 0; i < n_polys; i++ )
1974 int n_outlines = atoi( tmp.c_str() );
1976 if( n_outlines < 0 )
1979 for(
int j = 0; j < n_outlines; j++ )
1986 int n_vertices = atoi( tmp.c_str() );
1988 for(
int v = 0; v < n_vertices; v++ )
1992 aStream >> tmp; p.
x = atoi( tmp.c_str() );
1993 aStream >> tmp; p.
y = atoi( tmp.c_str() );
1997 paths.push_back( outline );
2011 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2028 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2031 bb = *
m_polys[i][0].GetCachedBBox();
2048 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2063 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2066 *aLocation = nearest;
2069 *aActual = sqrt( dist_sq );
2087 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2090 *aLocation = nearest;
2093 *aActual = sqrt( dist_sq );
2110 int extra = segment->
GetWidth() / 2;
2112 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2115 *aActual = std::max( 0, *aActual - extra );
2128 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
2131 *aActual = std::max( 0, *aActual - extra );
2141 int actual = INT_MAX;
2148 if( aActual || aLocation )
2153 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2155 if( triActual < actual )
2158 location = triLocation;
2164 if( aShape->
Collide( &tri, aClearance ) )
2170 if( actual < INT_MAX )
2173 *aActual = std::max( 0, actual );
2176 *aLocation = location;
2194 if( aPolygonIdx < 0 )
2195 aPolygonIdx +=
m_polys.size();
2197 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2217 std::vector<VERTEX_INDEX> indices_to_remove;
2222 segmentStart = *iterator;
2228 segmentEnd = contourStart;
2236 contourStart = *iterator;
2244 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2246 segmentEnd = *iterator;
2250 if( segmentStart == segmentEnd )
2252 indices_to_remove.push_back( indexStart );
2259 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2282 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2284 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2285 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2312 Append( aP.
x, aP.
y, aOutline, aHole );
2318 int aClearance )
const
2321 bool collision =
false;
2331 delta = *iterator - aPoint;
2334 distance_squared =
delta.SquaredEuclideanNorm();
2337 if( distance_squared <= clearance_squared )
2339 if( !aClosestVertex )
2345 clearance_squared = distance_squared;
2348 *aClosestVertex = iterator.GetIndex();
2358 int aClearance )
const
2361 bool collision =
false;
2366 const SEG currentSegment = *iterator;
2370 if( distance_squared <= clearance_squared )
2372 if( !aClosestVertex )
2378 clearance_squared = distance_squared;
2381 *aClosestVertex = iterator.GetIndex();
2391 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2395 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2402 bool aUseBBoxCaches )
const
2408 if( aSubpolyIndex >= 0 )
2409 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2412 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2414 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2430 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2447 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2458 bool aUseBBoxCaches )
const
2464 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2486 path.Move( aVector );
2490 tri->Move( aVector );
2502 path.Mirror( aRef, aFlipDirection );
2515 path.Rotate( aAngle, aCenter );
2531 c +=
path.PointCount();
2568 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2570 for( iterator++; iterator && minDistance > 0; iterator++ )
2572 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2574 if( currentDistance < minDistance )
2577 *aNearest = (*iterator).NearestPoint( aPoint );
2579 minDistance = currentDistance;
2595 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2601 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2603 if( aNearest && minDistance == 0 )
2604 *aNearest = ( *iterator ).NearestPoint( aSegment );
2606 for( iterator++; iterator && minDistance > 0; iterator++ )
2610 if( currentDistance < minDistance )
2613 *aNearest = (*iterator).NearestPoint( aSegment );
2615 minDistance = currentDistance;
2620 return minDistance < 0 ? 0 : minDistance;
2627 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2628 "support aOutlineOnly==true" ) );
2635 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2638 aNearest ? &nearest :
nullptr );
2640 if( currentDistance_sq < minDistance_sq )
2643 *aNearest = nearest;
2645 minDistance_sq = currentDistance_sq;
2649 return minDistance_sq;
2660 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2663 aNearest ? &nearest :
nullptr );
2665 if( currentDistance_sq < minDistance_sq )
2668 *aNearest = nearest;
2670 minDistance_sq = currentDistance_sq;
2674 return minDistance_sq;
2695 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2706 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2714 unsigned int aDistance,
2715 int aIndex,
int aErrorMax )
2724 if( aDistance == 0 )
2736 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2739 int x1 = currContour.
CPoint( currVertex ).
x;
2740 int y1 = currContour.CPoint( currVertex ).y;
2749 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2752 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2755 double xa = currContour.CPoint( prevVertex ).x - x1;
2756 double ya = currContour.CPoint( prevVertex ).y - y1;
2759 double xb = currContour.CPoint( nextVertex ).x - x1;
2760 double yb = currContour.CPoint( nextVertex ).y - y1;
2763 if(
std::abs( xa + xb ) < std::numeric_limits<double>::epsilon()
2764 &&
std::abs( ya + yb ) < std::numeric_limits<double>::epsilon() )
2770 double lena = hypot( xa, ya );
2771 double lenb = hypot( xb, yb );
2788 newContour.
Append( x1 + nx1, y1 + ny1 );
2793 newContour.
Append( x1 + nx2, y1 + ny2 );
2797 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2799 double radius = aDistance;
2800 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2803 if( std::isinf( denom ) )
2807 if( 0.5 * lena * denom < radius )
2808 radius = 0.5 * lena * denom;
2810 if( 0.5 * lenb * denom < radius )
2811 radius = 0.5 * lenb * denom;
2814 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2815 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2816 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2817 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2818 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2821 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2822 double xs = x1 + k * xa / lena - xc;
2823 double ys = y1 + k * ya / lena - yc;
2824 double xe = x1 + k * xb / lenb - xc;
2825 double ye = y1 + k * yb / lenb - yc;
2828 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2834 else if( argument > 1 )
2837 double arcAngle = acos( argument );
2841 double deltaAngle = arcAngle / segments;
2842 double startAngle = atan2( -ys, xs );
2845 if( xa * yb - ya * xb <= 0 )
2848 double nx = xc + xs;
2849 double ny = yc + ys;
2851 if( std::isnan( nx ) || std::isnan( ny ) )
2860 for(
int j = 0; j < segments; j++ )
2862 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2863 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2865 if( std::isnan( nx ) || std::isnan( ny ) )
2881 newPoly.push_back( newContour );
2890 static_cast<SHAPE&
>(*this) = aOther;
2939 if( w == 0.0 || h == 0.0 )
2942 int n_cells_x, n_cells_y;
2946 n_cells_x = w / aSize;
2947 n_cells_y = floor( h / w * n_cells_x ) + 1;
2951 n_cells_y = h / aSize;
2952 n_cells_x = floor( w / h * n_cells_y ) + 1;
2955 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2957 for(
int yy = 0; yy < n_cells_y; yy++ )
2959 for(
int xx = 0; xx < n_cells_x; xx++ )
2963 p.
x = bb.
GetX() + w * xx / n_cells_x;
2964 p.
y = bb.
GetY() + h * yy / n_cells_y;
2968 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2969 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2977 mask.SetClosed(
true );
2979 if( ( xx ^ yy ) & 1 )
2986 ps1.BooleanIntersection( maskSetOdd );
2987 ps2.BooleanIntersection( maskSetEven );
2991 for(
int i = 0; i < ps2.OutlineCount(); i++ )
2992 ps1.AddOutline( ps2.COutline( i ) );
2994 if( ps1.OutlineCount() )
3002 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3018 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3019 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3021 bool triangulationValid =
false;
3025 if( hintData && hintData->size() != (unsigned) polySet.
OutlineCount() )
3030 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3031 dest.erase( dest.end() - 1 );
3033 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3040 hintData ? hintData->at( index ).get() :
nullptr ) )
3054 triangulationValid =
false;
3061 triangulationValid =
true;
3064 return triangulationValid;
3076 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
3083 else if( aSimplify )
3092 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
3133 hash.
add( outline.size() );
3137 hash.
add( lc.PointCount() );
3139 for(
int i = 0; i < lc.PointCount(); i++ )
3167 std::set<long long> ptHashes;
3171 for(
const VECTOR2I& pt : lc.CPoints() )
3173 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3175 if( ptHashes.count( ptHash ) > 0 )
3178 ptHashes.insert( ptHash );
3197 n += t->GetTriangleCount();
3210 aSubshapes.push_back( &tri );
3221 if( aClearance != 0 )
3273 Clipper2Lib::Clipper64 clipper;
3274 Clipper2Lib::PolyTree64 tree;
3275 Clipper2Lib::Paths64 paths;
3279 Clipper2Lib::Path64 lc;
3280 lc.reserve(
path.PointCount() );
3282 for(
int i = 0; i <
path.PointCount(); i++ )
3283 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3285 paths.push_back( lc );
3288 clipper.AddSubject( paths );
3289 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
3290 : Clipper2Lib::FillRule::NonZero, tree );
3293 std::vector<CLIPPER_Z_VALUE> zValues;
3294 std::vector<SHAPE_ARC> arcBuffer;
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
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.
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.
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.
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
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
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
@ 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...
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I