32#include <clipper2/clipper.h>
53 for(
size_t i = 0; i < aV.size(); i+= 2 )
74 m_width( aArc.GetWidth() )
82 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
83 const std::vector<SHAPE_ARC>& aArcBuffer ) :
85 m_closed( true ), m_width( 0 )
87 std::map<ssize_t, ssize_t> loadedArcs;
92 [&]( ssize_t aArcIndex ) -> ssize_t
98 else if( loadedArcs.count( aArcIndex ) == 0 )
100 loadedArcs.insert( { aArcIndex,
m_arcs.size() } );
101 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
104 return loadedArcs.at( aArcIndex );
107 for(
size_t ii = 0; ii < aPath.size(); ++ii )
109 Append( aPath[ii].x, aPath[ii].y );
112 int idx_z = aPath[ii].z;
114 if( idx_z < 0 || idx_z >= (
int)aZValueBuffer.size() )
117 m_shapes[ii].first = loadArc( aZValueBuffer[idx_z].m_FirstArcIdx );
118 m_shapes[ii].second = loadArc( aZValueBuffer[idx_z].m_SecondArcIdx );
132 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
133 std::vector<SHAPE_ARC>& aArcBuffer )
const
135 Clipper2Lib::Path64 c_path;
137 bool orientation =
Area(
false ) >= 0;
138 ssize_t shape_offset = aArcBuffer.size();
140 if( orientation != aRequiredOrientation )
146 c_path.reserve( pointCount );
148 for(
int i = 0; i < pointCount; i++ )
153 size_t z_value_ptr = aZValueBuffer.size();
154 aZValueBuffer.push_back( z_value );
156 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
159 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
172 size_t rotations = 0;
223 aArcIndex +=
m_arcs.size();
225 if( aArcIndex >=
static_cast<ssize_t
>(
m_arcs.size() ) )
232 [&]( ssize_t& aShapeIndex )
234 if( aShapeIndex == aArcIndex )
237 if( aShapeIndex > aArcIndex )
242 std::swap( sh.first, sh.second );
252 wxCHECK_MSG( aArcIndex <
m_arcs.size(), ,
253 wxT(
"Invalid arc index requested." ) );
262 m_arcs[aArcIndex] = newArc;
277 wxCHECK_MSG( aPtIndex <
static_cast<ssize_t
>(
m_shapes.size() ), ,
278 wxT(
"Invalid point index requested." ) );
282 if( aCoincident || aPtIndex == 0 )
285 ssize_t firstArcIndex =
m_shapes[aPtIndex].first;
289 amendArc( firstArcIndex, newStart, newEnd );
304 ssize_t currArcIdx =
ArcIndex( aPtIndex );
319 if( !aCoincident &&
ArcIndex( aPtIndex - 1 ) != currArcIdx )
322 m_arcs[currArcIdx] = newArc2;
326 m_arcs[currArcIdx] = newArc1;
327 m_arcs.insert(
m_arcs.begin() + currArcIdx + 1, newArc2 );
331 m_shapes[aPtIndex].second = currArcIdx + 1;
336 for(
int i = aPtIndex; i <
PointCount(); i++ )
369 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
371 if( dist_sq < closest_dist_sq )
374 closest_dist_sq = dist_sq;
376 if( closest_dist_sq == 0 )
380 if( closest_dist_sq < clearance_sq && !aActual )
385 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
388 *aLocation = nearest;
391 *aActual = sqrt( closest_dist_sq );
426 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
428 if( dist_sq < closest_dist_sq )
431 closest_dist_sq = dist_sq;
433 if( closest_dist_sq == 0 )
437 if( closest_dist_sq < clearance_sq && !aActual )
442 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
445 *aLocation = nearest;
448 *aActual = sqrt( closest_dist_sq );
454 for(
size_t i = 0; i <
ArcCount(); i++ )
459 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
461 if( arc.
Collide( aP, aClearance, aActual, aLocation ) )
475 arc.Rotate( aAngle, aCenter );
482 const std::vector<VECTOR2I>& myPts =
m_points;
483 const std::vector<VECTOR2I>& otherPts = aOther.
m_points;
485 const int c_maxBoxes = 100;
486 const int c_minPtsPerBox = 20;
488 int myPointsPerBox = std::max( c_minPtsPerBox,
int( myPts.size() / c_maxBoxes ) + 1 );
489 int otherPointsPerBox = std::max( c_minPtsPerBox,
int( otherPts.size() / c_maxBoxes ) + 1 );
491 int myNumBoxes = ( myPts.size() + myPointsPerBox - 1 ) / myPointsPerBox;
492 int otherNumBoxes = ( otherPts.size() + otherPointsPerBox - 1 ) / otherPointsPerBox;
502 std::vector<BOX> myBoxes( myNumBoxes );
503 std::vector<BOX> otherBoxes( otherNumBoxes );
506 for(
size_t i = 0; i < myPts.size(); i++ )
509 BOX& box = myBoxes[i / myPointsPerBox];
513 box.bbox.Merge( pt );
522 for(
size_t i = 0; i < otherPts.size(); i++ )
525 BOX& box = otherBoxes[i / otherPointsPerBox];
529 box.bbox.Merge( pt );
539 for( BOX& box : myBoxes )
541 box.center = box.bbox.GetCenter();
542 box.radius = int( box.bbox.GetDiameter() / 2 );
545 for( BOX& box : otherBoxes )
547 box.center = box.bbox.GetCenter();
548 box.radius = int( box.bbox.GetDiameter() / 2 );
554 DIST_PAIR( int64_t aDistSq,
size_t aIdA,
size_t aIdB ) :
555 dist( aDistSq ), idA( aIdA ), idB( aIdB )
564 std::vector<DIST_PAIR> pairsToTest;
566 for(
size_t ia = 0; ia < myBoxes.size(); ia++ )
568 for(
size_t ib = 0; ib < otherBoxes.size(); ib++ )
570 const BOX& ca = myBoxes[ia];
571 const BOX& cb = otherBoxes[ib];
573 if( !ca.valid || !cb.valid )
579 int64_t dist = ( pB - pA ).EuclideanNorm();
584 pairsToTest.emplace_back( dist, ia, ib );
588 std::sort( pairsToTest.begin(), pairsToTest.end(),
589 [](
const DIST_PAIR& a,
const DIST_PAIR& b )
591 return a.dist < b.dist;
594 const int c_polyPairsLimit = 5;
599 for(
size_t pairId = 0; pairId < pairsToTest.size() && pairId < c_polyPairsLimit; pairId++ )
601 const DIST_PAIR& pair = pairsToTest[pairId];
607 size_t myStartId = pair.idA * myPointsPerBox;
608 size_t myEndId = myStartId + myPointsPerBox;
610 if( myEndId > myPts.size() )
611 myEndId = myPts.size();
613 VECTOR2I myPrevPt = myPts[myStartId == 0 ? myPts.size() - 1 : myStartId - 1];
615 size_t otherStartId = pair.idB * otherPointsPerBox;
616 size_t otherEndId = otherStartId + otherPointsPerBox;
618 if( otherEndId > otherPts.size() )
619 otherEndId = otherPts.size();
621 VECTOR2I otherPrevPt = otherPts[otherStartId == 0 ? otherPts.size() - 1 : otherStartId - 1];
623 if(
ClosestSegments( myPrevPt, myPts.begin() + myStartId, myPts.begin() + myEndId,
624 otherPrevPt, otherPts.begin() + otherStartId,
625 otherPts.begin() + otherEndId, ptA, ptB, dist_sq ) )
627 if( dist_sq < total_closest_dist_sq )
629 total_closest_dist_sq = dist_sq;
646 if( aMyStart == aMyEnd )
649 if( aOtherStart == aOtherEnd )
655 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
660 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
664 SEG segA( lastPtA, ptA );
665 SEG segB( lastPtB, ptB );
671 if( segA.
NearestPoints( segB, nearestA, nearestB, dist_sq ) )
673 if( dist_sq < closest_dist_sq )
675 closest_dist_sq = dist_sq;
687 aDistSq = closest_dist_sq;
698 for(
point_citer itA = aMyStart; itA != aMyEnd; itA++ )
702 for(
point_citer itB = aOtherStart; itB != aOtherEnd; itB++ )
711 if( dist_sq < closest_dist_sq )
713 closest_dist_sq = dist_sq;
720 aDistSq = closest_dist_sq;
731 aOther.
m_points.cend(), aPt0, aPt1, dist_sq );
758 if( dist_sq < closest_dist_sq )
763 closest_dist_sq = dist_sq;
765 if( closest_dist_sq == 0)
769 if( closest_dist_sq < clearance_sq && !aActual )
774 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
777 *aLocation = nearest;
780 *aActual = sqrt( closest_dist_sq );
816 if( dist_sq < closest_dist_sq )
821 closest_dist_sq = dist_sq;
823 if( closest_dist_sq == 0 )
827 if( closest_dist_sq < clearance_sq && !aActual )
832 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
835 *aLocation = nearest;
838 *aActual = sqrt( closest_dist_sq );
843 int dist = std::numeric_limits<int>::max();
844 SEG::ecoord closest_dist = sqrt( closest_dist_sq );
847 for(
size_t i = 0; i <
ArcCount(); i++ )
853 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
855 if( arc.
Collide( aSeg, aClearance, aActual || aLocation ? &dist :
nullptr,
856 aLocation ? &pos :
nullptr ) )
861 if( dist < closest_dist )
869 if( closest_dist == 0 || closest_dist < aClearance )
872 *aLocation = nearest;
875 *aActual = closest_dist;
897 [&]( ssize_t& aShapeIndex )
900 aShapeIndex = a.
m_arcs.size() - aShapeIndex - 1;
909 std::swap( sh.first, sh.second );
925 for( ssize_t arcIndex =
m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
941 for(
size_t i = 0; i <
ArcCount(); i++ )
942 l +=
CArcs()[i].GetLength();
952 if( aFlipDirection == FLIP_DIRECTION::LEFT_RIGHT )
953 pt.x = -pt.x + 2 * aRef.
x;
955 pt.y = -pt.y + 2 * aRef.
y;
959 arc.Mirror( aRef, aFlipDirection );
975 Remove( aStartIndex, aEndIndex );
976 Insert( aStartIndex, aP );
986 if( aStartIndex < 0 )
990 wxASSERT( aStartIndex <= aEndIndex );
991 wxASSERT( aEndIndex <
static_cast<int>(
m_points.size() ) );
998 Remove( aStartIndex, aEndIndex );
1011 Remove( aStartIndex, aEndIndex );
1022 Remove( aStartIndex, aEndIndex );
1029 size_t prev_arc_count =
m_arcs.size();
1030 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.
m_shapes;
1032 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
1035 [&]( ssize_t& aShape )
1038 aShape += prev_arc_count;
1042 m_shapes.insert(
m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
1063 if( aStartIndex < 0 )
1086 if( aStartIndex > aEndIndex )
1092 std::set<size_t> extra_arcs;
1093 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
1096 extra_arcs.insert( aShapeIndex );
1100 for(
int i = aStartIndex; i <= aEndIndex; i++ )
1104 if( i == aStartIndex )
1106 logArcIdxRemoval(
m_shapes[i].second );
1113 else if( i == aEndIndex )
1115 logArcIdxRemoval(
m_shapes[i].first );
1118 assert( i > aStartIndex || (
IsSharedPt( i - 1 )
1130 for(
auto arc : extra_arcs )
1160 int found_index =
Find( aP );
1162 if( found_index >= 0 && aExact )
1172 if( dist < min_dist && seg.
A != aP && seg.
B != aP )
1175 if( found_index < 0 )
1177 else if( s < found_index )
1191 size_t newIndex =
static_cast<size_t>( ii ) + 1;
1215 if( aThreshold == 0 )
1222 if( (
CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
1245 wxCHECK2_MSG(
m_points.size() ==
m_shapes.size(),
return 0,
"Invalid chain!" );
1266 wxCHECK( aIndex < segCount && aIndex >= 0,
1278 if( aPointIndex < 0 )
1281 if( aPointIndex < 0 )
1287 if( aPointIndex >= lastIndex )
1292 if( aPointIndex == lastIndex - 1 )
1301 return aPointIndex + 1;
1305 int arcStart = aPointIndex;
1309 wxCHECK2_MSG(
m_shapes[aPointIndex].first !=
SHAPE_IS_PT,
return -1,
"malformed chain!" );
1311 ssize_t currentArcIdx =
ArcIndex( aPointIndex );
1314 while( aPointIndex < lastIndex &&
ArcIndex( aPointIndex ) == currentArcIdx )
1321 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1324 if( aPointIndex == lastIndex )
1346 [&]( ssize_t& aIdx )
1356 if( aPointIndex < 0 )
1359 if( aPointIndex >=
PointCount() || aPointIndex < 0 )
1368 int start = aPointIndex;
1369 int end = aPointIndex;
1370 int arcIdx =
ArcIndex( aPointIndex );
1375 while( start > 0 &&
ArcIndex(
static_cast<ssize_t
>( start ) - 1 ) == arcIdx )
1379 if( !
IsArcEnd( end ) || start == end )
1393 if( aStartIndex < 0 )
1403 int numPoints =
static_cast<int>(
m_points.size() );
1408 ssize_t arcToSplitIndex =
ArcIndex( aStartIndex );
1412 for(
size_t i = aStartIndex; i <
m_points.size() && arcToSplitIndex ==
ArcIndex( i ); i++ )
1429 rv.
m_arcs.push_back( newArc );
1434 for(
int i = aStartIndex; i <= aEndIndex && i < numPoints; i =
NextShape( i ) )
1440 bool isLastShape = nextShape < 0;
1444 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1445 || ( nextShape > aEndIndex ) )
1447 if( i == aEndIndex )
1459 for( ; i <= aEndIndex && i < numPoints; i++ )
1479 rv.
m_arcs.push_back( newArc );
1496 wxT(
"Still on an arc segment, we missed something..." ) );
1498 if( i == aStartIndex )
1501 bool nextPointIsArc = isLastShape ? false :
IsArcSegment( nextShape );
1503 if( !nextPointIsArc && i <
SegmentCount() && i < aEndIndex )
1524 size_t num_arcs =
m_arcs.size();
1527 auto fixShapeIndices =
1528 [&](
const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1530 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1535 aIndex = aIndex + num_arcs;
1558 for(
int i = 1; i < aOtherLine.
PointCount(); i++ )
1563 ssize_t arcIndex = aOtherLine.
ArcIndex( i );
1593 chain.
m_arcs.push_back( aArc );
1594 chain.
m_arcs.back().SetWidth( 0 );
1614 wxCHECK( aVertex <
m_points.size(), );
1616 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1629 wxCHECK( aVertex <
m_points.size(), );
1631 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1635 ssize_t arc_pos =
m_arcs.size();
1637 for(
auto arc_it =
m_shapes.rbegin() ;
1638 arc_it !=
m_shapes.rend() + aVertex;
1643 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1652 [&]( ssize_t& aIndex )
1654 if( aIndex >= arc_pos )
1666 m_points.insert(
m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1670 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1671 { arc_pos, SHAPE_IS_PT } );
1673 m_shapes.insert(
m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1707 aIp.push_back( is );
1712 sort( aIp.begin(), aIp.end(), comp );
1721 if( aIps.size() == 0 )
1723 aIps.push_back( aP );
1727 aIps.push_back( aP );
1732 bool aExcludeColinearAndTouching,
BOX2I* aChainBBox )
const
1734 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.
BBox();
1739 const BOX2I bb_cur( a.
A, a.
B - a.
A );
1759 if( coll && ! aExcludeColinearAndTouching )
1835 bool indexMatch =
true;
1845 indexMatch = ( i == aIndex );
1851 sum += ( aP - seg.
A ).EuclideanNorm();
1863 bool aUseBBoxCache )
const
1887 bool inside =
false;
1889 for(
int i = 0; i < pointCount; )
1898 const int d =
rescale( diff.
x, ( aPt.
y - p1.
y ), diff.
y );
1900 if( ( ( p1.
y >= aPt.
y ) != ( p2.
y >= aPt.
y ) ) && ( aPt.
x - p1.
x < d ) )
1906 if( aAccuracy <= 1 )
1928 return ( hypot( dist.
x, dist.
y ) <= aAccuracy + 1 ) ? 0 : -1;
1935 if( s.
A == aPt || s.
B == aPt )
1938 if( s.
Distance( aPt ) <= aAccuracy + 1 )
1957 if( s.
A == aP || s.
B == aP )
1976 if( s1 + 1 != s2 &&
CSegment( s1 ).Contains( s2a ) )
1984 else if(
CSegment( s1 ).Contains( s2b ) &&
2012 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2029const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2032 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
2034 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2037 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
2043 std::vector<VECTOR2I> candidatePts = circle.
Intersect( aSeg );
2045 for(
const VECTOR2I& candidate : candidatePts )
2048 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2051 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
2054 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
2066 std::vector<VECTOR2I> candidatePts;
2068 aArc1.
Intersect( aArc2, &candidatePts );
2070 for(
const VECTOR2I& candidate : candidatePts )
2073 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
2076 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2080 *aLocation = candidate;
2088 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
2095 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
2098 is.index_their = s2;
2109 is.index_their = s2;
2120 is.index_their = s2;
2131 std::vector<SHAPE_KEY> shapeCache;
2132 for(
int si = 0; si != -1; si =
NextShape( si ) )
2136 shapeCache.emplace_back( si, arci,
2141 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2143 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2192 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2197 bool aAllowInternalShapePoints )
const
2205 int min_d = std::numeric_limits<int>::max();
2219 if( !aAllowInternalShapePoints )
2242 return nearestArc.
GetP1();
2244 return nearestArc.
GetP0();
2264 dist = std::numeric_limits<int>::max();
2277 return CPoint( nearest );
2283 int min_d = std::numeric_limits<int>::max();
2303 std::stringstream ss;
2305 ss <<
"SHAPE_LINE_CHAIN( { ";
2315 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2336 if( a.m_points.size() != b.
m_points.size() )
2339 for(
int i = 0; i < a.PointCount(); i++ )
2341 if( a.CPoint( i ) != b.
CPoint( i ) )
2371 if( n_pts > aStream.str().size() )
2377 if( n_arcs > aStream.str().size() )
2380 for(
size_t i = 0; i < n_pts; i++ )
2392 for(
size_t i = 0; i < n_arcs; i++ )
2414 if( aPathLength == 0 )
2422 if( total + l >= aPathLength )
2425 return s.
A + d.
Resize( aPathLength - total );
2445 for(
int i = 0, j = size - 1; i < size; ++i )
2453 return std::fabs( area * 0.5 );
2461 std::vector<VECTOR2I> pts_unique;
2462 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2493 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2498 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2499 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2501 pts_unique.push_back(
CPoint( i ) );
2502 shapes_unique.push_back( shapeToKeep );
2510 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2512 const VECTOR2I p0 = pts_unique[ii];
2515 m_shapes.push_back( shapes_unique[ii] );
2526 std::vector<VECTOR2I> new_points;
2527 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2529 new_points.reserve(
m_points.size() );
2530 new_shapes.reserve(
m_shapes.size() );
2532 for(
size_t start_idx = 0; start_idx <
m_points.size(); )
2534 new_points.push_back(
m_points[start_idx] );
2535 new_shapes.push_back(
m_shapes[start_idx] );
2542 size_t end_idx = ( start_idx + 2 ) %
m_points.size();
2543 bool can_simplify =
true;
2545 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx ||
m_closed ) )
2548 for(
size_t test_idx = ( start_idx + 1 ) %
m_points.size();
2549 test_idx != end_idx;
2550 test_idx = ( test_idx + 1 ) %
m_points.size() )
2557 can_simplify =
false;
2564 can_simplify =
false;
2572 end_idx = ( end_idx + 1 ) %
m_points.size();
2577 if( end_idx == ( start_idx + 2 ) %
m_points.size() )
2584 size_t new_start_idx = ( end_idx +
m_points.size() - 1 ) %
m_points.size();
2587 if( new_start_idx <= start_idx )
2590 start_idx = new_start_idx;
2595 if( new_points.size() == 1 )
2597 new_points.push_back(
m_points.back() );
2598 new_shapes.push_back(
m_shapes.back() );
2605 new_points.push_back(
m_points.back() );
2606 new_shapes.push_back(
m_shapes.back() );
2628 int i_start = l.
Find( m );
2629 int i_end = l.
Find( n );
2631 if( i_start > i_end )
2634 i_start = l.
Find( m );
2635 i_end = l.
Find( n );
2638 aPre = l.
Slice( 0, i_start );
2639 aPost = l.
Slice( i_end, -1 );
2640 aMid = l.
Slice( i_start, i_end );
2647 std::vector<VECTOR2I> pts_unique;
2648 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2681 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2686 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2687 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2689 pts_unique.push_back(
CPoint( i ) );
2690 shapes_unique.push_back( shapeToKeep );
2697 np = pts_unique.size();
2711 && (
SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2712 ||
SEG( p0, pts_unique[n + 2] ).Collinear(
SEG( p0, pts_unique[n + 1] ) ) ) )
2717 m_shapes.push_back( shapes_unique[i] );
2724 m_points.push_back( pts_unique[np - 1] );
2725 m_shapes.push_back( shapes_unique[np - 1] );
2734 m_points.push_back( pts_unique[np - 2] );
2735 m_shapes.push_back( shapes_unique[np - 2] );
2738 m_points.push_back( pts_unique[np - 1] );
2739 m_shapes.push_back( shapes_unique[np - 1] );
2748 bool aSimplify )
const
2754 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2772 outline.
Split( start,
true );
2773 outline.
Split( end,
true );
2775 const int idA = outline.
Find( start );
2776 const int idB = outline.
Find( end );
2778 if( idA == -1 || idB == -1 )
2784 for(
int i = idA;; )
2803 for(
int i = idB;; )
2822 if( aLeft.
CPoint( 0 ) != start )
2825 wxASSERT( aLeft.
CPoint( 0 ) == start );
2828 if( aRight.
CPoint( 0 ) != start )
2831 wxASSERT( aRight.
CPoint( 0 ) == start );
2835 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2836 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2838 if( sideLeft == 0 || sideRight == 0 )
2841 if( sideLeft == sideRight )
2844 if( sideLeft > 0 && sideRight < 0 )
2845 std::swap( aLeft, aRight );
2872 m_finished( false ),
2882 if( ipNext.
y == m_point.y )
2884 if( ( ipNext.
x == m_point.x )
2885 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2893 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2895 if( ip.
x >= m_point.x )
2897 if( ipNext.
x > m_point.x )
2899 m_state = 1 - m_state;
2903 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2904 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2913 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2914 m_state = 1 - m_state;
2919 if( ipNext.
x > m_point.x )
2921 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2922 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2931 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2932 m_state = 1 - m_state;
2945 m_lastPoint = aPolyline.
CPoint( 0 );
2946 m_firstPoint = aPolyline.
CPoint( 0 );
2951 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
2953 auto p = aPolyline.
CPoint( i );
2955 if( !processVertex( m_lastPoint, p ) )
2966 processVertex( m_lastPoint, m_firstPoint );
2992 size_t nextIdx = aSegment + 1;
2994 if( nextIdx >
m_shapes.size() - 1 )
3023 size_t prevIndex = aIndex - 1;
3027 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.
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
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.
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.
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 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
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