41#include <unordered_set>
46#include <clipper2/clipper.h>
101 m_polys( aOther.m_polys )
127 m_polys( aOther.m_polys )
156 unsigned int contourIdx = 0;
159 int currentGlobalIdx = 0;
161 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
165 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
168 int totalPoints = currentContour.
PointCount();
170 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
173 if( currentGlobalIdx == aGlobalIdx )
175 aRelativeIndices->
m_polygon = polygonIdx;
176 aRelativeIndices->
m_contour = contourIdx;
177 aRelativeIndices->
m_vertex = vertexIdx;
193 int& aGlobalIdx )
const
195 int selectedVertex = aRelativeIndices.
m_vertex;
196 unsigned int selectedContour = aRelativeIndices.
m_contour;
197 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
200 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
201 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
207 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
209 currentPolygon =
Polygon( polygonIdx );
211 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
212 aGlobalIdx += currentPolygon[contourIdx].PointCount();
215 currentPolygon =
Polygon( selectedPolygon );
217 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
218 aGlobalIdx += currentPolygon[contourIdx].PointCount();
220 aGlobalIdx += selectedVertex;
237 poly.push_back( empty_path );
254 m_polys[aOutline].push_back( empty_path );
256 return m_polys.back().size() - 2;
274 assert( aOutline < (
int)
m_polys.size() );
275 assert( idx < (
int)
m_polys[aOutline].size() );
277 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
279 return m_polys[aOutline][idx].PointCount();
297 assert( aOutline < (
int)
m_polys.size() );
298 assert( idx < (
int)
m_polys[aOutline].size() );
300 m_polys[aOutline][idx].Append( aArc, aAccuracy );
302 return m_polys[aOutline][idx].PointCount();
310 if( aGlobalIndex < 0 )
323 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
343 if( aOutline >= (
int)
m_polys.size() )
346 if( idx >= (
int)
m_polys[aOutline].size() )
349 return m_polys[aOutline][idx].PointCount();
364 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
366 full_count +=
m_polys[ii][idx].PointCount();
376 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
380 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
399 assert( aOutline < (
int)
m_polys.size() );
400 assert( idx < (
int)
m_polys[aOutline].size() );
402 return m_polys[aOutline][idx].CPoint( aIndex );
412 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
442 else if( index.
m_vertex == lastpoint )
457 *aPrevious = previous;
473 std::vector<SEG> segments;
477 segments.emplace_back( *it );
479 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
481 int min_a_x = std::min( a.A.x, a.B.x );
482 int min_b_x = std::min( b.A.x, b.B.x );
484 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 ) );
487 for(
auto it = segments.begin(); it != segments.end(); ++it )
489 SEG& firstSegment = *it;
492 auto innerIterator = it;
493 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
494 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
497 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
499 SEG& secondSegment = *innerIterator;
500 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
501 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
505 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
509 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
512 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
523 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
539 poly.push_back( aOutline );
554 assert( aOutline < (
int)
m_polys.size() );
558 assert( poly.size() );
560 poly.push_back( aHole );
562 return poly.size() - 2;
582 for(
int j = 0; j <
HoleCount( i ); j++ )
596 for(
size_t i = 0; i < poly.size(); i++ )
608 for(
size_t i = 0; i < poly.size(); i++ )
611 aArcBuffer.push_back( arc );
621 for(
size_t i = 0; i < poly.size(); i++ )
629 std::vector<SHAPE_LINE_CHAIN> contours;
632 contours.insert( contours.end(), poly.begin(), poly.end() );
634 std::map<int, std::set<int>> parentToChildren;
635 std::map<int, std::set<int>> childToParents;
638 contour.GenerateBBoxCache();
640 for(
size_t i = 0; i < contours.size(); i++ )
644 for(
size_t j = 0; j < contours.size(); j++ )
654 parentToChildren[i].emplace( j );
655 childToParents[j].emplace( i );
660 std::set<int> topLevelParents;
662 for(
size_t i = 0; i < contours.size(); i++ )
664 if( childToParents[i].size() == 0 )
666 topLevelParents.emplace( i );
672 std::function<void(
int,
int, std::vector<int> )>
process;
675 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
677 std::set<int> relParents = childToParents[myId];
679 for(
int pathId :
path )
681 int erased = relParents.erase( pathId );
682 wxASSERT( erased > 0 );
685 wxASSERT( relParents.size() == 0 );
689 bool isOutline =
path.size() % 2 == 0;
693 int outlineId = result.
AddOutline( contours[myId] );
694 myOutline = outlineId;
698 wxASSERT( parentOutlineId != -1 );
699 result.
AddHole( contours[myId], parentOutlineId );
702 auto it = parentToChildren.find( myId );
703 if( it != parentToChildren.end() )
705 std::vector<int> thisPath =
path;
706 thisPath.emplace_back( myId );
708 std::set<int> thisPathSet;
709 thisPathSet.insert( thisPath.begin(), thisPath.end() );
711 for(
int childId : it->second )
713 const std::set<int>& childPathSet = childToParents[childId];
715 if( thisPathSet != childPathSet )
718 process( childId, myOutline, thisPath );
723 for(
int topParentId : topLevelParents )
725 std::vector<int>
path;
736 booleanOp( aType, *
this, aOtherShape, aFastMode );
746 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
747 "ClearArcs() before carrying out the boolean operation." ) );
750 ClipperLib::Clipper c;
754 std::vector<CLIPPER_Z_VALUE> zValues;
755 std::vector<SHAPE_ARC> arcBuffer;
756 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
760 for(
size_t i = 0; i < poly.size(); i++ )
762 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
763 ClipperLib::ptSubject,
true );
769 for(
size_t i = 0; i < poly.size(); i++ )
771 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
772 ClipperLib::ptClip,
true );
776 ClipperLib::PolyTree solution;
778 ClipperLib::ZFillCallback callback =
779 [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
780 ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
781 ClipperLib::IntPoint & pt )
784 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
788 retval = zValues.at( aZvalue ).m_SecondArcIdx;
790 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
791 retval = zValues.at( aZvalue ).m_FirstArcIdx;
797 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
799 ssize_t retval = arcIndex( aBottomZ );
803 if( retval != arcIndex( aTopZ, retval ) )
810 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
811 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
815 if( e1ArcSegmentIndex != -1 )
826 size_t z_value_ptr = zValues.size();
827 zValues.push_back( newZval );
831 newIntersectPoints.insert( {
VECTOR2I( pt.X, pt.Y ), newZval } );
837 c.ZFillFunction( std::move( callback ) );
839 c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
857 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
858 "ClearArcs() before carrying out the boolean operation." ) );
861 Clipper2Lib::Clipper64 c;
863 std::vector<CLIPPER_Z_VALUE> zValues;
864 std::vector<SHAPE_ARC> arcBuffer;
865 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
867 Clipper2Lib::Paths64 paths;
868 Clipper2Lib::Paths64 clips;
872 for(
size_t i = 0; i < poly.size(); i++ )
874 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
880 for(
size_t i = 0; i < poly.size(); i++ )
882 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
886 c.AddSubject( paths );
889 Clipper2Lib::PolyTree64 solution;
891 Clipper2Lib::ZCallback64 callback =
892 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
893 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
894 Clipper2Lib::Point64 & pt )
897 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
901 retval = zValues.at( aZvalue ).m_SecondArcIdx;
903 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
904 retval = zValues.at( aZvalue ).m_FirstArcIdx;
910 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
912 ssize_t retval = arcIndex( aBottomZ );
916 if( retval != arcIndex( aTopZ, retval ) )
923 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
924 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
928 if( e1ArcSegmentIndex != -1 )
939 size_t z_value_ptr = zValues.size();
940 zValues.push_back( newZval );
944 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
950 c.SetZCallback( std::move( callback ) );
952 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
962 booleanOp( Clipper2Lib::ClipType::Union, b );
964 booleanOp( ClipperLib::ctUnion, b, aFastMode );
971 booleanOp( Clipper2Lib::ClipType::Difference, b );
973 booleanOp( ClipperLib::ctDifference, b, aFastMode );
980 booleanOp( Clipper2Lib::ClipType::Intersection, b );
982 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
989 booleanOp( Clipper2Lib::ClipType::Xor, b );
991 booleanOp( ClipperLib::ctXor, b, aFastMode );
999 booleanOp( Clipper2Lib::ClipType::Union, a, b );
1001 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
1009 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
1011 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
1019 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
1021 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
1029 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
1031 booleanOp( ClipperLib::ctXor, a, b, aFastMode );
1039 Inflate( aFactor, aCornerStrategy, aMaxError );
1046 using namespace ClipperLib;
1050 #define SEG_CNT_MAX 64
1051 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1058 JoinType joinType = jtRound;
1059 double miterLimit = 2.0;
1060 JoinType miterFallback = jtSquare;
1062 switch( aCornerStrategy )
1064 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1067 miterFallback = jtSquare;
1070 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1072 miterFallback = jtRound;
1075 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1077 miterFallback = jtSquare;
1080 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1081 joinType = jtSquare;
1082 miterFallback = jtSquare;
1085 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1087 miterFallback = jtSquare;
1091 std::vector<CLIPPER_Z_VALUE> zValues;
1092 std::vector<SHAPE_ARC> arcBuffer;
1096 for(
size_t i = 0; i < poly.size(); i++ )
1098 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
1099 joinType, etClosedPolygon );
1109 if( aCircleSegCount < 6 )
1110 aCircleSegCount = 6;
1114 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1116 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1119 arc_tolerance_factor[aCircleSegCount] = coeff;
1123 coeff = arc_tolerance_factor[aCircleSegCount];
1126 c.ArcTolerance =
std::abs( aAmount ) * coeff;
1127 c.MiterLimit = miterLimit;
1128 c.MiterFallback = miterFallback;
1129 c.Execute( solution, aAmount );
1138 using namespace Clipper2Lib;
1142 #define SEG_CNT_MAX 64
1143 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1150 JoinType joinType = JoinType::Round;
1151 double miterLimit = 2.0;
1153 switch( aCornerStrategy )
1155 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1156 joinType = JoinType::Miter;
1160 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1161 joinType = JoinType::Miter;
1164 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1165 joinType = JoinType::Miter;
1168 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1169 joinType = JoinType::Square;
1172 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1173 joinType = JoinType::Round;
1177 std::vector<CLIPPER_Z_VALUE> zValues;
1178 std::vector<SHAPE_ARC> arcBuffer;
1184 for(
size_t i = 0; i < poly.size(); i++ )
1185 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1187 c.AddPaths( paths, joinType, EndType::Polygon );
1194 if( aCircleSegCount < 6 )
1195 aCircleSegCount = 6;
1199 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1201 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1204 arc_tolerance_factor[aCircleSegCount] = coeff;
1208 coeff = arc_tolerance_factor[aCircleSegCount];
1211 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1212 c.MiterLimit( miterLimit );
1219 c.Execute( aAmount, paths );
1221 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1224 c2.PreserveCollinear(
false );
1225 c2.ReverseSolution(
false );
1226 c2.AddSubject( paths );
1227 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1231 c.Execute( aAmount, tree );
1242 using namespace Clipper2Lib;
1246 #define SEG_CNT_MAX 64
1247 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1254 JoinType joinType = JoinType::Round;
1255 double miterLimit = 2.0;
1257 switch( aCornerStrategy )
1259 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1260 joinType = JoinType::Miter;
1264 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1265 joinType = JoinType::Miter;
1268 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1269 joinType = JoinType::Miter;
1272 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1273 joinType = JoinType::Square;
1276 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1277 joinType = JoinType::Round;
1281 std::vector<CLIPPER_Z_VALUE> zValues;
1282 std::vector<SHAPE_ARC> arcBuffer;
1285 c.AddPath(
path, joinType, EndType::Butt );
1291 if( aCircleSegCount < 6 )
1292 aCircleSegCount = 6;
1296 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1298 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1301 arc_tolerance_factor[aCircleSegCount] = coeff;
1305 coeff = arc_tolerance_factor[aCircleSegCount];
1308 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1309 c.MiterLimit( miterLimit );
1316 c.Execute( aAmount, paths2 );
1318 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1321 c2.PreserveCollinear(
false );
1322 c2.ReverseSolution(
false );
1323 c2.AddSubject( paths2 );
1324 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1328 c.Execute( aAmount, tree );
1342 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1344 inflate1( aAmount, segCount, aCornerStrategy );
1353 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1358 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1359 const std::vector<SHAPE_ARC>& aArcBuffer )
1363 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
1368 paths.reserve( n->Childs.size() + 1 );
1370 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
1372 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
1373 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
1382 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1383 const std::vector<SHAPE_ARC>& aArcBuffer )
1385 if( !aPolyPath->IsHole() )
1388 paths.reserve( aPolyPath->Count() + 1 );
1389 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1391 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1393 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1395 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1405 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1406 const std::vector<SHAPE_ARC>& aArcBuffer )
1410 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1416 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1417 const std::vector<SHAPE_ARC>& aArcBuffer )
1422 for(
const Clipper2Lib::Path64& n : aPath )
1424 if( Clipper2Lib::Area( n ) > 0 )
1433 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1436 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1473 int x = edge.
m_p1.
x;
1474 int y = edge.
m_p1.
y;
1475 int min_dist = std::numeric_limits<int>::max();
1494 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1502 int dist = ( x - x_intersect );
1504 if( dist >= 0 && dist < min_dist )
1507 x_nearest = x_intersect;
1520 edges[hole2outline_index] =
1523 edges[split_index] =
1528 e_nearest->
m_next = outline2hole_index;
1531 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1533 last->
m_next = hole2outline_index;
1543 bool outline =
true;
1545 if( paths.size() == 1 )
1548 size_t total_point_count = 0;
1552 total_point_count +=
path.PointCount();
1555 if( total_point_count > std::numeric_limits<FractureEdge::Index>::max() )
1557 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1564 edges.reserve( total_point_count + paths.size() * 3 );
1570 int path_or_provoking_index;
1575 std::vector<PathInfo> sorted_paths;
1576 const int paths_count =
static_cast<int>( paths.size() );
1577 sorted_paths.reserve( paths_count );
1579 for(
int path_index = 0; path_index < paths_count; path_index++ )
1582 const std::vector<VECTOR2I>& points =
path.CPoints();
1583 const int point_count =
static_cast<int>( points.size() );
1584 int x_min = std::numeric_limits<int>::max();
1585 int y_min = std::numeric_limits<int>::max();
1588 for(
int point_index = 0; point_index < point_count; point_index++ )
1590 const VECTOR2I& point = points[point_index];
1591 if( point.
x < x_min )
1594 leftmost = point_index;
1596 if( point.
y < y_min )
1600 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1603 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1604 [](
const PathInfo& a,
const PathInfo& b )
1607 return a.y_or_bridge < b.y_or_bridge;
1613 for( PathInfo& path_info : sorted_paths )
1616 const std::vector<VECTOR2I>& points =
path.CPoints();
1617 const size_t point_count = points.size();
1622 for(
size_t i = 0; i < point_count - 1; i++ )
1624 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1629 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1636 path_info.path_or_provoking_index = provoking_edge;
1637 path_info.y_or_bridge = edge_index;
1641 edges.resize( edge_index );
1647 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1649 auto edge =
processHole( edges, it->path_or_provoking_index,
1650 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1655 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1703 int x = edge->
m_p1.
x;
1704 int y = edge->
m_p1.
y;
1705 int min_dist = std::numeric_limits<int>::max();
1712 if( !e->matches( y ) )
1717 if( e->m_p1.y == e->m_p2.y )
1719 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1723 x_intersect = e->m_p1.x
1724 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1727 int dist = ( x - x_intersect );
1729 if( dist >= 0 && dist < min_dist && e->m_connected )
1732 x_nearest = x_intersect;
1748 edges.push_back( split_2 );
1749 edges.push_back( lead1 );
1750 edges.push_back( lead2 );
1755 e_nearest->
m_next = lead1;
1760 for( last = edge; last->
m_next != edge; last = last->
m_next )
1786 if( paths.size() == 1 )
1789 int num_unconnected = 0;
1793 const std::vector<VECTOR2I>& points =
path.CPoints();
1794 int pointCount = points.size();
1798 int x_min = std::numeric_limits<int>::max();
1800 for(
int i = 0; i < pointCount; i++ )
1802 if( points[i].x < x_min )
1803 x_min = points[i].x;
1808 points[i + 1 == pointCount ? 0 : i + 1] );
1819 if( i == pointCount - 1 )
1823 edges.push_back( fe );
1827 if( fe->
m_p1.
x == x_min )
1828 border_edges.push_back( fe );
1839 while( num_unconnected > 0 )
1841 int x_min = std::numeric_limits<int>::max();
1842 auto it = border_edges.begin();
1847 for( ; it != border_edges.end(); ++it )
1850 int xt = border_edge->
m_p1.
x;
1852 if( ( xt <= x_min ) && !border_edge->
m_connected )
1855 smallestX = border_edge;
1859 int num_processed =
processEdge( edges, smallestX );
1862 if( !num_processed )
1864 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1872 num_unconnected -= num_processed;
1890 paths.push_back( std::move( newPath ) );
1913 assert( aPoly.size() == 1 );
1919 bool m_duplicate =
false;
1926 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1928 return (s1.
A == s2.
B && s1.
B == s2.
A);
1933 return compareSegs( m_poly->
CSegment( m_index ),
1934 aOther.m_poly->CSegment( aOther.m_index ) );
1939 return !compareSegs( m_poly->
CSegment( m_index ),
1940 aOther.m_poly->CSegment( aOther.m_index ) );
1945 std::size_t operator()(
const EDGE& aEdge )
const
1947 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1948 std::size_t seed = 0xa82de1c0;
1955 struct EDGE_LIST_ENTRY
1958 EDGE_LIST_ENTRY*
next;
1961 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1966 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1970 edgeList[i].index = i;
1971 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1974 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1979 uniqueEdges.insert( e );
1985 auto it = uniqueEdges.find( e );
1987 if( it != uniqueEdges.end() && it->m_index != i )
1989 int e1 = it->m_index;
1993 std::swap( e1, e2 );
1995 int e1_prev = e1 - 1;
2000 int e2_prev = e2 - 1;
2005 int e1_next = e1 + 1;
2010 int e2_next = e2 + 1;
2015 edgeList[e1_prev].next = &edgeList[ e2_next ];
2016 edgeList[e2_prev].next = &edgeList[ e1_next ];
2017 edgeList[i].next =
nullptr;
2018 edgeList[it->m_index].next =
nullptr;
2024 if( edgeList[i].
next )
2025 queue.insert( &edgeList[i] );
2028 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
2034 double max_poly = 0.0;
2036 while( queue.size() )
2038 EDGE_LIST_ENTRY* e_first = *queue.begin();
2039 EDGE_LIST_ENTRY* e = e_first;
2046 }
while( e && e != e_first );
2050 for(
int i = 0; i < cnt; i++ )
2054 queue.erase( edgeBuf[i] );
2059 double area = std::fabs( outl.
Area() );
2061 if( area > max_poly )
2067 result.push_back( outl );
2072 std::swap( result[0], result[outline] );
2084 if( paths.size() > 1 )
2119 path.Simplify( aMaxError );
2137 while( outline.size() > 1 )
2162 std::stringstream ss;
2164 ss <<
"SHAPE_LINE_CHAIN poly; \n";
2166 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2168 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
2171 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
2177 ss <<
" poly.AddOutline(tmp); } \n";
2181 ss <<
" poly.AddHole(tmp); } \n";
2197 if( tmp !=
"polyset" )
2202 int n_polys = atoi( tmp.c_str() );
2207 for(
int i = 0; i < n_polys; i++ )
2217 int n_outlines = atoi( tmp.c_str() );
2219 if( n_outlines < 0 )
2222 for(
int j = 0; j < n_outlines; j++ )
2229 int n_vertices = atoi( tmp.c_str() );
2231 for(
int v = 0; v < n_vertices; v++ )
2235 aStream >> tmp; p.
x = atoi( tmp.c_str() );
2236 aStream >> tmp; p.
y = atoi( tmp.c_str() );
2240 paths.push_back( outline );
2254 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2271 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2274 bb = *
m_polys[i][0].GetCachedBBox();
2291 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2306 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2309 *aLocation = nearest;
2312 *aActual = sqrt( dist_sq );
2330 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2333 *aLocation = nearest;
2336 *aActual = sqrt( dist_sq );
2353 int extra = segment->
GetWidth() / 2;
2355 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2358 *aActual = std::max( 0, *aActual - extra );
2371 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
2374 *aActual = std::max( 0, *aActual - extra );
2384 int actual = INT_MAX;
2391 if( aActual || aLocation )
2396 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2398 if( triActual < actual )
2401 location = triLocation;
2407 if( aShape->
Collide( &tri, aClearance ) )
2413 if( actual < INT_MAX )
2416 *aActual = std::max( 0, actual );
2419 *aLocation = location;
2437 if( aPolygonIdx < 0 )
2438 aPolygonIdx +=
m_polys.size();
2440 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2454 std::vector<VERTEX_INDEX> indices_to_remove;
2459 segmentStart = *iterator;
2465 segmentEnd = contourStart;
2473 contourStart = *iterator;
2481 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2483 segmentEnd = *iterator;
2487 if( segmentStart == segmentEnd )
2489 indices_to_remove.push_back( indexStart );
2496 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2519 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2521 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2522 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2545 Append( aP.
x, aP.
y, aOutline, aHole );
2551 int aClearance )
const
2554 bool collision =
false;
2564 delta = *iterator - aPoint;
2567 distance_squared =
delta.SquaredEuclideanNorm();
2570 if( distance_squared <= clearance_squared )
2572 if( !aClosestVertex )
2578 clearance_squared = distance_squared;
2581 *aClosestVertex = iterator.GetIndex();
2591 int aClearance )
const
2594 bool collision =
false;
2599 const SEG currentSegment = *iterator;
2603 if( distance_squared <= clearance_squared )
2605 if( !aClosestVertex )
2611 clearance_squared = distance_squared;
2614 *aClosestVertex = iterator.GetIndex();
2624 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2628 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2635 bool aUseBBoxCaches )
const
2641 if( aSubpolyIndex >= 0 )
2642 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2645 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2647 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2663 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2680 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2691 bool aUseBBoxCaches )
const
2697 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2719 path.Move( aVector );
2723 tri->Move( aVector );
2734 path.Mirror( aX, aY, aRef );
2747 path.Rotate( aAngle, aCenter );
2763 c +=
path.PointCount();
2800 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2802 for( iterator++; iterator && minDistance > 0; iterator++ )
2804 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2806 if( currentDistance < minDistance )
2809 *aNearest = (*iterator).NearestPoint( aPoint );
2811 minDistance = currentDistance;
2827 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2833 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2835 if( aNearest && minDistance == 0 )
2836 *aNearest = ( *iterator ).NearestPoint( aSegment );
2838 for( iterator++; iterator && minDistance > 0; iterator++ )
2840 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
2842 if( currentDistance < minDistance )
2845 *aNearest = (*iterator).NearestPoint( aSegment );
2847 minDistance = currentDistance;
2852 return minDistance < 0 ? 0 : minDistance;
2859 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2860 "support aOutlineOnly==true" ) );
2867 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2870 aNearest ? &nearest :
nullptr );
2872 if( currentDistance_sq < minDistance_sq )
2875 *aNearest = nearest;
2877 minDistance_sq = currentDistance_sq;
2881 return minDistance_sq;
2892 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2895 aNearest ? &nearest :
nullptr );
2897 if( currentDistance_sq < minDistance_sq )
2900 *aNearest = nearest;
2902 minDistance_sq = currentDistance_sq;
2906 return minDistance_sq;
2927 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2938 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2946 unsigned int aDistance,
2947 int aIndex,
int aErrorMax )
2956 if( aDistance == 0 )
2968 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2971 int x1 = currContour.
CPoint( currVertex ).
x;
2972 int y1 = currContour.CPoint( currVertex ).y;
2981 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2984 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2987 double xa = currContour.CPoint( prevVertex ).x - x1;
2988 double ya = currContour.CPoint( prevVertex ).y - y1;
2991 double xb = currContour.CPoint( nextVertex ).x - x1;
2992 double yb = currContour.CPoint( nextVertex ).y - y1;
2995 if(
std::abs( xa + xb ) < std::numeric_limits<double>::epsilon()
2996 &&
std::abs( ya + yb ) < std::numeric_limits<double>::epsilon() )
3002 double lena = hypot( xa, ya );
3003 double lenb = hypot( xb, yb );
3020 newContour.
Append( x1 + nx1, y1 + ny1 );
3025 newContour.
Append( x1 + nx2, y1 + ny2 );
3029 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
3031 double radius = aDistance;
3032 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
3035 if( std::isinf( denom ) )
3039 if( 0.5 * lena * denom < radius )
3040 radius = 0.5 * lena * denom;
3042 if( 0.5 * lenb * denom < radius )
3043 radius = 0.5 * lenb * denom;
3046 double k = radius / sqrt( .5 * ( 1 - cosine ) );
3047 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
3048 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
3049 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
3050 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
3053 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
3054 double xs = x1 + k * xa / lena - xc;
3055 double ys = y1 + k * ya / lena - yc;
3056 double xe = x1 + k * xb / lenb - xc;
3057 double ye = y1 + k * yb / lenb - yc;
3060 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
3066 else if( argument > 1 )
3069 double arcAngle = acos( argument );
3073 double deltaAngle = arcAngle / segments;
3074 double startAngle = atan2( -ys, xs );
3077 if( xa * yb - ya * xb <= 0 )
3080 double nx = xc + xs;
3081 double ny = yc + ys;
3083 if( std::isnan( nx ) || std::isnan( ny ) )
3092 for(
int j = 0; j < segments; j++ )
3094 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
3095 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
3097 if( std::isnan( nx ) || std::isnan( ny ) )
3113 newPoly.push_back( newContour );
3122 static_cast<SHAPE&
>(*this) = aOther;
3170 if( w == 0.0 || h == 0.0 )
3173 int n_cells_x, n_cells_y;
3177 n_cells_x = w / aSize;
3178 n_cells_y = floor( h / w * n_cells_x ) + 1;
3182 n_cells_y = h / aSize;
3183 n_cells_x = floor( w / h * n_cells_y ) + 1;
3186 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
3188 for(
int yy = 0; yy < n_cells_y; yy++ )
3190 for(
int xx = 0; xx < n_cells_x; xx++ )
3194 p.
x = bb.
GetX() + w * xx / n_cells_x;
3195 p.
y = bb.
GetY() + h * yy / n_cells_y;
3199 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
3200 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
3208 mask.SetClosed(
true );
3210 if( ( xx ^ yy ) & 1 )
3222 for(
int i = 0; i < ps2.OutlineCount(); i++ )
3223 ps1.AddOutline( ps2.COutline( i ) );
3225 if( ps1.OutlineCount() )
3233 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3249 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3250 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3252 bool triangulationValid =
false;
3256 if( hintData && hintData->size() != (unsigned) polySet.
OutlineCount() )
3261 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3262 dest.erase( dest.end() - 1 );
3264 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3271 hintData ? hintData->at( index ).get() :
nullptr ) )
3279 else if( pass == 2 )
3294 triangulationValid =
false;
3301 triangulationValid =
true;
3304 if( triangulationValid && wxLog::IsLevelEnabled(wxLOG_Trace, wxLOG_COMPONENT) )
3309 return triangulationValid;
3321 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
3328 else if( aSimplify )
3337 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
3377 hash.
Hash( outline.size() );
3381 hash.
Hash( lc.PointCount() );
3383 for(
int i = 0; i < lc.PointCount(); i++ )
3385 hash.
Hash( lc.CPoint( i ).x );
3386 hash.
Hash( lc.CPoint( i ).y );
3411 std::set<long long> ptHashes;
3415 for(
const VECTOR2I& pt : lc.CPoints() )
3417 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3419 if( ptHashes.count( ptHash ) > 0 )
3422 ptHashes.insert( ptHash );
3441 n += t->GetTriangleCount();
3454 aSubshapes.push_back( &tri );
3465 if( aClearance != 0 )
3515 bool aReverseOrientation,
bool aEvenOdd )
3517 ClipperLib::Clipper clipper;
3518 ClipperLib::PolyTree tree;
3524 ClipperLib::Path lc;
3526 for(
int i = 0; i <
path.PointCount(); i++ )
3528 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3531 clipper.AddPath( lc, ClipperLib::ptSubject,
true );
3534 clipper.StrictlySimple(
true );
3535 clipper.Execute( ClipperLib::ctUnion, tree,
3536 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
3537 ClipperLib::pftNonZero );
3540 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
3546 for(
unsigned int i = 0; i < n->Contour.size(); i++ )
3547 result.
Outline( outl ).
Append( n->Contour[i].X, n->Contour[i].Y );
3549 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
3551 int outh = result.
NewHole( outl );
3552 for(
unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
3554 result.
Hole( outl, outh )
3555 .
Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
bool operator!=(const BOM_FIELD &lhs, const BOM_FIELD &rhs)
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)
void SetValid(bool aValid)
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
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.
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.
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 difference For aFastMode meaning, see function booleanOp.
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes.
void InflateWithLinkedHoles(int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
CONST_ITERATOR CIterateWithHoles() const
void BooleanXor(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset exclusive or For aFastMode meaning, see function booleanOp.
void Fracture(POLYGON_MODE aFastMode)
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
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)
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_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 BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union For aFastMode meaning, see function booleanOp.
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
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)
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
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.
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
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...
void Simplify(POLYGON_MODE aFastMode)
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
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 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
Count the number of arc shapes present.
void Unfracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with 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.
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.
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()
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.
MD5_HASH checksum() const
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 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.
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 importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
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.
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
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 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
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)
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
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).