41#include <unordered_set>
46#include <clipper2/clipper.h>
101 m_polys( aOther.m_polys )
129 m_polys( aOther.m_polys )
159 unsigned int contourIdx = 0;
162 int currentGlobalIdx = 0;
164 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
168 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
171 int totalPoints = currentContour.
PointCount();
173 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
176 if( currentGlobalIdx == aGlobalIdx )
178 aRelativeIndices->
m_polygon = polygonIdx;
179 aRelativeIndices->
m_contour = contourIdx;
180 aRelativeIndices->
m_vertex = vertexIdx;
196 int& aGlobalIdx )
const
198 int selectedVertex = aRelativeIndices.
m_vertex;
199 unsigned int selectedContour = aRelativeIndices.
m_contour;
200 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
203 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
204 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
210 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
212 currentPolygon =
Polygon( polygonIdx );
214 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
215 aGlobalIdx += currentPolygon[contourIdx].PointCount();
218 currentPolygon =
Polygon( selectedPolygon );
220 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
221 aGlobalIdx += currentPolygon[contourIdx].PointCount();
223 aGlobalIdx += selectedVertex;
240 poly.push_back( empty_path );
257 m_polys[aOutline].push_back( empty_path );
259 return m_polys.back().size() - 2;
277 assert( aOutline < (
int)
m_polys.size() );
278 assert( idx < (
int)
m_polys[aOutline].size() );
280 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
282 return m_polys[aOutline][idx].PointCount();
300 assert( aOutline < (
int)
m_polys.size() );
301 assert( idx < (
int)
m_polys[aOutline].size() );
303 m_polys[aOutline][idx].Append( aArc, aAccuracy );
305 return m_polys[aOutline][idx].PointCount();
313 if( aGlobalIndex < 0 )
326 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
346 if( aOutline >= (
int)
m_polys.size() )
349 if( idx >= (
int)
m_polys[aOutline].size() )
352 return m_polys[aOutline][idx].PointCount();
367 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
369 full_count +=
m_polys[ii][idx].PointCount();
379 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
383 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
402 assert( aOutline < (
int)
m_polys.size() );
403 assert( idx < (
int)
m_polys[aOutline].size() );
405 return m_polys[aOutline][idx].CPoint( aIndex );
415 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
445 else if( index.
m_vertex == lastpoint )
460 *aPrevious = previous;
476 std::vector<SEG> segments;
480 segments.emplace_back( *it );
482 std::sort( segments.begin(), segments.end(), [](
const SEG& a,
const SEG& b )
484 int min_a_x = std::min( a.A.x, a.B.x );
485 int min_b_x = std::min( b.A.x, b.B.x );
487 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 ) );
490 for(
auto it = segments.begin(); it != segments.end(); ++it )
492 SEG& firstSegment = *it;
495 auto innerIterator = it;
496 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
497 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
500 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
502 SEG& secondSegment = *innerIterator;
503 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
504 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
508 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
512 bool adjacent = ( index_diff == 1) || (index_diff == ((
int)segments.size() - 1) );
515 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
526 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
542 poly.push_back( aOutline );
557 assert( aOutline < (
int)
m_polys.size() );
561 assert( poly.size() );
563 poly.push_back( aHole );
565 return poly.size() - 2;
585 for(
int j = 0; j <
HoleCount( i ); j++ )
599 for(
size_t i = 0; i < poly.size(); i++ )
611 for(
size_t i = 0; i < poly.size(); i++ )
614 aArcBuffer.push_back( arc );
624 for(
size_t i = 0; i < poly.size(); i++ )
632 std::vector<SHAPE_LINE_CHAIN> contours;
635 contours.insert( contours.end(), poly.begin(), poly.end() );
637 std::map<int, std::set<int>> parentToChildren;
638 std::map<int, std::set<int>> childToParents;
641 contour.GenerateBBoxCache();
643 for(
size_t i = 0; i < contours.size(); i++ )
647 for(
size_t j = 0; j < contours.size(); j++ )
657 parentToChildren[i].emplace( j );
658 childToParents[j].emplace( i );
663 std::set<int> topLevelParents;
665 for(
size_t i = 0; i < contours.size(); i++ )
667 if( childToParents[i].size() == 0 )
669 topLevelParents.emplace( i );
675 std::function<void(
int,
int, std::vector<int> )>
process;
678 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
680 std::set<int> relParents = childToParents[myId];
682 for(
int pathId :
path )
684 int erased = relParents.erase( pathId );
685 wxASSERT( erased > 0 );
688 wxASSERT( relParents.size() == 0 );
692 bool isOutline =
path.size() % 2 == 0;
696 int outlineId = result.
AddOutline( contours[myId] );
697 myOutline = outlineId;
701 wxASSERT( parentOutlineId != -1 );
702 result.
AddHole( contours[myId], parentOutlineId );
705 auto it = parentToChildren.find( myId );
706 if( it != parentToChildren.end() )
708 std::vector<int> thisPath =
path;
709 thisPath.emplace_back( myId );
711 std::set<int> thisPathSet;
712 thisPathSet.insert( thisPath.begin(), thisPath.end() );
714 for(
int childId : it->second )
716 const std::set<int>& childPathSet = childToParents[childId];
718 if( thisPathSet != childPathSet )
721 process( childId, myOutline, thisPath );
726 for(
int topParentId : topLevelParents )
728 std::vector<int>
path;
739 booleanOp( aType, *
this, aOtherShape, aFastMode );
749 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
750 "ClearArcs() before carrying out the boolean operation." ) );
753 ClipperLib::Clipper c;
757 std::vector<CLIPPER_Z_VALUE> zValues;
758 std::vector<SHAPE_ARC> arcBuffer;
759 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
763 for(
size_t i = 0; i < poly.size(); i++ )
765 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
766 ClipperLib::ptSubject,
true );
772 for(
size_t i = 0; i < poly.size(); i++ )
774 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
775 ClipperLib::ptClip,
true );
779 ClipperLib::PolyTree solution;
781 ClipperLib::ZFillCallback callback =
782 [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
783 ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
784 ClipperLib::IntPoint & pt )
787 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
791 retval = zValues.at( aZvalue ).m_SecondArcIdx;
793 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
794 retval = zValues.at( aZvalue ).m_FirstArcIdx;
800 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
802 ssize_t retval = arcIndex( aBottomZ );
806 if( retval != arcIndex( aTopZ, retval ) )
813 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
814 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
818 if( e1ArcSegmentIndex != -1 )
829 size_t z_value_ptr = zValues.size();
830 zValues.push_back( newZval );
834 newIntersectPoints.insert( {
VECTOR2I( pt.X, pt.Y ), newZval } );
840 c.ZFillFunction( std::move( callback ) );
842 c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
860 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
861 "ClearArcs() before carrying out the boolean operation." ) );
864 Clipper2Lib::Clipper64 c;
866 std::vector<CLIPPER_Z_VALUE> zValues;
867 std::vector<SHAPE_ARC> arcBuffer;
868 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
870 Clipper2Lib::Paths64 paths;
871 Clipper2Lib::Paths64 clips;
875 for(
size_t i = 0; i < poly.size(); i++ )
877 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
883 for(
size_t i = 0; i < poly.size(); i++ )
885 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
889 c.AddSubject( paths );
892 Clipper2Lib::PolyTree64 solution;
894 Clipper2Lib::ZCallback64 callback =
895 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
896 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
897 Clipper2Lib::Point64 & pt )
900 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
904 retval = zValues.at( aZvalue ).m_SecondArcIdx;
906 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
907 retval = zValues.at( aZvalue ).m_FirstArcIdx;
913 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
915 ssize_t retval = arcIndex( aBottomZ );
919 if( retval != arcIndex( aTopZ, retval ) )
926 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
927 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
931 if( e1ArcSegmentIndex != -1 )
942 size_t z_value_ptr = zValues.size();
943 zValues.push_back( newZval );
947 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
953 c.SetZCallback( std::move( callback ) );
955 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
965 booleanOp( Clipper2Lib::ClipType::Union, b );
967 booleanOp( ClipperLib::ctUnion, b, aFastMode );
974 booleanOp( Clipper2Lib::ClipType::Difference, b );
976 booleanOp( ClipperLib::ctDifference, b, aFastMode );
983 booleanOp( Clipper2Lib::ClipType::Intersection, b );
985 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
992 booleanOp( Clipper2Lib::ClipType::Xor, b );
994 booleanOp( ClipperLib::ctXor, b, aFastMode );
1002 booleanOp( Clipper2Lib::ClipType::Union, a, b );
1004 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
1012 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
1014 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
1022 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
1024 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
1032 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
1034 booleanOp( ClipperLib::ctXor, a, b, aFastMode );
1042 Inflate( aFactor, aCornerStrategy, aMaxError );
1049 using namespace ClipperLib;
1053 #define SEG_CNT_MAX 64
1054 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1061 JoinType joinType = jtRound;
1062 double miterLimit = 2.0;
1063 JoinType miterFallback = jtSquare;
1065 switch( aCornerStrategy )
1067 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1070 miterFallback = jtSquare;
1073 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1075 miterFallback = jtRound;
1078 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1080 miterFallback = jtSquare;
1083 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1084 joinType = jtSquare;
1085 miterFallback = jtSquare;
1088 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1090 miterFallback = jtSquare;
1094 std::vector<CLIPPER_Z_VALUE> zValues;
1095 std::vector<SHAPE_ARC> arcBuffer;
1099 for(
size_t i = 0; i < poly.size(); i++ )
1101 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
1102 joinType, etClosedPolygon );
1112 if( aCircleSegCount < 6 )
1113 aCircleSegCount = 6;
1117 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1119 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1122 arc_tolerance_factor[aCircleSegCount] = coeff;
1126 coeff = arc_tolerance_factor[aCircleSegCount];
1129 c.ArcTolerance =
std::abs( aAmount ) * coeff;
1130 c.MiterLimit = miterLimit;
1131 c.MiterFallback = miterFallback;
1132 c.Execute( solution, aAmount );
1141 using namespace Clipper2Lib;
1145 #define SEG_CNT_MAX 64
1146 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1153 JoinType joinType = JoinType::Round;
1154 double miterLimit = 2.0;
1156 switch( aCornerStrategy )
1158 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1159 joinType = JoinType::Miter;
1163 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1164 joinType = JoinType::Miter;
1167 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1168 joinType = JoinType::Miter;
1171 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1172 joinType = JoinType::Square;
1175 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1176 joinType = JoinType::Round;
1180 std::vector<CLIPPER_Z_VALUE> zValues;
1181 std::vector<SHAPE_ARC> arcBuffer;
1187 for(
size_t i = 0; i < poly.size(); i++ )
1188 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1190 c.AddPaths( paths, joinType, EndType::Polygon );
1197 if( aCircleSegCount < 6 )
1198 aCircleSegCount = 6;
1202 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1204 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1207 arc_tolerance_factor[aCircleSegCount] = coeff;
1211 coeff = arc_tolerance_factor[aCircleSegCount];
1214 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1215 c.MiterLimit( miterLimit );
1222 c.Execute( aAmount, paths );
1224 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1227 c2.PreserveCollinear(
false );
1228 c2.ReverseSolution(
false );
1229 c2.AddSubject( paths );
1230 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1234 c.Execute( aAmount, tree );
1245 using namespace Clipper2Lib;
1249 #define SEG_CNT_MAX 64
1250 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1257 JoinType joinType = JoinType::Round;
1258 double miterLimit = 2.0;
1260 switch( aCornerStrategy )
1262 case CORNER_STRATEGY::ALLOW_ACUTE_CORNERS:
1263 joinType = JoinType::Miter;
1267 case CORNER_STRATEGY::CHAMFER_ACUTE_CORNERS:
1268 joinType = JoinType::Miter;
1271 case CORNER_STRATEGY::ROUND_ACUTE_CORNERS:
1272 joinType = JoinType::Miter;
1275 case CORNER_STRATEGY::CHAMFER_ALL_CORNERS:
1276 joinType = JoinType::Square;
1279 case CORNER_STRATEGY::ROUND_ALL_CORNERS:
1280 joinType = JoinType::Round;
1284 std::vector<CLIPPER_Z_VALUE> zValues;
1285 std::vector<SHAPE_ARC> arcBuffer;
1288 c.AddPath(
path, joinType, EndType::Butt );
1294 if( aCircleSegCount < 6 )
1295 aCircleSegCount = 6;
1299 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1301 coeff = 1.0 - cos( M_PI / aCircleSegCount );
1304 arc_tolerance_factor[aCircleSegCount] = coeff;
1308 coeff = arc_tolerance_factor[aCircleSegCount];
1311 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1312 c.MiterLimit( miterLimit );
1319 c.Execute( aAmount, paths2 );
1321 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1324 c2.PreserveCollinear(
false );
1325 c2.ReverseSolution(
false );
1326 c2.AddSubject( paths2 );
1327 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1331 c.Execute( aAmount, tree );
1345 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1347 inflate1( aAmount, segCount, aCornerStrategy );
1356 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1361 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1362 const std::vector<SHAPE_ARC>& aArcBuffer )
1366 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
1371 paths.reserve( n->Childs.size() + 1 );
1373 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
1375 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
1376 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
1385 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1386 const std::vector<SHAPE_ARC>& aArcBuffer )
1388 if( !aPolyPath->IsHole() )
1391 paths.reserve( aPolyPath->Count() + 1 );
1392 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1394 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1396 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1398 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1408 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1409 const std::vector<SHAPE_ARC>& aArcBuffer )
1413 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1419 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1420 const std::vector<SHAPE_ARC>& aArcBuffer )
1425 for(
const Clipper2Lib::Path64& n : aPath )
1427 if( Clipper2Lib::Area( n ) > 0 )
1436 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1439 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1476 int x = edge.
m_p1.
x;
1477 int y = edge.
m_p1.
y;
1478 int min_dist = std::numeric_limits<int>::max();
1497 x_intersect = std::max( e.
m_p1.
x, e.
m_p2.
x );
1505 int dist = ( x - x_intersect );
1507 if( dist >= 0 && dist < min_dist )
1510 x_nearest = x_intersect;
1523 edges[hole2outline_index] =
1526 edges[split_index] =
1531 e_nearest->
m_next = outline2hole_index;
1534 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1536 last->
m_next = hole2outline_index;
1546 bool outline =
true;
1548 if( paths.size() == 1 )
1551 size_t total_point_count = 0;
1555 total_point_count +=
path.PointCount();
1558 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1560 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1567 edges.reserve( total_point_count + paths.size() * 3 );
1573 int path_or_provoking_index;
1578 std::vector<PathInfo> sorted_paths;
1579 const int paths_count =
static_cast<int>( paths.size() );
1580 sorted_paths.reserve( paths_count );
1582 for(
int path_index = 0; path_index < paths_count; path_index++ )
1585 const std::vector<VECTOR2I>& points =
path.CPoints();
1586 const int point_count =
static_cast<int>( points.size() );
1587 int x_min = std::numeric_limits<int>::max();
1588 int y_min = std::numeric_limits<int>::max();
1591 for(
int point_index = 0; point_index < point_count; point_index++ )
1593 const VECTOR2I& point = points[point_index];
1594 if( point.
x < x_min )
1597 leftmost = point_index;
1599 if( point.
y < y_min )
1603 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1606 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1607 [](
const PathInfo& a,
const PathInfo& b )
1610 return a.y_or_bridge < b.y_or_bridge;
1616 for( PathInfo& path_info : sorted_paths )
1619 const std::vector<VECTOR2I>& points =
path.CPoints();
1620 const size_t point_count = points.size();
1625 for(
size_t i = 0; i < point_count - 1; i++ )
1627 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1632 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1639 path_info.path_or_provoking_index = provoking_edge;
1640 path_info.y_or_bridge = edge_index;
1644 edges.resize( edge_index );
1650 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1652 auto edge =
processHole( edges, it->path_or_provoking_index,
1653 it->path_or_provoking_index + it->leftmost, it->y_or_bridge );
1658 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1706 int x = edge->
m_p1.
x;
1707 int y = edge->
m_p1.
y;
1708 int min_dist = std::numeric_limits<int>::max();
1715 if( !e->matches( y ) )
1720 if( e->m_p1.y == e->m_p2.y )
1722 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1726 x_intersect = e->m_p1.x
1727 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1730 int dist = ( x - x_intersect );
1732 if( dist >= 0 && dist < min_dist && e->m_connected )
1735 x_nearest = x_intersect;
1751 edges.push_back( split_2 );
1752 edges.push_back( lead1 );
1753 edges.push_back( lead2 );
1758 e_nearest->
m_next = lead1;
1763 for( last = edge; last->
m_next != edge; last = last->
m_next )
1789 if( paths.size() == 1 )
1792 int num_unconnected = 0;
1796 const std::vector<VECTOR2I>& points =
path.CPoints();
1797 int pointCount = points.size();
1801 int x_min = std::numeric_limits<int>::max();
1803 for(
int i = 0; i < pointCount; i++ )
1805 if( points[i].x < x_min )
1806 x_min = points[i].x;
1811 points[i + 1 == pointCount ? 0 : i + 1] );
1822 if( i == pointCount - 1 )
1826 edges.push_back( fe );
1830 if( fe->
m_p1.
x == x_min )
1831 border_edges.push_back( fe );
1842 while( num_unconnected > 0 )
1844 int x_min = std::numeric_limits<int>::max();
1845 auto it = border_edges.begin();
1850 for( ; it != border_edges.end(); ++it )
1853 int xt = border_edge->
m_p1.
x;
1855 if( ( xt <= x_min ) && !border_edge->
m_connected )
1858 smallestX = border_edge;
1862 int num_processed =
processEdge( edges, smallestX );
1865 if( !num_processed )
1867 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1875 num_unconnected -= num_processed;
1893 paths.push_back( std::move( newPath ) );
1916 assert( aPoly.size() == 1 );
1922 bool m_duplicate =
false;
1929 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const
1931 return (s1.
A == s2.
B && s1.
B == s2.
A);
1936 return compareSegs( m_poly->
CSegment( m_index ),
1937 aOther.m_poly->CSegment( aOther.m_index ) );
1942 return !compareSegs( m_poly->
CSegment( m_index ),
1943 aOther.m_poly->CSegment( aOther.m_index ) );
1948 std::size_t operator()(
const EDGE& aEdge )
const
1950 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1951 std::size_t seed = 0xa82de1c0;
1958 struct EDGE_LIST_ENTRY
1961 EDGE_LIST_ENTRY*
next;
1964 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1969 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1973 edgeList[i].index = i;
1974 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1977 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1982 uniqueEdges.insert( e );
1988 auto it = uniqueEdges.find( e );
1990 if( it != uniqueEdges.end() && it->m_index != i )
1992 int e1 = it->m_index;
1996 std::swap( e1, e2 );
1998 int e1_prev = e1 - 1;
2003 int e2_prev = e2 - 1;
2008 int e1_next = e1 + 1;
2013 int e2_next = e2 + 1;
2018 edgeList[e1_prev].next = &edgeList[ e2_next ];
2019 edgeList[e2_prev].next = &edgeList[ e1_next ];
2020 edgeList[i].next =
nullptr;
2021 edgeList[it->m_index].next =
nullptr;
2027 if( edgeList[i].
next )
2028 queue.insert( &edgeList[i] );
2031 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
2037 double max_poly = 0.0;
2039 while( queue.size() )
2041 EDGE_LIST_ENTRY* e_first = *queue.begin();
2042 EDGE_LIST_ENTRY* e = e_first;
2049 }
while( e && e != e_first );
2053 for(
int i = 0; i < cnt; i++ )
2057 queue.erase( edgeBuf[i] );
2062 double area = std::fabs( outl.
Area() );
2064 if( area > max_poly )
2070 result.push_back( outl );
2075 std::swap( result[0], result[outline] );
2087 if( paths.size() > 1 )
2122 path.Simplify( aMaxError );
2140 while( outline.size() > 1 )
2165 std::stringstream ss;
2167 ss <<
"SHAPE_LINE_CHAIN poly; \n";
2169 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2171 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
2174 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
2180 ss <<
" poly.AddOutline(tmp); } \n";
2184 ss <<
" poly.AddHole(tmp); } \n";
2200 if( tmp !=
"polyset" )
2205 int n_polys = atoi( tmp.c_str() );
2210 for(
int i = 0; i < n_polys; i++ )
2220 int n_outlines = atoi( tmp.c_str() );
2222 if( n_outlines < 0 )
2225 for(
int j = 0; j < n_outlines; j++ )
2232 int n_vertices = atoi( tmp.c_str() );
2234 for(
int v = 0; v < n_vertices; v++ )
2238 aStream >> tmp; p.
x = atoi( tmp.c_str() );
2239 aStream >> tmp; p.
y = atoi( tmp.c_str() );
2243 paths.push_back( outline );
2257 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2274 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2277 bb = *
m_polys[i][0].GetCachedBBox();
2294 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2309 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2312 *aLocation = nearest;
2315 *aActual = sqrt( dist_sq );
2333 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2336 *aLocation = nearest;
2339 *aActual = sqrt( dist_sq );
2356 int extra = segment->
GetWidth() / 2;
2358 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2361 *aActual = std::max( 0, *aActual - extra );
2374 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
2377 *aActual = std::max( 0, *aActual - extra );
2387 int actual = INT_MAX;
2394 if( aActual || aLocation )
2399 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
2401 if( triActual < actual )
2404 location = triLocation;
2410 if( aShape->
Collide( &tri, aClearance ) )
2416 if( actual < INT_MAX )
2419 *aActual = std::max( 0, actual );
2422 *aLocation = location;
2440 if( aPolygonIdx < 0 )
2441 aPolygonIdx +=
m_polys.size();
2443 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2463 std::vector<VERTEX_INDEX> indices_to_remove;
2468 segmentStart = *iterator;
2474 segmentEnd = contourStart;
2482 contourStart = *iterator;
2490 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2492 segmentEnd = *iterator;
2496 if( segmentStart == segmentEnd )
2498 indices_to_remove.push_back( indexStart );
2505 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2528 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2530 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2531 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2558 Append( aP.
x, aP.
y, aOutline, aHole );
2564 int aClearance )
const
2567 bool collision =
false;
2577 delta = *iterator - aPoint;
2580 distance_squared =
delta.SquaredEuclideanNorm();
2583 if( distance_squared <= clearance_squared )
2585 if( !aClosestVertex )
2591 clearance_squared = distance_squared;
2594 *aClosestVertex = iterator.GetIndex();
2604 int aClearance )
const
2607 bool collision =
false;
2612 const SEG currentSegment = *iterator;
2616 if( distance_squared <= clearance_squared )
2618 if( !aClosestVertex )
2624 clearance_squared = distance_squared;
2627 *aClosestVertex = iterator.GetIndex();
2637 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2641 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
2648 bool aUseBBoxCaches )
const
2654 if( aSubpolyIndex >= 0 )
2655 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
2658 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
2660 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
2676 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2693 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
2704 bool aUseBBoxCaches )
const
2710 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
2732 path.Move( aVector );
2736 tri->Move( aVector );
2748 path.Mirror( aX, aY, aRef );
2761 path.Rotate( aAngle, aCenter );
2777 c +=
path.PointCount();
2814 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
2816 for( iterator++; iterator && minDistance > 0; iterator++ )
2818 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
2820 if( currentDistance < minDistance )
2823 *aNearest = (*iterator).NearestPoint( aPoint );
2825 minDistance = currentDistance;
2841 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
2847 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
2849 if( aNearest && minDistance == 0 )
2850 *aNearest = ( *iterator ).NearestPoint( aSegment );
2852 for( iterator++; iterator && minDistance > 0; iterator++ )
2856 if( currentDistance < minDistance )
2859 *aNearest = (*iterator).NearestPoint( aSegment );
2861 minDistance = currentDistance;
2866 return minDistance < 0 ? 0 : minDistance;
2873 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
2874 "support aOutlineOnly==true" ) );
2881 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2884 aNearest ? &nearest :
nullptr );
2886 if( currentDistance_sq < minDistance_sq )
2889 *aNearest = nearest;
2891 minDistance_sq = currentDistance_sq;
2895 return minDistance_sq;
2906 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
2909 aNearest ? &nearest :
nullptr );
2911 if( currentDistance_sq < minDistance_sq )
2914 *aNearest = nearest;
2916 minDistance_sq = currentDistance_sq;
2920 return minDistance_sq;
2941 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2952 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2960 unsigned int aDistance,
2961 int aIndex,
int aErrorMax )
2970 if( aDistance == 0 )
2982 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2985 int x1 = currContour.
CPoint( currVertex ).
x;
2986 int y1 = currContour.CPoint( currVertex ).y;
2995 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2998 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
3001 double xa = currContour.CPoint( prevVertex ).x - x1;
3002 double ya = currContour.CPoint( prevVertex ).y - y1;
3005 double xb = currContour.CPoint( nextVertex ).x - x1;
3006 double yb = currContour.CPoint( nextVertex ).y - y1;
3009 if(
std::abs( xa + xb ) < std::numeric_limits<double>::epsilon()
3010 &&
std::abs( ya + yb ) < std::numeric_limits<double>::epsilon() )
3016 double lena = hypot( xa, ya );
3017 double lenb = hypot( xb, yb );
3034 newContour.
Append( x1 + nx1, y1 + ny1 );
3039 newContour.
Append( x1 + nx2, y1 + ny2 );
3043 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
3045 double radius = aDistance;
3046 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
3049 if( std::isinf( denom ) )
3053 if( 0.5 * lena * denom < radius )
3054 radius = 0.5 * lena * denom;
3056 if( 0.5 * lenb * denom < radius )
3057 radius = 0.5 * lenb * denom;
3060 double k = radius / sqrt( .5 * ( 1 - cosine ) );
3061 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
3062 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
3063 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
3064 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
3067 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
3068 double xs = x1 + k * xa / lena - xc;
3069 double ys = y1 + k * ya / lena - yc;
3070 double xe = x1 + k * xb / lenb - xc;
3071 double ye = y1 + k * yb / lenb - yc;
3074 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
3080 else if( argument > 1 )
3083 double arcAngle = acos( argument );
3087 double deltaAngle = arcAngle / segments;
3088 double startAngle = atan2( -ys, xs );
3091 if( xa * yb - ya * xb <= 0 )
3094 double nx = xc + xs;
3095 double ny = yc + ys;
3097 if( std::isnan( nx ) || std::isnan( ny ) )
3106 for(
int j = 0; j < segments; j++ )
3108 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
3109 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
3111 if( std::isnan( nx ) || std::isnan( ny ) )
3127 newPoly.push_back( newContour );
3136 static_cast<SHAPE&
>(*this) = aOther;
3185 if( w == 0.0 || h == 0.0 )
3188 int n_cells_x, n_cells_y;
3192 n_cells_x = w / aSize;
3193 n_cells_y = floor( h / w * n_cells_x ) + 1;
3197 n_cells_y = h / aSize;
3198 n_cells_x = floor( w / h * n_cells_y ) + 1;
3201 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
3203 for(
int yy = 0; yy < n_cells_y; yy++ )
3205 for(
int xx = 0; xx < n_cells_x; xx++ )
3209 p.
x = bb.
GetX() + w * xx / n_cells_x;
3210 p.
y = bb.
GetY() + h * yy / n_cells_y;
3214 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
3215 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
3223 mask.SetClosed(
true );
3225 if( ( xx ^ yy ) & 1 )
3237 for(
int i = 0; i < ps2.OutlineCount(); i++ )
3238 ps1.AddOutline( ps2.COutline( i ) );
3240 if( ps1.OutlineCount() )
3248 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* aHintData )
3264 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3265 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData )
3267 bool triangulationValid =
false;
3271 if( hintData && hintData->size() != (unsigned) polySet.
OutlineCount() )
3276 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3277 dest.erase( dest.end() - 1 );
3279 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3286 hintData ? hintData->at( index ).get() :
nullptr ) )
3294 else if( pass == 2 )
3309 triangulationValid =
false;
3316 triangulationValid =
true;
3319 return triangulationValid;
3331 for(
int jj = 0; jj <
HoleCount( ii ); ++jj )
3338 else if( aSimplify )
3347 wxLogTrace(
TRIANGULATE_TRACE,
"Failed to triangulate partitioned polygon %d", ii );
3389 hash.
add( outline.size() );
3393 hash.
add( lc.PointCount() );
3395 for(
int i = 0; i < lc.PointCount(); i++ )
3423 std::set<long long> ptHashes;
3427 for(
const VECTOR2I& pt : lc.CPoints() )
3429 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3431 if( ptHashes.count( ptHash ) > 0 )
3434 ptHashes.insert( ptHash );
3453 n += t->GetTriangleCount();
3466 aSubshapes.push_back( &tri );
3477 if( aClearance != 0 )
3527 bool aReverseOrientation,
bool aEvenOdd )
3529 ClipperLib::Clipper clipper;
3530 ClipperLib::PolyTree tree;
3536 ClipperLib::Path lc;
3538 for(
int i = 0; i <
path.PointCount(); i++ )
3540 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
3543 clipper.AddPath( lc, ClipperLib::ptSubject,
true );
3546 clipper.StrictlySimple(
true );
3547 clipper.Execute( ClipperLib::ctUnion, tree,
3548 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
3549 ClipperLib::pftNonZero );
3552 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
3558 for(
unsigned int i = 0; i < n->Contour.size(); i++ )
3559 result.
Outline( outl ).
Append( n->Contour[i].X, n->Contour[i].Y );
3561 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
3563 int outh = result.
NewHole( outl );
3564 for(
unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
3566 result.
Hole( outl, outh )
3567 .
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)
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr coord_type GetY() const
constexpr size_type GetWidth() const
constexpr coord_type GetX() const
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr size_type GetHeight() const
constexpr coord_type GetLeft() const
constexpr coord_type GetRight() const
constexpr coord_type GetTop() const
constexpr coord_type GetBottom() const
A streaming C++ equivalent for MurmurHash3_x64_128.
FORCE_INLINE void add(const std::string &input)
FORCE_INLINE HASH_128 digest()
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
ecoord SquaredDistance(const SEG &aSeg) const
VECTOR2I::extended_type ecoord
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
static SEG::ecoord Square(int a)
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
SHAPE_TYPE Type() const
Return the type of the shape.
const VECTOR2I GetCenter() const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
void GenerateBBoxCache() const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
Clipper2Lib::Path64 convertToClipper2(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
bool IsEndContour() const
Base class for iterating over all segments in a given SHAPE_POLY_SET.
TRIANGULATED_POLYGON(int aSourceOutline)
std::deque< TRI > m_triangles
std::deque< VECTOR2I > m_vertices
void AddTriangle(int a, int b, int c)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
Represent a set of closed polygons.
std::mutex m_triangulationMutex
virtual bool HasIndexableSubshapes() const override
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.
void RemoveOutline(int aOutlineIdx)
Delete the aOutlineIdx-th outline of the set including its contours and holes.
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const override
void 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.
HASH_128 checksum() const
void Inflate(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify=false)
Perform outline inflation/deflation.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
int AddPolygon(const POLYGON &apolygon)
Adds a polygon to the set.
const std::string Format(bool aCplusPlus=true) const override
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.
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
constexpr extended_type SquaredDistance(const VECTOR2< T > &aVector) const
Compute the squared distance between two vectors.
static constexpr extended_type ECOORD_MAX
CORNER_STRATEGY
define how inflate transform build inflated polygon
static bool empty(const wxTextEntryBase *aCtrl)
static constexpr EDA_ANGLE FULL_CIRCLE
a few functions useful in geometry calculations.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
static constexpr void hash_combine(std::size_t &seed)
This is a dummy function to take the final case of hash_combine below.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
static PGM_BASE * process
#define TRIANGULATE_TRACE
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
A storage class for 128-bit hash value.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
TRIANGULATED_POLYGON * parent
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I