32#include <clipper2/clipper.h>
64 for(
size_t i = 0; i < aV.size(); i+= 2 )
87 m_width( aArc.GetWidth() )
89 if( aMaxError.has_value() )
90 Append( aArc, aMaxError.value() );
99 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
100 const std::vector<SHAPE_ARC>& aArcBuffer ) :
106 std::map<ssize_t, ssize_t> loadedArcs;
111 [&]( ssize_t aArcIndex ) -> ssize_t
117 else if( loadedArcs.count( aArcIndex ) == 0 )
119 loadedArcs.insert( { aArcIndex,
m_arcs.size() } );
120 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
123 return loadedArcs.at( aArcIndex );
126 for(
size_t ii = 0; ii < aPath.size(); ++ii )
128 Append( aPath[ii].x, aPath[ii].y );
131 int idx_z = aPath[ii].z;
133 if( idx_z < 0 || idx_z >= (
int)aZValueBuffer.size() )
136 m_shapes[ii].first = loadArc( aZValueBuffer[idx_z].m_FirstArcIdx );
137 m_shapes[ii].second = loadArc( aZValueBuffer[idx_z].m_SecondArcIdx );
151 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
152 std::vector<SHAPE_ARC>& aArcBuffer )
const
154 Clipper2Lib::Path64 c_path;
156 bool orientation =
Area(
false ) >= 0;
157 ssize_t shape_offset = aArcBuffer.size();
159 if( orientation != aRequiredOrientation )
165 c_path.reserve( pointCount );
167 for(
int i = 0; i < pointCount; i++ )
172 size_t z_value_ptr = aZValueBuffer.size();
173 aZValueBuffer.push_back( z_value );
175 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
178 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
191 size_t rotations = 0;
242 aArcIndex +=
m_arcs.size();
244 if( aArcIndex >=
static_cast<ssize_t
>(
m_arcs.size() ) )
251 [&]( ssize_t& aShapeIndex )
253 if( aShapeIndex == aArcIndex )
256 if( aShapeIndex > aArcIndex )
261 std::swap( sh.first, sh.second );
271 wxCHECK_MSG( aArcIndex <
m_arcs.size(), ,
272 wxT(
"Invalid arc index requested." ) );
281 m_arcs[aArcIndex] = newArc;
296 wxCHECK_MSG( aPtIndex <
static_cast<ssize_t
>(
m_shapes.size() ), ,
297 wxT(
"Invalid point index requested." ) );
301 if( aCoincident || aPtIndex == 0 )
304 ssize_t firstArcIndex =
m_shapes[aPtIndex].first;
308 amendArc( firstArcIndex, newStart, newEnd );
323 ssize_t currArcIdx =
ArcIndex( aPtIndex );
338 if( !aCoincident &&
ArcIndex( aPtIndex - 1 ) != currArcIdx )
341 m_arcs[currArcIdx] = newArc2;
345 m_arcs[currArcIdx] = newArc1;
346 m_arcs.insert(
m_arcs.begin() + currArcIdx + 1, newArc2 );
350 m_shapes[aPtIndex].second = currArcIdx + 1;
355 for(
int i = aPtIndex; i <
PointCount(); i++ )
388 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
390 if( dist_sq < closest_dist_sq )
393 closest_dist_sq = dist_sq;
395 if( closest_dist_sq == 0 )
399 if( closest_dist_sq < clearance_sq && !aActual )
404 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
407 *aLocation = nearest;
410 *aActual = sqrt( closest_dist_sq );
445 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
447 if( dist_sq < closest_dist_sq )
450 closest_dist_sq = dist_sq;
452 if( closest_dist_sq == 0 )
456 if( closest_dist_sq < clearance_sq && !aActual )
461 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
464 *aLocation = nearest;
467 *aActual = sqrt( closest_dist_sq );
473 for(
size_t i = 0; i <
ArcCount(); i++ )
478 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
480 if( arc.
Collide( aP, aClearance, aActual, aLocation ) )
494 arc.Rotate( aAngle, aCenter );
501 const std::vector<VECTOR2I>& myPts =
m_points;
502 const std::vector<VECTOR2I>& otherPts = aOther.
m_points;
504 const int c_maxBoxes = 100;
505 const int c_minPtsPerBox = 20;
507 int myPointsPerBox = std::max( c_minPtsPerBox,
int( myPts.size() / c_maxBoxes ) + 1 );
508 int otherPointsPerBox = std::max( c_minPtsPerBox,
int( otherPts.size() / c_maxBoxes ) + 1 );
510 int myNumBoxes = ( myPts.size() + myPointsPerBox - 1 ) / myPointsPerBox;
511 int otherNumBoxes = ( otherPts.size() + otherPointsPerBox - 1 ) / otherPointsPerBox;
521 std::vector<BOX> myBoxes( myNumBoxes );
522 std::vector<BOX> otherBoxes( otherNumBoxes );
525 for(
size_t i = 0; i < myPts.size(); i++ )
528 BOX& box = myBoxes[i / myPointsPerBox];
532 box.bbox.Merge( pt );
541 for(
size_t i = 0; i < otherPts.size(); i++ )
544 BOX& box = otherBoxes[i / otherPointsPerBox];
548 box.bbox.Merge( pt );
558 for( BOX& box : myBoxes )
560 box.center = box.bbox.GetCenter();
561 box.radius = int( box.bbox.GetDiameter() / 2 );
564 for( BOX& box : otherBoxes )
566 box.center = box.bbox.GetCenter();
567 box.radius = int( box.bbox.GetDiameter() / 2 );
573 DIST_PAIR( int64_t aDistSq,
size_t aIdA,
size_t aIdB ) :
574 dist( aDistSq ), idA( aIdA ), idB( aIdB )
583 std::vector<DIST_PAIR> pairsToTest;
585 for(
size_t ia = 0; ia < myBoxes.size(); ia++ )
587 for(
size_t ib = 0; ib < otherBoxes.size(); ib++ )
589 const BOX& ca = myBoxes[ia];
590 const BOX& cb = otherBoxes[ib];
592 if( !ca.valid || !cb.valid )
598 int64_t dist = ( pB - pA ).EuclideanNorm();
603 pairsToTest.emplace_back( dist, ia, ib );
607 std::sort( pairsToTest.begin(), pairsToTest.end(),
608 [](
const DIST_PAIR& a,
const DIST_PAIR& b )
610 return a.dist < b.dist;
613 const int c_polyPairsLimit = 5;
618 for(
size_t pairId = 0; pairId < pairsToTest.size() && pairId < c_polyPairsLimit; pairId++ )
620 const DIST_PAIR& pair = pairsToTest[pairId];
626 size_t myStartId = pair.idA * myPointsPerBox;
627 size_t myEndId = myStartId + myPointsPerBox;
629 if( myEndId > myPts.size() )
630 myEndId = myPts.size();
632 VECTOR2I myPrevPt = myPts[myStartId == 0 ? myPts.size() - 1 : myStartId - 1];
634 size_t otherStartId = pair.idB * otherPointsPerBox;
635 size_t otherEndId = otherStartId + otherPointsPerBox;
637 if( otherEndId > otherPts.size() )
638 otherEndId = otherPts.size();
640 VECTOR2I otherPrevPt = otherPts[otherStartId == 0 ? otherPts.size() - 1 : otherStartId - 1];
642 if(
ClosestSegments( myPrevPt, myPts.begin() + myStartId, myPts.begin() + myEndId,
643 otherPrevPt, otherPts.begin() + otherStartId,
644 otherPts.begin() + otherEndId, ptA, ptB, dist_sq ) )
646 if( dist_sq < total_closest_dist_sq )
648 total_closest_dist_sq = dist_sq;
665 if( aMyStart == aMyEnd )
668 if( aOtherStart == aOtherEnd )
674 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
679 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
683 SEG segA( lastPtA, ptA );
684 SEG segB( lastPtB, ptB );
690 if( segA.
NearestPoints( segB, nearestA, nearestB, dist_sq ) )
692 if( dist_sq < closest_dist_sq )
694 closest_dist_sq = dist_sq;
706 aDistSq = closest_dist_sq;
717 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
721 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
730 if( dist_sq < closest_dist_sq )
732 closest_dist_sq = dist_sq;
739 aDistSq = closest_dist_sq;
750 aOther.
m_points.cend(), aPt0, aPt1, dist_sq );
777 if( dist_sq < closest_dist_sq )
782 closest_dist_sq = dist_sq;
784 if( closest_dist_sq == 0)
788 if( closest_dist_sq < clearance_sq && !aActual )
793 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
796 *aLocation = nearest;
799 *aActual = sqrt( closest_dist_sq );
835 if( dist_sq < closest_dist_sq )
840 closest_dist_sq = dist_sq;
842 if( closest_dist_sq == 0 )
846 if( closest_dist_sq < clearance_sq && !aActual )
851 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
854 *aLocation = nearest;
857 *aActual = sqrt( closest_dist_sq );
862 int dist = std::numeric_limits<int>::max();
863 SEG::ecoord closest_dist = sqrt( closest_dist_sq );
866 for(
size_t i = 0; i <
ArcCount(); i++ )
872 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
874 if( arc.
Collide( aSeg, aClearance, aActual || aLocation ? &dist :
nullptr,
875 aLocation ? &pos :
nullptr ) )
880 if( dist < closest_dist )
888 if( closest_dist == 0 || closest_dist < aClearance )
891 *aLocation = nearest;
894 *aActual = closest_dist;
916 [&]( ssize_t& aShapeIndex )
919 aShapeIndex = a.
m_arcs.size() - aShapeIndex - 1;
928 std::swap( sh.first, sh.second );
944 for( ssize_t arcIndex =
m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
960 for(
size_t i = 0; i <
ArcCount(); i++ )
961 l +=
CArcs()[i].GetLength();
971 if( aFlipDirection == FLIP_DIRECTION::LEFT_RIGHT )
972 pt.x = -pt.x + 2 * aRef.
x;
974 pt.y = -pt.y + 2 * aRef.
y;
978 arc.Mirror( aRef, aFlipDirection );
994 Remove( aStartIndex, aEndIndex );
995 Insert( aStartIndex, aP );
1005 if( aStartIndex < 0 )
1009 wxASSERT( aStartIndex <= aEndIndex );
1010 wxASSERT( aEndIndex <
static_cast<int>(
m_points.size() ) );
1017 Remove( aStartIndex, aEndIndex );
1030 Remove( aStartIndex, aEndIndex );
1041 Remove( aStartIndex, aEndIndex );
1048 size_t prev_arc_count =
m_arcs.size();
1049 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.
m_shapes;
1051 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
1054 [&]( ssize_t& aShape )
1057 aShape += prev_arc_count;
1061 m_shapes.insert(
m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
1082 if( aStartIndex < 0 )
1105 if( aStartIndex > aEndIndex )
1111 std::set<size_t> extra_arcs;
1112 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
1115 extra_arcs.insert( aShapeIndex );
1119 for(
int i = aStartIndex; i <= aEndIndex; i++ )
1123 if( i == aStartIndex )
1125 logArcIdxRemoval(
m_shapes[i].second );
1132 else if( i == aEndIndex )
1134 logArcIdxRemoval(
m_shapes[i].first );
1137 assert( i > aStartIndex || (
IsSharedPt( i - 1 )
1149 for(
auto arc : extra_arcs )
1179 int found_index =
Find( aP );
1181 if( found_index >= 0 && aExact )
1191 if( dist < min_dist && seg.
A != aP && seg.
B != aP )
1194 if( found_index < 0 )
1196 else if( s < found_index )
1210 size_t newIndex =
static_cast<size_t>( ii ) + 1;
1234 if( aThreshold == 0 )
1241 if( (
CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
1264 wxCHECK2_MSG(
m_points.size() ==
m_shapes.size(),
return 0,
"Invalid chain!" );
1285 wxCHECK( aIndex < segCount && aIndex >= 0,
1297 if( aPointIndex < 0 )
1300 if( aPointIndex < 0 )
1306 if( aPointIndex >= lastIndex )
1311 if( aPointIndex == lastIndex - 1 )
1320 return aPointIndex + 1;
1324 int arcStart = aPointIndex;
1328 wxCHECK2_MSG(
m_shapes[aPointIndex].first !=
SHAPE_IS_PT,
return -1,
"malformed chain!" );
1330 ssize_t currentArcIdx =
ArcIndex( aPointIndex );
1333 while( aPointIndex < lastIndex &&
ArcIndex( aPointIndex ) == currentArcIdx )
1340 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1343 if( aPointIndex == lastIndex )
1365 [&]( ssize_t& aIdx )
1375 if( aPointIndex < 0 )
1378 if( aPointIndex >=
PointCount() || aPointIndex < 0 )
1387 int start = aPointIndex;
1388 int end = aPointIndex;
1389 int arcIdx =
ArcIndex( aPointIndex );
1394 while( start > 0 &&
ArcIndex(
static_cast<ssize_t
>( start ) - 1 ) == arcIdx )
1418 if( aStartIndex < 0 )
1428 int numPoints =
static_cast<int>(
m_points.size() );
1433 ssize_t arcToSplitIndex =
ArcIndex( aStartIndex );
1437 for(
size_t i = aStartIndex; i <
m_points.size() && arcToSplitIndex ==
ArcIndex( i ); i++ )
1454 rv.
m_arcs.push_back( newArc );
1459 for(
int i = aStartIndex; i <= aEndIndex && i < numPoints; i =
NextShape( i ) )
1465 bool isLastShape = nextShape < 0;
1469 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1470 || ( nextShape > aEndIndex ) )
1472 if( i == aEndIndex )
1484 for( ; i <= aEndIndex && i < numPoints; i++ )
1504 rv.
m_arcs.push_back( newArc );
1512 rv.
Append( currentArc, aMaxError );
1520 wxASSERT_MSG( !
IsArcSegment( i ), wxT(
"Still on an arc segment, we missed something..." ) );
1522 if( i == aStartIndex )
1525 bool nextPointIsArc = isLastShape ? false :
IsArcSegment( nextShape );
1527 if( !nextPointIsArc && i <
SegmentCount() && i < aEndIndex )
1548 size_t num_arcs =
m_arcs.size();
1551 auto fixShapeIndices =
1552 [&](
const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1554 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1559 aIndex = aIndex + num_arcs;
1582 for(
int i = 1; i < aOtherLine.
PointCount(); i++ )
1587 ssize_t arcIndex = aOtherLine.
ArcIndex( i );
1638 wxCHECK( aVertex <
m_points.size(), );
1640 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1659 wxCHECK( aVertex <
m_points.size(), );
1661 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1665 ssize_t arc_pos =
m_arcs.size();
1667 for(
auto arc_it =
m_shapes.rbegin() ;
1668 arc_it !=
m_shapes.rend() + aVertex;
1673 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1682 [&]( ssize_t& aIndex )
1684 if( aIndex >= arc_pos )
1700 std::vector<std::pair<ssize_t, ssize_t>> new_points(
chain.
PointCount(),
1701 { arc_pos, SHAPE_IS_PT } );
1703 m_shapes.insert(
m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1737 aIp.push_back( is );
1742 sort( aIp.begin(), aIp.end(), comp );
1763 if( aIps.size() == 0 )
1765 aIps.push_back( aP );
1769 aIps.push_back( aP );
1774 bool aExcludeColinearAndTouching,
BOX2I* aChainBBox )
const
1776 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.
BBox();
1781 const BOX2I bb_cur( a.
A, a.
B - a.
A );
1801 if( coll && ! aExcludeColinearAndTouching )
1877 bool indexMatch =
true;
1887 indexMatch = ( i == aIndex );
1893 sum += ( aP - seg.
A ).EuclideanNorm();
1905 bool aUseBBoxCache )
const
1929 bool inside =
false;
1931 for(
int i = 0; i < pointCount; )
1940 const int d =
rescale( diff.
x, ( aPt.
y - p1.
y ), diff.
y );
1942 if( ( ( p1.
y >= aPt.
y ) != ( p2.
y >= aPt.
y ) ) && ( aPt.
x - p1.
x < d ) )
1948 if( aAccuracy <= 1 )
1963 const int threshold = aAccuracy + 1;
1964 const int64_t thresholdSq = int64_t( threshold ) * threshold;
1971 else if( pointCount == 1 )
1974 return distSq <= thresholdSq ? 0 : -1;
1979 for(
size_t i = 0; i < segCount; i++ )
1983 if( s.
A == aPt || s.
B == aPt )
2005 if( s.
A == aP || s.
B == aP )
2019 std::vector<SEG> segments( segCount );
2021 for(
size_t s = 0; s < segCount; s++ )
2024 for(
size_t s1 = 0; s1 < segCount; s1++ )
2026 const SEG& cs1 = segments[s1];
2028 for(
size_t s2 = s1 + 1; s2 < segCount; s2++ )
2030 const SEG& cs2 = segments[s2];
2033 if( s1 + 1 != s2 && cs1.
Contains( s2a ) )
2045 !(
IsClosed() && s1 == 0 && s2 == segCount - 1 ) )
2069 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2086const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2089 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
2091 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2094 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
2100 std::vector<VECTOR2I> candidatePts =
circle.Intersect( aSeg );
2102 for(
const VECTOR2I& candidate : candidatePts )
2105 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2108 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
2111 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
2123 std::vector<VECTOR2I> candidatePts;
2125 aArc1.
Intersect( aArc2, &candidatePts );
2127 for(
const VECTOR2I& candidate : candidatePts )
2130 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
2133 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2137 *aLocation = candidate;
2145 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
2152 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
2155 is.index_their = s2;
2166 is.index_their = s2;
2177 is.index_their = s2;
2188 std::vector<SHAPE_KEY> shapeCache;
2189 for(
int si = 0; si != -1; si =
NextShape( si ) )
2193 shapeCache.emplace_back( si, arci,
2198 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2200 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2249 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2254 bool aAllowInternalShapePoints )
const
2262 int min_d = std::numeric_limits<int>::max();
2276 if( !aAllowInternalShapePoints )
2299 return nearestArc.
GetP1();
2301 return nearestArc.
GetP0();
2321 dist = std::numeric_limits<int>::max();
2334 return CPoint( nearest );
2340 int min_d = std::numeric_limits<int>::max();
2360 std::stringstream ss;
2362 ss <<
"SHAPE_LINE_CHAIN( { ";
2372 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2393 if( a.m_points.size() != b.
m_points.size() )
2396 for(
int i = 0; i < a.PointCount(); i++ )
2398 if( a.CPoint( i ) != b.
CPoint( i ) )
2428 if( n_pts > aStream.str().size() )
2434 if( n_arcs > aStream.str().size() )
2437 for(
size_t i = 0; i < n_pts; i++ )
2449 for(
size_t i = 0; i < n_arcs; i++ )
2471 if( aPathLength == 0 )
2479 if( total + l >= aPathLength )
2482 return s.
A + d.
Resize( aPathLength - total );
2502 for(
int i = 0, j = size - 1; i < size; ++i )
2510 return std::fabs( area * 0.5 );
2518 std::vector<VECTOR2I> pts_unique;
2519 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2550 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2555 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2556 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2558 pts_unique.push_back(
CPoint( i ) );
2559 shapes_unique.push_back( shapeToKeep );
2567 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2569 const VECTOR2I p0 = pts_unique[ii];
2572 m_shapes.push_back( shapes_unique[ii] );
2583 std::vector<VECTOR2I> new_points;
2584 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2586 new_points.reserve(
m_points.size() );
2587 new_shapes.reserve(
m_shapes.size() );
2589 for(
size_t start_idx = 0; start_idx <
m_points.size(); )
2591 new_points.push_back(
m_points[start_idx] );
2592 new_shapes.push_back(
m_shapes[start_idx] );
2599 size_t end_idx = ( start_idx + 2 ) %
m_points.size();
2600 bool can_simplify =
true;
2602 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx ||
m_closed ) )
2605 for(
size_t test_idx = ( start_idx + 1 ) %
m_points.size();
2606 test_idx != end_idx;
2607 test_idx = ( test_idx + 1 ) %
m_points.size() )
2614 can_simplify =
false;
2621 can_simplify =
false;
2629 end_idx = ( end_idx + 1 ) %
m_points.size();
2634 if( end_idx == ( start_idx + 2 ) %
m_points.size() )
2641 size_t new_start_idx = ( end_idx +
m_points.size() - 1 ) %
m_points.size();
2644 if( new_start_idx <= start_idx )
2647 start_idx = new_start_idx;
2652 if( new_points.size() == 1 )
2654 new_points.push_back(
m_points.back() );
2655 new_shapes.push_back(
m_shapes.back() );
2662 new_points.push_back(
m_points.back() );
2663 new_shapes.push_back(
m_shapes.back() );
2668 m_points = std::move( new_points );
2669 m_shapes = std::move( new_shapes );
2685 int i_start = l.
Find( m );
2686 int i_end = l.
Find( n );
2688 if( i_start > i_end )
2691 i_start = l.
Find( m );
2692 i_end = l.
Find( n );
2695 aPre = l.
Slice( 0, i_start );
2696 aPost = l.
Slice( i_end, -1 );
2697 aMid = l.
Slice( i_start, i_end );
2704 std::vector<VECTOR2I> pts_unique;
2705 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2738 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2743 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2744 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2746 pts_unique.push_back(
CPoint( i ) );
2747 shapes_unique.push_back( shapeToKeep );
2754 np = pts_unique.size();
2768 && (
SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2769 ||
SEG( p0, pts_unique[n + 2] ).Collinear(
SEG( p0, pts_unique[n + 1] ) ) ) )
2774 m_shapes.push_back( shapes_unique[i] );
2781 m_points.push_back( pts_unique[np - 1] );
2782 m_shapes.push_back( shapes_unique[np - 1] );
2791 m_points.push_back( pts_unique[np - 2] );
2792 m_shapes.push_back( shapes_unique[np - 2] );
2795 m_points.push_back( pts_unique[np - 1] );
2796 m_shapes.push_back( shapes_unique[np - 1] );
2805 bool aSimplify )
const
2811 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2829 outline.
Split( start,
true );
2832 const int idA = outline.
Find( start );
2833 const int idB = outline.
Find(
end );
2835 if( idA == -1 || idB == -1 )
2841 for(
int i = idA;; )
2860 for(
int i = idB;; )
2879 if( aLeft.
CPoint( 0 ) != start )
2882 wxASSERT( aLeft.
CPoint( 0 ) == start );
2885 if( aRight.
CPoint( 0 ) != start )
2888 wxASSERT( aRight.
CPoint( 0 ) == start );
2892 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2893 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2895 if( sideLeft == 0 || sideRight == 0 )
2898 if( sideLeft == sideRight )
2901 if( sideLeft > 0 && sideRight < 0 )
2902 std::swap( aLeft, aRight );
2929 m_finished( false ),
2939 if( ipNext.
y == m_point.y )
2941 if( ( ipNext.
x == m_point.x )
2942 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2950 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2952 if( ip.
x >= m_point.x )
2954 if( ipNext.
x > m_point.x )
2956 m_state = 1 - m_state;
2960 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2961 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2970 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2971 m_state = 1 - m_state;
2976 if( ipNext.
x > m_point.x )
2978 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2979 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2988 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2989 m_state = 1 - m_state;
3002 m_lastPoint = aPolyline.
CPoint( 0 );
3003 m_firstPoint = aPolyline.
CPoint( 0 );
3008 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
3010 auto p = aPolyline.
CPoint( i );
3012 if( !processVertex( m_lastPoint, p ) )
3023 processVertex( m_lastPoint, m_firstPoint );
3049 size_t nextIdx = aSegment + 1;
3051 if( nextIdx >
m_shapes.size() - 1 )
3080 size_t prevIndex = aIndex - 1;
3084 else if( aIndex >
m_points.size() -1 )
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
constexpr bool Intersects(const BOX2< Vec > &aRect) const
Represent basic circle geometry with utility geometry functions.
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.
bool Intersects(const SEG &aSeg) const
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.
const SHAPE_LINE_CHAIN ConvertToPolyline(int aMaxError=DefaultAccuracyForPCB(), int *aActualError=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
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,...
static int 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
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.
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.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
BOX2I m_bbox
cached bounding box
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.
bool Intersects(const SEG &aSeg) const
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.
SHAPE_LINE_CHAIN & Simplify2(bool aRemoveColinear=true)
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.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
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...
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
void Mirror(const VECTOR2I &aRef, FLIP_DIRECTION aFlipDirection)
Mirror the line points about y or x (or both).
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 std::vector< VECTOR2I > & CPoints() const
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
constexpr extended_type SquaredDistance(const VECTOR2< T > &aVector) const
Compute the squared distance between two vectors.
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
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)
int getArcPolygonizationMaxError()
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)
const SHAPE_LINE_CHAIN chain
SHAPE_CIRCLE circle(c.m_circle_center, c.m_circle_radius)
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