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 )
136 m_polys( aOther.m_polys )
165 unsigned int contourIdx = 0;
168 int currentGlobalIdx = 0;
170 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
174 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
177 int totalPoints = currentContour.
PointCount();
179 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
182 if( currentGlobalIdx == aGlobalIdx )
184 aRelativeIndices->
m_polygon = polygonIdx;
185 aRelativeIndices->
m_contour = contourIdx;
186 aRelativeIndices->
m_vertex = vertexIdx;
202 int& aGlobalIdx )
const
204 int selectedVertex = aRelativeIndices.
m_vertex;
205 unsigned int selectedContour = aRelativeIndices.
m_contour;
206 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
209 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
210 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
216 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
218 currentPolygon =
Polygon( polygonIdx );
220 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
221 aGlobalIdx += currentPolygon[contourIdx].PointCount();
224 currentPolygon =
Polygon( selectedPolygon );
226 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
227 aGlobalIdx += currentPolygon[contourIdx].PointCount();
229 aGlobalIdx += selectedVertex;
246 poly.push_back( empty_path );
263 m_polys[aOutline].push_back( empty_path );
265 return m_polys.back().size() - 2;
283 assert( aOutline < (
int)
m_polys.size() );
284 assert( idx < (
int)
m_polys[aOutline].size() );
286 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
288 return m_polys[aOutline][idx].PointCount();
306 assert( aOutline < (
int)
m_polys.size() );
307 assert( idx < (
int)
m_polys[aOutline].size() );
309 m_polys[aOutline][idx].Append( aArc, aAccuracy );
311 return m_polys[aOutline][idx].PointCount();
319 if( aGlobalIndex < 0 )
332 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
352 if( aOutline >= (
int)
m_polys.size() )
355 if( idx >= (
int)
m_polys[aOutline].size() )
358 return m_polys[aOutline][idx].PointCount();
373 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
375 full_count +=
m_polys[ii][idx].PointCount();
385 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
389 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
408 assert( aOutline < (
int)
m_polys.size() );
409 assert( idx < (
int)
m_polys[aOutline].size() );
411 return m_polys[aOutline][idx].CPoint( aIndex );
421 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
451 else if( index.
m_vertex == lastpoint )
469 *aPrevious = previous;
485 std::vector<SEG> segments;
489 segments.emplace_back( *it );
491 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
493 int min_a_x = std::min( a.A.x, a.B.x );
494 int min_b_x = std::min( b.A.x, b.B.x );
496 return min_a_x < min_b_x || ( min_a_x == min_b_x && std::min( a.A.y, a.B.y ) < std::min( b.A.y, b.B.y ) );
499 for(
auto it = segments.begin(); it != segments.end(); ++it )
501 SEG& firstSegment = *it;
504 auto innerIterator = it;
505 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
506 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
509 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
511 SEG& secondSegment = *innerIterator;
512 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
513 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
517 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
521 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
524 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
535 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
549 poly.push_back( aOutline );
554 wxCHECK2_MSG( aOutline.
IsClosed(), poly.back().SetClosed(
true ),
555 "Warning: non-closed outline added to SHAPE_POLY_SET" );
570 assert( aOutline < (
int)
m_polys.size() );
574 assert( poly.size() );
576 poly.push_back( aHole );
578 return poly.size() - 2;
598 for(
int j = 0; j <
HoleCount( i ); j++ )
612 for(
size_t i = 0; i < poly.size(); i++ )
624 for(
size_t i = 0; i < poly.size(); i++ )
627 aArcBuffer.push_back( arc );
637 for(
size_t i = 0; i < poly.size(); i++ )
645 std::vector<SHAPE_LINE_CHAIN> contours;
648 contours.insert( contours.end(), poly.begin(), poly.end() );
650 std::map<int, std::set<int>> parentToChildren;
651 std::map<int, std::set<int>> childToParents;
654 contour.GenerateBBoxCache();
656 for(
size_t i = 0; i < contours.size(); i++ )
660 for(
size_t j = 0; j < contours.size(); j++ )
670 parentToChildren[i].emplace( j );
671 childToParents[j].emplace( i );
676 std::set<int> topLevelParents;
678 for(
size_t i = 0; i < contours.size(); i++ )
680 if( childToParents[i].size() == 0 )
682 topLevelParents.emplace( i );
688 std::function<void(
int,
int, std::vector<int> )>
process;
691 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
693 std::set<int> relParents = childToParents[myId];
695 for(
int pathId :
path )
697 int erased = relParents.erase( pathId );
698 wxASSERT( erased > 0 );
701 wxASSERT( relParents.size() == 0 );
705 bool isOutline =
path.size() % 2 == 0;
709 int outlineId = result.
AddOutline( contours[myId] );
710 myOutline = outlineId;
714 wxASSERT( parentOutlineId != -1 );
715 result.
AddHole( contours[myId], parentOutlineId );
718 auto it = parentToChildren.find( myId );
719 if( it != parentToChildren.end() )
721 std::vector<int> thisPath =
path;
722 thisPath.emplace_back( myId );
724 std::set<int> thisPathSet;
725 thisPathSet.insert( thisPath.begin(), thisPath.end() );
727 for(
int childId : it->second )
729 const std::set<int>& childPathSet = childToParents[childId];
731 if( thisPathSet != childPathSet )
734 process( childId, myOutline, thisPath );
739 for(
int topParentId : topLevelParents )
741 std::vector<int>
path;
761 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
762 "ClearArcs() before carrying out the boolean operation." ) );
765 Clipper2Lib::Clipper64 c;
767 std::vector<CLIPPER_Z_VALUE> zValues;
768 std::vector<SHAPE_ARC> arcBuffer;
769 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
771 Clipper2Lib::Paths64 paths;
772 Clipper2Lib::Paths64 clips;
776 for(
size_t i = 0; i < poly.size(); i++ )
778 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
784 for(
size_t i = 0; i < poly.size(); i++ )
786 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
790 c.AddSubject( paths );
793 Clipper2Lib::PolyTree64 solution;
795 Clipper2Lib::ZCallback64 callback =
796 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
797 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
798 Clipper2Lib::Point64 & pt )
801 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
805 retval = zValues.at( aZvalue ).m_SecondArcIdx;
807 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
808 retval = zValues.at( aZvalue ).m_FirstArcIdx;
814 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
816 ssize_t retval = arcIndex( aBottomZ );
820 if( retval != arcIndex( aTopZ, retval ) )
827 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
828 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
832 if( e1ArcSegmentIndex != -1 )
843 size_t z_value_ptr = zValues.size();
844 zValues.push_back( newZval );
848 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
854 c.SetZCallback( std::move( callback ) );
856 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
865 booleanOp( Clipper2Lib::ClipType::Union, b );
871 booleanOp( Clipper2Lib::ClipType::Difference, b );
877 booleanOp( Clipper2Lib::ClipType::Intersection, b );
883 booleanOp( Clipper2Lib::ClipType::Xor, b );
889 booleanOp( Clipper2Lib::ClipType::Union, a, b );
895 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
901 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
907 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
915 Inflate( aFactor, aCornerStrategy, aMaxError );
923 using namespace Clipper2Lib;
927 #define SEG_CNT_MAX 64
928 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
935 JoinType joinType = JoinType::Round;
936 double miterLimit = 2.0;
938 switch( aCornerStrategy )
940 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
941 joinType = JoinType::Miter;
945 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
946 joinType = JoinType::Miter;
949 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
950 joinType = JoinType::Miter;
953 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
954 joinType = JoinType::Square;
957 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
958 joinType = JoinType::Round;
962 std::vector<CLIPPER_Z_VALUE> zValues;
963 std::vector<SHAPE_ARC> arcBuffer;
969 for(
size_t i = 0; i < poly.size(); i++ )
970 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
972 c.AddPaths( paths, joinType, EndType::Polygon );
979 if( aCircleSegCount < 6 )
984 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
986 coeff = 1.0 - cos( M_PI / aCircleSegCount );
989 arc_tolerance_factor[aCircleSegCount] = coeff;
993 coeff = arc_tolerance_factor[aCircleSegCount];
996 c.ArcTolerance(
std::abs( aAmount ) * coeff );
997 c.MiterLimit( miterLimit );
1004 c.Execute( aAmount, paths );
1006 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1009 c2.PreserveCollinear(
false );
1010 c2.ReverseSolution(
false );
1011 c2.AddSubject( paths );
1012 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1016 c.Execute( aAmount, tree );
1027 using namespace Clipper2Lib;
1031 #define SEG_CNT_MAX 64
1032 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1039 JoinType joinType = JoinType::Round;
1040 double miterLimit = 2.0;
1042 switch( aCornerStrategy )
1044 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1045 joinType = JoinType::Miter;
1049 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1050 joinType = JoinType::Miter;
1053 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1054 joinType = JoinType::Miter;
1057 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1058 joinType = JoinType::Square;
1061 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1062 joinType = JoinType::Round;
1066 std::vector<CLIPPER_Z_VALUE> zValues;
1067 std::vector<SHAPE_ARC> arcBuffer;
1070 c.AddPath(
path, joinType, EndType::Butt );
1076 if( aCircleSegCount < 6 )
1077 aCircleSegCount = 6;
1081 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1083 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1086 arc_tolerance_factor[aCircleSegCount] = coeff;
1090 coeff = arc_tolerance_factor[aCircleSegCount];
1093 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1094 c.MiterLimit( miterLimit );
1101 c.Execute( aAmount, paths2 );
1103 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1106 c2.PreserveCollinear(
false );
1107 c2.ReverseSolution(
false );
1108 c2.AddSubject( paths2 );
1109 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1113 c.Execute( aAmount, tree );
1126 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1135 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1140 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1141 const std::vector<SHAPE_ARC>& aArcBuffer )
1143 if( !aPolyPath->IsHole() )
1146 paths.reserve( aPolyPath->Count() + 1 );
1147 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1149 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1151 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1153 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1163 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1164 const std::vector<SHAPE_ARC>& aArcBuffer )
1168 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1174 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1175 const std::vector<SHAPE_ARC>& aArcBuffer )
1180 for(
const Clipper2Lib::Path64& n : aPath )
1182 if( Clipper2Lib::Area( n ) > 0 )
1191 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1194 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1231 int x = edge.
m_p1.
x;
1232 int y = edge.
m_p1.
y;
1233 int min_dist = std::numeric_limits<int>::max();
1252 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1260 int dist = ( x - x_intersect );
1262 if( dist >= 0 && dist < min_dist )
1265 x_nearest = x_intersect;
1278 edges[hole2outline_index] =
1281 edges[split_index] =
1286 e_nearest->
m_next = outline2hole_index;
1289 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1291 last->
m_next = hole2outline_index;
1301 bool outline =
true;
1303 if( paths.size() == 1 )
1306 size_t total_point_count = 0;
1310 total_point_count +=
path.PointCount();
1313 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1315 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1322 edges.reserve( total_point_count + paths.size() * 3 );
1328 int path_or_provoking_index;
1333 std::vector<PathInfo> sorted_paths;
1334 const int paths_count =
static_cast<int>( paths.size() );
1335 sorted_paths.reserve( paths_count );
1337 for(
int path_index = 0; path_index < paths_count; path_index++ )
1340 const std::vector<VECTOR2I>& points =
path.CPoints();
1341 const int point_count =
static_cast<int>( points.size() );
1342 int x_min = std::numeric_limits<int>::max();
1343 int y_min = std::numeric_limits<int>::max();
1346 for(
int point_index = 0; point_index < point_count; point_index++ )
1348 const VECTOR2I& point = points[point_index];
1349 if( point.
x < x_min )
1352 leftmost = point_index;
1354 if( point.
y < y_min )
1358 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1361 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1362 [](
const PathInfo& a,
const PathInfo& b )
1365 return a.y_or_bridge < b.y_or_bridge;
1371 for( PathInfo& path_info : sorted_paths )
1374 const std::vector<VECTOR2I>& points =
path.CPoints();
1375 const size_t point_count = points.size();
1380 for(
size_t i = 0; i < point_count - 1; i++ )
1382 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1387 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1394 path_info.path_or_provoking_index = provoking_edge;
1395 path_info.y_or_bridge = edge_index;
1399 edges.resize( edge_index );
1405 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1407 auto edge =
processHole( edges, it->path_or_provoking_index,
1408 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1413 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1461 int x = edge->
m_p1.
x;
1462 int y = edge->
m_p1.
y;
1463 int min_dist = std::numeric_limits<int>::max();
1470 if( !e->matches( y ) )
1475 if( e->m_p1.y == e->m_p2.y )
1477 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1481 x_intersect = e->m_p1.x
1482 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1485 int dist = ( x - x_intersect );
1487 if( dist >= 0 && dist < min_dist && e->m_connected )
1490 x_nearest = x_intersect;
1506 edges.push_back( split_2 );
1507 edges.push_back( lead1 );
1508 edges.push_back( lead2 );
1513 e_nearest->
m_next = lead1;
1518 for( last = edge; last->
m_next != edge; last = last->
m_next )
1544 if( paths.size() == 1 )
1547 int num_unconnected = 0;
1551 const std::vector<VECTOR2I>& points =
path.CPoints();
1552 int pointCount = points.size();
1556 int x_min = std::numeric_limits<int>::max();
1558 for(
int i = 0; i < pointCount; i++ )
1560 if( points[i].x < x_min )
1561 x_min = points[i].x;
1566 points[i + 1 == pointCount ? 0 : i + 1] );
1577 if( i == pointCount - 1 )
1581 edges.push_back( fe );
1585 if( fe->
m_p1.
x == x_min )
1586 border_edges.push_back( fe );
1597 while( num_unconnected > 0 )
1599 int x_min = std::numeric_limits<int>::max();
1600 auto it = border_edges.begin();
1605 for( ; it != border_edges.end(); ++it )
1608 int xt = border_edge->
m_p1.
x;
1610 if( ( xt <= x_min ) && !border_edge->
m_connected )
1613 smallestX = border_edge;
1617 int num_processed =
processEdge( edges, smallestX );
1620 if( !num_processed )
1622 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1630 num_unconnected -= num_processed;
1648 paths.push_back( std::move( newPath ) );
1671 assert( aPoly.size() == 1 );
1677 bool m_duplicate =
false;
1684 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1686 return (s1.
A == s2.
B && s1.
B == s2.
A);
1691 return compareSegs( m_poly->
CSegment( m_index ),
1692 aOther.m_poly->CSegment( aOther.m_index ) );
1697 return !compareSegs( m_poly->
CSegment( m_index ),
1698 aOther.m_poly->CSegment( aOther.m_index ) );
1703 std::size_t operator()(
const EDGE& aEdge )
const
1705 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1706 std::size_t seed = 0xa82de1c0;
1713 struct EDGE_LIST_ENTRY
1716 EDGE_LIST_ENTRY*
next;
1719 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1724 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1728 edgeList[i].index = i;
1729 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1732 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1737 uniqueEdges.insert( e );
1743 auto it = uniqueEdges.find( e );
1745 if( it != uniqueEdges.end() && it->m_index != i )
1747 int e1 = it->m_index;
1751 std::swap( e1, e2 );
1753 int e1_prev = e1 - 1;
1758 int e2_prev = e2 - 1;
1763 int e1_next = e1 + 1;
1768 int e2_next = e2 + 1;
1773 edgeList[e1_prev].next = &edgeList[ e2_next ];
1774 edgeList[e2_prev].next = &edgeList[ e1_next ];
1775 edgeList[i].next =
nullptr;
1776 edgeList[it->m_index].next =
nullptr;
1782 if( edgeList[i].
next )
1783 queue.insert( &edgeList[i] );
1786 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1792 double max_poly = 0.0;
1794 while( queue.size() )
1796 EDGE_LIST_ENTRY* e_first = *queue.begin();
1797 EDGE_LIST_ENTRY* e = e_first;
1804 }
while( e && e != e_first );
1808 for(
int i = 0; i < cnt; i++ )
1812 queue.erase( edgeBuf[i] );
1817 double area = std::fabs( outl.
Area() );
1819 if( area > max_poly )
1825 result.push_back( outl );
1830 std::swap( result[0], result[outline] );
1842 if( paths.size() > 1 )
1874 path.Simplify( aMaxError );
1892 while( outline.size() > 1 )
1917 std::stringstream ss;
1919 ss <<
"SHAPE_LINE_CHAIN poly; \n";
1921 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1923 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
1926 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
1932 ss <<
" poly.AddOutline(tmp); } \n";
1936 ss <<
" poly.AddHole(tmp); } \n";
1952 if( tmp !=
"polyset" )
1957 int n_polys = atoi( tmp.c_str() );
1962 for(
int i = 0; i < n_polys; i++ )
1972 int n_outlines = atoi( tmp.c_str() );
1974 if( n_outlines < 0 )
1977 for(
int j = 0; j < n_outlines; j++ )
1984 int n_vertices = atoi( tmp.c_str() );
1986 for(
int v = 0; v < n_vertices; v++ )
1990 aStream >> tmp; p.
x = atoi( tmp.c_str() );
1991 aStream >> tmp; p.
y = atoi( tmp.c_str() );
1995 paths.push_back( outline );
2009 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2026 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2029 bb = *
m_polys[i][0].GetCachedBBox();
2046 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2061 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2064 *aLocation = nearest;
2067 *aActual = sqrt( dist_sq );
2085 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2088 *aLocation = nearest;
2091 *aActual = sqrt( dist_sq );
2108 int extra = segment->
GetWidth() / 2;
2110 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2113 *aActual = std::max( 0, *aActual - extra );
2126 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
2129 *aActual = std::max( 0, *aActual - extra );
2139 int actual = INT_MAX;
2146 if( aActual || aLocation )
2151 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2153 if( triActual < actual )
2156 location = triLocation;
2162 if( aShape->
Collide( &tri, aClearance ) )
2168 if( actual < INT_MAX )
2171 *aActual = std::max( 0, actual );
2174 *aLocation = location;
2192 if( aPolygonIdx < 0 )
2193 aPolygonIdx +=
m_polys.size();
2195 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2215 std::vector<VERTEX_INDEX> indices_to_remove;
2220 segmentStart = *iterator;
2226 segmentEnd = contourStart;
2234 contourStart = *iterator;
2242 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2244 segmentEnd = *iterator;
2248 if( segmentStart == segmentEnd )
2250 indices_to_remove.push_back( indexStart );
2257 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2280 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2282 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2283 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2310 Append( aP.
x, aP.
y, aOutline, aHole );
2316 int aClearance )
const
2319 bool collision =
false;
2329 delta = *iterator - aPoint;
2332 distance_squared =
delta.SquaredEuclideanNorm();
2335 if( distance_squared <= clearance_squared )
2337 if( !aClosestVertex )
2343 clearance_squared = distance_squared;
2346 *aClosestVertex = iterator.GetIndex();
2356 int aClearance )
const
2359 bool collision =
false;
2364 const SEG currentSegment = *iterator;
2368 if( distance_squared <= clearance_squared )
2370 if( !aClosestVertex )
2376 clearance_squared = distance_squared;
2379 *aClosestVertex = iterator.GetIndex();
2389 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2393 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2400 bool aUseBBoxCaches )
const
2406 if( aSubpolyIndex >= 0 )
2407 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2410 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2412 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2428 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2445 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2456 bool aUseBBoxCaches )
const
2462 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2484 path.Move( aVector );
2488 tri->Move( aVector );
2500 path.Mirror( aRef, aFlipDirection );
2513 path.Rotate( aAngle, aCenter );
2529 c +=
path.PointCount();
2566 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2568 for( iterator++; iterator && minDistance > 0; iterator++ )
2570 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2572 if( currentDistance < minDistance )
2575 *aNearest = (*iterator).NearestPoint( aPoint );
2577 minDistance = currentDistance;
2593 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2599 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2601 if( aNearest && minDistance == 0 )
2602 *aNearest = ( *iterator ).NearestPoint( aSegment );
2604 for( iterator++; iterator && minDistance > 0; iterator++ )
2608 if( currentDistance < minDistance )
2611 *aNearest = (*iterator).NearestPoint( aSegment );
2613 minDistance = currentDistance;
2618 return minDistance < 0 ? 0 : minDistance;
2625 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2626 "support aOutlineOnly==true" ) );
2633 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2636 aNearest ? &nearest :
nullptr );
2638 if( currentDistance_sq < minDistance_sq )
2641 *aNearest = nearest;
2643 minDistance_sq = currentDistance_sq;
2647 return minDistance_sq;
2658 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2661 aNearest ? &nearest :
nullptr );
2663 if( currentDistance_sq < minDistance_sq )
2666 *aNearest = nearest;
2668 minDistance_sq = currentDistance_sq;
2672 return minDistance_sq;
2693 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2704 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2712 unsigned int aDistance,
2713 int aIndex,
int aErrorMax )
2722 if( aDistance == 0 )
2734 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2737 int x1 = currContour.
CPoint( currVertex ).
x;
2738 int y1 = currContour.CPoint( currVertex ).y;
2747 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2750 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2753 double xa = currContour.CPoint( prevVertex ).x - x1;
2754 double ya = currContour.CPoint( prevVertex ).y - y1;
2757 double xb = currContour.CPoint( nextVertex ).x - x1;
2758 double yb = currContour.CPoint( nextVertex ).y - y1;
2761 if(
std::abs( xa + xb ) < std::numeric_limits<double>::epsilon()
2762 &&
std::abs( ya + yb ) < std::numeric_limits<double>::epsilon() )
2768 double lena = hypot( xa, ya );
2769 double lenb = hypot( xb, yb );
2786 newContour.
Append( x1 + nx1, y1 + ny1 );
2791 newContour.
Append( x1 + nx2, y1 + ny2 );
2795 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2797 double radius = aDistance;
2798 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2801 if( std::isinf( denom ) )
2805 if( 0.5 * lena * denom < radius )
2806 radius = 0.5 * lena * denom;
2808 if( 0.5 * lenb * denom < radius )
2809 radius = 0.5 * lenb * denom;
2812 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2813 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2814 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2815 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2816 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2819 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2820 double xs = x1 + k * xa / lena - xc;
2821 double ys = y1 + k * ya / lena - yc;
2822 double xe = x1 + k * xb / lenb - xc;
2823 double ye = y1 + k * yb / lenb - yc;
2826 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2832 else if( argument > 1 )
2835 double arcAngle = acos( argument );
2839 double deltaAngle = arcAngle / segments;
2840 double startAngle = atan2( -ys, xs );
2843 if( xa * yb - ya * xb <= 0 )
2846 double nx = xc + xs;
2847 double ny = yc + ys;
2849 if( std::isnan( nx ) || std::isnan( ny ) )
2858 for(
int j = 0; j < segments; j++ )
2860 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2861 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2863 if( std::isnan( nx ) || std::isnan( ny ) )
2879 newPoly.push_back( newContour );
2888 SHAPE::operator=( aOther );
2948 if( w == 0.0 || h == 0.0 )
2951 int n_cells_x, n_cells_y;
2955 n_cells_x = w / aSize;
2956 n_cells_y = floor( h / w * n_cells_x ) + 1;
2960 n_cells_y = h / aSize;
2961 n_cells_x = floor( w / h * n_cells_y ) + 1;
2964 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2966 for(
int yy = 0; yy < n_cells_y; yy++ )
2968 for(
int xx = 0; xx < n_cells_x; xx++ )
2972 p.
x = bb.
GetX() + w * xx / n_cells_x;
2973 p.
y = bb.
GetY() + h * yy / n_cells_y;
2977 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2978 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2986 mask.SetClosed(
true );
2988 if( ( xx ^ yy ) & 1 )
2995 ps1.BooleanIntersection( maskSetOdd );
2996 ps2.BooleanIntersection( maskSetEven );
3000 for(
int i = 0; i < ps2.OutlineCount(); i++ )
3001 ps1.AddOutline( ps2.COutline( i ) );
3003 if( ps1.OutlineCount() )
3011 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3027 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3028 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3030 bool triangulationValid =
false;
3034 if( hintData && hintData->size() != (unsigned) polySet.
OutlineCount() )
3039 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3040 dest.erase( dest.end() - 1 );
3042 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3049 hintData ? hintData->at( index ).get() :
nullptr ) )
3063 triangulationValid =
false;
3070 triangulationValid =
true;
3073 return triangulationValid;
3085 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
3092 else if( aSimplify )
3101 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
3142 hash.
add( outline.size() );
3146 hash.
add( lc.PointCount() );
3148 for(
int i = 0; i < lc.PointCount(); i++ )
3176 std::set<long long> ptHashes;
3180 for(
const VECTOR2I& pt : lc.CPoints() )
3182 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3184 if( ptHashes.count( ptHash ) > 0 )
3187 ptHashes.insert( ptHash );
3206 n += t->GetTriangleCount();
3219 aSubshapes.push_back( &tri );
3230 if( aClearance != 0 )
3282 Clipper2Lib::Clipper64 clipper;
3283 Clipper2Lib::PolyTree64 tree;
3284 Clipper2Lib::Paths64 paths;
3288 Clipper2Lib::Path64 lc;
3289 lc.reserve(
path.PointCount() );
3291 for(
int i = 0; i <
path.PointCount(); i++ )
3292 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3294 paths.push_back( lc );
3297 clipper.AddSubject( paths );
3298 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
3299 : Clipper2Lib::FillRule::NonZero, tree );
3302 std::vector<CLIPPER_Z_VALUE> zValues;
3303 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