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 )
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 );
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 )
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 )
1921 const int threshold = aAccuracy + 1;
1922 const int64_t thresholdSq = int64_t( threshold ) * threshold;
1929 else if( pointCount == 1 )
1932 return distSq <= thresholdSq ? 0 : -1;
1937 for(
size_t i = 0; i < segCount; i++ )
1941 if( s.
A == aPt || s.
B == aPt )
1963 if( s.
A == aP || s.
B == aP )
1977 std::vector<SEG> segments( segCount );
1979 for(
size_t s = 0; s < segCount; s++ )
1982 for(
size_t s1 = 0; s1 < segCount; s1++ )
1984 const SEG& cs1 = segments[s1];
1986 for(
size_t s2 = s1 + 1; s2 < segCount; s2++ )
1988 const SEG& cs2 = segments[s2];
1991 if( s1 + 1 != s2 && cs1.
Contains( s2a ) )
2003 !(
IsClosed() && s1 == 0 && s2 == segCount - 1 ) )
2027 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2044const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2047 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
2049 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2052 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
2058 std::vector<VECTOR2I> candidatePts =
circle.Intersect( aSeg );
2060 for(
const VECTOR2I& candidate : candidatePts )
2063 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2066 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
2069 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
2081 std::vector<VECTOR2I> candidatePts;
2083 aArc1.
Intersect( aArc2, &candidatePts );
2085 for(
const VECTOR2I& candidate : candidatePts )
2088 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
2091 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2095 *aLocation = candidate;
2103 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
2110 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
2113 is.index_their = s2;
2124 is.index_their = s2;
2135 is.index_their = s2;
2146 std::vector<SHAPE_KEY> shapeCache;
2147 for(
int si = 0; si != -1; si =
NextShape( si ) )
2151 shapeCache.emplace_back( si, arci,
2156 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2158 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2207 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2212 bool aAllowInternalShapePoints )
const
2220 int min_d = std::numeric_limits<int>::max();
2234 if( !aAllowInternalShapePoints )
2257 return nearestArc.
GetP1();
2259 return nearestArc.
GetP0();
2279 dist = std::numeric_limits<int>::max();
2292 return CPoint( nearest );
2298 int min_d = std::numeric_limits<int>::max();
2318 std::stringstream ss;
2320 ss <<
"SHAPE_LINE_CHAIN( { ";
2330 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2351 if( a.m_points.size() != b.
m_points.size() )
2354 for(
int i = 0; i < a.PointCount(); i++ )
2356 if( a.CPoint( i ) != b.
CPoint( i ) )
2386 if( n_pts > aStream.str().size() )
2392 if( n_arcs > aStream.str().size() )
2395 for(
size_t i = 0; i < n_pts; i++ )
2407 for(
size_t i = 0; i < n_arcs; i++ )
2429 if( aPathLength == 0 )
2437 if( total + l >= aPathLength )
2440 return s.
A + d.
Resize( aPathLength - total );
2460 for(
int i = 0, j = size - 1; i < size; ++i )
2468 return std::fabs( area * 0.5 );
2476 std::vector<VECTOR2I> pts_unique;
2477 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2508 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2513 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2514 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2516 pts_unique.push_back(
CPoint( i ) );
2517 shapes_unique.push_back( shapeToKeep );
2525 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2527 const VECTOR2I p0 = pts_unique[ii];
2530 m_shapes.push_back( shapes_unique[ii] );
2541 std::vector<VECTOR2I> new_points;
2542 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2544 new_points.reserve(
m_points.size() );
2545 new_shapes.reserve(
m_shapes.size() );
2547 for(
size_t start_idx = 0; start_idx <
m_points.size(); )
2549 new_points.push_back(
m_points[start_idx] );
2550 new_shapes.push_back(
m_shapes[start_idx] );
2557 size_t end_idx = ( start_idx + 2 ) %
m_points.size();
2558 bool can_simplify =
true;
2560 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx ||
m_closed ) )
2563 for(
size_t test_idx = ( start_idx + 1 ) %
m_points.size();
2564 test_idx != end_idx;
2565 test_idx = ( test_idx + 1 ) %
m_points.size() )
2572 can_simplify =
false;
2579 can_simplify =
false;
2587 end_idx = ( end_idx + 1 ) %
m_points.size();
2592 if( end_idx == ( start_idx + 2 ) %
m_points.size() )
2599 size_t new_start_idx = ( end_idx +
m_points.size() - 1 ) %
m_points.size();
2602 if( new_start_idx <= start_idx )
2605 start_idx = new_start_idx;
2610 if( new_points.size() == 1 )
2612 new_points.push_back(
m_points.back() );
2613 new_shapes.push_back(
m_shapes.back() );
2620 new_points.push_back(
m_points.back() );
2621 new_shapes.push_back(
m_shapes.back() );
2643 int i_start = l.
Find( m );
2644 int i_end = l.
Find( n );
2646 if( i_start > i_end )
2649 i_start = l.
Find( m );
2650 i_end = l.
Find( n );
2653 aPre = l.
Slice( 0, i_start );
2654 aPost = l.
Slice( i_end, -1 );
2655 aMid = l.
Slice( i_start, i_end );
2662 std::vector<VECTOR2I> pts_unique;
2663 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2696 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2701 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2702 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2704 pts_unique.push_back(
CPoint( i ) );
2705 shapes_unique.push_back( shapeToKeep );
2712 np = pts_unique.size();
2726 && (
SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2727 ||
SEG( p0, pts_unique[n + 2] ).Collinear(
SEG( p0, pts_unique[n + 1] ) ) ) )
2732 m_shapes.push_back( shapes_unique[i] );
2739 m_points.push_back( pts_unique[np - 1] );
2740 m_shapes.push_back( shapes_unique[np - 1] );
2749 m_points.push_back( pts_unique[np - 2] );
2750 m_shapes.push_back( shapes_unique[np - 2] );
2753 m_points.push_back( pts_unique[np - 1] );
2754 m_shapes.push_back( shapes_unique[np - 1] );
2763 bool aSimplify )
const
2769 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2787 outline.
Split( start,
true );
2790 const int idA = outline.
Find( start );
2791 const int idB = outline.
Find(
end );
2793 if( idA == -1 || idB == -1 )
2799 for(
int i = idA;; )
2818 for(
int i = idB;; )
2837 if( aLeft.
CPoint( 0 ) != start )
2840 wxASSERT( aLeft.
CPoint( 0 ) == start );
2843 if( aRight.
CPoint( 0 ) != start )
2846 wxASSERT( aRight.
CPoint( 0 ) == start );
2850 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2851 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2853 if( sideLeft == 0 || sideRight == 0 )
2856 if( sideLeft == sideRight )
2859 if( sideLeft > 0 && sideRight < 0 )
2860 std::swap( aLeft, aRight );
2887 m_finished( false ),
2897 if( ipNext.
y == m_point.y )
2899 if( ( ipNext.
x == m_point.x )
2900 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2908 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2910 if( ip.
x >= m_point.x )
2912 if( ipNext.
x > m_point.x )
2914 m_state = 1 - m_state;
2918 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2919 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2928 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2929 m_state = 1 - m_state;
2934 if( ipNext.
x > m_point.x )
2936 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2937 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2946 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2947 m_state = 1 - m_state;
2960 m_lastPoint = aPolyline.
CPoint( 0 );
2961 m_firstPoint = aPolyline.
CPoint( 0 );
2966 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
2968 auto p = aPolyline.
CPoint( i );
2970 if( !processVertex( m_lastPoint, p ) )
2981 processVertex( m_lastPoint, m_firstPoint );
3007 size_t nextIdx = aSegment + 1;
3009 if( nextIdx >
m_shapes.size() - 1 )
3038 size_t prevIndex = aIndex - 1;
3042 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.
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 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)
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