37#include <unordered_map>
38#include <unordered_set>
44#include <clipper2/clipper.h>
68#if defined( __MINGW32__ )
69 #define TRIANGULATESIMPLIFICATIONLEVEL 50
70 #define ENABLECACHEFRIENDLYFRACTURE true
71 #define ENABLEFRACTUREEDGEINDEX true
73 #define TRIANGULATESIMPLIFICATIONLEVEL ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel
74 #define ENABLECACHEFRIENDLYFRACTURE ADVANCED_CFG::GetCfg().m_EnableCacheFriendlyFracture
75 #define ENABLEFRACTUREEDGEINDEX ADVANCED_CFG::GetCfg().m_EnableFractureEdgeIndex
120 m_triangulatedPolys.reserve( aOther.TriangulatedPolyCount() );
122 for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
124 const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
125 m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
136 m_triangulationValid =
false;
139 m_failedHash = aOther.m_failedHash;
140 m_failedHashValid.store( aOther.m_failedHashValid.load() );
175 unsigned int contourIdx = 0;
178 int currentGlobalIdx = 0;
180 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
184 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
187 int totalPoints = currentContour.
PointCount();
189 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
192 if( currentGlobalIdx == aGlobalIdx )
194 aRelativeIndices->
m_polygon = polygonIdx;
195 aRelativeIndices->
m_contour = contourIdx;
196 aRelativeIndices->
m_vertex = vertexIdx;
212 int& aGlobalIdx )
const
214 int selectedVertex = aRelativeIndices.
m_vertex;
215 unsigned int selectedContour = aRelativeIndices.
m_contour;
216 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
219 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
220 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
226 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
228 currentPolygon =
Polygon( polygonIdx );
230 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
231 aGlobalIdx += currentPolygon[contourIdx].PointCount();
234 currentPolygon =
Polygon( selectedPolygon );
236 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
237 aGlobalIdx += currentPolygon[contourIdx].PointCount();
239 aGlobalIdx += selectedVertex;
256 poly.push_back( empty_path );
257 m_polys.push_back( std::move( poly ) );
273 m_polys[aOutline].push_back( empty_path );
275 return m_polys.back().size() - 2;
293 assert( aOutline < (
int)
m_polys.size() );
294 assert( idx < (
int)
m_polys[aOutline].size() );
296 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
298 return m_polys[aOutline][idx].PointCount();
303 std::optional<int> aMaxError )
317 assert( aOutline < (
int)
m_polys.size() );
318 assert( idx < (
int)
m_polys[aOutline].size() );
320 if( aMaxError.has_value() )
321 m_polys[aOutline][idx].Append( aArc, aMaxError.value() );
323 m_polys[aOutline][idx].Append( aArc );
325 return m_polys[aOutline][idx].PointCount();
333 if( aGlobalIndex < 0 )
346 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
366 if( aOutline >= (
int)
m_polys.size() )
369 if( idx >= (
int)
m_polys[aOutline].size() )
372 return m_polys[aOutline][idx].PointCount();
387 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
389 full_count +=
m_polys[ii][idx].PointCount();
399 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
422 assert( aOutline < (
int)
m_polys.size() );
423 assert( idx < (
int)
m_polys[aOutline].size() );
425 return m_polys[aOutline][idx].CPoint( aIndex );
435 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
460 if(
index.m_vertex == 0 )
462 index.m_vertex = lastpoint - 1;
465 else if(
index.m_vertex == lastpoint )
483 *aPrevious = previous;
506 std::vector<CONTOUR_SEG> segments;
510 segments.push_back( { *it, it.GetIndex().m_contour } );
512 std::sort( segments.begin(), segments.end(), [](
const CONTOUR_SEG& aA,
const CONTOUR_SEG& aB )
514 const SEG& a = aA.seg;
515 const SEG& b = aB.seg;
516 int min_a_x = std::min( a.A.x, a.B.x );
517 int min_b_x = std::min( b.A.x, b.B.x );
519 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 ) );
524 for(
auto it = segments.begin(); it != segments.end(); ++it )
526 SEG& firstSegment = it->seg;
529 auto innerIterator = it;
530 int max_x = std::max( firstSegment.
A.
x, firstSegment.
B.
x );
531 int max_y = std::max( firstSegment.
A.
y, firstSegment.
B.
y );
534 for( innerIterator++; innerIterator != segments.end(); innerIterator++ )
536 SEG& secondSegment = innerIterator->seg;
537 int min_x = std::min( secondSegment.
A.
x, secondSegment.
B.
x );
538 int min_y = std::min( secondSegment.
A.
y, secondSegment.
B.
y );
542 if( max_x < min_x || ( max_x == min_x && max_y < min_y ) )
545 bool adjacent =
false;
547 if( it->contour == innerIterator->contour )
550 adjacent = ( index_diff == 1 ) || ( index_diff ==
polygon[it->contour].SegmentCount() - 1 );
554 if( !adjacent && firstSegment.
Collide( secondSegment, 0 ) )
579 poly.push_back( aOutline );
584 wxCHECK2_MSG( aOutline.
IsClosed(), poly.back().SetClosed(
true ),
585 "Warning: non-closed outline added to SHAPE_POLY_SET" );
587 m_polys.push_back( std::move( poly ) );
589 return (
int)
m_polys.size() - 1;
598 aOutline += (int)
m_polys.size();
600 assert( aOutline < (
int)
m_polys.size() );
604 assert( poly.size() );
606 poly.push_back( aHole );
608 return (
int) poly.size() - 2;
628 for(
int j = 0; j <
HoleCount( i ); j++ )
642 for(
size_t i = 0; i < poly.size(); i++ )
654 for(
size_t i = 0; i < poly.size(); i++ )
657 aArcBuffer.push_back( arc );
667 for(
size_t i = 0; i < poly.size(); i++ )
675 std::vector<SHAPE_LINE_CHAIN> contours;
678 contours.insert( contours.end(), poly.begin(), poly.end() );
680 std::map<int, std::set<int>> parentToChildren;
681 std::map<int, std::set<int>> childToParents;
684 contour.GenerateBBoxCache();
686 for(
size_t i = 0; i < contours.size(); i++ )
690 for(
size_t j = 0; j < contours.size(); j++ )
700 parentToChildren[i].emplace( j );
701 childToParents[j].emplace( i );
706 std::set<int> topLevelParents;
708 for(
size_t i = 0; i < contours.size(); i++ )
710 if( childToParents[i].size() == 0 )
712 topLevelParents.emplace( i );
718 std::function<void(
int,
int, std::vector<int> )>
process;
721 [&](
int myId,
int parentOutlineId,
const std::vector<int>&
path )
723 std::set<int> relParents = childToParents[myId];
725 for(
int pathId :
path )
727 int erased = relParents.erase( pathId );
728 wxASSERT( erased > 0 );
731 wxASSERT( relParents.size() == 0 );
735 bool isOutline =
path.size() % 2 == 0;
739 int outlineId =
result.AddOutline( contours[myId] );
740 myOutline = outlineId;
744 wxASSERT( parentOutlineId != -1 );
745 result.AddHole( contours[myId], parentOutlineId );
748 auto it = parentToChildren.find( myId );
749 if( it != parentToChildren.end() )
751 std::vector<int> thisPath =
path;
752 thisPath.emplace_back( myId );
754 std::set<int> thisPathSet;
755 thisPathSet.insert( thisPath.begin(), thisPath.end() );
757 for(
int childId : it->second )
759 const std::set<int>& childPathSet = childToParents[childId];
761 if( thisPathSet != childPathSet )
764 process( childId, myOutline, thisPath );
769 for(
int topParentId : topLevelParents )
771 std::vector<int>
path;
775 *
this = std::move(
result );
798 bool operator==(
const DIRECTED_EDGE& aOther )
const
800 return from == aOther.from && to == aOther.to;
804 struct DIRECTED_EDGE_HASH
806 std::size_t operator()(
const DIRECTED_EDGE& aEdge )
const
808 std::size_t seed = 0x51ed27a3;
809 hash_combine( seed, aEdge.from.x, aEdge.from.y, aEdge.to.x, aEdge.to.y );
814 const std::vector<VECTOR2I>& pts = aChain.
CPoints();
815 const int count =
static_cast<int>( pts.size() );
818 std::unordered_map<DIRECTED_EDGE, std::vector<int>, DIRECTED_EDGE_HASH> unpaired;
819 std::vector<int>
partner( count, -1 );
820 bool hasBridge =
false;
822 unpaired.reserve( count );
824 for(
int ii = 0; ii < count; ++ii )
827 const VECTOR2I& b = pts[( ii + 1 ) % count];
832 auto twin = unpaired.find( { b, a } );
834 if( twin != unpaired.end() )
836 const int jj = twin->second.back();
838 twin->second.pop_back();
840 if( twin->second.empty() )
841 unpaired.erase( twin );
849 unpaired[{ a, b }].push_back( ii );
858 [&](
int aEdge ) ->
int
860 int next = ( aEdge + 1 ) % count;
873 std::vector<bool> visited( count,
false );
875 for(
int start = 0; start < count; ++start )
877 if( visited[start] ||
partner[start] >= 0 )
885 if( edge < 0 || visited[edge] )
891 visited[edge] =
true;
892 ring.
Append( pts[edge],
true );
893 edge = nextEdge( edge );
894 }
while( edge != start );
899 aRings.push_back( std::move( ring ) );
908 std::vector<CLIPPER_Z_VALUE>& aZValues,
909 std::vector<SHAPE_ARC>& aArcBuffer )
912 constexpr int kMinPoints = 1024;
917 std::vector<SHAPE_LINE_CHAIN> rings;
924 const bool flip = aChain.
Area(
false ) < 0;
927 aPaths.push_back( ring.convertToClipper2( ( ring.Area(
false ) >= 0 ) != flip, aZValues, aArcBuffer ) );
939 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call "
940 "ClearArcs() before carrying out the boolean operation." ) );
943 Clipper2Lib::Clipper64 c;
945 std::vector<CLIPPER_Z_VALUE> zValues;
946 std::vector<SHAPE_ARC> arcBuffer;
947 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
949 Clipper2Lib::Paths64 paths;
950 Clipper2Lib::Paths64 clips;
957 for(
size_t i = 0; i < poly.size(); i++ )
959 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
968 for(
size_t i = 0; i < poly.size(); i++ )
970 clips.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
974 c.AddSubject( paths );
977 Clipper2Lib::PolyTree64 solution;
979 Clipper2Lib::ZCallback64 callback =
980 [&](
const Clipper2Lib::Point64 & e1bot,
const Clipper2Lib::Point64 & e1top,
981 const Clipper2Lib::Point64 & e2bot,
const Clipper2Lib::Point64 & e2top,
982 Clipper2Lib::Point64 & pt )
985 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
989 retval = zValues.at( aZvalue ).m_SecondArcIdx;
991 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
992 retval = zValues.at( aZvalue ).m_FirstArcIdx;
998 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
1000 ssize_t retval = arcIndex( aBottomZ );
1004 if( retval != arcIndex( aTopZ, retval ) )
1011 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.z, e1top.z );
1012 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.z, e2top.z );
1016 if( e1ArcSegmentIndex != -1 )
1027 size_t z_value_ptr = zValues.size();
1028 zValues.push_back( newZval );
1032 newIntersectPoints.insert( {
VECTOR2I( pt.x, pt.y ), newZval } );
1038 c.SetZCallback( std::move( callback ) );
1040 c.Execute( aType, Clipper2Lib::FillRule::NonZero, solution );
1049 booleanOp( Clipper2Lib::ClipType::Union, b );
1055 booleanOp( Clipper2Lib::ClipType::Difference, b );
1061 booleanOp( Clipper2Lib::ClipType::Intersection, b );
1067 booleanOp( Clipper2Lib::ClipType::Xor, b );
1073 booleanOp( Clipper2Lib::ClipType::Union, a, b );
1079 booleanOp( Clipper2Lib::ClipType::Difference, a, b );
1085 booleanOp( Clipper2Lib::ClipType::Intersection, a, b );
1091 booleanOp( Clipper2Lib::ClipType::Xor, a, b );
1099 Inflate( aFactor, aCornerStrategy, aMaxError );
1107 using namespace Clipper2Lib;
1111 #define SEG_CNT_MAX 64
1112 static thread_local double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1119 JoinType joinType = JoinType::Round;
1120 double miterLimit = 2.0;
1122 switch( aCornerStrategy )
1125 joinType = JoinType::Miter;
1130 joinType = JoinType::Miter;
1134 joinType = JoinType::Miter;
1138 joinType = JoinType::Square;
1142 joinType = JoinType::Round;
1146 std::vector<CLIPPER_Z_VALUE> zValues;
1147 std::vector<SHAPE_ARC> arcBuffer;
1153 for(
size_t i = 0; i < poly.size(); i++ )
1154 paths.push_back( poly[i].convertToClipper2( i == 0, zValues, arcBuffer ) );
1156 c.AddPaths( paths, joinType, EndType::Polygon );
1163 if( aCircleSegCount < 6 )
1164 aCircleSegCount = 6;
1168 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1170 coeff = 1.0 - cos(
M_PI / aCircleSegCount );
1173 arc_tolerance_factor[aCircleSegCount] = coeff;
1177 coeff = arc_tolerance_factor[aCircleSegCount];
1180 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1181 c.MiterLimit( miterLimit );
1188 c.Execute( aAmount, paths );
1190 Clipper2Lib::SimplifyPaths( paths,
std::abs( aAmount ) * coeff,
true );
1193 c2.PreserveCollinear(
false );
1194 c2.ReverseSolution(
false );
1195 c2.AddSubject( paths );
1196 c2.Execute(ClipType::Union, FillRule::Positive, tree);
1200 c.Execute( aAmount, tree );
1211 using namespace Clipper2Lib;
1215 #define SEG_CNT_MAX 64
1216 static thread_local double arc_tolerance_factor[
SEG_CNT_MAX + 1];
1223 JoinType joinType = JoinType::Round;
1224 double miterLimit = 2.0;
1226 switch( aCornerStrategy )
1229 joinType = JoinType::Miter;
1234 joinType = JoinType::Miter;
1238 joinType = JoinType::Miter;
1242 joinType = JoinType::Square;
1246 joinType = JoinType::Round;
1250 std::vector<CLIPPER_Z_VALUE> zValues;
1251 std::vector<SHAPE_ARC> arcBuffer;
1254 c.AddPath(
path, joinType, EndType::Butt );
1260 if( aCircleSegCount < 6 )
1261 aCircleSegCount = 6;
1265 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
1267 coeff = 1.0 - cos(
M_PI / aCircleSegCount );
1270 arc_tolerance_factor[aCircleSegCount] = coeff;
1274 coeff = arc_tolerance_factor[aCircleSegCount];
1277 c.ArcTolerance(
std::abs( aAmount ) * coeff );
1278 c.MiterLimit( miterLimit );
1285 c.Execute( aAmount, paths2 );
1287 Clipper2Lib::SimplifyPaths( paths2,
std::abs( aAmount ) * coeff,
false );
1290 c2.PreserveCollinear(
false );
1291 c2.ReverseSolution(
false );
1292 c2.AddSubject( paths2 );
1293 c2.Execute( ClipType::Union, FillRule::Positive, tree );
1297 c.Execute( aAmount, tree );
1310 inflate2( aAmount, segCount, aCornerStrategy, aSimplify );
1319 inflateLine2( aLine, aAmount, segCount, aCornerStrategy, aSimplify );
1324 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1325 const std::vector<SHAPE_ARC>& aArcBuffer )
1327 if( !aPolyPath->IsHole() )
1330 paths.reserve( aPolyPath->Count() + 1 );
1331 paths.emplace_back( aPolyPath->Polygon(), aZValueBuffer, aArcBuffer );
1333 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& child : *aPolyPath )
1335 paths.emplace_back( child->Polygon(), aZValueBuffer, aArcBuffer );
1337 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& grandchild : *child )
1341 m_polys.emplace_back( std::move( paths ) );
1347 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1348 const std::vector<SHAPE_ARC>& aArcBuffer )
1352 for(
const std::unique_ptr<Clipper2Lib::PolyPath64>& n : tree )
1358 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1359 const std::vector<SHAPE_ARC>& aArcBuffer )
1364 for(
const Clipper2Lib::Path64& n : aPath )
1366 if( Clipper2Lib::Area( n ) > 0 )
1375 wxCHECK2_MSG( !
path.empty(),
continue, wxT(
"Cannot add a hole before an outline" ) );
1378 path.emplace_back( n, aZValueBuffer, aArcBuffer );
1424 template <
typename Originals>
1426 uint32_t aStripeCount,
size_t aHoleCount ) :
1431 m_maxNodes( (
KIGEOM::FRACTURE_INDEX::MAX_BUCKET_SPAN + 2 ) * aHoleCount ),
1435 size_t bucketIds = 0;
1439 [&]( uint32_t, uint32_t aFirst, uint32_t aLast )
1447 bucketIds += aLast - aFirst + 1;
1449 for( uint32_t stripe = aFirst; stripe <= aLast; ++stripe )
1462 for( uint32_t stripe = 0; stripe <
m_stripeCount; ++stripe )
1471 [&]( uint32_t aEdge, uint32_t aFirst, uint32_t aLast )
1479 for( uint32_t stripe = aFirst; stripe <= aLast; ++stripe )
1489 for( uint32_t stripe = 0; stripe <
m_stripeCount; ++stripe )
1495 for(
size_t pos = 1; pos <
m_longIds.size(); ++pos )
1500 size_t allocated_bytes = 0;
1505 &allocated_bytes ) )
1516 template <
typename Visitor>
1517 void Query(
int aY,
Index aProvokingIndex, Visitor&& aVisitor )
const
1519 const uint32_t stripe =
map( aY );
1526 if( edge >=
static_cast<uint32_t
>( aProvokingIndex ) )
1529 aVisitor(
static_cast<Index>( edge ) );
1534 if( edge >=
static_cast<uint32_t
>( aProvokingIndex ) )
1537 aVisitor(
static_cast<Index>( edge ) );
1546 for(
Index edge = aFirst; edge < aFirst + 3; ++edge )
1556 for( uint32_t stripe = first; stripe <= last; ++stripe )
1557 insert(
static_cast<uint32_t
>( edge ), stripe );
1563 static constexpr uint32_t
INVALID = std::numeric_limits<uint32_t>::max();
1572 template <
typename Visitor>
1580 assert( node.
edge <
static_cast<uint32_t
>( aProvokingIndex ) );
1582 if( node.
edge <
static_cast<uint32_t
>( aProvokingIndex ) )
1583 aVisitor(
static_cast<Index>( node.
edge ) );
1589 void insert( uint32_t aEdge, uint32_t aHead )
1596 static void logAccepted(
size_t aEdges,
size_t aHoles, uint32_t aStripes,
size_t aBytes )
1598 wxLogTrace( wxS(
"KICAD_FRACTURE_INDEX" ),
1599 wxS(
"Using fracture edge index: edges=%zu, holes=%zu, stripes=%u, allocated=%zu bytes" ),
1600 aEdges, aHoles, aStripes, aBytes );
1622 return std::max( aEdge.
m_p1.
x, aEdge.
m_p2.
x );
1634 int x = edge.
m_p1.
x;
1635 int y = edge.
m_p1.
y;
1636 int min_dist = std::numeric_limits<int>::max();
1656 int dist = x - x_intersect;
1659 && ( dist < min_dist
1660 || ( nearest_index >= 0 && dist == min_dist && aCandidateIndex < nearest_index ) ) )
1663 x_nearest = x_intersect;
1664 nearest_index = aCandidateIndex;
1668 aIndex->
Query( y, provokingIndex, consider );
1670 if( nearest_index >= 0 )
1671 e_nearest = &edges[nearest_index];
1683 int dist = x - x_intersect;
1685 if( dist >= 0 && dist < min_dist )
1688 x_nearest = x_intersect;
1689 e_nearest = &candidate;
1702 edges[hole2outline_index] =
1705 edges[split_index] =
1712 e_nearest->
m_next = outline2hole_index;
1715 for( ; last->
m_next != edgeIndex; last = &edges[last->
m_next] )
1717 last->
m_next = hole2outline_index;
1730 bool outline =
true;
1732 if( paths.size() == 1 )
1735 size_t total_point_count = 0;
1739 total_point_count +=
path.PointCount();
1742 if( total_point_count > (
size_t) std::numeric_limits<FractureEdge::Index>::max() )
1744 wxLogWarning( wxT(
"Polygon has more points than int limit" ) );
1751 edges.reserve( total_point_count + paths.size() * 3 );
1757 int path_or_provoking_index;
1762 std::vector<PathInfo> sorted_paths;
1763 const int paths_count =
static_cast<int>( paths.size() );
1764 sorted_paths.reserve( paths_count );
1766 for(
int path_index = 0; path_index < paths_count; path_index++ )
1769 const std::vector<VECTOR2I>& points =
path.CPoints();
1770 const int point_count =
static_cast<int>( points.size() );
1771 int x_min = std::numeric_limits<int>::max();
1772 int y_min = std::numeric_limits<int>::max();
1775 for(
int point_index = 0; point_index < point_count; point_index++ )
1777 const VECTOR2I& point = points[point_index];
1778 if( point.
x < x_min )
1781 leftmost = point_index;
1783 if( point.
y < y_min )
1787 sorted_paths.emplace_back( PathInfo{ path_index, leftmost, x_min, y_min } );
1790 std::sort( sorted_paths.begin() + 1, sorted_paths.end(),
1791 [](
const PathInfo& a,
const PathInfo& b )
1794 return a.y_or_bridge < b.y_or_bridge;
1800 for( PathInfo& path_info : sorted_paths )
1803 const std::vector<VECTOR2I>& points =
path.CPoints();
1804 const size_t point_count = points.size();
1809 for(
size_t i = 0; i < point_count - 1; i++ )
1811 edges.emplace_back( points[i], points[i + 1], edge_index + 1 );
1816 edges.emplace_back( points[point_count - 1], points[0], provoking_edge );
1823 path_info.path_or_provoking_index = provoking_edge;
1824 path_info.y_or_bridge = edge_index;
1828 edges.resize( edge_index );
1834 assert( edges.size() == total_point_count + 3 * ( paths.size() - 1 ) );
1838 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1840 assert( it->path_or_provoking_index == expected_edge );
1841 expected_edge = it->y_or_bridge + 3;
1847 uint64_t estimated_visits = 0;
1849 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1850 estimated_visits +=
static_cast<uint64_t
>( it->path_or_provoking_index );
1852 std::unique_ptr<FRACTURE_EDGE_INDEX>
index;
1856 int min_y = std::numeric_limits<int>::max();
1857 int max_y = std::numeric_limits<int>::min();
1864 min_y = std::min( min_y, point.y );
1865 max_y = std::max( max_y, point.y );
1869 auto visitOriginals = [&](
auto&& aVisitor )
1877 min_y, max_y, stripe_count );
1878 aVisitor(
static_cast<uint32_t
>( edge ), first, last );
1882 visitRange( 0, paths[0].PointCount() );
1884 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); ++it )
1885 visitRange( it->path_or_provoking_index, it->y_or_bridge );
1888 index = std::make_unique<FRACTURE_EDGE_INDEX>( edges, visitOriginals, min_y, max_y, stripe_count,
1891 if( !
index->IsValid() )
1895 for(
auto it = sorted_paths.begin() + 1; it != sorted_paths.end(); it++ )
1897 auto edge =
processHole( edges, it->path_or_provoking_index, it->path_or_provoking_index + it->leftmost,
1898 it->y_or_bridge,
index.get() );
1903 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1951 int x = edge->
m_p1.
x;
1952 int y = edge->
m_p1.
y;
1953 int min_dist = std::numeric_limits<int>::max();
1960 if( !e->matches( y ) )
1965 if( e->m_p1.y == e->m_p2.y )
1967 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
1971 x_intersect = e->m_p1.x
1972 +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y, e->m_p2.y - e->m_p1.y );
1975 int dist = ( x - x_intersect );
1977 if( dist >= 0 && dist < min_dist && e->m_connected )
1980 x_nearest = x_intersect;
1996 edges.push_back( split_2 );
1997 edges.push_back( lead1 );
1998 edges.push_back( lead2 );
2003 e_nearest->
m_next = lead1;
2008 for( last = edge; last->
m_next != edge; last = last->
m_next )
2034 if( paths.size() == 1 )
2037 int num_unconnected = 0;
2041 const std::vector<VECTOR2I>& points =
path.CPoints();
2042 int pointCount = points.size();
2046 int x_min = std::numeric_limits<int>::max();
2048 for(
int i = 0; i < pointCount; i++ )
2050 if( points[i].x < x_min )
2051 x_min = points[i].x;
2056 points[i + 1 == pointCount ? 0 : i + 1] );
2067 if( i == pointCount - 1 )
2071 edges.push_back( fe );
2075 if( fe->
m_p1.
x == x_min )
2076 border_edges.push_back( fe );
2087 while( num_unconnected > 0 )
2089 int x_min = std::numeric_limits<int>::max();
2090 auto it = border_edges.begin();
2095 for( ; it != border_edges.end(); ++it )
2098 int xt = border_edge->
m_p1.
x;
2100 if( ( xt <= x_min ) && !border_edge->
m_connected )
2103 smallestX = border_edge;
2107 int num_processed =
processEdge( edges, smallestX );
2110 if( !num_processed )
2112 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
2120 num_unconnected -= num_processed;
2138 paths.push_back( std::move( newPath ) );
2162 assert( aPoly.size() == 1 );
2170 std::vector<SHAPE_LINE_CHAIN> rings;
2174 aPoly[0] = std::move( lc );
2178 auto outline = std::max_element( rings.begin(), rings.end(),
2181 return std::fabs( aA.Area() ) < std::fabs( aB.Area() );
2184 std::iter_swap( rings.begin(), outline );
2185 aPoly = std::move( rings );
2195 if( paths.size() > 1 )
2219 std::array<VECTOR2I,4> pts = { aSegA.
A, aSegA.
B, aSegB.
A, aSegB.
B };
2221 std::sort( pts.begin(), pts.end(), [axis](
const VECTOR2I& p,
const VECTOR2I& q )
2224 return p.x < q.x || ( p.x == q.x && p.y < q.y );
2226 return p.y < q.y || ( p.y == q.y && p.x < q.x );
2247 wxLogTrace( wxT(
"collinear" ), wxT(
"Found exterior waist between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)" ),
2248 aSegA.
A.
x, aSegA.
A.
y, aSegA.
B.
x, aSegA.
B.
y,
2249 aSegB.
A.
x, aSegB.
A.
y, aSegB.
B.
x, aSegB.
B.
y );
2260 for(
size_t polyIdx = 0; polyIdx <
m_polys.size(); ++polyIdx )
2262 bool changed =
true;
2271 std::vector<SEG> segs;
2272 segs.reserve( count );
2274 for( intptr_t i = 0; i < count; ++i )
2275 segs.emplace_back( outline.
CPoint( i ), outline.
CPoint( ( i + 1 ) % count ) );
2283 for( intptr_t i = 0; i < count && !found; ++i )
2290 [&](
int j ) ->
bool
2292 if( j == i || j == ( ( i + 1 ) % count ) || j == ( ( i + count - 1 ) % count ) )
2297 SEG other( oa, ob );
2301 if( oa == a && ob == b )
2304 if( oa == b && ob == a )
2318 index.VisitCandidates( seg, 0, visitor );
2325 int a1 = ( segA + 1 ) % outline.
PointCount();
2327 int b1 = ( segB + 1 ) % outline.
PointCount();
2353 m_polys[polyIdx][0] = std::move( lc1 );
2356 np.push_back( std::move( lc2 ) );
2357 m_polys.push_back( std::move( np ) );
2367 for(
size_t polyIdx = 0; polyIdx <
m_polys.size(); ++polyIdx )
2369 bool changed =
true;
2383 std::vector<double> prefix;
2386 [&](
int aFrom,
int aTo ) ->
double
2388 if( prefix.empty() )
2390 prefix.resize( count + 1, 0.0 );
2392 for(
int ii = 0; ii < count; ++ii )
2397 prefix[ii + 1] = prefix[ii]
2398 + ( (double) a.
x + b.
x ) * ( (
double) a.
y - b.
y );
2402 double term = aFrom <= aTo ? prefix[aTo] - prefix[aFrom]
2403 : prefix[count] - prefix[aFrom] + prefix[aTo];
2408 return term + ( (double) last.
x + first.
x ) * ( (
double) last.
y - first.
y );
2412 [&](
int aFrom,
int aTo )
2414 return aFrom <= aTo ? aTo - aFrom + 1 : count - aFrom + aTo + 1;
2420 [&](
int aVertIdx,
int aSegIdx )
2422 const int start = ( aSegIdx + 1 ) % count;
2424 if( ringSize( start, aVertIdx ) < 3 || ringSize( aVertIdx, aSegIdx ) < 3 )
2427 const bool sign = ringTerm( 0, count - 1 ) > 0;
2428 const double term1 = ringTerm( start, aVertIdx );
2429 const double term2 = ringTerm( aVertIdx, aSegIdx );
2431 return term1 != 0.0 && term2 != 0.0 && ( term1 > 0 ) ==
sign
2432 && ( term2 > 0 ) ==
sign;
2435 int insertSegIdx = -1;
2436 int insertVertIdx = -1;
2440 for(
int vertIdx = 0; vertIdx < count && insertSegIdx < 0; ++vertIdx )
2443 const int prevSeg = ( vertIdx + count - 1 ) % count;
2445 for(
int segIdx = 0; segIdx < count; ++segIdx )
2448 if( segIdx == prevSeg || segIdx == vertIdx )
2459 && splittable( vertIdx, segIdx ) )
2461 insertSegIdx = segIdx;
2462 insertVertIdx = vertIdx;
2470 std::vector<SEG> segs;
2471 segs.reserve( count );
2473 for(
int i = 0; i < count; ++i )
2474 segs.emplace_back( outline.
CPoint( i ), outline.
CPoint( ( i + 1 ) % count ) );
2478 for(
int vertIdx = 0; vertIdx < count && insertSegIdx < 0; ++vertIdx )
2481 const int prevSeg = ( vertIdx + count - 1 ) % count;
2484 [&](
int segIdx ) ->
bool
2486 if( segIdx == prevSeg || segIdx == vertIdx )
2497 && splittable( vertIdx, segIdx ) )
2499 insertSegIdx = segIdx;
2500 insertVertIdx = vertIdx;
2507 index.VisitCandidates(
SEG( pt, pt ), 0, pinchVisitor );
2511 if( insertSegIdx < 0 )
2518 const int splitStart1 = ( insertSegIdx + 1 ) % count;
2519 const int size1 = ringSize( splitStart1, insertVertIdx );
2520 const int size2 = ringSize( insertVertIdx, insertSegIdx );
2527 int idx = splitStart1;
2529 for(
int i = 0; i < size1; ++i )
2532 idx = ( idx + 1 ) % count;
2537 idx = insertVertIdx;
2539 for(
int i = 0; i < size2; ++i )
2542 idx = ( idx + 1 ) % count;
2547 m_polys[polyIdx][0] = std::move( poly1 );
2550 np.push_back( std::move( poly2 ) );
2551 m_polys.push_back( std::move( np ) );
2575 path.Simplify( aTolerance );
2593 while( outline.size() > 1 )
2618 std::stringstream ss;
2620 ss <<
"SHAPE_LINE_CHAIN poly; \n";
2622 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2624 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
2627 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
2633 ss <<
" poly.AddOutline(tmp); } \n";
2637 ss <<
" poly.AddHole(tmp); } \n";
2653 if( tmp !=
"polyset" )
2658 int n_polys = atoi( tmp.c_str() );
2663 for(
int i = 0; i < n_polys; i++ )
2673 int n_outlines = atoi( tmp.c_str() );
2675 if( n_outlines < 0 )
2678 for(
int j = 0; j < n_outlines; j++ )
2685 int n_vertices = atoi( tmp.c_str() );
2687 for(
int v = 0; v < n_vertices; v++ )
2691 aStream >> tmp; p.
x = atoi( tmp.c_str() );
2692 aStream >> tmp; p.
y = atoi( tmp.c_str() );
2696 paths.push_back( std::move( outline ) );
2699 m_polys.push_back( std::move( paths ) );
2710 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2727 for(
unsigned i = 0; i <
m_polys.size(); i++ )
2730 bb = *
m_polys[i][0].GetCachedBBox();
2747 if( lineChain.PointOnEdge( aP, aAccuracy ) )
2762 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2765 *aLocation = nearest;
2768 *aActual = sqrt( dist_sq );
2786 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
2789 *aLocation = nearest;
2792 *aActual = sqrt( dist_sq );
2809 int extra = segment->
GetWidth() / 2;
2811 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
2814 *aActual = std::max( 0, *aActual - extra );
2825 int extra =
circle->GetRadius();
2827 if(
Collide(
circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
2830 *aActual = std::max( 0, *aActual - extra );
2840 if( !aActual && !aLocation )
2850 *aActual = std::max( 0,
actual );
2872 if( aPolygonIdx < 0 )
2873 aPolygonIdx +=
m_polys.size();
2875 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
2895 std::vector<VERTEX_INDEX> indices_to_remove;
2900 segmentStart = *iterator;
2906 segmentEnd = contourStart;
2914 contourStart = *iterator;
2922 wxCHECK_MSG( iterator, removed, wxT(
"Invalid polygon. Reached end without noticing. Please report this error" ) );
2924 segmentEnd = *iterator;
2928 if( segmentStart == segmentEnd )
2930 indices_to_remove.push_back( indexStart );
2937 for(
auto it = indices_to_remove.rbegin(); it != indices_to_remove.rend(); ++it )
2962 if( triangleSet->GetSourceOutlineIndex() == aIdx )
2964 else if( triangleSet->GetSourceOutlineIndex() > aIdx )
2965 triangleSet->SetSourceOutlineIndex( triangleSet->GetSourceOutlineIndex() - 1 );
2992 Append( aP.
x, aP.
y, aOutline, aHole );
2998 int aClearance )
const
3001 bool collision =
false;
3011 delta = *iterator - aPoint;
3014 distance_squared =
delta.SquaredEuclideanNorm();
3017 if( distance_squared <= clearance_squared )
3019 if( !aClosestVertex )
3025 clearance_squared = distance_squared;
3028 *aClosestVertex = iterator.GetIndex();
3038 int aClearance )
const
3041 bool collision =
false;
3046 const SEG currentSegment = *iterator;
3050 if( distance_squared <= clearance_squared )
3052 if( !aClosestVertex )
3058 clearance_squared = distance_squared;
3061 *aClosestVertex = iterator.GetIndex();
3071 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
3075 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
3082 bool aUseBBoxCaches )
const
3088 if( aSubpolyIndex >= 0 )
3089 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
3092 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
3094 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
3110 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
3127 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
3138 bool aUseBBoxCaches )
const
3144 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
3168 path.Move( aVector );
3172 tri->Move( aVector );
3184 path.Mirror( aRef, aFlipDirection );
3197 path.Mirror( aAxis );
3210 path.Rotate( aAngle, aCenter );
3226 c +=
path.PointCount();
3263 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
3266 *aNearest = ( *iterator ).NearestPoint( aPoint );
3268 for( iterator++; iterator && minDistance > 0; iterator++ )
3270 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
3272 if( currentDistance < minDistance )
3275 *aNearest = (*iterator).NearestPoint( aPoint );
3277 minDistance = currentDistance;
3293 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
3299 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
3302 *aNearest = ( *iterator ).NearestPoint( aSegment );
3304 for( iterator++; iterator && minDistance > 0; iterator++ )
3306 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
3308 if( currentDistance < minDistance )
3311 *aNearest = (*iterator).NearestPoint( aSegment );
3313 minDistance = currentDistance;
3318 return minDistance < 0 ? 0 : minDistance;
3325 wxASSERT_MSG( !aOutlineOnly, wxT(
"Warning: SHAPE_POLY_SET::SquaredDistance does not yet "
3326 "support aOutlineOnly==true" ) );
3333 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
3336 aNearest ? &nearest :
nullptr );
3338 if( currentDistance_sq < minDistance_sq )
3341 *aNearest = nearest;
3343 minDistance_sq = currentDistance_sq;
3347 return minDistance_sq;
3358 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
3361 aNearest ? &nearest :
nullptr );
3363 if( currentDistance_sq < minDistance_sq )
3366 *aNearest = nearest;
3368 minDistance_sq = currentDistance_sq;
3372 return minDistance_sq;
3385 return index.m_contour > 0;
3393 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
3404 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
3413 if(
this != &aOther )
3415 SHAPE::operator=( aOther );
3417 m_polys = std::move( aOther.m_polys );
3435 SHAPE::operator=( aOther );
3494 auto buildIndexes = [
this]()
3502 triCount +=
static_cast<int>( tpoly->GetTriangleCount() );
3535 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>& dest,
3536 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>>* hintData,
3539 bool triangulationValid =
false;
3543 if( hintData && hintData->size() != (
unsigned) polySet.
OutlineCount() )
3548 if( !dest.empty() && dest.back()->GetTriangleCount() == 0 )
3549 dest.erase( dest.end() - 1 );
3557 if( partitionLeaves > 1 )
3559 std::vector<SHAPE_LINE_CHAIN> partitions =
3562 if( partitions.size() > 1 )
3566 if( taskSubmitter && partitions.size() > 2 )
3568 size_t leafCount = partitions.size();
3570 struct WorkStealState
3572 std::unique_ptr<std::atomic<bool>[]> claimed;
3573 std::unique_ptr<std::atomic<bool>[]> done;
3574 std::unique_ptr<std::atomic<bool>[]> ok;
3576 explicit WorkStealState(
size_t n ) :
3577 claimed(
new std::atomic<bool>[n] ),
3578 done(
new std::atomic<bool>[n] ),
3579 ok(
new std::atomic<bool>[n] )
3581 for(
size_t i = 0; i < n; ++i )
3583 claimed[i].store(
false );
3584 done[i].store(
false );
3585 ok[i].store(
false );
3590 auto state = std::make_shared<WorkStealState>( leafCount );
3592 std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> results( leafCount );
3594 for(
size_t i = 0; i < leafCount; ++i )
3596 results[i] = std::make_unique<TRIANGULATED_POLYGON>( forOutline );
3599 for(
size_t i = 0; i < leafCount; ++i )
3601 auto* triPoly = results[i].get();
3602 auto* leaf = &partitions[i];
3604 taskSubmitter( [state, i, triPoly, leaf]()
3606 if( state->claimed[i].exchange(
true ) )
3611 state->done[i].store(
true, std::memory_order_release );
3615 for(
size_t i = 0; i < leafCount; ++i )
3617 if( state->claimed[i].exchange(
true ) )
3622 state->done[i].store(
true, std::memory_order_release );
3625 for(
size_t i = 0; i < leafCount; ++i )
3627 while( !state->done[i].load( std::memory_order_acquire ) )
3629 std::this_thread::yield();
3635 for(
size_t i = 0; i < leafCount; ++i )
3636 allOk = allOk && state->ok[i].load();
3640 for(
auto& r : results )
3642 if( r->GetTriangleCount() > 0 )
3643 dest.push_back( std::move( r ) );
3646 triangulationValid =
true;
3653 for(
auto it = partitions.rbegin(); it != partitions.rend(); ++it )
3662 dest.push_back( std::make_unique<TRIANGULATED_POLYGON>( forOutline ) );
3669 hintData ? hintData->at(
index ).get() :
nullptr ) )
3683 triangulationValid =
false;
3690 triangulationValid =
true;
3693 return triangulationValid;
3712 bool directOk =
true;
3714 for(
int ii = 0; ii < srcSet->
OutlineCount() && directOk; ++ii )
3719 if( poly.size() > 1 )
3732 for(
size_t jj = 1; jj < poly.size(); ++jj )
3772 double originalArea =
std::abs( poly.front().Area() );
3774 if( originalArea > 0.0 )
3776 double triArea = 0.0;
3781 double coverage = triArea / originalArea;
3783 if( coverage > 1.01 || coverage < 0.99 )
3796 bool splitOk =
true;
3798 for(
int jj = 0; jj < splitSet.
OutlineCount() && splitOk; ++jj )
3823 bool fallbackOk =
true;
3825 for(
int ii = 0; ii < srcSet->
OutlineCount() && fallbackOk; ++ii )
3830 for(
size_t jj = 1; jj < poly.size(); ++jj )
3890 hash.
add( outline.size() );
3894 hash.
add( lc.PointCount() );
3896 for(
int i = 0; i < lc.PointCount(); i++ )
3924 std::set<long long> ptHashes;
3928 for(
const VECTOR2I& pt : lc.CPoints() )
3930 const long long ptHash = (
long long) pt.x << 32 | pt.y;
3932 if( ptHashes.count( ptHash ) > 0 )
3935 ptHashes.insert( ptHash );
3954 n += t->GetTriangleCount();
3967 aSubshapes.push_back( &tri );
3978 if( aClearance != 0 )
4020 if( triCount < 2 || triCount >
static_cast<size_t>( std::numeric_limits<int>::max() ) / 6 )
4023 const int halfEdgeCount =
static_cast<int>( 3 * triCount );
4026 std::vector<int> heVertex( halfEdgeCount );
4028 for(
size_t k = 0; k < triCount; k++ )
4035 auto nextInTriangle = [](
int aEdge ) {
return aEdge - aEdge % 3 + ( aEdge + 1 ) % 3; };
4039 std::vector<int> twin( halfEdgeCount, -1 );
4043 while( tableSize < halfEdgeCount * 2 )
4046 const uint32_t tableMask =
static_cast<uint32_t
>( tableSize - 1 );
4047 std::vector<int> slotEdge( tableSize, -1 );
4051 std::vector<char> retired( tableSize, 0 );
4052 std::vector<int> toVisit;
4053 std::vector<char> queued( halfEdgeCount, 0 );
4055 for(
int edge = 0; edge < halfEdgeCount; edge++ )
4057 int from = heVertex[edge];
4058 int to = heVertex[nextInTriangle( edge )];
4059 uint32_t keyLow =
static_cast<uint32_t
>( from < to ? from : to );
4060 uint32_t keyHigh =
static_cast<uint32_t
>( from < to ? to : from );
4061 uint32_t slot = ( ( keyLow * 0x9e3779b1u ) ^ ( keyHigh * 0x85ebca6bu ) ) & tableMask;
4062 bool handled =
false;
4064 while( slotEdge[slot] != -1 )
4066 int other = slotEdge[slot];
4067 int otherFrom = heVertex[other];
4068 int otherTo = heVertex[nextInTriangle( other )];
4069 uint32_t otherLow =
static_cast<uint32_t
>( otherFrom < otherTo ? otherFrom : otherTo );
4070 uint32_t otherHigh =
static_cast<uint32_t
>( otherFrom < otherTo ? otherTo : otherFrom );
4072 if( otherLow == keyLow && otherHigh == keyHigh )
4078 else if( twin[other] == -1 )
4083 toVisit.push_back( other );
4088 int mate = twin[other];
4098 slot = ( slot + 1 ) & tableMask;
4102 slotEdge[slot] = edge;
4105 while( !toVisit.empty() )
4107 int edge = toVisit.back();
4111 int twinEdge = twin[edge];
4113 if( twinEdge == -1 )
4116 int tri = edge - edge % 3;
4117 int twinTri = twinEdge - twinEdge % 3;
4119 int apexAEdge = tri + ( edge + 2 ) % 3;
4120 int sharedEndEdge = tri + ( edge + 1 ) % 3;
4121 int apexBEdge = twinTri + ( twinEdge + 2 ) % 3;
4122 int twinSharedEdge = twinTri + ( twinEdge + 1 ) % 3;
4124 int apexA = heVertex[apexAEdge];
4125 int sharedFrom = heVertex[edge];
4126 int sharedTo = heVertex[sharedEndEdge];
4127 int apexB = heVertex[apexBEdge];
4149 if( legal && curSlivers == 0 )
4155 bool doFlip = ( flipSlivers != curSlivers ) ? ( flipSlivers < curSlivers ) : !legal;
4160 heVertex[edge] = apexB;
4161 heVertex[twinEdge] = apexA;
4163 int apexBOuterTwin = twin[apexBEdge];
4164 int apexAOuterTwin = twin[apexAEdge];
4166 twin[edge] = apexBOuterTwin;
4168 if( apexBOuterTwin != -1 )
4169 twin[apexBOuterTwin] = edge;
4171 twin[twinEdge] = apexAOuterTwin;
4173 if( apexAOuterTwin != -1 )
4174 twin[apexAOuterTwin] = twinEdge;
4176 twin[apexAEdge] = apexBEdge;
4177 twin[apexBEdge] = apexAEdge;
4180 for(
int outer : { edge, twinEdge, sharedEndEdge, twinSharedEdge } )
4182 if( twin[outer] != -1 && !queued[outer] )
4185 toVisit.push_back( outer );
4190 std::deque<TRI> refined;
4192 for(
size_t i = 0; i < triCount; i++ )
4193 refined.emplace_back( heVertex[3 * i + 0], heVertex[3 * i + 1], heVertex[3 * i + 2],
this );
4216 for(
int i = 0; i <
path.PointCount(); i++ )
4220 vec.
x = ( pt.
x - aCenter.
x ) * aScaleFactorX;
4221 vec.
y = ( pt.
y - aCenter.
y ) * aScaleFactorY;
4224 path.SetPoint( i, pt );
4238 Clipper2Lib::Clipper64 clipper;
4239 Clipper2Lib::PolyTree64 tree;
4240 Clipper2Lib::Paths64 paths;
4244 Clipper2Lib::Path64 lc;
4245 lc.reserve(
path.PointCount() );
4247 for(
int i = 0; i <
path.PointCount(); i++ )
4248 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
4250 paths.push_back( std::move( lc ) );
4253 clipper.AddSubject( paths );
4254 clipper.Execute( Clipper2Lib::ClipType::Union, aEvenOdd ? Clipper2Lib::FillRule::EvenOdd
4255 : Clipper2Lib::FillRule::NonZero, tree );
4257 std::vector<CLIPPER_Z_VALUE> zValues;
4258 std::vector<SHAPE_ARC> arcBuffer;
4278 int aSpacing,
int aLineLength )
const
4280 std::vector<SEG> hatchLines;
4293 if( iterator->x < min_x )
4294 min_x = iterator->x;
4296 if( iterator->x > max_x )
4297 max_x = iterator->x;
4299 if( iterator->y < min_y )
4300 min_y = iterator->y;
4302 if( iterator->y > max_y )
4303 max_y = iterator->y;
4306 auto sortEndsByDescendingX =
4309 return tst.x < ref.
x;
4312 for(
double slope : aSlopes )
4314 int64_t max_a, min_a;
4327 min_a = ( min_a / aSpacing ) * aSpacing;
4330 std::vector<VECTOR2I> pointbuffer;
4331 pointbuffer.reserve( 256 );
4333 for( int64_t a = min_a; a < max_a; a += aSpacing )
4335 pointbuffer.clear();
4340 const SEG seg = *iterator;
4346 if( pt.
x < min_x || pt.
x > max_x || pt.
y < min_y || pt.
y > max_y )
4357 if( pointbuffer.size() > 2 )
4358 sort( pointbuffer.begin(), pointbuffer.end(), sortEndsByDescendingX );
4361 for(
size_t ip = 0; ip + 1 < pointbuffer.size(); ip++ )
4363 const VECTOR2I& p1 = pointbuffer[ip];
4364 const VECTOR2I& p2 = pointbuffer[ip + 1];
4370 SEG candidate( p1, p2 );
4372 VECTOR2I mid( ( candidate.
A.
x + candidate.
B.
x ) / 2, ( candidate.
A.
y + candidate.
B.
y ) / 2 );
4377 int dx = p2.
x - p1.
x;
4381 if( aLineLength == -1 ||
std::abs( dx ) < 2 * aLineLength )
4383 hatchLines.emplace_back( candidate );
4387 double dy = p2.
y - p1.
y;
4397 int y1 =
KiROUND( p1.
y + dx * slope );
4398 int y2 =
KiROUND( p2.
y - dx * slope );
4400 hatchLines.emplace_back(
SEG( p1.
x, p1.
y, x1, y1 ) );
4402 hatchLines.emplace_back(
SEG( p2.
x, p2.
y, x2, y2 ) );
bool operator==(const wxAuiPaneInfo &aLhs, const wxAuiPaneInfo &aRhs)
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr coord_type GetLeft() const
constexpr coord_type GetRight() const
constexpr coord_type GetTop() const
constexpr coord_type GetBottom() const
void InsertBridges(Index aFirst)
void insert(uint32_t aEdge, uint32_t aHead)
std::vector< NODE > m_nodes
std::vector< uint32_t > m_bucketIds
FractureEdge::Index Index
void Query(int aY, Index aProvokingIndex, Visitor &&aVisitor) const
std::vector< uint32_t > m_longIds
std::vector< uint32_t > m_offsets
static void logAccepted(size_t aEdges, size_t aHoles, uint32_t aStripes, size_t aBytes)
std::pair< uint32_t, uint32_t > span(const FractureEdge &aEdge) const
FRACTURE_EDGE_INDEX(FractureEdgeSet &aEdges, Originals &&aOriginals, int aMinY, int aMaxY, uint32_t aStripeCount, size_t aHoleCount)
uint32_t map(int aY) const
static constexpr uint32_t INVALID
void visitOverflow(uint32_t aNode, Index aProvokingIndex, Visitor &&aVisitor) const
FractureEdgeSet & m_edges
std::vector< uint32_t > m_heads
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_POLY_SET::POLYGON &aPolygon, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
Triangulate a polygon with holes by bridging holes directly into the outer ring's VERTEX linked list,...
std::vector< SHAPE_LINE_CHAIN > partitionPolygonBalanced(const SHAPE_LINE_CHAIN &aPoly, size_t aTargetLeaves) const
size_t suggestedPartitionLeafCount(const SHAPE_LINE_CHAIN &aPoly) const
Immutable owning spatial snapshot of straight segments.
ecoord SquaredDistance(const SEG &aSeg) const
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
VECTOR2I::extended_type ecoord
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
static SEG::ecoord Square(int a)
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
SHAPE_TYPE Type() const
Return the type of the shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
void GenerateBBoxCache() const
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void ReservePoints(size_t aSize)
Allocate a number of points all at once (for performance).
void Clear()
Remove all points from the line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
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.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
const std::vector< VECTOR2I > & CPoints() const
bool IsEndContour() const
void Refine()
Refine this triangulation in place with boundary-preserving Lawson edge flips, minimizing the number ...
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)
std::mutex m_triangulationMutex
virtual bool HasIndexableSubshapes() const override
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
void RemoveAllContours()
Remove all outlines & holes (clears) the polygon set.
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
void RemoveOutline(int aOutlineIdx)
Delete the aOutlineIdx-th outline of the set including its contours and holes.
void Scale(double aScaleFactorX, double aScaleFactorY, const VECTOR2I &aCenter)
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
virtual void GetIndexableSubshapes(std::vector< const SHAPE * > &aSubshapes) const override
void BooleanXor(const SHAPE_POLY_SET &b)
Perform boolean polyset exclusive or.
ITERATOR_TEMPLATE< VECTOR2I > ITERATOR
void fractureSingle(POLYGON &paths)
bool HasHoles() const
Return true if the polygon set has any holes.
void cacheTriangulation(bool aSimplify, std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > *aHintData, const TASK_SUBMITTER &aSubmitter={}, bool aBuildIndexes=false)
CONST_ITERATOR CIterateWithHoles() const
void BooleanAdd(const SHAPE_POLY_SET &b)
Perform boolean polyset union.
ITERATOR IterateWithHoles()
void ClearArcs()
Removes all arc references from all the outlines and holes in the polyset.
bool IsTriangulationUpToDate() const
void importPaths(Clipper2Lib::Paths64 &paths, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
std::atomic< bool > m_failedHashValid
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of vertices in a given outline/hole.
void DeletePolygon(int aIdx)
Delete aIdx-th polygon from the set.
void splitCollinearOutlines()
double Area()
Return the area of this poly set.
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
virtual void CacheTriangulation(bool aSimplify=false, const TASK_SUBMITTER &aSubmitter={}, bool aBuildIndexes=false)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
void BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Return total number of vertices stored in the set.
POLYGON & Polygon(int aIndex)
Return the aIndex-th subpolygon in the set.
int FullPointCount() const
Return the number of points in the shape poly set.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Appends all the arcs in this polyset to aArcBuffer.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
static bool appendBridgeFreePaths(const SHAPE_LINE_CHAIN &aChain, Clipper2Lib::Paths64 &aPaths, std::vector< CLIPPER_Z_VALUE > &aZValues, std::vector< SHAPE_ARC > &aArcBuffer)
Append the rings left after cutting the fracture bridges out of aChain.
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
void unfractureSingle(POLYGON &path)
void inflateLine2(const SHAPE_LINE_CHAIN &aLine, int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify=false)
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
HASH_128 checksum() const
void Inflate(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify=false)
Perform outline inflation/deflation.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
int AddPolygon(const POLYGON &apolygon)
Adds a polygon to the set.
const std::vector< SEG > GenerateHatchLines(const std::vector< double > &aSlopes, int aSpacing, int aLineLength) const
const std::string Format(bool aCplusPlus=true) const override
void Simplify()
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections)
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
ITERATOR_TEMPLATE< const VECTOR2I > CONST_ITERATOR
void inflate2(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy, bool aSimplify=false)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index.
SEG::ecoord SquaredDistance(const VECTOR2I &aPoint, bool aOutlineOnly, VECTOR2I *aNearest) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void Unfracture()
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int ArcCount() const
Count the number of arc shapes present.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext) const
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
std::unique_ptr< TRIANGULATION_INDEX > m_triIndex
One index over every triangle of every polygon above.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the reference to aHole-th hole in the aIndex-th outline.
int NewOutline()
Creates a new empty polygon in the set and returns its index.
void SimplifyOutlines(int aMaxError=0)
Simplifies the lines in the polyset.
void booleanOp(Clipper2Lib::ClipType aType, const SHAPE_POLY_SET &aOtherShape)
This is the engine to execute all polygon boolean transforms (AND, OR, ... and polygon simplification...
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool hasTouchingHoles(const POLYGON &aPoly) const
Return true if the polygon set has any holes that touch share a vertex.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
std::atomic< bool > m_hashValid
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX *aClosestVertex=nullptr, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
void DeletePolygonAndTriangulationData(int aIdx, bool aUpdateHash=true)
Delete aIdx-th polygon and its triangulation data from the set.
unsigned int TriangulatedPolyCount() const
Return the number of triangulated polygons.
std::atomic< bool > m_triangulationValid
void UpdateTriangulationDataHash()
void BooleanIntersection(const SHAPE_POLY_SET &b)
Perform boolean polyset intersection.
int NewHole(int aOutline=-1)
Creates a new hole in a given outline.
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
virtual size_t GetIndexableSubshapeCount() const override
SEG::ecoord SquaredDistanceToSeg(const SEG &aSegment, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aSegment and all the polygons in the set.
void importPolyPath(const std::unique_ptr< Clipper2Lib::PolyPath64 > &aPolyPath, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffer)
void RebuildHolesFromContours()
Extract all contours from this polygon set, then recreate polygons with holes.
void Mirror(const VECTOR2I &aRef, FLIP_DIRECTION aFlipDirection)
Mirror the line points about y or x (or both)
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
std::vector< POLYGON > m_polys
void splitSelfTouchingOutlines()
Split outline segments at vertices that lie on them (self-touching polygons).
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the index-th vertex in a given hole outline within a given outline.
int OutlineCount() const
Return the number of outlines in the set.
void InflateWithLinkedHoles(int aFactor, CORNER_STRATEGY aCornerStrategy, int aMaxError)
Perform outline inflation/deflation, using round corners.
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
void Move(const VECTOR2I &aVector) override
bool HasTouchingHoles() const
Return true if the polygon set has any holes that share a vertex.
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
void Fracture(bool aSimplify=true)
Convert a set of polygons with holes to a single outline with "slits"/"fractures" connecting the oute...
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &aOther)
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
SHAPE_POLY_SET CloneDropTriangulation() const
bool isExteriorWaist(const SEG &aSegA, const SEG &aSegB) const
Check if two line segments are collinear and overlap.
void BooleanSubtract(const SHAPE_POLY_SET &b)
Perform boolean polyset difference.
const POLYGON & CPolygon(int aIndex) const
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
std::function< void(std::function< void()>)> TASK_SUBMITTER
Callback that submits a unit of work for asynchronous execution.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
const BOX2I BBoxFromCaches() const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
void importTree(Clipper2Lib::PolyTree64 &tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
SEGMENT_ITERATOR_TEMPLATE< const SEG > CONST_SEGMENT_ITERATOR
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
const SEG & GetSeg() const
int GetWidth() const override
VECTOR2I::extended_type ecoord
SHAPE(SHAPE_TYPE aType)
Create an empty shape of type aType.
static constexpr extended_type ECOORD_MAX
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
CORNER_STRATEGY
define how inflate transform build inflated polygon
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
@ ROUND_ALL_CORNERS
All angles are rounded.
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
static bool empty(const wxTextEntryBase *aCtrl)
static constexpr EDA_ANGLE FULL_CIRCLE
Exact orientation and in-circle predicates over integer coordinates.
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.
std::pair< uint32_t, uint32_t > StripeSpan(int aY1, int aY2, int aMinY, int aMaxY, uint32_t aStripeCount)
bool ActualCapacityFits(size_t aBucketIds, size_t aLongIds, size_t aOffsets, size_t aScratch, size_t aHeads, size_t aNodes, size_t aNodeSize, size_t aBudget, size_t *aBytes=nullptr)
bool ShouldIndex(uint64_t aEstimatedVisits, size_t aHoleCount)
bool CapacityFits(size_t aBucketIds, size_t aLongIds, size_t aStripeCount, size_t aHoleCount, size_t aNodeSize, size_t aBudget)
uint32_t MapYToStripe(int aY, int aMinY, int aMaxY, uint32_t aStripeCount)
constexpr uint32_t MAX_BUCKET_SPAN
uint32_t StripeCountFor(size_t aEdgeCount)
Construction helpers for the interactive arc drawing modes.
int OrientationSign(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c)
Orientation of triangle (a, b, c): +1 counter-clockwise, -1 clockwise, 0 collinear.
bool InCircleDelaunayLegal(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c, const VECTOR2I &p)
True when p is outside the circumcircle of CCW triangle (a, b, c): the shared edge is already Delauna...
bool IsSliverTriangle(const VECTOR2I &a, const VECTOR2I &b, const VECTOR2I &c)
A triangle is a sliver when its longest edge exceeds ten times its shortest.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
static PGM_BASE * process
#define TRIANGULATE_TRACE
#define TRIANGULATESIMPLIFICATIONLEVEL
@ SH_POLY_SET
set of polygons (with holes, etc.)
static void fractureSingleCacheFriendly(SHAPE_POLY_SET::POLYGON &paths)
static constexpr int RTREE_THRESHOLD
static void fractureSingleSlow(SHAPE_POLY_SET::POLYGON &paths)
static int fractureIntersectX(const FractureEdge &aEdge, int aY)
std::vector< FractureEdge > FractureEdgeSet
std::vector< FractureEdgeSlow * > FractureEdgeSetSlow
#define ENABLEFRACTUREEDGEINDEX
static bool splitAtBridges(const SHAPE_LINE_CHAIN &aChain, std::vector< SHAPE_LINE_CHAIN > &aRings)
Split a closed ring into the rings left once pairs of coincident opposite edges are removed.
#define ENABLECACHEFRIENDLYFRACTURE
static FractureEdge * processHole(FractureEdgeSet &edges, FractureEdge::Index provokingIndex, FractureEdge::Index edgeIndex, FractureEdge::Index bridgeIndex, FRACTURE_EDGE_INDEX *aIndex)
static int processEdge(FractureEdgeSetSlow &edges, FractureEdgeSlow *edge)
bool AnyTriangleHit(const TRIANGULATION_INDEX *aIndex, const std::vector< std::unique_ptr< SHAPE_POLY_SET::TRIANGULATED_POLYGON > > &aPolys, const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr)
Return true if any candidate triangle collides with aShape within aClearance.
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
FractureEdgeSlow(int y=0)
FractureEdgeSlow * m_next
bool matches(int y) const
FractureEdgeSlow(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
FractureEdge(const VECTOR2I &p1, const VECTOR2I &p2, Index next)
bool matches(int y) const
A storage class for 128-bit hash value.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
TRIANGULATED_POLYGON * parent
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
wxString result
Test unit parsing edge cases and error handling.
constexpr int sign(T val)
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I
VECTOR2< double > VECTOR2D
static PIECE polygon(std::vector< VIA_CROSS_SECTION_GEOMETRY::POINT > aPoints, bool aMixed=false)