41 #include <type_traits> 42 #include <unordered_set> 45 #include <clipper.hpp> 89 m_polys( aOther.m_polys )
126 unsigned int contourIdx = 0;
129 int currentGlobalIdx = 0;
131 for( polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
135 for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
138 int totalPoints = currentContour.
PointCount();
140 for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
143 if( currentGlobalIdx == aGlobalIdx )
145 aRelativeIndices->
m_polygon = polygonIdx;
146 aRelativeIndices->
m_contour = contourIdx;
147 aRelativeIndices->
m_vertex = vertexIdx;
163 int& aGlobalIdx )
const 165 int selectedVertex = aRelativeIndices.
m_vertex;
166 unsigned int selectedContour = aRelativeIndices.
m_contour;
167 unsigned int selectedPolygon = aRelativeIndices.
m_polygon;
170 if( selectedPolygon <
m_polys.size() && selectedContour <
m_polys[selectedPolygon].size()
171 && selectedVertex <
m_polys[selectedPolygon][selectedContour].PointCount() )
177 for(
unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
179 currentPolygon =
Polygon( polygonIdx );
181 for(
unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
182 aGlobalIdx += currentPolygon[contourIdx].PointCount();
185 currentPolygon =
Polygon( selectedPolygon );
187 for(
unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
188 aGlobalIdx += currentPolygon[contourIdx].PointCount();
190 aGlobalIdx += selectedVertex;
207 poly.push_back( empty_path );
224 m_polys[aOutline].push_back( empty_path );
226 return m_polys.back().size() - 2;
244 assert( aOutline < (
int)
m_polys.size() );
245 assert( idx < (
int)
m_polys[aOutline].size() );
247 m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
249 return m_polys[aOutline][idx].PointCount();
267 assert( aOutline < (
int)
m_polys.size() );
268 assert( idx < (
int)
m_polys[aOutline].size() );
270 m_polys[aOutline][idx].Append( aArc );
272 return m_polys[aOutline][idx].PointCount();
280 if( aGlobalIndex < 0 )
293 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
313 if( aOutline >= (
int)
m_polys.size() )
316 if( idx >= (
int)
m_polys[aOutline].size() )
319 return m_polys[aOutline][idx].PointCount();
334 for(
int idx = 0; idx <=
HoleCount( ii ); idx++ )
336 full_count +=
m_polys[ii][idx].PointCount();
346 assert( aFirstPolygon >= 0 && aLastPolygon <=
OutlineCount() );
350 for(
int index = aFirstPolygon; index < aLastPolygon; index++ )
369 assert( aOutline < (
int)
m_polys.size() );
370 assert( idx < (
int)
m_polys[aOutline].size() );
372 return m_polys[aOutline][idx].CPoint( aIndex );
382 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
412 else if( index.
m_vertex == lastpoint )
427 *aPrevious = previous;
448 SEG firstSegment = *iterator;
451 innerIterator = iterator;
454 for( innerIterator++; innerIterator; innerIterator++ )
456 SEG secondSegment = *innerIterator;
459 if( !iterator.
IsAdjacent( innerIterator ) && firstSegment.
Collide( secondSegment, 0 ) )
470 for(
unsigned int polygon = 0; polygon <
m_polys.size(); polygon++ )
486 poly.push_back( aOutline );
501 assert( aOutline < (
int)
m_polys.size() );
505 assert( poly.size() );
507 poly.push_back( aHole );
509 return poly.size() - 2;
521 for(
int j = 0; j <
HoleCount( i ); j++ )
535 for(
size_t i = 0; i < poly.size(); i++ )
547 for(
size_t i = 0; i < poly.size(); i++ )
550 aArcBuffer.push_back( arc );
560 for(
size_t i = 0; i < poly.size(); i++ )
569 booleanOp( aType, *
this, aOtherShape, aFastMode );
579 wxFAIL_MSG( wxT(
"Boolean ops on curved polygons are not supported. You should call " 580 "ClearArcs() before carrying out the boolean operation." ) );
583 ClipperLib::Clipper c;
587 std::vector<CLIPPER_Z_VALUE> zValues;
588 std::vector<SHAPE_ARC> arcBuffer;
589 std::map<VECTOR2I, CLIPPER_Z_VALUE> newIntersectPoints;
593 for(
size_t i = 0; i < poly.size(); i++ )
595 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
596 ClipperLib::ptSubject,
true );
602 for(
size_t i = 0; i < poly.size(); i++ )
604 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
605 ClipperLib::ptClip,
true );
609 ClipperLib::PolyTree solution;
611 ClipperLib::ZFillCallback callback =
612 [&]( ClipperLib::IntPoint & e1bot, ClipperLib::IntPoint & e1top,
613 ClipperLib::IntPoint & e2bot, ClipperLib::IntPoint & e2top,
614 ClipperLib::IntPoint & pt )
617 [&](
const ssize_t& aZvalue,
const ssize_t& aCompareVal = -1 ) -> ssize_t
621 retval = zValues.at( aZvalue ).m_SecondArcIdx;
623 if( retval == -1 || ( aCompareVal > 0 && retval != aCompareVal ) )
624 retval = zValues.at( aZvalue ).m_FirstArcIdx;
630 [&](
const ssize_t& aBottomZ,
const ssize_t aTopZ ) -> ssize_t
632 ssize_t retval = arcIndex( aBottomZ );
636 if( retval != arcIndex( aTopZ, retval ) )
643 ssize_t e1ArcSegmentIndex = arcSegment( e1bot.Z, e1top.Z );
644 ssize_t e2ArcSegmentIndex = arcSegment( e2bot.Z, e2top.Z );
648 if( e1ArcSegmentIndex != -1 )
659 size_t z_value_ptr = zValues.size();
660 zValues.push_back( newZval );
664 newIntersectPoints.insert( {
VECTOR2I( pt.X, pt.Y ), newZval } );
670 c.ZFillFunction( callback );
672 c.Execute( aType, solution, ClipperLib::pftNonZero, ClipperLib::pftNonZero );
680 booleanOp( ClipperLib::ctUnion, b, aFastMode );
686 booleanOp( ClipperLib::ctDifference, b, aFastMode );
692 booleanOp( ClipperLib::ctIntersection, b, aFastMode );
699 booleanOp( ClipperLib::ctUnion, a, b, aFastMode );
706 booleanOp( ClipperLib::ctDifference, a, b, aFastMode );
713 booleanOp( ClipperLib::ctIntersection, a, b, aFastMode );
721 Inflate( aFactor, aCircleSegmentsCount );
728 using namespace ClipperLib;
732 #define SEG_CNT_MAX 64 733 static double arc_tolerance_factor[
SEG_CNT_MAX + 1];
740 JoinType joinType = jtRound;
741 double miterLimit = 2.0;
742 JoinType miterFallback = jtSquare;
744 switch( aCornerStrategy )
749 miterFallback = jtSquare;
754 miterFallback = jtRound;
759 miterFallback = jtSquare;
764 miterFallback = jtSquare;
769 miterFallback = jtSquare;
773 std::vector<CLIPPER_Z_VALUE> zValues;
774 std::vector<SHAPE_ARC> arcBuffer;
778 for(
size_t i = 0; i < poly.size(); i++ )
780 c.AddPath( poly[i].convertToClipper( i == 0, zValues, arcBuffer ),
781 joinType, etClosedPolygon );
791 if( aCircleSegCount < 6 )
796 if( aCircleSegCount >
SEG_CNT_MAX || arc_tolerance_factor[aCircleSegCount] == 0 )
798 coeff = 1.0 - cos( M_PI / aCircleSegCount );
801 arc_tolerance_factor[aCircleSegCount] = coeff;
805 coeff = arc_tolerance_factor[aCircleSegCount];
808 c.ArcTolerance = std::abs( aAmount ) * coeff;
809 c.MiterLimit = miterLimit;
810 c.MiterFallback = miterFallback;
811 c.Execute( solution, aAmount );
818 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
819 const std::vector<SHAPE_ARC>& aArcBuffer )
823 for( ClipperLib::PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
828 paths.reserve( n->Childs.size() + 1 );
830 paths.emplace_back( n->Contour, aZValueBuffer, aArcBuffer );
832 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
833 paths.emplace_back( n->Childs[i]->Contour, aZValueBuffer, aArcBuffer );
844 m_connected( false ),
851 m_connected( connected ),
860 return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
875 int x = edge->
m_p1.
x;
876 int y = edge->
m_p1.
y;
877 int min_dist = std::numeric_limits<int>::max();
884 if( !e->matches( y ) )
889 if( e->m_p1.y == e->m_p2.y )
891 x_intersect = std::max( e->m_p1.x, e->m_p2.x );
895 x_intersect = e->m_p1.x +
rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
896 e->m_p2.y - e->m_p1.y );
899 int dist = ( x - x_intersect );
901 if( dist >= 0 && dist < min_dist && e->m_connected )
904 x_nearest = x_intersect;
917 edges.push_back( split_2 );
918 edges.push_back( lead1 );
919 edges.push_back( lead2 );
924 e_nearest->
m_next = lead1;
929 for( last = edge; last->
m_next != edge; last = last->
m_next )
955 if( paths.size() == 1 )
958 int num_unconnected = 0;
962 const std::vector<VECTOR2I>& points =
path.CPoints();
963 int pointCount = points.size();
967 int x_min = std::numeric_limits<int>::max();
969 for(
int i = 0; i < pointCount; i++ )
971 if( points[i].x < x_min )
977 points[ i+1 == pointCount ? 0 : i+1 ] );
988 if( i == pointCount - 1 )
992 edges.push_back( fe );
996 if( fe->
m_p1.
x == x_min )
997 border_edges.push_back( fe );
1008 while( num_unconnected > 0 )
1010 int x_min = std::numeric_limits<int>::max();
1011 auto it = border_edges.begin();
1016 for( ; it != border_edges.end(); ++it )
1019 int xt = border_edge->
m_p1.
x;
1021 if( ( xt <= x_min ) && !border_edge->
m_connected )
1024 smallestX = border_edge;
1028 int num_processed =
processEdge( edges, smallestX );
1031 if( !num_processed )
1033 wxLogWarning( wxT(
"Broken polygon, dropping path" ) );
1041 num_unconnected -= num_processed;
1059 paths.push_back( std::move( newPath ) );
1074 assert( aPoly.size() == 1 );
1080 bool m_duplicate =
false;
1087 bool compareSegs(
const SEG& s1,
const SEG& s2 )
const 1089 return (s1.
A == s2.
B && s1.
B == s2.
A);
1094 return compareSegs( m_poly->
CSegment( m_index ),
1095 aOther.m_poly->CSegment( aOther.m_index ) );
1100 return !compareSegs( m_poly->
CSegment( m_index ),
1101 aOther.m_poly->CSegment( aOther.m_index ) );
1106 std::size_t operator()(
const EDGE& aEdge )
const 1108 const SEG& a = aEdge.m_poly->CSegment( aEdge.m_index );
1110 return (std::size_t) ( a.
A.
x + a.
B.
x + a.
A.
y + a.
B.
y );
1115 struct EDGE_LIST_ENTRY
1118 EDGE_LIST_ENTRY*
next;
1121 std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
1126 auto edgeList = std::make_unique<EDGE_LIST_ENTRY[]>( lc.
SegmentCount() );
1130 edgeList[i].index = i;
1131 edgeList[i].next = &edgeList[ (i != lc.
SegmentCount() - 1) ? i + 1 : 0 ];
1134 std::unordered_set<EDGE_LIST_ENTRY*> queue;
1139 uniqueEdges.insert( e );
1145 auto it = uniqueEdges.find( e );
1147 if( it != uniqueEdges.end() && it->m_index != i )
1149 int e1 = it->m_index;
1153 std::swap( e1, e2 );
1155 int e1_prev = e1 - 1;
1160 int e2_prev = e2 - 1;
1165 int e1_next = e1 + 1;
1170 int e2_next = e2 + 1;
1175 edgeList[e1_prev].next = &edgeList[ e2_next ];
1176 edgeList[e2_prev].next = &edgeList[ e1_next ];
1177 edgeList[i].next =
nullptr;
1178 edgeList[it->m_index].next =
nullptr;
1184 if( edgeList[i].
next )
1185 queue.insert( &edgeList[i] );
1188 auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.
SegmentCount() );
1194 double max_poly = 0.0;
1196 while( queue.size() )
1198 EDGE_LIST_ENTRY* e_first = *queue.begin();
1199 EDGE_LIST_ENTRY* e = e_first;
1206 }
while( e && e != e_first );
1210 for(
int i = 0; i < cnt; i++ )
1214 queue.erase( edgeBuf[i] );
1219 double area = std::fabs( outl.
Area() );
1221 if( area > max_poly )
1227 result.push_back( outl );
1232 std::swap( result[0], result[outline] );
1244 if( paths.size() > 1 )
1282 while( outline.size() > 1 )
1305 std::stringstream ss;
1307 ss <<
"SHAPE_LINE_CHAIN poly; \n";
1309 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1311 for(
unsigned j = 0; j <
m_polys[i].size(); j++ )
1314 ss <<
"{ auto tmp = " <<
m_polys[i][j].Format() <<
";\n";
1320 ss <<
" poly.AddOutline(tmp); } \n";
1324 ss <<
" poly.AddHole(tmp); } \n";
1340 if( tmp !=
"polyset" )
1345 int n_polys = atoi( tmp.c_str() );
1350 for(
int i = 0; i < n_polys; i++ )
1360 int n_outlines = atoi( tmp.c_str() );
1362 if( n_outlines < 0 )
1365 for(
int j = 0; j < n_outlines; j++ )
1372 int n_vertices = atoi( tmp.c_str() );
1374 for(
int v = 0; v < n_vertices; v++ )
1378 aStream >> tmp; p.
x = atoi( tmp.c_str() );
1379 aStream >> tmp; p.
y = atoi( tmp.c_str() );
1383 paths.push_back( outline );
1397 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1414 for(
unsigned i = 0; i <
m_polys.size(); i++ )
1417 bb = *
m_polys[i][0].GetCachedBBox();
1434 if( lineChain.PointOnEdge( aP ) )
1449 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
1452 *aLocation = nearest;
1455 *aActual = sqrt( dist_sq );
1473 if( dist_sq == 0 || dist_sq <
SEG::Square( aClearance ) )
1476 *aLocation = nearest;
1479 *aActual = sqrt( dist_sq );
1495 const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1496 int extra = segment->
GetWidth() / 2;
1498 if(
Collide( segment->
GetSeg(), aClearance + extra, aActual, aLocation ) )
1501 *aActual = std::max( 0, *aActual - extra );
1511 const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1514 if(
Collide( circle->
GetCenter(), aClearance + extra, aActual, aLocation ) )
1517 *aActual = std::max( 0, *aActual - extra );
1525 const_cast<SHAPE_POLY_SET*>(
this )->CacheTriangulation(
false );
1527 int actual = INT_MAX;
1534 if( aActual || aLocation )
1539 if( aShape->
Collide( &tri, aClearance, &triActual, &triLocation ) )
1541 if( triActual < actual )
1544 location = triLocation;
1550 if( aShape->
Collide( &tri, aClearance ) )
1556 if( actual < INT_MAX )
1559 *aActual = std::max( 0, actual );
1562 *aLocation = location;
1580 if( aPolygonIdx < 0 )
1581 aPolygonIdx +=
m_polys.size();
1583 m_polys[aPolygonIdx].erase(
m_polys[aPolygonIdx].begin() + aContourIdx );
1601 segmentStart = *iterator;
1607 segmentEnd = contourStart;
1613 contourStart = *iterator;
1621 segmentEnd = *iterator;
1625 if( segmentStart == segmentEnd )
1654 Append( aP.
x, aP.
y, aOutline, aHole );
1660 int aClearance )
const 1663 bool collision =
false;
1670 clearance = aClearance;
1675 delta = *iterator - aPoint;
1689 aClosestVertex = iterator.GetIndex();
1699 int aClearance )
const 1702 bool collision =
false;
1706 const SEG currentSegment = *iterator;
1718 aClosestVertex = iterator.GetIndex();
1728 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
1732 for(
int holeIdx = 0; holeIdx <
HoleCount( polygonIdx ); holeIdx++ )
1739 bool aUseBBoxCaches )
const 1745 if( aSubpolyIndex >= 0 )
1746 return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1749 for(
int polygonIdx = 0; polygonIdx <
OutlineCount(); polygonIdx++ )
1751 if(
containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1767 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
1784 throw( std::out_of_range(
"aGlobalIndex-th vertex does not exist" ) );
1795 bool aUseBBoxCaches )
const 1798 if(
m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1801 for(
int holeIdx = 0; holeIdx <
HoleCount( aSubpolyIndex ); holeIdx++ )
1823 path.Move( aVector );
1827 tri->Move( aVector );
1838 path.Mirror( aX, aY, aRef );
1851 path.Rotate( aAngle, aCenter );
1867 c +=
path.PointCount();
1904 SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1906 for( iterator++; iterator && minDistance > 0; iterator++ )
1908 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1910 if( currentDistance < minDistance )
1913 *aNearest = (*iterator).NearestPoint( aPoint );
1915 minDistance = currentDistance;
1931 *aNearest = ( aSegment.
A + aSegment.
B ) / 2;
1937 SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1939 if( aNearest && minDistance == 0 )
1940 *aNearest = ( *iterator ).NearestPoint( aSegment );
1942 for( iterator++; iterator && minDistance > 0; iterator++ )
1944 SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1946 if( currentDistance < minDistance )
1949 *aNearest = (*iterator).NearestPoint( aSegment );
1951 minDistance = currentDistance;
1956 return minDistance < 0 ? 0 : minDistance;
1967 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
1970 aNearest ? &nearest :
nullptr );
1972 if( currentDistance_sq < minDistance_sq )
1975 *aNearest = nearest;
1977 minDistance_sq = currentDistance_sq;
1981 return minDistance_sq;
1992 for(
unsigned int polygonIdx = 0; polygonIdx <
m_polys.size(); polygonIdx++ )
1995 aNearest ? &nearest :
nullptr );
1997 if( currentDistance_sq < minDistance_sq )
2000 *aNearest = nearest;
2002 minDistance_sq = currentDistance_sq;
2006 return minDistance_sq;
2027 for(
unsigned int idx = 0; idx <
m_polys.size(); idx++ )
2038 for(
size_t idx = 0; idx <
m_polys.size(); idx++ )
2046 unsigned int aDistance,
2047 int aIndex,
int aErrorMax )
2056 if( aDistance == 0 )
2068 for(
int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
2071 int x1 = currContour.
CPoint( currVertex ).
x;
2072 int y1 = currContour.CPoint( currVertex ).y;
2081 prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
2084 nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
2087 double xa = currContour.CPoint( prevVertex ).x - x1;
2088 double ya = currContour.CPoint( prevVertex ).y - y1;
2091 double xb = currContour.CPoint( nextVertex ).x - x1;
2092 double yb = currContour.CPoint( nextVertex ).y - y1;
2095 double lena = hypot( xa, ya );
2096 double lenb = hypot( xb, yb );
2099 if( aMode == CORNER_MODE::CHAMFERED )
2113 newContour.
Append( x1 + nx1, y1 + ny1 );
2118 newContour.
Append( x1 + nx2, y1 + ny2 );
2122 double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
2124 double radius = aDistance;
2125 double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
2128 if( std::isinf( denom ) )
2132 if( 0.5 * lena * denom < radius )
2133 radius = 0.5 * lena * denom;
2135 if( 0.5 * lenb * denom < radius )
2136 radius = 0.5 * lenb * denom;
2139 double k = radius / sqrt( .5 * ( 1 - cosine ) );
2140 double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
2141 ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
2142 double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
2143 double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
2146 k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
2147 double xs = x1 + k * xa / lena - xc;
2148 double ys = y1 + k * ya / lena - yc;
2149 double xe = x1 + k * xb / lenb - xc;
2150 double ye = y1 + k * yb / lenb - yc;
2153 double argument = ( xs * xe + ys * ye ) / ( radius * radius );
2159 else if( argument > 1 )
2162 double arcAngle = acos( argument );
2163 double arcAngleDegrees = arcAngle * 180.0 / M_PI;
2166 double deltaAngle = arcAngle / segments;
2167 double startAngle = atan2( -ys, xs );
2170 if( xa * yb - ya * xb <= 0 )
2173 double nx = xc + xs;
2174 double ny = yc + ys;
2182 for(
int j = 0; j < segments; j++ )
2184 nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2185 ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
2200 newPoly.push_back( newContour );
2209 static_cast<SHAPE&>(*
this) = aOther;
2261 if( w == 0.0 || h == 0.0 )
2264 int n_cells_x, n_cells_y;
2268 n_cells_x = w / aSize;
2269 n_cells_y = floor( h / w * n_cells_x ) + 1;
2273 n_cells_y = h / aSize;
2274 n_cells_x = floor( w / h * n_cells_y ) + 1;
2277 SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2279 for(
int yy = 0; yy < n_cells_y; yy++ )
2281 for(
int xx = 0; xx < n_cells_x; xx++ )
2285 p.
x = bb.
GetX() + w * xx / n_cells_x;
2286 p.
y = bb.
GetY() + h * yy / n_cells_y;
2290 p2.
x = bb.
GetX() + w * ( xx + 1 ) / n_cells_x;
2291 p2.
y = bb.
GetY() + h * ( yy + 1 ) / n_cells_y;
2299 mask.SetClosed(
true );
2301 if( ( xx ^ yy ) & 1 )
2315 for(
int i = 0; i < ps2.OutlineCount(); i++ )
2377 if( !tess.TesselatePolygon( tmpSet.
Polygon( 0 ).front() ) )
2401 hash.
Hash( outline.size() );
2405 hash.
Hash( lc.PointCount() );
2407 for(
int i = 0; i < lc.PointCount(); i++ )
2409 hash.
Hash( lc.CPoint( i ).x );
2410 hash.
Hash( lc.CPoint( i ).y );
2435 std::set<long long> ptHashes;
2439 for(
const VECTOR2I& pt : lc.CPoints() )
2441 const long long ptHash = (
long long) pt.x << 32 | pt.y;
2443 if( ptHashes.count( ptHash ) > 0 )
2446 ptHashes.insert( ptHash );
2465 n += t->GetTriangleCount();
2478 aSubshapes.push_back( &tri );
2485 BOX2I bbox( parent->m_vertices[a] );
2486 bbox.
Merge( parent->m_vertices[b] );
2487 bbox.
Merge( parent->m_vertices[c] );
2489 if( aClearance != 0 )
2498 m_triangles.emplace_back( a, b, c,
this );
2507 for(
TRI& tri : m_triangles )
2517 for(
TRI& tri : m_triangles )
2536 bool aReverseOrientation,
bool aEvenOdd )
2538 ClipperLib::Clipper clipper;
2539 ClipperLib::PolyTree tree;
2545 ClipperLib::Path lc;
2547 for(
int i = 0; i <
path.PointCount(); i++ )
2549 lc.emplace_back(
path.CPoint( i ).x,
path.CPoint( i ).y );
2552 clipper.AddPath( lc, ClipperLib::ptSubject,
true );
2555 clipper.StrictlySimple(
true );
2556 clipper.Execute( ClipperLib::ctUnion, tree,
2557 aEvenOdd ? ClipperLib::pftEvenOdd : ClipperLib::pftNonZero,
2558 ClipperLib::pftNonZero );
2561 for( ClipperLib::PolyNode* n = tree.GetFirst(); n; n = n->GetNext() )
2567 for(
unsigned int i = 0; i < n->Contour.size(); i++ )
2568 result.
Outline( outl ).
Append( n->Contour[i].X, n->Contour[i].Y );
2570 for(
unsigned int i = 0; i < n->Childs.size(); i++ )
2572 int outh = result.
NewHole( outl );
2573 for(
unsigned int j = 0; j < n->Childs[i]->Contour.size(); j++ )
2575 result.
Hole( outl, outh )
2576 .
Append( n->Childs[i]->Contour[j].X, n->Childs[i]->Contour[j].Y );
int TotalVertices() const
Delete aIdx-th polygon from the set.
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
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, ...
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
const POLYGON & CPolygon(int aIndex) const
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Return the number of vertices in a given outline/hole.
All angles are chamfered.
bool IsEndContour() const
void fractureSingle(POLYGON &paths)
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
coord_type GetTop() const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
const BOX2I BBoxFromCaches() const
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the aGlobalIndex-th vertex in the poly set.
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
VECTOR2I::extended_type ecoord
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
bool operator!=(const SYMBOL_LIB &aLibrary, const wxString &aName)
coord_type GetRight() const
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
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.
double Area()
Count the number of arc shapes present.
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
MD5_HASH checksum() const
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
Base class for iterating over all segments in a given SHAPE_POLY_SET.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
const VECTOR2I GetCenter() const
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
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.
double Area(bool aAbsolute=true) const
Return the area of this chain.
coord_type GetBottom() const
bool m_triangulationValid
int PointCount() const
Return the number of points (vertices) in this line chain.
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
static SEG::ecoord Square(int a)
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
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,...
bool IsTriangulationUpToDate() const
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
const SEG & GetSeg() const
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void DeletePolygon(int aIdx)
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
static constexpr extended_type ECOORD_MAX
void Hash(uint8_t *data, uint32_t length)
Acute angles are rounded.
std::deque< TRI > m_triangles
void Move(const VECTOR2I &aVector) override
bool IsClosed() const override
bool operator==(const SYMBOL_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
coord_type GetWidth() const
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
An abstract shape on 2D plane.
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
const std::string Format() const override
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
int NewOutline()
Creates a new hole in a given outline.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Acute angles are chamfered.
int SegmentCount() const
Return the number of segments in this line chain.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
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,...
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
set of polygons (with holes, etc.)
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
void AddTriangle(int a, int b, int c)
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool matches(int y) const
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
ITERATOR IterateWithHoles()
VECTOR2I::extended_type ecoord
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
static bool empty(const wxTextEntryBase *aCtrl)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
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 ...
coord_type GetHeight() const
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void CacheTriangulation(bool aPartition=true)
Build a polygon triangulation, needed to draw a polygon on OpenGL and in some other calculations.
void GenerateBBoxCache() const
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
POLYGON_MODE
Operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
coord_type GetLeft() const
POLYGON & Polygon(int aIndex)
int FullPointCount() const
Returns the number of holes in a given outline.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
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 BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
just inflate the polygon. Acute angles create spikes
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
SHAPE_TYPE Type() const
Return the type of the shape.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
CONST_ITERATOR CIterateWithHoles() const
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
void importTree(ClipperLib::PolyTree *tree, const std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, const std::vector< SHAPE_ARC > &aArcBuffe)
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &aOther)
std::deque< VECTOR2I > m_vertices
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.