42#include <unordered_set>
46#include <clipper2/clipper.h>
94 m_polys( aOther.m_polys )
120 m_polys( aOther.m_polys )
141 return SHAPE_POLY_SET( *
this, DROP_TRIANGULATION_FLAG::SINGLETON );
149 unsigned int contourIdx = 0;
152 int currentGlobalIdx = 0;
154 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
158 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
161 int totalPoints = currentContour.
PointCount();
163 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
166 if( currentGlobalIdx == aGlobalIdx )
168 aRelativeIndices->
m_polygon = polygonIdx;
169 aRelativeIndices->
m_contour = contourIdx;
170 aRelativeIndices->
m_vertex = vertexIdx;
186 int& aGlobalIdx )
const
188 int selectedVertex = aRelativeIndices.
m_vertex;
189 unsigned int selectedContour = aRelativeIndices.
m_contour;
190 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
193 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
194 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
200 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
202 currentPolygon =
Polygon( polygonIdx );
204 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
205 aGlobalIdx += currentPolygon[contourIdx].PointCount();
208 currentPolygon =
Polygon( selectedPolygon );
210 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
211 aGlobalIdx += currentPolygon[contourIdx].PointCount();
213 aGlobalIdx += selectedVertex;
230 poly.push_back( empty_path );
247 m_polys[aOutline].push_back( empty_path );
249 return m_polys.back().size() - 2;
267 assert( aOutline < (
int)
m_polys.size() );
268 assert( idx < (
int)
m_polys[aOutline].size() );
270 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
272 return m_polys[aOutline][idx].PointCount();
290 assert( aOutline < (
int)
m_polys.size() );
291 assert( idx < (
int)
m_polys[aOutline].size() );
293 m_polys[aOutline][idx].Append( aArc, aAccuracy );
295 return m_polys[aOutline][idx].PointCount();
303 if( aGlobalIndex < 0 )
316 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
336 if( aOutline >= (
int)
m_polys.size() )
339 if( idx >= (
int)
m_polys[aOutline].size() )
342 return m_polys[aOutline][idx].PointCount();
357 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
359 full_count +=
m_polys[ii][idx].PointCount();
369 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
373 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
392 assert( aOutline < (
int)
m_polys.size() );
393 assert( idx < (
int)
m_polys[aOutline].size() );
395 return m_polys[aOutline][idx].CPoint( aIndex );
405 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
435 else if( index.
m_vertex == lastpoint )
450 *aPrevious = previous;
466 std::vector<SEG> segments;
470 segments.emplace_back( *it );
472 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
474 int min_a_x = std::min( a.A.x, a.B.x );
475 int min_b_x = std::min( b.A.x, b.B.x );
477 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 ) );
480 for(
auto it = segments.begin(); it != segments.end(); ++it )
482 SEG& firstSegment = *it;
485 auto innerIterator = it;
486 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
487 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
490 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
492 SEG& secondSegment = *innerIterator;
493 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
494 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
498 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
502 bool adjacent = ( index_diff == 1) || (index_diff == (segments.size() - 1) );
505 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
516 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
532 poly.push_back( aOutline );
547 assert( aOutline < (
int)
m_polys.size() );
551 assert( poly.size() );
553 poly.push_back( aHole );
555 return poly.size() - 2;
567 for(
int j = 0; j <
HoleCount( i ); j++ )
581 for(
size_t i = 0; i < poly.size(); i++ )
593 for(
size_t i = 0; i < poly.size(); i++ )
596 aArcBuffer.push_back( arc );
606 for(
size_t i = 0; i < poly.size(); i++ )
615 booleanOp( aType, *
this, aOtherShape, aFastMode );
625 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
626 "ClearArcs() before carrying out the boolean operation." ) );
629 ClipperLib::Clipper c;
633 std::vector<CLIPPER_Z_VALUE> zValues;
634 std::vector<SHAPE_ARC> arcBuffer;
635 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
639 for(
size_t i = 0; i < poly.size(); i++ )
641 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
642 ClipperLib::ptSubject,
true );
648 for(
size_t i = 0; i < poly.size(); i++ )
650 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
651 ClipperLib::ptClip,
true );
655 ClipperLib::PolyTree solution;
657 ClipperLib::ZFillCallback callback =
658 [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
659 ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
660 ClipperLib::IntPoint & pt )
663 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
667 retval = zValues.at( aZvalue ).m_SecondArcIdx;
669 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
670 retval = zValues.at( aZvalue ).m_FirstArcIdx;
676 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
678 ssize_t retval = arcIndex( aBottomZ );
682 if( retval != arcIndex( aTopZ, retval ) )
689 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
690 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
694 if( e1ArcSegmentIndex != -1 )
705 size_t z_value_ptr = zValues.size();
706 zValues.push_back( newZval );
710 newIntersectPoints.insert( {
VECTOR2I( pt.X, pt.Y ), newZval } );
716 c.ZFillFunction( callback );
718 c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
736 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
737 "ClearArcs() before carrying out the boolean operation." ) );
740 Clipper2Lib::Clipper64 c;
742 std::vector<CLIPPER_Z_VALUE> zValues;
743 std::vector<SHAPE_ARC> arcBuffer;
744 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
746 Clipper2Lib::Paths64 paths;
747 Clipper2Lib::Paths64 clips;
751 for(
size_t i = 0; i < poly.size(); i++ )
753 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
759 for(
size_t i = 0; i < poly.size(); i++ )
761 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
765 c.AddSubject( paths );
768 Clipper2Lib::PolyTree64 solution;
770 Clipper2Lib::ZCallback64 callback =
771 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
772 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
773 Clipper2Lib::Point64 & pt )
776 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
780 retval = zValues.at( aZvalue ).m_SecondArcIdx;
782 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
783 retval = zValues.at( aZvalue ).m_FirstArcIdx;
789 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
791 ssize_t retval = arcIndex( aBottomZ );
795 if( retval != arcIndex( aTopZ, retval ) )
802 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
803 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
807 if( e1ArcSegmentIndex != -1 )
818 size_t z_value_ptr = zValues.size();
819 zValues.push_back( newZval );
823 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
829 c.SetZCallback( callback );
831 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
841 booleanOp( Clipper2Lib::ClipType::Union, b );
843 booleanOp( ClipperLib::ctUnion, b, aFastMode );
850 booleanOp( Clipper2Lib::ClipType::Difference, b );
852 booleanOp( ClipperLib::ctDifference, b, aFastMode );
859 booleanOp( Clipper2Lib::ClipType::Intersection, b );
861 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
869 booleanOp( Clipper2Lib::ClipType::Union, a, b );
871 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
879 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
881 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
889 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
891 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
899 Inflate( aFactor, aCircleSegmentsCount );
906 using namespace ClipperLib;
910 #define SEG_CNT_MAX 64
911 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
918 JoinType joinType = jtRound;
919 double miterLimit = 2.0;
920 JoinType miterFallback = jtSquare;
922 switch( aCornerStrategy )
927 miterFallback = jtSquare;
932 miterFallback = jtRound;
937 miterFallback = jtSquare;
942 miterFallback = jtSquare;
947 miterFallback = jtSquare;
951 std::vector<CLIPPER_Z_VALUE> zValues;
952 std::vector<SHAPE_ARC> arcBuffer;
956 for(
size_t i = 0; i < poly.size(); i++ )
958 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
959 joinType, etClosedPolygon );
969 if( aCircleSegCount < 6 )
974 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
976 coeff = 1.0 - cos( M_PI / aCircleSegCount );
979 arc_tolerance_factor[aCircleSegCount] = coeff;
983 coeff = arc_tolerance_factor[aCircleSegCount];
986 c.ArcTolerance =
std::abs( aAmount ) * coeff;
987 c.MiterLimit = miterLimit;
988 c.MiterFallback = miterFallback;
989 c.Execute( solution, aAmount );
997 using namespace Clipper2Lib;
1001 #define SEG_CNT_MAX 64
1002 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1009 JoinType joinType = JoinType::Round;
1010 double miterLimit = 2.0;
1011 JoinType miterFallback = JoinType::Square;
1013 switch( aCornerStrategy )
1016 joinType = JoinType::Miter;
1021 joinType = JoinType::Miter;
1025 joinType = JoinType::Miter;
1029 joinType = JoinType::Square;
1033 joinType = JoinType::Round;
1037 std::vector<CLIPPER_Z_VALUE> zValues;
1038 std::vector<SHAPE_ARC> arcBuffer;
1044 for(
size_t i = 0; i < poly.size(); i++ )
1045 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1047 c.AddPaths( paths, joinType, EndType::Polygon );
1054 if( aCircleSegCount < 6 )
1055 aCircleSegCount = 6;
1059 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1061 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1064 arc_tolerance_factor[aCircleSegCount] = coeff;
1068 coeff = arc_tolerance_factor[aCircleSegCount];
1071 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1072 c.MiterLimit( miterLimit );
1073 c.MergeGroups(
true );
1074 Paths64 solution = c.Execute( aAmount );
1080 c2.PreserveCollinear =
false;
1081 c2.ReverseSolution =
false;
1082 c2.AddSubject( solution );
1083 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1093 inflate2( aAmount, aCircleSegCount, aCornerStrategy );
1095 inflate1( aAmount, aCircleSegCount, aCornerStrategy );
1100 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1101 const std::vector<SHAPE_ARC>& aArcBuffer )
1105 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
1110 paths.reserve( n->Childs.size() + 1 );
1112 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
1114 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
1115 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
1124 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1125 const std::vector<SHAPE_ARC>& aArcBuffer )
1127 if( !aPolyPath->IsHole() )
1130 paths.reserve( aPolyPath->Count() + 1 );
1131 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1133 for( Clipper2Lib::PolyPath64* child : *aPolyPath )
1135 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1137 for( Clipper2Lib::PolyPath64* grandchild : *child )
1147 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1148 const std::vector<SHAPE_ARC>& aArcBuffer )
1152 for( Clipper2Lib::PolyPath64* n : tree )
1158 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1159 const std::vector<SHAPE_ARC>& aArcBuffer )
1164 for(
const Clipper2Lib::Path64& n : aPath )
1166 if( Clipper2Lib::Area( n ) > 0 )
1175 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1178 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1220 int x = edge->
m_p1.
x;
1221 int y = edge->
m_p1.
y;
1222 int min_dist = std::numeric_limits<int>::max();
1229 if( !e->matches( y ) )
1234 if( e->m_p1.y == e->m_p2.y )
1236 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1240 x_intersect = e->m_p1.x +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
1241 e->m_p2.y - e->m_p1.y );
1244 int dist = ( x - x_intersect );
1246 if( dist >= 0 && dist < min_dist && e->m_connected )
1249 x_nearest = x_intersect;
1262 edges.push_back( split_2 );
1263 edges.push_back( lead1 );
1264 edges.push_back( lead2 );
1269 e_nearest->
m_next = lead1;
1274 for( last = edge; last->
m_next != edge; last = last->
m_next )
1300 if( paths.size() == 1 )
1303 int num_unconnected = 0;
1307 const std::vector<VECTOR2I>& points =
path.CPoints();
1308 int pointCount = points.size();
1312 int x_min = std::numeric_limits<int>::max();
1314 for(
int i = 0; i < pointCount; i++ )
1316 if( points[i].x < x_min )
1317 x_min = points[i].x;
1322 points[ i+1 == pointCount ? 0 : i+1 ] );
1333 if( i == pointCount - 1 )
1337 edges.push_back( fe );
1341 if( fe->
m_p1.
x == x_min )
1342 border_edges.push_back( fe );
1353 while( num_unconnected > 0 )
1355 int x_min = std::numeric_limits<int>::max();
1356 auto it = border_edges.begin();
1361 for( ; it != border_edges.end(); ++it )
1364 int xt = border_edge->
m_p1.
x;
1366 if( ( xt <= x_min ) && !border_edge->
m_connected )
1369 smallestX = border_edge;
1373 int num_processed =
processEdge( edges, smallestX );
1376 if( !num_processed )
1378 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1386 num_unconnected -= num_processed;
1404 paths.push_back( std::move( newPath ) );
1419 assert( aPoly.size() == 1 );
1425 bool m_duplicate =
false;
1432 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1434 return (s1.
A == s2.
B && s1.
B == s2.
A);
1439 return compareSegs( m_poly->
CSegment( m_index ),
1440 aOther.m_poly->CSegment( aOther.m_index ) );
1445 return !compareSegs( m_poly->
CSegment( m_index ),
1446 aOther.m_poly->CSegment( aOther.m_index ) );
1451 std::size_t operator()(
const EDGE& aEdge )
const
1453 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1454 std::size_t seed = 0xa82de1c0;
1461 struct EDGE_LIST_ENTRY
1464 EDGE_LIST_ENTRY*
next;
1467 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1472 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1476 edgeList[i].index = i;
1477 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1480 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1485 uniqueEdges.insert( e );
1491 auto it = uniqueEdges.find( e );
1493 if( it != uniqueEdges.end() && it->m_index != i )
1495 int e1 = it->m_index;
1499 std::swap( e1, e2 );
1501 int e1_prev = e1 - 1;
1506 int e2_prev = e2 - 1;
1511 int e1_next = e1 + 1;
1516 int e2_next = e2 + 1;
1521 edgeList[e1_prev].next = &edgeList[ e2_next ];
1522 edgeList[e2_prev].next = &edgeList[ e1_next ];
1523 edgeList[i].next =
nullptr;
1524 edgeList[it->m_index].next =
nullptr;
1530 if( edgeList[i].
next )
1531 queue.insert( &edgeList[i] );
1534 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1540 double max_poly = 0.0;
1542 while( queue.size() )
1544 EDGE_LIST_ENTRY* e_first = *queue.begin();
1545 EDGE_LIST_ENTRY* e = e_first;
1552 }
while( e && e != e_first );
1556 for(
int i = 0; i < cnt; i++ )
1560 queue.erase( edgeBuf[i] );
1565 double area = std::fabs( outl.
Area() );
1567 if( area > max_poly )
1573 result.push_back( outl );
1578 std::swap( result[0], result[outline] );
1590 if( paths.size() > 1 )
1631 while( outline.size() > 1 )
1656 std::stringstream ss;
1658 ss <<
"SHAPE_LINE_CHAIN poly; \n";
1660 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1662 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
1665 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
1671 ss <<
" poly.AddOutline(tmp); } \n";
1675 ss <<
" poly.AddHole(tmp); } \n";
1691 if( tmp !=
"polyset" )
1696 int n_polys = atoi( tmp.c_str() );
1701 for(
int i = 0; i < n_polys; i++ )
1711 int n_outlines = atoi( tmp.c_str() );
1713 if( n_outlines < 0 )
1716 for(
int j = 0; j < n_outlines; j++ )
1723 int n_vertices = atoi( tmp.c_str() );
1725 for(
int v = 0; v < n_vertices; v++ )
1729 aStream >> tmp; p.
x = atoi( tmp.c_str() );
1730 aStream >> tmp; p.
y = atoi( tmp.c_str() );
1734 paths.push_back( outline );
1748 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1765 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1768 bb = *
m_polys[i][0].GetCachedBBox();
1785 if( lineChain.PointOnEdge( aP ) )
1800 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
1803 *aLocation = nearest;
1806 *aActual = sqrt( dist_sq );
1824 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
1827 *aLocation = nearest;
1830 *aActual = sqrt( dist_sq );
1847 int extra = segment->
GetWidth() / 2;
1849 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
1852 *aActual = std::max( 0, *aActual - extra );
1865 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
1868 *aActual = std::max( 0, *aActual - extra );
1878 int actual = INT_MAX;
1885 if( aActual || aLocation )
1890 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
1892 if( triActual < actual )
1895 location = triLocation;
1901 if( aShape->
Collide( &tri, aClearance ) )
1907 if( actual < INT_MAX )
1910 *aActual = std::max( 0, actual );
1913 *aLocation = location;
1931 if( aPolygonIdx < 0 )
1932 aPolygonIdx +=
m_polys.size();
1934 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
1948 std::vector<VERTEX_INDEX> indices_to_remove;
1953 segmentStart = *iterator;
1959 segmentEnd = contourStart;
1967 contourStart = *iterator;
1975 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
1977 segmentEnd = *iterator;
1981 if( segmentStart == segmentEnd )
1983 indices_to_remove.push_back( indexStart );
1990 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2013 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2015 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2016 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2039 Append( aP.
x, aP.
y, aOutline, aHole );
2045 int aClearance )
const
2048 bool collision =
false;
2058 delta = *iterator - aPoint;
2061 distance_squared =
delta.SquaredEuclideanNorm();
2064 if( distance_squared <= clearance_squared )
2066 if( !aClosestVertex )
2072 clearance_squared = distance_squared;
2075 *aClosestVertex = iterator.GetIndex();
2085 int aClearance )
const
2088 bool collision =
false;
2093 const SEG currentSegment = *iterator;
2097 if( distance_squared <= clearance_squared )
2099 if( !aClosestVertex )
2105 clearance_squared = distance_squared;
2108 *aClosestVertex = iterator.GetIndex();
2118 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2122 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2129 bool aUseBBoxCaches )
const
2135 if( aSubpolyIndex >= 0 )
2136 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2139 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2141 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2157 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2174 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2185 bool aUseBBoxCaches )
const
2188 if(
m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
2191 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2213 path.Move( aVector );
2217 tri->Move( aVector );
2228 path.Mirror( aX, aY, aRef );
2241 path.Rotate( aAngle, aCenter );
2257 c +=
path.PointCount();
2294 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2296 for( iterator++; iterator && minDistance > 0; iterator++ )
2298 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2300 if( currentDistance < minDistance )
2303 *aNearest = (*iterator).NearestPoint( aPoint );
2305 minDistance = currentDistance;
2321 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2327 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2329 if( aNearest && minDistance == 0 )
2330 *aNearest = ( *iterator ).NearestPoint( aSegment );
2332 for( iterator++; iterator && minDistance > 0; iterator++ )
2334 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2336 if( currentDistance < minDistance )
2339 *aNearest = (*iterator).NearestPoint( aSegment );
2341 minDistance = currentDistance;
2346 return minDistance < 0 ? 0 : minDistance;
2357 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2360 aNearest ? &nearest :
nullptr );
2362 if( currentDistance_sq < minDistance_sq )
2365 *aNearest = nearest;
2367 minDistance_sq = currentDistance_sq;
2371 return minDistance_sq;
2382 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2385 aNearest ? &nearest :
nullptr );
2387 if( currentDistance_sq < minDistance_sq )
2390 *aNearest = nearest;
2392 minDistance_sq = currentDistance_sq;
2396 return minDistance_sq;
2417 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2428 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2436 unsigned int aDistance,
2437 int aIndex,
int aErrorMax )
2446 if( aDistance == 0 )
2458 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2461 int x1 = currContour.
CPoint( currVertex ).
x;
2462 int y1 = currContour.CPoint( currVertex ).y;
2471 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2474 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2477 double xa = currContour.CPoint( prevVertex ).x - x1;
2478 double ya = currContour.CPoint( prevVertex ).y - y1;
2481 double xb = currContour.CPoint( nextVertex ).x - x1;
2482 double yb = currContour.CPoint( nextVertex ).y - y1;
2485 double lena = hypot( xa, ya );
2486 double lenb = hypot( xb, yb );
2489 if( aMode == CORNER_MODE::CHAMFERED )
2503 newContour.
Append( x1 + nx1, y1 + ny1 );
2508 newContour.
Append( x1 + nx2, y1 + ny2 );
2512 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2514 double radius = aDistance;
2515 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2518 if( std::isinf( denom ) )
2522 if( 0.5 * lena * denom < radius )
2523 radius = 0.5 * lena * denom;
2525 if( 0.5 * lenb * denom < radius )
2526 radius = 0.5 * lenb * denom;
2529 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2530 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2531 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2532 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2533 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2536 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2537 double xs = x1 + k * xa / lena - xc;
2538 double ys = y1 + k * ya / lena - yc;
2539 double xe = x1 + k * xb / lenb - xc;
2540 double ye = y1 + k * yb / lenb - yc;
2543 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2549 else if( argument > 1 )
2552 double arcAngle = acos( argument );
2556 double deltaAngle = arcAngle / segments;
2557 double startAngle = atan2( -ys, xs );
2560 if( xa * yb - ya * xb <= 0 )
2563 double nx = xc + xs;
2564 double ny = yc + ys;
2572 for(
int j = 0; j < segments; j++ )
2574 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2575 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2590 newPoly.push_back( newContour );
2599 static_cast<SHAPE&
>(*this) = aOther;
2647 if( w == 0.0 || h == 0.0 )
2650 int n_cells_x, n_cells_y;
2654 n_cells_x = w / aSize;
2655 n_cells_y = floor( h / w * n_cells_x ) + 1;
2659 n_cells_y = h / aSize;
2660 n_cells_x = floor( w / h * n_cells_y ) + 1;
2663 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2665 for(
int yy = 0; yy < n_cells_y; yy++ )
2667 for(
int xx = 0; xx < n_cells_x; xx++ )
2671 p.
x = bb.
GetX() + w * xx / n_cells_x;
2672 p.
y = bb.
GetY() + h * yy / n_cells_y;
2676 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2677 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2685 mask.SetClosed(
true );
2687 if( ( xx ^ yy ) & 1 )
2699 for(
int i = 0; i < ps2.OutlineCount(); i++ )
2700 ps1.AddOutline( ps2.COutline( i ) );
2702 if( ps1.OutlineCount() )
2733 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest )
2735 bool triangulationValid =
false;
2740 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
2741 dest.erase( dest.end() - 1 );
2743 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
2755 else if( pass == 2 )
2760 triangulationValid =
false;
2765 triangulationValid =
true;
2768 return triangulationValid;
2781 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
2788 else if( aSimplify )
2806 else if( aSimplify )
2825 hash.
Hash( outline.size() );
2829 hash.
Hash( lc.PointCount() );
2831 for(
int i = 0; i < lc.PointCount(); i++ )
2833 hash.
Hash( lc.CPoint( i ).x );
2834 hash.
Hash( lc.CPoint( i ).y );
2859 std::set<long long> ptHashes;
2863 for(
const VECTOR2I& pt : lc.CPoints() )
2865 const long long ptHash = (
long long) pt.x << 32 | pt.y;
2867 if( ptHashes.count( ptHash ) > 0 )
2870 ptHashes.insert( ptHash );
2889 n += t->GetTriangleCount();
2902 aSubshapes.push_back( &tri );
2913 if( aClearance != 0 )
2963 bool aReverseOrientation,
bool aEvenOdd )
2965 ClipperLib::Clipper clipper;
2966 ClipperLib::PolyTree tree;
2972 ClipperLib::Path lc;
2974 for(
int i = 0; i <
path.PointCount(); i++ )
2976 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
2979 clipper.AddPath( lc, ClipperLib::ptSubject,
true );
2982 clipper.StrictlySimple(
true );
2983 clipper.Execute( ClipperLib::ctUnion, tree,
2984 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
2985 ClipperLib::pftNonZero );
2988 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
2994 for(
unsigned int i = 0; i < n->Contour.size(); i++ )
2995 result.
Outline( outl ).
Append( n->Contour[i].X, n->Contour[i].Y );
2997 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
2999 int outh = result.
NewHole( outl );
3000 for(
unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
3002 result.
Hole( outl, outh )
3003 .
Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
coord_type GetTop() const
coord_type GetHeight() const
coord_type GetWidth() const
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
coord_type GetRight() const
coord_type GetLeft() const
coord_type GetBottom() const
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
void Hash(uint8_t *data, uint32_t length)
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
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
Check if point aP lies inside a polygon (any type) defined by the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
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.
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.
virtual bool HasIndexableSubshapes() const override
bool m_triangulationValid
static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aReverseOrientation=false, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
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 BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CONST_ITERATOR CIterateWithHoles() const
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
ITERATOR IterateWithHoles()
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
bool IsTriangulationUpToDate() const
void inflate2(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy)
void importPaths(Clipper2Lib::Paths64 &paths, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
POLYGON_MODE
Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon and its triangulation data from the set.
double Area()
Count the number of arc shapes present.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
void CacheTriangulation(bool aPartition=true, bool aSimplify=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
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,...
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Delete aIdx-th polygon from the set.
POLYGON & Polygon(int aIndex)
int FullPointCount() const
Returns the number of holes in a given outline.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
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 BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
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.
void inflate1(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy)
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
const std::string Format(bool aCplusPlus=true) const override
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
This is the engine to execute all polygon boolean transforms (AND, OR, ... and polygon simplification...
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void Simplify(POLYGON_MODE aFastMode)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
SHAPE_LINE_CHAIN & Outline(int aIndex)
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
int NewOutline()
Creates a new hole in a given outline.
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool hasTouchingHoles(const POLYGON &aPoly) const
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)
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
void UpdateTriangulationDataHash()
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
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).
virtual size_t GetIndexableSubshapeCount() const override
MD5_HASH checksum() const
void importPolyPath(Clipper2Lib::PolyPath64 *aPolyPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
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 aGlobalIndex-th vertex in the poly set.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
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
Creates a new empty polygon in the set and returns its index.
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
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.
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.
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
static constexpr extended_type ECOORD_MAX
static bool empty(const wxTextEntryBase *aCtrl)
a few functions useful in geometry calculations.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
static void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
const bool operator==(const COLOR4D &lhs, const COLOR4D &rhs)
Equality operator, are two colors equal.
const bool operator!=(const COLOR4D &lhs, const COLOR4D &rhs)
Not equality operator, are two colors not equal.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
@ SH_POLY_SET
set of polygons (with holes, etc.)
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
static SHAPE_POLY_SET partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize)
std::vector< FractureEdge * > FractureEdgeSet
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
bool matches(int y) const
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...
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).