33#include <clipper2/clipper.h>
54 for(
size_t i = 0; i < aV.size(); i+= 2 )
75 m_width( aArc.GetWidth() )
83 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
84 const std::vector<SHAPE_ARC>& aArcBuffer ) :
86 m_closed( true ), m_width( 0 )
88 std::map<ssize_t, ssize_t> loadedArcs;
93 [&]( ssize_t aArcIndex ) -> ssize_t
99 else if( loadedArcs.count( aArcIndex ) == 0 )
101 loadedArcs.insert( { aArcIndex,
m_arcs.size() } );
102 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
105 return loadedArcs.at( aArcIndex );
108 for(
size_t ii = 0; ii < aPath.size(); ++ii )
110 Append( aPath[ii].
X, aPath[ii].Y );
112 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
113 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
127 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
128 const std::vector<SHAPE_ARC>& aArcBuffer ) :
130 m_closed( true ), m_width( 0 )
132 std::map<ssize_t, ssize_t> loadedArcs;
137 [&]( ssize_t aArcIndex ) -> ssize_t
143 else if( loadedArcs.count( aArcIndex ) == 0 )
145 loadedArcs.insert( { aArcIndex,
m_arcs.size() } );
146 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
149 return loadedArcs.at( aArcIndex );
152 for(
size_t ii = 0; ii < aPath.size(); ++ii )
154 Append( aPath[ii].x, aPath[ii].y );
156 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
157 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
171 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
172 std::vector<SHAPE_ARC>& aArcBuffer )
const
174 ClipperLib::Path c_path;
176 bool orientation =
Area(
false ) >= 0;
177 ssize_t shape_offset = aArcBuffer.size();
179 if( orientation != aRequiredOrientation )
185 c_path.reserve( pointCount );
187 for(
int i = 0; i < pointCount; i++ )
192 size_t z_value_ptr = aZValueBuffer.size();
193 aZValueBuffer.push_back( z_value );
195 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
198 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
205 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
206 std::vector<SHAPE_ARC>& aArcBuffer )
const
208 Clipper2Lib::Path64 c_path;
210 bool orientation =
Area(
false ) >= 0;
211 ssize_t shape_offset = aArcBuffer.size();
213 if( orientation != aRequiredOrientation )
219 c_path.reserve( pointCount );
221 for(
int i = 0; i < pointCount; i++ )
226 size_t z_value_ptr = aZValueBuffer.size();
227 aZValueBuffer.push_back( z_value );
229 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
232 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
245 size_t rotations = 0;
296 aArcIndex +=
m_arcs.size();
298 if( aArcIndex >=
static_cast<ssize_t
>(
m_arcs.size() ) )
305 [&]( ssize_t& aShapeIndex )
307 if( aShapeIndex == aArcIndex )
310 if( aShapeIndex > aArcIndex )
315 std::swap( sh.first, sh.second );
325 wxCHECK_MSG( aArcIndex <
m_arcs.size(), ,
326 wxT(
"Invalid arc index requested." ) );
335 m_arcs[aArcIndex] = newArc;
350 wxCHECK_MSG( aPtIndex <
static_cast<ssize_t
>(
m_shapes.size() ), ,
351 wxT(
"Invalid point index requested." ) );
355 if( aCoincident || aPtIndex == 0 )
358 ssize_t firstArcIndex =
m_shapes[aPtIndex].first;
362 amendArc( firstArcIndex, newStart, newEnd );
377 ssize_t currArcIdx =
ArcIndex( aPtIndex );
392 if( !aCoincident &&
ArcIndex( aPtIndex - 1 ) != currArcIdx )
395 m_arcs[currArcIdx] = newArc2;
399 m_arcs[currArcIdx] = newArc1;
400 m_arcs.insert(
m_arcs.begin() + currArcIdx + 1, newArc2 );
404 m_shapes[aPtIndex].second = currArcIdx + 1;
409 for(
int i = aPtIndex; i <
PointCount(); i++ )
442 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
444 if( dist_sq < closest_dist_sq )
447 closest_dist_sq = dist_sq;
449 if( closest_dist_sq == 0 )
453 if( closest_dist_sq < clearance_sq && !aActual )
458 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
461 *aLocation = nearest;
464 *aActual = sqrt( closest_dist_sq );
499 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
501 if( dist_sq < closest_dist_sq )
504 closest_dist_sq = dist_sq;
506 if( closest_dist_sq == 0 )
510 if( closest_dist_sq < clearance_sq && !aActual )
515 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
518 *aLocation = nearest;
521 *aActual = sqrt( closest_dist_sq );
527 for(
size_t i = 0; i <
ArcCount(); i++ )
532 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
534 if( arc.
Collide( aP, aClearance, aActual, aLocation ) )
548 arc.Rotate( aAngle, aCenter );
555 const std::vector<VECTOR2I>& myPts =
m_points;
556 const std::vector<VECTOR2I>& otherPts = aOther.
m_points;
558 const int c_maxBoxes = 100;
559 const int c_minPtsPerBox = 20;
561 int myPointsPerBox = std::max( c_minPtsPerBox,
int( myPts.size() / c_maxBoxes ) + 1 );
562 int otherPointsPerBox = std::max( c_minPtsPerBox,
int( otherPts.size() / c_maxBoxes ) + 1 );
564 int myNumBoxes = ( myPts.size() + myPointsPerBox - 1 ) / myPointsPerBox;
565 int otherNumBoxes = ( otherPts.size() + otherPointsPerBox - 1 ) / otherPointsPerBox;
575 std::vector<BOX> myBoxes( myNumBoxes );
576 std::vector<BOX> otherBoxes( otherNumBoxes );
579 for(
size_t i = 0; i < myPts.size(); i++ )
582 BOX& box = myBoxes[i / myPointsPerBox];
586 box.bbox.Merge( pt );
595 for(
size_t i = 0; i < otherPts.size(); i++ )
598 BOX& box = otherBoxes[i / otherPointsPerBox];
602 box.bbox.Merge( pt );
612 for( BOX& box : myBoxes )
614 box.center = box.bbox.GetCenter();
615 box.radius = int( box.bbox.GetDiameter() / 2 );
618 for( BOX& box : otherBoxes )
620 box.center = box.bbox.GetCenter();
621 box.radius = int( box.bbox.GetDiameter() / 2 );
627 DIST_PAIR( int64_t aDistSq,
size_t aIdA,
size_t aIdB ) :
628 dist( aDistSq ), idA( aIdA ), idB( aIdB )
637 std::vector<DIST_PAIR> pairsToTest;
639 for(
size_t ia = 0; ia < myBoxes.size(); ia++ )
641 for(
size_t ib = 0; ib < otherBoxes.size(); ib++ )
643 const BOX& ca = myBoxes[ia];
644 const BOX& cb = otherBoxes[ib];
646 if( !ca.valid || !cb.valid )
652 int64_t dist = ( pB - pA ).EuclideanNorm();
657 pairsToTest.emplace_back( dist, ia, ib );
661 std::sort( pairsToTest.begin(), pairsToTest.end(),
662 [](
const DIST_PAIR& a,
const DIST_PAIR& b )
664 return a.dist < b.dist;
667 const int c_polyPairsLimit = 5;
672 for(
size_t pairId = 0; pairId < pairsToTest.size() && pairId < c_polyPairsLimit; pairId++ )
674 const DIST_PAIR& pair = pairsToTest[pairId];
680 size_t myStartId = pair.idA * myPointsPerBox;
681 size_t myEndId = myStartId + myPointsPerBox;
683 if( myEndId > myPts.size() )
684 myEndId = myPts.size();
686 VECTOR2I myPrevPt = myPts[myStartId == 0 ? myPts.size() - 1 : myStartId - 1];
688 size_t otherStartId = pair.idB * otherPointsPerBox;
689 size_t otherEndId = otherStartId + otherPointsPerBox;
691 if( otherEndId > otherPts.size() )
692 otherEndId = otherPts.size();
694 VECTOR2I otherPrevPt = otherPts[otherStartId == 0 ? otherPts.size() - 1 : otherStartId - 1];
696 if(
ClosestSegments( myPrevPt, myPts.begin() + myStartId, myPts.begin() + myEndId,
697 otherPrevPt, otherPts.begin() + otherStartId,
698 otherPts.begin() + otherEndId, ptA, ptB, dist_sq ) )
700 if( dist_sq < total_closest_dist_sq )
702 total_closest_dist_sq = dist_sq;
719 if( aMyStart == aMyEnd )
722 if( aOtherStart == aOtherEnd )
728 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
733 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
737 SEG segA( lastPtA, ptA );
738 SEG segB( lastPtB, ptB );
744 if( segA.
NearestPoints( segB, nearestA, nearestB, dist_sq ) )
746 if( dist_sq < closest_dist_sq )
748 closest_dist_sq = dist_sq;
760 aDistSq = closest_dist_sq;
771 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
775 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
784 if( dist_sq < closest_dist_sq )
786 closest_dist_sq = dist_sq;
793 aDistSq = closest_dist_sq;
804 aOther.
m_points.cend(), aPt0, aPt1, dist_sq );
831 if( dist_sq < closest_dist_sq )
836 closest_dist_sq = dist_sq;
838 if( closest_dist_sq == 0)
842 if( closest_dist_sq < clearance_sq && !aActual )
847 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
850 *aLocation = nearest;
853 *aActual = sqrt( closest_dist_sq );
889 if( dist_sq < closest_dist_sq )
894 closest_dist_sq = dist_sq;
896 if( closest_dist_sq == 0 )
900 if( closest_dist_sq < clearance_sq && !aActual )
905 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
908 *aLocation = nearest;
911 *aActual = sqrt( closest_dist_sq );
916 int dist = std::numeric_limits<int>::max();
917 SEG::ecoord closest_dist = sqrt( closest_dist_sq );
920 for(
size_t i = 0; i <
ArcCount(); i++ )
926 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
928 if( arc.
Collide( aSeg, aClearance, aActual || aLocation ? &dist :
nullptr,
929 aLocation ? &pos :
nullptr ) )
934 if( dist < closest_dist )
942 if( closest_dist == 0 || closest_dist < aClearance )
945 *aLocation = nearest;
948 *aActual = closest_dist;
970 [&]( ssize_t& aShapeIndex )
973 aShapeIndex = a.
m_arcs.size() - aShapeIndex - 1;
982 std::swap( sh.first, sh.second );
998 for( ssize_t arcIndex =
m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
1005 long long int l = 0;
1014 for(
size_t i = 0; i <
ArcCount(); i++ )
1015 l +=
CArcs()[i].GetLength();
1026 pt.x = -pt.x + 2 * aRef.
x;
1029 pt.y = -pt.y + 2 * aRef.
y;
1032 for(
auto& arc :
m_arcs )
1033 arc.Mirror( aX, aY, aRef );
1042 for(
auto& arc :
m_arcs )
1049 Remove( aStartIndex, aEndIndex );
1050 Insert( aStartIndex, aP );
1060 if( aStartIndex < 0 )
1064 wxASSERT( aStartIndex <= aEndIndex );
1065 wxASSERT( aEndIndex <
static_cast<int>(
m_points.size() ) );
1072 Remove( aStartIndex, aEndIndex );
1085 Remove( aStartIndex, aEndIndex );
1096 Remove( aStartIndex, aEndIndex );
1103 size_t prev_arc_count =
m_arcs.size();
1104 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.
m_shapes;
1106 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
1109 [&]( ssize_t& aShape )
1112 aShape += prev_arc_count;
1116 m_shapes.insert(
m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
1137 if( aStartIndex < 0 )
1160 if( aStartIndex > aEndIndex )
1166 std::set<size_t> extra_arcs;
1167 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
1170 extra_arcs.insert( aShapeIndex );
1174 for(
int i = aStartIndex; i <= aEndIndex; i++ )
1178 if( i == aStartIndex )
1180 logArcIdxRemoval(
m_shapes[i].second );
1187 else if( i == aEndIndex )
1189 logArcIdxRemoval(
m_shapes[i].first );
1192 assert( i > aStartIndex || (
IsSharedPt( i - 1 )
1204 for(
auto arc : extra_arcs )
1234 int found_index =
Find( aP );
1236 if( found_index >= 0 && aExact )
1246 if( dist < min_dist && seg.
A != aP && seg.
B != aP )
1249 if( found_index < 0 )
1251 else if( s < found_index )
1265 size_t newIndex =
static_cast<size_t>( ii ) + 1;
1289 if( aThreshold == 0 )
1296 if( (
CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
1319 wxCHECK2_MSG(
m_points.size() ==
m_shapes.size(),
return 0,
"Invalid chain!" );
1350 if( aPointIndex < 0 )
1353 if( aPointIndex < 0 )
1359 if( aPointIndex >= lastIndex )
1364 if( aPointIndex == lastIndex - 1 )
1373 return aPointIndex + 1;
1377 int arcStart = aPointIndex;
1381 wxCHECK2_MSG(
m_shapes[aPointIndex].first !=
SHAPE_IS_PT,
return -1,
"malformed chain!" );
1383 ssize_t currentArcIdx =
ArcIndex( aPointIndex );
1386 while( aPointIndex < lastIndex &&
ArcIndex( aPointIndex ) == currentArcIdx )
1393 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1396 if( aPointIndex == lastIndex )
1418 [&]( ssize_t& aIdx )
1428 if( aPointIndex < 0 )
1431 if( aPointIndex >=
PointCount() || aPointIndex < 0 )
1440 int start = aPointIndex;
1441 int end = aPointIndex;
1442 int arcIdx =
ArcIndex( aPointIndex );
1447 while( start > 0 &&
ArcIndex(
static_cast<ssize_t
>( start ) - 1 ) == arcIdx )
1451 if( !
IsArcEnd( end ) || start == end )
1465 if( aStartIndex < 0 )
1475 int numPoints =
static_cast<int>(
m_points.size() );
1480 ssize_t arcToSplitIndex =
ArcIndex( aStartIndex );
1484 for(
size_t i = aStartIndex; i <
m_points.size() && arcToSplitIndex ==
ArcIndex( i ); i++ )
1501 rv.
m_arcs.push_back( newArc );
1506 for(
int i = aStartIndex; i <= aEndIndex && i < numPoints; i =
NextShape( i ) )
1512 bool isLastShape = nextShape < 0;
1516 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1517 || ( nextShape > aEndIndex ) )
1519 if( i == aEndIndex )
1531 for( ; i <= aEndIndex && i < numPoints; i++ )
1551 rv.
m_arcs.push_back( newArc );
1568 wxT(
"Still on an arc segment, we missed something..." ) );
1570 if( i == aStartIndex )
1573 bool nextPointIsArc = isLastShape ? false :
IsArcSegment( nextShape );
1575 if( !nextPointIsArc && i <
SegmentCount() && i < aEndIndex )
1596 size_t num_arcs =
m_arcs.size();
1599 auto fixShapeIndices =
1600 [&](
const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1602 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1607 aIndex = aIndex + num_arcs;
1630 for(
int i = 1; i < aOtherLine.
PointCount(); i++ )
1635 ssize_t arcIndex = aOtherLine.
ArcIndex( i );
1665 chain.
m_arcs.push_back( aArc );
1666 chain.
m_arcs.back().SetWidth( 0 );
1686 wxCHECK( aVertex <
m_points.size(), );
1688 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1701 wxCHECK( aVertex <
m_points.size(), );
1703 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1707 ssize_t arc_pos =
m_arcs.size();
1709 for(
auto arc_it =
m_shapes.rbegin() ;
1710 arc_it !=
m_shapes.rend() + aVertex;
1715 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1724 [&]( ssize_t& aIndex )
1726 if( aIndex >= arc_pos )
1738 m_points.insert(
m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1742 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1743 { arc_pos, SHAPE_IS_PT } );
1745 m_shapes.insert(
m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1779 aIp.push_back( is );
1784 sort( aIp.begin(), aIp.end(), comp );
1793 if( aIps.size() == 0 )
1795 aIps.push_back( aP );
1799 aIps.push_back( aP );
1804 bool aExcludeColinearAndTouching,
BOX2I* aChainBBox )
const
1806 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.
BBox();
1811 const BOX2I bb_cur( a.
A, a.
B - a.
A );
1831 if( coll && ! aExcludeColinearAndTouching )
1907 bool indexMatch =
true;
1917 indexMatch = ( i == aIndex );
1923 sum += ( aP - seg.
A ).EuclideanNorm();
1935 bool aUseBBoxCache )
const
1947 bool inside =
false;
1962 for(
int i = 0; i < pointCount; )
1965 const auto p2 =
GetPoint( i == pointCount ? 0 : i );
1966 const auto diff = p2 - p1;
1970 const int d =
rescale( diff.x, ( aPt.
y - p1.y ), diff.y );
1972 if( ( ( p1.y > aPt.
y ) != ( p2.y > aPt.
y ) ) && ( aPt.
x - p1.x < d ) )
1979 if( aAccuracy <= 1 )
2001 return ( hypot( dist.
x, dist.
y ) <= aAccuracy + 1 ) ? 0 : -1;
2008 if( s.
A == aPt || s.
B == aPt )
2011 if( s.
Distance( aPt ) <= aAccuracy + 1 )
2030 if( s.
A == aP || s.
B == aP )
2049 if( s1 + 1 != s2 &&
CSegment( s1 ).Contains( s2a ) )
2057 else if(
CSegment( s1 ).Contains( s2b ) &&
2085 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2102const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2105 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
2107 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2110 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
2116 std::vector<VECTOR2I> candidatePts = circle.
Intersect( aSeg );
2118 for(
const VECTOR2I& candidate : candidatePts )
2121 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2124 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
2127 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
2139 std::vector<VECTOR2I> candidatePts;
2141 aArc1.
Intersect( aArc2, &candidatePts );
2143 for(
const VECTOR2I& candidate : candidatePts )
2146 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
2149 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2153 *aLocation = candidate;
2161 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
2168 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
2171 is.index_their = s2;
2182 is.index_their = s2;
2193 is.index_their = s2;
2204 std::vector<SHAPE_KEY> shapeCache;
2205 for(
int si = 0; si != -1; si =
NextShape( si ) )
2209 shapeCache.emplace_back( si, arci,
2214 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2216 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2265 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2270 bool aAllowInternalShapePoints )
const
2278 int min_d = std::numeric_limits<int>::max();
2292 if( !aAllowInternalShapePoints )
2315 return nearestArc.
GetP1();
2317 return nearestArc.
GetP0();
2337 dist = std::numeric_limits<int>::max();
2350 return CPoint( nearest );
2356 int min_d = std::numeric_limits<int>::max();
2376 std::stringstream ss;
2378 ss <<
"SHAPE_LINE_CHAIN( { ";
2388 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2409 if( a.m_points.size() != b.
m_points.size() )
2412 for(
int i = 0; i < a.PointCount(); i++ )
2414 if( a.CPoint( i ) != b.
CPoint( i ) )
2444 if( n_pts > aStream.str().size() )
2450 if( n_arcs > aStream.str().size() )
2453 for(
size_t i = 0; i < n_pts; i++ )
2465 for(
size_t i = 0; i < n_arcs; i++ )
2487 if( aPathLength == 0 )
2495 if( total + l >= aPathLength )
2498 return s.
A + d.
Resize( aPathLength - total );
2518 for(
int i = 0, j = size - 1; i < size; ++i )
2526 return std::fabs( area * 0.5 );
2534 std::vector<VECTOR2I> pts_unique;
2535 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2566 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2571 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2572 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2574 pts_unique.push_back(
CPoint( i ) );
2575 shapes_unique.push_back( shapeToKeep );
2583 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2585 const VECTOR2I p0 = pts_unique[ii];
2588 m_shapes.push_back( shapes_unique[ii] );
2599 std::vector<VECTOR2I> new_points;
2600 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2602 new_points.reserve(
m_points.size() );
2603 new_shapes.reserve(
m_shapes.size() );
2605 for(
size_t start_idx = 0; start_idx <
m_points.size(); )
2607 new_points.push_back(
m_points[start_idx] );
2608 new_shapes.push_back(
m_shapes[start_idx] );
2615 size_t end_idx = ( start_idx + 2 ) %
m_points.size();
2616 bool can_simplify =
true;
2618 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx ||
m_closed ) )
2621 for(
size_t test_idx = ( start_idx + 1 ) %
m_points.size();
2622 test_idx != end_idx;
2623 test_idx = ( test_idx + 1 ) %
m_points.size() )
2630 can_simplify =
false;
2637 can_simplify =
false;
2645 end_idx = ( end_idx + 1 ) %
m_points.size();
2650 if( end_idx == ( start_idx + 2 ) %
m_points.size() )
2657 size_t new_start_idx = ( end_idx +
m_points.size() - 1 ) %
m_points.size();
2660 if( new_start_idx <= start_idx )
2663 start_idx = new_start_idx;
2668 if( new_points.size() == 1 )
2670 new_points.push_back(
m_points.back() );
2671 new_shapes.push_back(
m_shapes.back() );
2678 new_points.push_back(
m_points.back() );
2679 new_shapes.push_back(
m_shapes.back() );
2701 int i_start = l.
Find( m );
2702 int i_end = l.
Find( n );
2704 if( i_start > i_end )
2707 i_start = l.
Find( m );
2708 i_end = l.
Find( n );
2711 aPre = l.
Slice( 0, i_start );
2712 aPost = l.
Slice( i_end, -1 );
2713 aMid = l.
Slice( i_start, i_end );
2719 bool aSimplify )
const
2725 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2743 outline.
Split( start,
true );
2744 outline.
Split( end,
true );
2746 const int idA = outline.
Find( start );
2747 const int idB = outline.
Find( end );
2749 if( idA == -1 || idB == -1 )
2755 for(
int i = idA;; )
2774 for(
int i = idB;; )
2793 if( aLeft.
CPoint( 0 ) != start )
2796 wxASSERT( aLeft.
CPoint( 0 ) == start );
2799 if( aRight.
CPoint( 0 ) != start )
2802 wxASSERT( aRight.
CPoint( 0 ) == start );
2806 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2807 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2809 if( sideLeft == 0 || sideRight == 0 )
2812 if( sideLeft == sideRight )
2815 if( sideLeft > 0 && sideRight < 0 )
2816 std::swap( aLeft, aRight );
2843 m_finished( false ),
2853 if( ipNext.
y == m_point.y )
2855 if( ( ipNext.
x == m_point.x )
2856 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2864 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2866 if( ip.
x >= m_point.x )
2868 if( ipNext.
x > m_point.x )
2870 m_state = 1 - m_state;
2874 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2875 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2884 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2885 m_state = 1 - m_state;
2890 if( ipNext.
x > m_point.x )
2892 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2893 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2902 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2903 m_state = 1 - m_state;
2916 m_lastPoint = aPolyline.
CPoint( 0 );
2917 m_firstPoint = aPolyline.
CPoint( 0 );
2922 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
2924 auto p = aPolyline.
CPoint( i );
2926 if( !processVertex( m_lastPoint, p ) )
2937 processVertex( m_lastPoint, m_firstPoint );
2963 size_t nextIdx = aSegment + 1;
2965 if( nextIdx >
m_shapes.size() - 1 )
2994 size_t prevIndex = aIndex - 1;
2998 else if( aIndex >
m_points.size() -1 )
bool Intersects(const BOX2< Vec > &aRect) const
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Represent basic circle geometry with utility geometry functions.
std::vector< VECTOR2I > Intersect(const CIRCLE &aCircle) const
Compute the intersection points between this circle and aCircle.
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
ecoord SquaredDistance(const SEG &aSeg) const
VECTOR2I::extended_type ecoord
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
int Length() const
Return the length (this).
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
static SEG::ecoord Square(int a)
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
bool NearestPoints(const SEG &aSeg, VECTOR2I &aPtA, VECTOR2I &aPtB, int64_t &aDistSq) const
Compute closest points between this segment and aSeg.
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
bool Contains(const SEG &aSeg) const
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
int Intersect(const CIRCLE &aArc, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and a CIRCLE.
void SetWidth(int aWidth)
SHAPE_ARC & ConstructFromStartEndCenter(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aClockwise=false, double aWidth=0)
Constructs this arc from the given start, end and center.
const VECTOR2I & GetP1() const
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
static double DefaultAccuracyForPCB()
const VECTOR2I & GetP0() const
const VECTOR2I & GetCenter() const
POINT_INSIDE_TRACKER(const VECTOR2I &aPoint)
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual BOX2I * GetCachedBBox() const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
virtual bool IsClosed() const =0
virtual const SEG GetSegment(int aIndex) const =0
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const override
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
const std::optional< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
bool Parse(std::stringstream &aStream) override
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Check if point aP is closer to (or on) an edge or vertex of the line chain.
std::vector< SHAPE_ARC > m_arcs
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
ClipperLib::Path convertToClipper(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
const VECTOR2I PointAlong(int aPathLength) const
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
std::vector< VECTOR2I > m_points
array of vertices
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
SHAPE_LINE_CHAIN()
Initialize an empty line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
bool IsArcEnd(size_t aIndex) const
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
void TransformToPolygon(SHAPE_POLY_SET &aBuffer, int aError, ERROR_LOC aErrorLoc) const override
Fills a SHAPE_POLY_SET with a polygon representation of this shape.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
BOX2I m_bbox
cached bounding box
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
bool m_closed
is the line chain closed?
const std::vector< SHAPE_ARC > & CArcs() const
const std::optional< INTERSECTION > SelfIntersectingWithArcs() const
Check if the line chain is self-intersecting.
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both).
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
bool ClosestPoints(const SHAPE_LINE_CHAIN &aOther, VECTOR2I &aPt0, VECTOR2I &aPt1) const
Finds closest points between this and the other line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
virtual const SEG GetSegment(int aIndex) const override
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int SegmentCount() const
Return the number of segments in this line chain.
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
bool ClosestSegmentsFast(const SHAPE_LINE_CHAIN &aOther, VECTOR2I &aPt0, VECTOR2I &aPt1) const
Finds closest points between segments of this and the other line chain.
const std::string Format(bool aCplusPlus=true) const override
static bool ClosestSegments(const VECTOR2I &aMyPrevPt, const point_citer &aMyStart, const point_citer &aMyEnd, const VECTOR2I &aOtherPrevPt, const point_citer &aOtherStart, const point_citer &aOtherEnd, VECTOR2I &aPt0, VECTOR2I &aPt1, int64_t &aDistSq)
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.
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
virtual size_t GetSegmentCount() const override
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
void RemoveDuplicatePoints()
Remove the duplicate points from the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
void Insert(size_t aVertex, const VECTOR2I &aP)
bool IsArcStart(size_t aIndex) const
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
std::vector< VECTOR2I >::const_iterator point_citer
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
static const ssize_t SHAPE_IS_PT
bool OffsetLine(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, SHAPE_LINE_CHAIN &aLeft, SHAPE_LINE_CHAIN &aRight, bool aSimplify=false) const
Creates line chains aLeft and aRight offset to this line chain.
Represent a set of closed polygons.
bool HasHoles() const
Return true if the polygon set has any holes.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
int OutlineCount() const
Return the number of outlines in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
An abstract shape on 2D plane.
VECTOR2I::extended_type ecoord
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).
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
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
std::optional< VECTOR2I > OPT_VECTOR2I
@ SH_LINE_CHAIN
line chain (polyline)
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
std::vector< FAB_LAYER_COLOR > dummy
A min-max version of BOX2 for fast intersection checking.
bool Intersects(const BOX2I_MINMAX &aOther) const
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
SHAPE_KEY(int aFirstIdx, int aArcIdx, const BOX2I_MINMAX &aBBox)
Represent an intersection between two line segments.
bool is_corner_their
When true, the corner [index_their] of the 'their' line lies exactly on 'our' line.
bool is_corner_our
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
int index_our
Index of the intersecting corner/segment in the 'our' (== this) line.
VECTOR2I p
Point of intersection between our and their.
bool valid
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
int index_their
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB) const
compareOriginDistance(const VECTOR2I &aOrigin)
bool TestSegmentHit(const VECTOR2I &aRefPoint, const VECTOR2I &aStart, const VECTOR2I &aEnd, int aDist)
Test if aRefPoint is with aDistance on the line defined by aStart and aEnd.
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< double > VECTOR2D