41#include <unordered_set>
46#include <clipper2/clipper.h>
53#include <geometry/rtree.h>
66#if defined( __MINGW32__ )
67 #define TRIANGULATESIMPLIFICATIONLEVEL 50
68 #define ENABLECACHEFRIENDLYFRACTURE true
70 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
71 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
112 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
114 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
116 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
117 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
128 m_triangulationValid =
false;
164 unsigned int contourIdx = 0;
167 int currentGlobalIdx = 0;
169 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
173 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
176 int totalPoints = currentContour.
PointCount();
178 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
181 if( currentGlobalIdx == aGlobalIdx )
183 aRelativeIndices->
m_polygon = polygonIdx;
184 aRelativeIndices->
m_contour = contourIdx;
185 aRelativeIndices->
m_vertex = vertexIdx;
201 int& aGlobalIdx )
const
203 int selectedVertex = aRelativeIndices.
m_vertex;
204 unsigned int selectedContour = aRelativeIndices.
m_contour;
205 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
208 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
209 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
215 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
217 currentPolygon =
Polygon( polygonIdx );
219 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
220 aGlobalIdx += currentPolygon[contourIdx].PointCount();
223 currentPolygon =
Polygon( selectedPolygon );
225 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
226 aGlobalIdx += currentPolygon[contourIdx].PointCount();
228 aGlobalIdx += selectedVertex;
245 poly.push_back( empty_path );
246 m_polys.push_back( std::move( poly ) );
262 m_polys[aOutline].push_back( empty_path );
264 return m_polys.back().size() - 2;
282 assert( aOutline < (
int)
m_polys.size() );
283 assert( idx < (
int)
m_polys[aOutline].size() );
285 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
287 return m_polys[aOutline][idx].PointCount();
292 std::optional<int> aMaxError )
306 assert( aOutline < (
int)
m_polys.size() );
307 assert( idx < (
int)
m_polys[aOutline].size() );
309 if( aMaxError.has_value() )
310 m_polys[aOutline][idx].Append( aArc, aMaxError.value() );
312 m_polys[aOutline][idx].Append( aArc );
314 return m_polys[aOutline][idx].PointCount();
322 if( aGlobalIndex < 0 )
335 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
355 if( aOutline >= (
int)
m_polys.size() )
358 if( idx >= (
int)
m_polys[aOutline].size() )
361 return m_polys[aOutline][idx].PointCount();
376 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
378 full_count +=
m_polys[ii][idx].PointCount();
388 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
392 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
411 assert( aOutline < (
int)
m_polys.size() );
412 assert( idx < (
int)
m_polys[aOutline].size() );
414 return m_polys[aOutline][idx].CPoint( aIndex );
424 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
454 else if( index.
m_vertex == lastpoint )
472 *aPrevious = previous;
488 std::vector<SEG> segments;
492 segments.emplace_back( *it );
494 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
496 int min_a_x = std::min( a.A.x, a.B.x );
497 int min_b_x = std::min( b.A.x, b.B.x );
499 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 ) );
502 for(
auto it = segments.begin(); it != segments.end(); ++it )
504 SEG& firstSegment = *it;
507 auto innerIterator = it;
508 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
509 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
512 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
514 SEG& secondSegment = *innerIterator;
515 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
516 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
520 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
524 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
527 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
538 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
552 poly.push_back( aOutline );
557 wxCHECK2_MSG( aOutline.
IsClosed(), poly.back().SetClosed(
true ),
558 "Warning: non-closed outline added to SHAPE_POLY_SET" );
560 m_polys.push_back( std::move( poly ) );
562 return (
int)
m_polys.size() - 1;
571 aOutline += (int)
m_polys.size();
573 assert( aOutline < (
int)
m_polys.size() );
577 assert( poly.size() );
579 poly.push_back( aHole );
581 return (
int) poly.size() - 2;
601 for(
int j = 0; j <
HoleCount( i ); j++ )
615 for(
size_t i = 0; i < poly.size(); i++ )
627 for(
size_t i = 0; i < poly.size(); i++ )
630 aArcBuffer.push_back( arc );
640 for(
size_t i = 0; i < poly.size(); i++ )
648 std::vector<SHAPE_LINE_CHAIN> contours;
651 contours.insert( contours.end(), poly.begin(), poly.end() );
653 std::map<int, std::set<int>> parentToChildren;
654 std::map<int, std::set<int>> childToParents;
657 contour.GenerateBBoxCache();
659 for(
size_t i = 0; i < contours.size(); i++ )
663 for(
size_t j = 0; j < contours.size(); j++ )
673 parentToChildren[i].emplace( j );
674 childToParents[j].emplace( i );
679 std::set<int> topLevelParents;
681 for(
size_t i = 0; i < contours.size(); i++ )
683 if( childToParents[i].size() == 0 )
685 topLevelParents.emplace( i );
691 std::function<void(
int,
int, std::vector<int> )>
process;
694 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
696 std::set<int> relParents = childToParents[myId];
698 for(
int pathId :
path )
700 int erased = relParents.erase( pathId );
701 wxASSERT( erased > 0 );
704 wxASSERT( relParents.size() == 0 );
708 bool isOutline =
path.size() % 2 == 0;
712 int outlineId =
result.AddOutline( contours[myId] );
713 myOutline = outlineId;
717 wxASSERT( parentOutlineId != -1 );
718 result.AddHole( contours[myId], parentOutlineId );
721 auto it = parentToChildren.find( myId );
722 if( it != parentToChildren.end() )
724 std::vector<int> thisPath =
path;
725 thisPath.emplace_back( myId );
727 std::set<int> thisPathSet;
728 thisPathSet.insert( thisPath.begin(), thisPath.end() );
730 for(
int childId : it->second )
732 const std::set<int>& childPathSet = childToParents[childId];
734 if( thisPathSet != childPathSet )
737 process( childId, myOutline, thisPath );
742 for(
int topParentId : topLevelParents )
744 std::vector<int>
path;
748 *
this = std::move(
result );
764 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
765 "ClearArcs() before carrying out the boolean operation." ) );
768 Clipper2Lib::Clipper64 c;
770 std::vector<CLIPPER_Z_VALUE> zValues;
771 std::vector<SHAPE_ARC> arcBuffer;
772 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
774 Clipper2Lib::Paths64 paths;
775 Clipper2Lib::Paths64 clips;
779 for(
size_t i = 0; i < poly.size(); i++ )
781 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
787 for(
size_t i = 0; i < poly.size(); i++ )
789 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
793 c.AddSubject( paths );
796 Clipper2Lib::PolyTree64 solution;
798 Clipper2Lib::ZCallback64 callback =
799 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
800 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
801 Clipper2Lib::Point64 & pt )
804 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
808 retval = zValues.at( aZvalue ).m_SecondArcIdx;
810 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
811 retval = zValues.at( aZvalue ).m_FirstArcIdx;
817 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
819 ssize_t retval = arcIndex( aBottomZ );
823 if( retval != arcIndex( aTopZ, retval ) )
830 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
831 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
835 if( e1ArcSegmentIndex != -1 )
846 size_t z_value_ptr = zValues.size();
847 zValues.push_back( newZval );
851 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
857 c.SetZCallback( std::move( callback ) );
859 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
868 booleanOp( Clipper2Lib::ClipType::Union, b );
874 booleanOp( Clipper2Lib::ClipType::Difference, b );
880 booleanOp( Clipper2Lib::ClipType::Intersection, b );
886 booleanOp( Clipper2Lib::ClipType::Xor, b );
892 booleanOp( Clipper2Lib::ClipType::Union, a, b );
898 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
904 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
910 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
918 Inflate( aFactor, aCornerStrategy, aMaxError );
926 using namespace Clipper2Lib;
930 #define SEG_CNT_MAX 64
931 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
938 JoinType joinType = JoinType::Round;
939 double miterLimit = 2.0;
941 switch( aCornerStrategy )
944 joinType = JoinType::Miter;
949 joinType = JoinType::Miter;
953 joinType = JoinType::Miter;
957 joinType = JoinType::Square;
961 joinType = JoinType::Round;
965 std::vector<CLIPPER_Z_VALUE> zValues;
966 std::vector<SHAPE_ARC> arcBuffer;
972 for(
size_t i = 0; i < poly.size(); i++ )
973 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
975 c.AddPaths( paths, joinType, EndType::Polygon );
982 if( aCircleSegCount < 6 )
987 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
989 coeff = 1.0 - cos(
M_PI / aCircleSegCount );
992 arc_tolerance_factor[aCircleSegCount] = coeff;
996 coeff = arc_tolerance_factor[aCircleSegCount];
999 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1000 c.MiterLimit( miterLimit );
1007 c.Execute( aAmount, paths );
1009 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1012 c2.PreserveCollinear(
false );
1013 c2.ReverseSolution(
false );
1014 c2.AddSubject( paths );
1015 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1019 c.Execute( aAmount, tree );
1030 using namespace Clipper2Lib;
1034 #define SEG_CNT_MAX 64
1035 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1042 JoinType joinType = JoinType::Round;
1043 double miterLimit = 2.0;
1045 switch( aCornerStrategy )
1048 joinType = JoinType::Miter;
1053 joinType = JoinType::Miter;
1057 joinType = JoinType::Miter;
1061 joinType = JoinType::Square;
1065 joinType = JoinType::Round;
1069 std::vector<CLIPPER_Z_VALUE> zValues;
1070 std::vector<SHAPE_ARC> arcBuffer;
1073 c.AddPath(
path, joinType, EndType::Butt );
1079 if( aCircleSegCount < 6 )
1080 aCircleSegCount = 6;
1084 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1086 coeff = 1.0 - cos(
M_PI / aCircleSegCount );
1089 arc_tolerance_factor[aCircleSegCount] = coeff;
1093 coeff = arc_tolerance_factor[aCircleSegCount];
1096 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1097 c.MiterLimit( miterLimit );
1104 c.Execute( aAmount, paths2 );
1106 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1109 c2.PreserveCollinear(
false );
1110 c2.ReverseSolution(
false );
1111 c2.AddSubject( paths2 );
1112 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1116 c.Execute( aAmount, tree );
1129 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1138 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1143 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1144 const std::vector<SHAPE_ARC>& aArcBuffer )
1146 if( !aPolyPath->IsHole() )
1149 paths.reserve( aPolyPath->Count() + 1 );
1150 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1152 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1154 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1156 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1160 m_polys.emplace_back( std::move( paths ) );
1166 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1167 const std::vector<SHAPE_ARC>& aArcBuffer )
1171 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1177 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1178 const std::vector<SHAPE_ARC>& aArcBuffer )
1183 for(
const Clipper2Lib::Path64& n : aPath )
1185 if( Clipper2Lib::Area( n ) > 0 )
1194 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1197 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1236 int x = edge.
m_p1.
x;
1237 int y = edge.
m_p1.
y;
1238 int min_dist = std::numeric_limits<int>::max();
1257 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1265 int dist = ( x - x_intersect );
1267 if( dist >= 0 && dist < min_dist )
1270 x_nearest = x_intersect;
1283 edges[hole2outline_index] =
1286 edges[split_index] =
1291 e_nearest->
m_next = outline2hole_index;
1294 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1296 last->
m_next = hole2outline_index;
1306 bool outline =
true;
1308 if( paths.size() == 1 )
1311 size_t total_point_count = 0;
1315 total_point_count +=
path.PointCount();
1318 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1320 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1327 edges.reserve( total_point_count + paths.size() * 3 );
1333 int path_or_provoking_index;
1338 std::vector<PathInfo> sorted_paths;
1339 const int paths_count =
static_cast<int>( paths.size() );
1340 sorted_paths.reserve( paths_count );
1342 for(
int path_index = 0; path_index < paths_count; path_index++ )
1345 const std::vector<VECTOR2I>& points =
path.CPoints();
1346 const int point_count =
static_cast<int>( points.size() );
1347 int x_min = std::numeric_limits<int>::max();
1348 int y_min = std::numeric_limits<int>::max();
1351 for(
int point_index = 0; point_index < point_count; point_index++ )
1353 const VECTOR2I& point = points[point_index];
1354 if( point.
x < x_min )
1357 leftmost = point_index;
1359 if( point.
y < y_min )
1363 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1366 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1367 [](
const PathInfo& a,
const PathInfo& b )
1370 return a.y_or_bridge < b.y_or_bridge;
1376 for( PathInfo& path_info : sorted_paths )
1379 const std::vector<VECTOR2I>& points =
path.CPoints();
1380 const size_t point_count = points.size();
1385 for(
size_t i = 0; i < point_count - 1; i++ )
1387 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1392 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1399 path_info.path_or_provoking_index = provoking_edge;
1400 path_info.y_or_bridge = edge_index;
1404 edges.resize( edge_index );
1410 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1412 auto edge =
processHole( edges, it->path_or_provoking_index,
1413 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1418 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1466 int x = edge->
m_p1.
x;
1467 int y = edge->
m_p1.
y;
1468 int min_dist = std::numeric_limits<int>::max();
1475 if( !e->matches( y ) )
1480 if( e->m_p1.y == e->m_p2.y )
1482 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1486 x_intersect = e->m_p1.x
1487 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1490 int dist = ( x - x_intersect );
1492 if( dist >= 0 && dist < min_dist && e->m_connected )
1495 x_nearest = x_intersect;
1511 edges.push_back( split_2 );
1512 edges.push_back( lead1 );
1513 edges.push_back( lead2 );
1518 e_nearest->
m_next = lead1;
1523 for( last = edge; last->
m_next != edge; last = last->
m_next )
1549 if( paths.size() == 1 )
1552 int num_unconnected = 0;
1556 const std::vector<VECTOR2I>& points =
path.CPoints();
1557 int pointCount = points.size();
1561 int x_min = std::numeric_limits<int>::max();
1563 for(
int i = 0; i < pointCount; i++ )
1565 if( points[i].x < x_min )
1566 x_min = points[i].x;
1571 points[i + 1 == pointCount ? 0 : i + 1] );
1582 if( i == pointCount - 1 )
1586 edges.push_back( fe );
1590 if( fe->
m_p1.
x == x_min )
1591 border_edges.push_back( fe );
1602 while( num_unconnected > 0 )
1604 int x_min = std::numeric_limits<int>::max();
1605 auto it = border_edges.begin();
1610 for( ; it != border_edges.end(); ++it )
1613 int xt = border_edge->
m_p1.
x;
1615 if( ( xt <= x_min ) && !border_edge->
m_connected )
1618 smallestX = border_edge;
1622 int num_processed =
processEdge( edges, smallestX );
1625 if( !num_processed )
1627 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1635 num_unconnected -= num_processed;
1653 paths.push_back( std::move( newPath ) );
1676 assert( aPoly.size() == 1 );
1682 bool m_duplicate =
false;
1689 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1691 return (s1.
A == s2.
B && s1.
B == s2.
A);
1696 return compareSegs( m_poly->
CSegment( m_index ),
1697 aOther.m_poly->CSegment( aOther.m_index ) );
1702 return !compareSegs( m_poly->
CSegment( m_index ),
1703 aOther.m_poly->CSegment( aOther.m_index ) );
1708 std::size_t operator()(
const EDGE& aEdge )
const
1710 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1711 std::size_t seed = 0xa82de1c0;
1718 struct EDGE_LIST_ENTRY
1721 EDGE_LIST_ENTRY*
next;
1724 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1729 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1733 edgeList[i].index = i;
1734 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1737 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1742 uniqueEdges.insert( e );
1748 auto it = uniqueEdges.find( e );
1750 if( it != uniqueEdges.end() && it->m_index != i )
1752 int e1 = it->m_index;
1756 std::swap( e1, e2 );
1758 int e1_prev = e1 - 1;
1763 int e2_prev = e2 - 1;
1768 int e1_next = e1 + 1;
1773 int e2_next = e2 + 1;
1778 edgeList[e1_prev].next = &edgeList[ e2_next ];
1779 edgeList[e2_prev].next = &edgeList[ e1_next ];
1780 edgeList[i].next =
nullptr;
1781 edgeList[it->m_index].next =
nullptr;
1787 if( edgeList[i].
next )
1788 queue.insert( &edgeList[i] );
1791 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1797 double max_poly = 0.0;
1799 while( queue.size() )
1801 EDGE_LIST_ENTRY* e_first = *queue.begin();
1802 EDGE_LIST_ENTRY* e = e_first;
1809 }
while( e && e != e_first );
1813 for(
int i = 0; i < cnt; i++ )
1817 queue.erase( edgeBuf[i] );
1822 double area = std::fabs( outl.
Area() );
1824 if( area > max_poly )
1830 result.push_back( outl );
1837 aPoly = std::move(
result );
1847 if( paths.size() > 1 )
1871 std::array<VECTOR2I,4> pts = { aSegA.
A, aSegA.
B, aSegB.
A, aSegB.
B };
1873 std::sort( pts.begin(), pts.end(), [axis](
const VECTOR2I& p,
const VECTOR2I& q )
1876 return p.x < q.x || ( p.x == q.x && p.y < q.y );
1878 return p.y < q.y || ( p.y == q.y && p.x < q.x );
1901 if( !side1 && !side2 )
1911 for(
size_t polyIdx = 0; polyIdx <
m_polys.size(); ++polyIdx )
1913 bool changed =
true;
1922 RTree<intptr_t, intptr_t, 2, intptr_t> rtree;
1924 for( intptr_t i = 0; i < count; ++i )
1928 intptr_t min[2] = { std::min( a.
x, b.
x ), std::min( a.
y, b.
y ) };
1929 intptr_t max[2] = { std::max( a.
x, b.
x ), std::max( a.
y, b.
y ) };
1930 rtree.Insert( min, max, i );
1937 for( intptr_t i = 0; i < count && !found; ++i )
1942 intptr_t min[2] = { std::min( a.
x, b.
x ), std::min( a.
y, b.
y ) };
1943 intptr_t max[2] = { std::max( a.
x, b.
x ), std::max( a.
y, b.
y ) };
1946 [&](
const int& j ) ->
bool
1948 if( j == i || j == ( ( i + 1 ) % count ) || j == ( ( i + count - 1 ) % count ) )
1953 SEG other( oa, ob );
1957 if( oa == a && ob == b )
1960 if( oa == b && ob == a )
1974 rtree.Search( min, max, visitor );
1981 int a1 = ( segA + 1 ) % outline.
PointCount();
1983 int b1 = ( segB + 1 ) % outline.
PointCount();
2009 m_polys[polyIdx][0] = std::move( lc1 );
2012 np.push_back( std::move( lc2 ) );
2013 m_polys.push_back( std::move( np ) );
2037 path.Simplify( aTolerance );
2055 while( outline.size() > 1 )
2080 std::stringstream ss;
2082 ss <<
"SHAPE_LINE_CHAIN poly; \n";
2084 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2086 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
2089 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
2095 ss <<
" poly.AddOutline(tmp); } \n";
2099 ss <<
" poly.AddHole(tmp); } \n";
2115 if( tmp !=
"polyset" )
2120 int n_polys = atoi( tmp.c_str() );
2125 for(
int i = 0; i < n_polys; i++ )
2135 int n_outlines = atoi( tmp.c_str() );
2137 if( n_outlines < 0 )
2140 for(
int j = 0; j < n_outlines; j++ )
2147 int n_vertices = atoi( tmp.c_str() );
2149 for(
int v = 0; v < n_vertices; v++ )
2153 aStream >> tmp; p.
x = atoi( tmp.c_str() );
2154 aStream >> tmp; p.
y = atoi( tmp.c_str() );
2158 paths.push_back( std::move( outline ) );
2161 m_polys.push_back( std::move( paths ) );
2172 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2189 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2192 bb = *
m_polys[i][0].GetCachedBBox();
2209 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2224 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2227 *aLocation = nearest;
2230 *aActual = sqrt( dist_sq );
2248 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2251 *aLocation = nearest;
2254 *aActual = sqrt( dist_sq );
2271 int extra = segment->
GetWidth() / 2;
2273 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2276 *aActual = std::max( 0, *aActual - extra );
2287 int extra =
circle->GetRadius();
2289 if(
Collide(
circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
2292 *aActual = std::max( 0, *aActual - extra );
2309 if( aActual || aLocation )
2314 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2325 if( aShape->
Collide( &tri, aClearance ) )
2334 *aActual = std::max( 0,
actual );
2357 if( aPolygonIdx < 0 )
2358 aPolygonIdx +=
m_polys.size();
2360 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2380 std::vector<VERTEX_INDEX> indices_to_remove;
2385 segmentStart = *iterator;
2391 segmentEnd = contourStart;
2399 contourStart = *iterator;
2407 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2409 segmentEnd = *iterator;
2413 if( segmentStart == segmentEnd )
2415 indices_to_remove.push_back( indexStart );
2422 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2445 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2447 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2448 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2475 Append( aP.
x, aP.
y, aOutline, aHole );
2481 int aClearance )
const
2484 bool collision =
false;
2494 delta = *iterator - aPoint;
2497 distance_squared =
delta.SquaredEuclideanNorm();
2500 if( distance_squared <= clearance_squared )
2502 if( !aClosestVertex )
2508 clearance_squared = distance_squared;
2511 *aClosestVertex = iterator.GetIndex();
2521 int aClearance )
const
2524 bool collision =
false;
2529 const SEG currentSegment = *iterator;
2533 if( distance_squared <= clearance_squared )
2535 if( !aClosestVertex )
2541 clearance_squared = distance_squared;
2544 *aClosestVertex = iterator.GetIndex();
2554 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2558 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2565 bool aUseBBoxCaches )
const
2571 if( aSubpolyIndex >= 0 )
2572 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2575 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2577 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2593 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2610 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2621 bool aUseBBoxCaches )
const
2627 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2649 path.Move( aVector );
2653 tri->Move( aVector );
2665 path.Mirror( aRef, aFlipDirection );
2678 path.Rotate( aAngle, aCenter );
2694 c +=
path.PointCount();
2731 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2733 for( iterator++; iterator && minDistance > 0; iterator++ )
2735 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2737 if( currentDistance < minDistance )
2740 *aNearest = (*iterator).NearestPoint( aPoint );
2742 minDistance = currentDistance;
2758 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2764 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2766 if( aNearest && minDistance == 0 )
2767 *aNearest = ( *iterator ).NearestPoint( aSegment );
2769 for( iterator++; iterator && minDistance > 0; iterator++ )
2771 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2773 if( currentDistance < minDistance )
2776 *aNearest = (*iterator).NearestPoint( aSegment );
2778 minDistance = currentDistance;
2783 return minDistance < 0 ? 0 : minDistance;
2790 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2791 "support aOutlineOnly==true" ) );
2798 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2801 aNearest ? &nearest :
nullptr );
2803 if( currentDistance_sq < minDistance_sq )
2806 *aNearest = nearest;
2808 minDistance_sq = currentDistance_sq;
2812 return minDistance_sq;
2823 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2826 aNearest ? &nearest :
nullptr );
2828 if( currentDistance_sq < minDistance_sq )
2831 *aNearest = nearest;
2833 minDistance_sq = currentDistance_sq;
2837 return minDistance_sq;
2858 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2869 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2878 SHAPE::operator=( aOther );
2938 if( w == 0.0 || h == 0.0 )
2941 int n_cells_x, n_cells_y;
2945 n_cells_x = w / aSize;
2946 n_cells_y = floor( h / w * n_cells_x ) + 1;
2950 n_cells_y = h / aSize;
2951 n_cells_x = floor( w / h * n_cells_y ) + 1;
2954 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2956 for(
int yy = 0; yy < n_cells_y; yy++ )
2958 for(
int xx = 0; xx < n_cells_x; xx++ )
2962 p.
x = bb.
GetX() + w * xx / n_cells_x;
2963 p.
y = bb.
GetY() + h * yy / n_cells_y;
2967 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2968 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2976 mask.SetClosed(
true );
2978 if( ( xx ^ yy ) & 1 )
2986 ps2.BooleanIntersection( maskSetEven );
2990 for(
int i = 0; i < ps2.OutlineCount(); i++ )
2991 ps1.AddOutline( ps2.COutline( i ) );
2993 if( ps1.OutlineCount() )
3001 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3017 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3018 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3020 bool triangulationValid =
false;
3024 if( hintData && hintData->size() != (
unsigned) polySet.
OutlineCount() )
3029 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3030 dest.erase( dest.end() - 1 );
3032 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3039 hintData ? hintData->at( index ).get() :
nullptr ) )
3053 triangulationValid =
false;
3060 triangulationValid =
true;
3063 return triangulationValid;
3075 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
3082 else if( aSimplify )
3091 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
3132 hash.
add( outline.size() );
3136 hash.
add( lc.PointCount() );
3138 for(
int i = 0; i < lc.PointCount(); i++ )
3166 std::set<long long> ptHashes;
3170 for(
const VECTOR2I& pt : lc.CPoints() )
3172 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3174 if( ptHashes.count( ptHash ) > 0 )
3177 ptHashes.insert( ptHash );
3196 n += t->GetTriangleCount();
3209 aSubshapes.push_back( &tri );
3220 if( aClearance != 0 )
3272 Clipper2Lib::Clipper64 clipper;
3273 Clipper2Lib::PolyTree64 tree;
3274 Clipper2Lib::Paths64 paths;
3278 Clipper2Lib::Path64 lc;
3279 lc.reserve(
path.PointCount() );
3281 for(
int i = 0; i <
path.PointCount(); i++ )
3282 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3284 paths.push_back( std::move( lc ) );
3287 clipper.AddSubject( paths );
3288 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
3289 : Clipper2Lib::FillRule::NonZero, tree );
3291 std::vector<CLIPPER_Z_VALUE> zValues;
3292 std::vector<SHAPE_ARC> arcBuffer;
3312 int aSpacing,
int aLineLength )
const
3314 std::vector<SEG> hatchLines;
3324 if( iterator->x < min_x )
3325 min_x = iterator->x;
3327 if( iterator->x > max_x )
3328 max_x = iterator->x;
3330 if( iterator->y < min_y )
3331 min_y = iterator->y;
3333 if( iterator->y > max_y )
3334 max_y = iterator->y;
3337 auto sortEndsByDescendingX =
3340 return tst.x < ref.
x;
3343 for(
double slope : aSlopes )
3345 int64_t max_a, min_a;
3358 min_a = ( min_a / aSpacing ) * aSpacing;
3361 std::vector<VECTOR2I> pointbuffer;
3362 pointbuffer.reserve( 256 );
3364 for( int64_t a = min_a; a < max_a; a += aSpacing )
3366 pointbuffer.clear();
3371 const SEG seg = *iterator;
3377 if( pt.
x < min_x || pt.
x > max_x || pt.
y < min_y || pt.
y > max_y )
3388 if( pointbuffer.size() > 2 )
3389 sort( pointbuffer.begin(), pointbuffer.end(), sortEndsByDescendingX );
3392 for(
size_t ip = 0; ip + 1 < pointbuffer.size(); ip++ )
3394 const VECTOR2I& p1 = pointbuffer[ip];
3395 const VECTOR2I& p2 = pointbuffer[ip + 1];
3401 SEG candidate( p1, p2 );
3403 VECTOR2I mid( ( candidate.
A.
x + candidate.
B.
x ) / 2, ( candidate.
A.
y + candidate.
B.
y ) / 2 );
3408 int dx = p2.
x - p1.
x;
3412 if( aLineLength == -1 ||
std::abs( dx ) < 2 * aLineLength )
3414 hatchLines.emplace_back( candidate );
3418 double dy = p2.
y - p1.
y;
3428 int y1 =
KiROUND( p1.
y + dx * slope );
3429 int y2 =
KiROUND( p2.
y - dx * slope );
3431 hatchLines.emplace_back(
SEG( p1.
x, p1.
y, x1, y1 ) );
3433 hatchLines.emplace_back(
SEG( p2.
x, p2.
y, x2, y2 ) );
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
bool operator!=(const BOM_FIELD &lhs, const BOM_FIELD &rhs)
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr coord_type GetY() const
constexpr size_type GetWidth() const
constexpr coord_type GetX() const
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr size_type GetHeight() const
constexpr coord_type GetLeft() const
constexpr coord_type GetRight() const
constexpr coord_type GetTop() const
constexpr coord_type GetBottom() const
A streaming C++ equivalent for MurmurHash3_x64_128.
FORCE_INLINE void add(const std::string &input)
FORCE_INLINE HASH_128 digest()
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
ecoord SquaredDistance(const SEG &aSeg) const
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
VECTOR2I::extended_type ecoord
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
static SEG::ecoord Square(int a)
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
SHAPE_TYPE Type() const
Return the type of the shape.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
void GenerateBBoxCache() const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
Clipper2Lib::Path64 convertToClipper2(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsEndContour() const
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.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes.
CONST_ITERATOR CIterateWithHoles() const
void BooleanAdd(const SHAPE_POLY_SET &b)
Perform boolean polyset union.
ITERATOR IterateWithHoles()
void ClearArcs()
Removes all arc references from all the outlines and holes in the polyset.
bool IsTriangulationUpToDate() const
void importPaths(Clipper2Lib::Paths64 &paths, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
virtual void CacheTriangulation(bool aPartition=true, bool aSimplify=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of vertices in a given outline/hole.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon from the set.
void splitCollinearOutlines()
double Area()
Return the area of this poly set.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
void Fracture()
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
void BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Return total number of vertices stored in the set.
POLYGON & Polygon(int aIndex)
Return the aIndex-th subpolygon in the set.
int FullPointCount() const
Return the number of points in the shape poly set.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Appends all the arcs in this polyset to aArcBuffer.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
void unfractureSingle(POLYGON &path)
void inflateLine2(const SHAPE_LINE_CHAIN &aLine, int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify=false)
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
HASH_128 checksum() const
void Inflate(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify=false)
Perform outline inflation/deflation.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
int AddPolygon(const POLYGON &apolygon)
Adds a polygon to the set.
const std::vector< SEG > GenerateHatchLines(const std::vector< double > &aSlopes, int aSpacing, int aLineLength) const
const std::string Format(bool aCplusPlus=true) const override
void Simplify()
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections)
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
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
bool isExteriorWaist(const SEG &aSegA, const SEG &aSegB) const
Check if two line segments are collinear and overlap.
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)
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
const SEG & GetSeg() const
int GetWidth() const override
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
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
static constexpr extended_type ECOORD_MAX
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
CORNER_STRATEGY
define how inflate transform build inflated polygon
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
static bool empty(const wxTextEntryBase *aCtrl)
static constexpr EDA_ANGLE FULL_CIRCLE
a few functions useful in geometry calculations.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
static constexpr void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
static PGM_BASE * process
#define TRIANGULATE_TRACE
#define TRIANGULATESIMPLIFICATIONLEVEL
@ SH_POLY_SET
set of polygons (with holes, etc.)
static void fractureSingleCacheFriendly(SHAPE_POLY_SET::POLYGON &paths)
static void fractureSingleSlow(SHAPE_POLY_SET::POLYGON &paths)
static FractureEdge * processHole(FractureEdgeSet &edges, FractureEdge::Index provokingIndex, FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex)
std::vector< FractureEdge > FractureEdgeSet
std::vector< FractureEdgeSlow * > FractureEdgeSetSlow
static SHAPE_POLY_SET partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize)
#define ENABLECACHEFRIENDLYFRACTURE
static int processEdge(FractureEdgeSetSlow &edges, FractureEdgeSlow *edge)
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
FractureEdgeSlow(int y=0)
FractureEdgeSlow * m_next
bool matches(int y) const
FractureEdgeSlow(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
FractureEdge(const VECTOR2I &p1, const VECTOR2I &p2, Index next)
bool matches(int y) const
A storage class for 128-bit hash value.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
TRIANGULATED_POLYGON * parent
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
wxString result
Test unit parsing edge cases and error handling.
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I
VECTOR2< double > VECTOR2D