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 );
1751 if( aIps.size() == 0 )
1753 aIps.push_back( aP );
1757 aIps.push_back( aP );
1762 bool aExcludeColinearAndTouching,
BOX2I* aChainBBox )
const
1764 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.
BBox();
1769 const BOX2I bb_cur( a.
A, a.
B - a.
A );
1789 if( coll && ! aExcludeColinearAndTouching )
1865 bool indexMatch =
true;
1875 indexMatch = ( i == aIndex );
1881 sum += ( aP - seg.
A ).EuclideanNorm();
1893 bool aUseBBoxCache )
const
1917 bool inside =
false;
1919 for(
int i = 0; i < pointCount; )
1928 const int d =
rescale( diff.
x, ( aPt.
y - p1.
y ), diff.
y );
1930 if( ( ( p1.
y >= aPt.
y ) != ( p2.
y >= aPt.
y ) ) && ( aPt.
x - p1.
x < d ) )
1936 if( aAccuracy <= 1 )
1951 const int threshold = aAccuracy + 1;
1952 const int64_t thresholdSq = int64_t( threshold ) * threshold;
1959 else if( pointCount == 1 )
1962 return distSq <= thresholdSq ? 0 : -1;
1967 for(
size_t i = 0; i < segCount; i++ )
1971 if( s.
A == aPt || s.
B == aPt )
1993 if( s.
A == aP || s.
B == aP )
2007 std::vector<SEG> segments( segCount );
2009 for(
size_t s = 0; s < segCount; s++ )
2012 for(
size_t s1 = 0; s1 < segCount; s1++ )
2014 const SEG& cs1 = segments[s1];
2016 for(
size_t s2 = s1 + 1; s2 < segCount; s2++ )
2018 const SEG& cs2 = segments[s2];
2021 if( s1 + 1 != s2 && cs1.
Contains( s2a ) )
2033 !(
IsClosed() && s1 == 0 && s2 == segCount - 1 ) )
2057 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2074const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2077 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
2079 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2082 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
2088 std::vector<VECTOR2I> candidatePts =
circle.Intersect( aSeg );
2090 for(
const VECTOR2I& candidate : candidatePts )
2093 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2096 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
2099 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
2111 std::vector<VECTOR2I> candidatePts;
2113 aArc1.
Intersect( aArc2, &candidatePts );
2115 for(
const VECTOR2I& candidate : candidatePts )
2118 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
2121 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2125 *aLocation = candidate;
2133 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
2140 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
2143 is.index_their = s2;
2154 is.index_their = s2;
2165 is.index_their = s2;
2176 std::vector<SHAPE_KEY> shapeCache;
2177 for(
int si = 0; si != -1; si =
NextShape( si ) )
2181 shapeCache.emplace_back( si, arci,
2186 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2188 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2237 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2242 bool aAllowInternalShapePoints )
const
2250 int min_d = std::numeric_limits<int>::max();
2264 if( !aAllowInternalShapePoints )
2287 return nearestArc.
GetP1();
2289 return nearestArc.
GetP0();
2309 dist = std::numeric_limits<int>::max();
2322 return CPoint( nearest );
2328 int min_d = std::numeric_limits<int>::max();
2348 std::stringstream ss;
2350 ss <<
"SHAPE_LINE_CHAIN( { ";
2360 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2381 if( a.m_points.size() != b.
m_points.size() )
2384 for(
int i = 0; i < a.PointCount(); i++ )
2386 if( a.CPoint( i ) != b.
CPoint( i ) )
2416 if( n_pts > aStream.str().size() )
2422 if( n_arcs > aStream.str().size() )
2425 for(
size_t i = 0; i < n_pts; i++ )
2437 for(
size_t i = 0; i < n_arcs; i++ )
2459 if( aPathLength == 0 )
2467 if( total + l >= aPathLength )
2470 return s.
A + d.
Resize( aPathLength - total );
2490 for(
int i = 0, j = size - 1; i < size; ++i )
2498 return std::fabs( area * 0.5 );
2506 std::vector<VECTOR2I> pts_unique;
2507 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2538 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2543 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2544 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2546 pts_unique.push_back(
CPoint( i ) );
2547 shapes_unique.push_back( shapeToKeep );
2555 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2557 const VECTOR2I p0 = pts_unique[ii];
2560 m_shapes.push_back( shapes_unique[ii] );
2571 std::vector<VECTOR2I> new_points;
2572 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2574 new_points.reserve(
m_points.size() );
2575 new_shapes.reserve(
m_shapes.size() );
2577 for(
size_t start_idx = 0; start_idx <
m_points.size(); )
2579 new_points.push_back(
m_points[start_idx] );
2580 new_shapes.push_back(
m_shapes[start_idx] );
2587 size_t end_idx = ( start_idx + 2 ) %
m_points.size();
2588 bool can_simplify =
true;
2590 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx ||
m_closed ) )
2593 for(
size_t test_idx = ( start_idx + 1 ) %
m_points.size();
2594 test_idx != end_idx;
2595 test_idx = ( test_idx + 1 ) %
m_points.size() )
2602 can_simplify =
false;
2609 can_simplify =
false;
2617 end_idx = ( end_idx + 1 ) %
m_points.size();
2622 if( end_idx == ( start_idx + 2 ) %
m_points.size() )
2629 size_t new_start_idx = ( end_idx +
m_points.size() - 1 ) %
m_points.size();
2632 if( new_start_idx <= start_idx )
2635 start_idx = new_start_idx;
2640 if( new_points.size() == 1 )
2642 new_points.push_back(
m_points.back() );
2643 new_shapes.push_back(
m_shapes.back() );
2650 new_points.push_back(
m_points.back() );
2651 new_shapes.push_back(
m_shapes.back() );
2656 m_points = std::move( new_points );
2657 m_shapes = std::move( new_shapes );
2673 int i_start = l.
Find( m );
2674 int i_end = l.
Find( n );
2676 if( i_start > i_end )
2679 i_start = l.
Find( m );
2680 i_end = l.
Find( n );
2683 aPre = l.
Slice( 0, i_start );
2684 aPost = l.
Slice( i_end, -1 );
2685 aMid = l.
Slice( i_start, i_end );
2692 std::vector<VECTOR2I> pts_unique;
2693 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2726 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2731 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2732 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2734 pts_unique.push_back(
CPoint( i ) );
2735 shapes_unique.push_back( shapeToKeep );
2742 np = pts_unique.size();
2756 && (
SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2757 ||
SEG( p0, pts_unique[n + 2] ).Collinear(
SEG( p0, pts_unique[n + 1] ) ) ) )
2762 m_shapes.push_back( shapes_unique[i] );
2769 m_points.push_back( pts_unique[np - 1] );
2770 m_shapes.push_back( shapes_unique[np - 1] );
2779 m_points.push_back( pts_unique[np - 2] );
2780 m_shapes.push_back( shapes_unique[np - 2] );
2783 m_points.push_back( pts_unique[np - 1] );
2784 m_shapes.push_back( shapes_unique[np - 1] );
2793 bool aSimplify )
const
2799 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2817 outline.
Split( start,
true );
2820 const int idA = outline.
Find( start );
2821 const int idB = outline.
Find(
end );
2823 if( idA == -1 || idB == -1 )
2829 for(
int i = idA;; )
2848 for(
int i = idB;; )
2867 if( aLeft.
CPoint( 0 ) != start )
2870 wxASSERT( aLeft.
CPoint( 0 ) == start );
2873 if( aRight.
CPoint( 0 ) != start )
2876 wxASSERT( aRight.
CPoint( 0 ) == start );
2880 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2881 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2883 if( sideLeft == 0 || sideRight == 0 )
2886 if( sideLeft == sideRight )
2889 if( sideLeft > 0 && sideRight < 0 )
2890 std::swap( aLeft, aRight );
2917 m_finished( false ),
2927 if( ipNext.
y == m_point.y )
2929 if( ( ipNext.
x == m_point.x )
2930 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2938 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2940 if( ip.
x >= m_point.x )
2942 if( ipNext.
x > m_point.x )
2944 m_state = 1 - m_state;
2948 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2949 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2958 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2959 m_state = 1 - m_state;
2964 if( ipNext.
x > m_point.x )
2966 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2967 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2976 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2977 m_state = 1 - m_state;
2990 m_lastPoint = aPolyline.
CPoint( 0 );
2991 m_firstPoint = aPolyline.
CPoint( 0 );
2996 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
2998 auto p = aPolyline.
CPoint( i );
3000 if( !processVertex( m_lastPoint, p ) )
3011 processVertex( m_lastPoint, m_firstPoint );
3037 size_t nextIdx = aSegment + 1;
3039 if( nextIdx >
m_shapes.size() - 1 )
3068 size_t prevIndex = aIndex - 1;
3072 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.
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.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
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.
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...
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