33#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 );
111 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
112 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
126 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
127 const std::vector<SHAPE_ARC>& aArcBuffer ) :
129 m_closed( true ), m_width( 0 )
131 std::map<ssize_t, ssize_t> loadedArcs;
136 [&]( ssize_t aArcIndex ) -> ssize_t
142 else if( loadedArcs.count( aArcIndex ) == 0 )
144 loadedArcs.insert( { aArcIndex,
m_arcs.size() } );
145 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
148 return loadedArcs.at( aArcIndex );
151 for(
size_t ii = 0; ii < aPath.size(); ++ii )
153 Append( aPath[ii].x, aPath[ii].y );
155 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
156 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
170 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
171 std::vector<SHAPE_ARC>& aArcBuffer )
const
173 ClipperLib::Path c_path;
175 bool orientation =
Area(
false ) >= 0;
176 ssize_t shape_offset = aArcBuffer.size();
178 if( orientation != aRequiredOrientation )
184 c_path.reserve( pointCount );
186 for(
int i = 0; i < pointCount; i++ )
191 size_t z_value_ptr = aZValueBuffer.size();
192 aZValueBuffer.push_back( z_value );
194 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
197 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
204 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
205 std::vector<SHAPE_ARC>& aArcBuffer )
const
207 Clipper2Lib::Path64 c_path;
209 bool orientation =
Area(
false ) >= 0;
210 ssize_t shape_offset = aArcBuffer.size();
212 if( orientation != aRequiredOrientation )
218 c_path.reserve( pointCount );
220 for(
int i = 0; i < pointCount; i++ )
225 size_t z_value_ptr = aZValueBuffer.size();
226 aZValueBuffer.push_back( z_value );
228 c_path.emplace_back( vertex.
x, vertex.
y, z_value_ptr );
231 aArcBuffer.insert( aArcBuffer.end(), input.
m_arcs.begin(), input.
m_arcs.end() );
244 size_t rotations = 0;
295 aArcIndex +=
m_arcs.size();
297 if( aArcIndex >=
static_cast<ssize_t
>(
m_arcs.size() ) )
304 [&]( ssize_t& aShapeIndex )
306 if( aShapeIndex == aArcIndex )
309 if( aShapeIndex > aArcIndex )
314 std::swap( sh.first, sh.second );
324 wxCHECK_MSG( aArcIndex <
m_arcs.size(), ,
325 wxT(
"Invalid arc index requested." ) );
334 m_arcs[aArcIndex] = newArc;
349 wxCHECK_MSG( aPtIndex <
static_cast<ssize_t
>(
m_shapes.size() ), ,
350 wxT(
"Invalid point index requested." ) );
354 if( aCoincident || aPtIndex == 0 )
357 ssize_t firstArcIndex =
m_shapes[aPtIndex].first;
361 amendArc( firstArcIndex, newStart, newEnd );
376 ssize_t currArcIdx =
ArcIndex( aPtIndex );
391 if( !aCoincident &&
ArcIndex( aPtIndex - 1 ) != currArcIdx )
394 m_arcs[currArcIdx] = newArc2;
398 m_arcs[currArcIdx] = newArc1;
399 m_arcs.insert(
m_arcs.begin() + currArcIdx + 1, newArc2 );
403 m_shapes[aPtIndex].second = currArcIdx + 1;
408 for(
int i = aPtIndex; i <
PointCount(); i++ )
441 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
443 if( dist_sq < closest_dist_sq )
446 closest_dist_sq = dist_sq;
448 if( closest_dist_sq == 0 )
452 if( closest_dist_sq < clearance_sq && !aActual )
457 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
460 *aLocation = nearest;
463 *aActual = sqrt( closest_dist_sq );
498 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
500 if( dist_sq < closest_dist_sq )
503 closest_dist_sq = dist_sq;
505 if( closest_dist_sq == 0 )
509 if( closest_dist_sq < clearance_sq && !aActual )
514 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
517 *aLocation = nearest;
520 *aActual = sqrt( closest_dist_sq );
526 for(
size_t i = 0; i <
ArcCount(); i++ )
531 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
533 if( arc.
Collide( aP, aClearance, aActual, aLocation ) )
547 arc.Rotate( aAngle, aCenter );
574 if( dist_sq < closest_dist_sq )
579 closest_dist_sq = dist_sq;
581 if( closest_dist_sq == 0)
585 if( closest_dist_sq < clearance_sq && !aActual )
590 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
593 *aLocation = nearest;
596 *aActual = sqrt( closest_dist_sq );
632 if( dist_sq < closest_dist_sq )
637 closest_dist_sq = dist_sq;
639 if( closest_dist_sq == 0 )
643 if( closest_dist_sq < clearance_sq && !aActual )
648 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
651 *aLocation = nearest;
654 *aActual = sqrt( closest_dist_sq );
659 int closest_dist = std::numeric_limits<int>::max();
662 closest_dist = sqrt( closest_dist_sq );
665 for(
size_t i = 0; i <
ArcCount(); i++ )
671 wxASSERT_MSG( arc.
GetWidth() == 0, wxT(
"Invalid arc width - should be zero" ) );
673 if( arc.
Collide( aSeg, aClearance, aActual || aLocation ? &dist :
nullptr,
674 aLocation ? &nearest :
nullptr ) )
679 if( dist < closest_dist )
684 if( closest_dist == 0 || closest_dist < aClearance )
687 *aLocation = nearest;
690 *aActual = closest_dist;
712 [&]( ssize_t& aShapeIndex )
715 aShapeIndex = a.
m_arcs.size() - aShapeIndex - 1;
724 std::swap( sh.first, sh.second );
740 for( ssize_t arcIndex =
m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
756 for(
size_t i = 0; i <
ArcCount(); i++ )
757 l +=
CArcs()[i].GetLength();
768 pt.x = -pt.x + 2 * aRef.
x;
771 pt.y = -pt.y + 2 * aRef.
y;
775 arc.Mirror( aX, aY, aRef );
791 Remove( aStartIndex, aEndIndex );
792 Insert( aStartIndex, aP );
802 if( aStartIndex < 0 )
806 wxASSERT( aStartIndex <= aEndIndex );
807 wxASSERT( aEndIndex <
static_cast<int>(
m_points.size() ) );
814 Remove( aStartIndex, aEndIndex );
827 Remove( aStartIndex, aEndIndex );
838 Remove( aStartIndex, aEndIndex );
845 size_t prev_arc_count =
m_arcs.size();
846 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.
m_shapes;
848 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
851 [&]( ssize_t& aShape )
854 aShape += prev_arc_count;
858 m_shapes.insert(
m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
879 if( aStartIndex < 0 )
902 if( aStartIndex > aEndIndex )
908 std::set<size_t> extra_arcs;
909 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
912 extra_arcs.insert( aShapeIndex );
916 for(
int i = aStartIndex; i <= aEndIndex; i++ )
920 if( i == aStartIndex )
922 logArcIdxRemoval(
m_shapes[i].second );
929 else if( i == aEndIndex )
931 logArcIdxRemoval(
m_shapes[i].first );
934 assert( i > aStartIndex || (
IsSharedPt( i - 1 )
946 for(
auto arc : extra_arcs )
976 int found_index =
Find( aP );
978 if( found_index >= 0 && aExact )
988 if( dist < min_dist && seg.
A != aP && seg.
B != aP )
991 if( found_index < 0 )
993 else if( s < found_index )
1007 size_t newIndex =
static_cast<size_t>( ii ) + 1;
1031 if( aThreshold == 0 )
1038 if( (
CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
1061 wxCHECK2_MSG(
m_points.size() ==
m_shapes.size(),
return 0,
"Invalid chain!" );
1092 if( aPointIndex < 0 )
1095 if( aPointIndex < 0 )
1101 if( aPointIndex >= lastIndex )
1106 if( aPointIndex == lastIndex - 1 )
1115 return aPointIndex + 1;
1119 int arcStart = aPointIndex;
1123 wxCHECK2_MSG(
m_shapes[aPointIndex].first !=
SHAPE_IS_PT,
return -1,
"malformed chain!" );
1125 ssize_t currentArcIdx =
ArcIndex( aPointIndex );
1128 while( aPointIndex < lastIndex &&
ArcIndex( aPointIndex ) == currentArcIdx )
1135 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1138 if( aPointIndex == lastIndex )
1160 [&]( ssize_t& aIdx )
1170 if( aPointIndex < 0 )
1173 if( aPointIndex >=
PointCount() || aPointIndex < 0 )
1182 int start = aPointIndex;
1183 int end = aPointIndex;
1184 int arcIdx =
ArcIndex( aPointIndex );
1189 while( start > 0 &&
ArcIndex(
static_cast<ssize_t
>( start ) - 1 ) == arcIdx )
1193 if( !
IsArcEnd( end ) || start == end )
1207 if( aStartIndex < 0 )
1217 int numPoints =
static_cast<int>(
m_points.size() );
1222 ssize_t arcToSplitIndex =
ArcIndex( aStartIndex );
1226 for(
size_t i = aStartIndex; arcToSplitIndex ==
ArcIndex( i ); i++ )
1243 rv.
m_arcs.push_back( newArc );
1248 for(
int i = aStartIndex; i <= aEndIndex && i < numPoints; i =
NextShape( i ) )
1254 bool isLastShape = nextShape < 0;
1258 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1259 || ( nextShape > aEndIndex ) )
1261 if( i == aEndIndex )
1273 for( ; i <= aEndIndex && i < numPoints; i++ )
1293 rv.
m_arcs.push_back( newArc );
1310 wxT(
"Still on an arc segment, we missed something..." ) );
1312 if( i == aStartIndex )
1315 bool nextPointIsArc = isLastShape ? false :
IsArcSegment( nextShape );
1317 if( !nextPointIsArc && i <
SegmentCount() && i < aEndIndex )
1336 size_t num_arcs =
m_arcs.size();
1339 auto fixShapeIndices =
1340 [&](
const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1342 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1347 aIndex = aIndex + num_arcs;
1370 for(
int i = 1; i < aOtherLine.
PointCount(); i++ )
1375 ssize_t arcIndex = aOtherLine.
ArcIndex( i );
1405 chain.
m_arcs.push_back( aArc );
1406 chain.
m_arcs.back().SetWidth( 0 );
1426 wxCHECK( aVertex <
m_points.size(), );
1428 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1441 wxCHECK( aVertex <
m_points.size(), );
1443 if( aVertex > 0 &&
IsPtOnArc( aVertex ) )
1447 ssize_t arc_pos =
m_arcs.size();
1449 for(
auto arc_it =
m_shapes.rbegin() ;
1450 arc_it !=
m_shapes.rend() + aVertex;
1455 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1464 [&]( ssize_t& aIndex )
1466 if( aIndex >= arc_pos )
1478 m_points.insert(
m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1482 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1483 { arc_pos, SHAPE_IS_PT } );
1485 m_shapes.insert(
m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1519 aIp.push_back( is );
1524 sort( aIp.begin(), aIp.end(), comp );
1533 if( aIps.size() == 0 )
1535 aIps.push_back( aP );
1539 aIps.push_back( aP );
1544 bool aExcludeColinearAndTouching,
BOX2I* aChainBBox )
const
1546 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.
BBox();
1551 const BOX2I bb_cur( a.
A, a.
B - a.
A );
1571 if( coll && ! aExcludeColinearAndTouching )
1647 bool indexMatch =
true;
1657 indexMatch = ( i == aIndex );
1675 bool aUseBBoxCache )
const
1687 bool inside =
false;
1702 for(
int i = 0; i < pointCount; )
1705 const auto p2 =
GetPoint( i == pointCount ? 0 : i );
1706 const auto diff = p2 - p1;
1710 const int d =
rescale( diff.x, ( aPt.
y - p1.y ), diff.y );
1712 if( ( ( p1.y > aPt.
y ) != ( p2.y > aPt.
y ) ) && ( aPt.
x - p1.x < d ) )
1719 if( aAccuracy <= 1 )
1741 return ( hypot( dist.
x, dist.
y ) <= aAccuracy + 1 ) ? 0 : -1;
1748 if( s.
A == aPt || s.
B == aPt )
1751 if( s.
Distance( aPt ) <= aAccuracy + 1 )
1770 if( s.
A == aP || s.
B == aP )
1789 if( s1 + 1 != s2 &&
CSegment( s1 ).Contains( s2a ) )
1797 else if(
CSegment( s1 ).Contains( s2b ) &&
1825 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
1889const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
1892 auto pointsClose = [](
const VECTOR2I& aPt1,
const VECTOR2I& aPt2 ) ->
bool
1894 return (
VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
1897 auto collideArcSeg = [&pointsClose](
const SHAPE_ARC& aArc,
const SEG& aSeg,
int aClearance = 0,
1903 std::vector<VECTOR2I> candidatePts = circle.
Intersect( aSeg );
1905 for(
const VECTOR2I& candidate : candidatePts )
1908 if( aArc.
GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
1911 if( aSeg.B == aArc.
GetP0() && pointsClose( candidate, aSeg.B ) )
1914 bool collides = aArc.
Collide( candidate, aClearance,
nullptr, aLocation );
1926 std::vector<VECTOR2I> candidatePts;
1928 aArc1.
Intersect( aArc2, &candidatePts );
1930 for(
const VECTOR2I& candidate : candidatePts )
1933 if( aArc1.
GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.
GetP1() ) )
1936 if( aArc2.GetP1() == aArc1.
GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
1940 *aLocation = candidate;
1948 auto collideSegSeg = [
this](
int s1,
int s2,
INTERSECTION& is )
1955 if( s1 + 1 != s2 && seg1.
Contains( s2a ) )
1958 is.index_their = s2;
1969 is.index_their = s2;
1980 is.index_their = s2;
1991 std::vector<SHAPE_KEY> shapeCache;
1992 for(
int si = 0; si != -1; si =
NextShape( si ) )
1996 shapeCache.emplace_back( si, arci,
2001 for(
size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2003 for(
size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2052 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2057 bool aAllowInternalShapePoints )
const
2065 int min_d = std::numeric_limits<int>::max();
2079 if( !aAllowInternalShapePoints )
2102 return nearestArc.
GetP1();
2104 return nearestArc.
GetP0();
2124 dist = std::numeric_limits<int>::max();
2137 return CPoint( nearest );
2143 int min_d = std::numeric_limits<int>::max();
2163 std::stringstream ss;
2165 ss <<
"SHAPE_LINE_CHAIN( { ";
2175 ss <<
"}, " << (
m_closed ?
"true" :
"false" );
2196 if( a.m_points.size() != b.
m_points.size() )
2199 for(
int i = 0; i < a.PointCount(); i++ )
2201 if( a.CPoint( i ) != b.
CPoint( i ) )
2231 if( n_pts > aStream.str().size() )
2237 if( n_arcs > aStream.str().size() )
2240 for(
size_t i = 0; i < n_pts; i++ )
2252 for(
size_t i = 0; i < n_arcs; i++ )
2274 if( aPathLength == 0 )
2282 if( total + l >= aPathLength )
2285 return s.
A + d.
Resize( aPathLength - total );
2305 for(
int i = 0, j = size - 1; i < size; ++i )
2313 return std::fabs( area * 0.5 );
2321 std::vector<VECTOR2I> pts_unique;
2322 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2353 std::pair<ssize_t,ssize_t> shapeToKeep =
m_shapes[i];
2358 assert( shapeToKeep.first <
static_cast<int>(
m_arcs.size() ) );
2359 assert( shapeToKeep.second <
static_cast<int>(
m_arcs.size() ) );
2361 pts_unique.push_back(
CPoint( i ) );
2362 shapes_unique.push_back( shapeToKeep );
2370 for(
size_t ii = 0; ii < pts_unique.size(); ++ii )
2372 const VECTOR2I p0 = pts_unique[ii];
2375 m_shapes.push_back( shapes_unique[ii] );
2386 std::vector<VECTOR2I> new_points;
2387 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2389 new_points.reserve(
m_points.size() );
2390 new_shapes.reserve(
m_shapes.size() );
2392 auto is_skip = [
this](
size_t i,
size_t j,
size_t k )
2402 for(
size_t ii = 0; ii <
m_points.size(); )
2404 new_points.push_back(
m_points[ii] );
2405 new_shapes.push_back(
m_shapes[ii] );
2406 size_t jj = ( ii + 1 ) %
m_points.size();
2407 size_t kk = ( ii + 2 ) %
m_points.size();
2411 || is_skip( ii, jj, kk ) )
2417 while( ii != kk && jj > ii && !( kk < ii && !
m_closed ) )
2419 bool too_far =
false;
2421 for(
size_t ll = ( ii + 1 ) %
m_points.size(); ll != kk;
2422 ll = ( ll + 1 ) %
m_points.size() )
2431 if( too_far || is_skip( ii, jj, kk ) )
2438 if( ii == kk || jj <= ii )
2445 if( new_points.size() == 1 )
2447 new_points.push_back(
m_points.back() );
2448 new_shapes.push_back(
m_shapes.back() );
2470 int i_start = l.
Find( m );
2471 int i_end = l.
Find( n );
2473 if( i_start > i_end )
2476 i_start = l.
Find( m );
2477 i_end = l.
Find( n );
2480 aPre = l.
Slice( 0, i_start );
2481 aPost = l.
Slice( i_end, -1 );
2482 aMid = l.
Slice( i_start, i_end );
2488 bool aSimplify )
const
2494 poly.
OffsetLineChain( *
this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2512 outline.
Split( start,
true );
2513 outline.
Split( end,
true );
2515 const int idA = outline.
Find( start );
2516 const int idB = outline.
Find( end );
2518 if( idA == -1 || idB == -1 )
2524 for(
int i = idA;; )
2543 for(
int i = idB;; )
2562 if( aLeft.
CPoint( 0 ) != start )
2565 wxASSERT( aLeft.
CPoint( 0 ) == start );
2568 if( aRight.
CPoint( 0 ) != start )
2571 wxASSERT( aRight.
CPoint( 0 ) == start );
2575 int sideLeft = base.
Side( aLeft.
CPoint( 1 ) );
2576 int sideRight = base.
Side( aRight.
CPoint( 1 ) );
2578 if( sideLeft == 0 || sideRight == 0 )
2581 if( sideLeft == sideRight )
2584 if( sideLeft > 0 && sideRight < 0 )
2585 std::swap( aLeft, aRight );
2612 m_finished( false ),
2622 if( ipNext.
y == m_point.y )
2624 if( ( ipNext.
x == m_point.x )
2625 || ( ip.
y == m_point.y && ( ( ipNext.
x > m_point.x ) == ( ip.
x < m_point.x ) ) ) )
2633 if( ( ip.
y < m_point.y ) != ( ipNext.
y < m_point.y ) )
2635 if( ip.
x >= m_point.x )
2637 if( ipNext.
x > m_point.x )
2639 m_state = 1 - m_state;
2643 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2644 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2653 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2654 m_state = 1 - m_state;
2659 if( ipNext.
x > m_point.x )
2661 double d = (double) ( ip.
x - m_point.x ) * ( ipNext.
y - m_point.y )
2662 - (
double) ( ipNext.
x - m_point.x ) * ( ip.
y - m_point.y );
2671 if( ( d > 0 ) == ( ipNext.
y > ip.
y ) )
2672 m_state = 1 - m_state;
2685 m_lastPoint = aPolyline.
CPoint( 0 );
2686 m_firstPoint = aPolyline.
CPoint( 0 );
2691 for(
int i = 1; i < aPolyline.
PointCount(); i++ )
2693 auto p = aPolyline.
CPoint( i );
2695 if( !processVertex( m_lastPoint, p ) )
2706 processVertex( m_lastPoint, m_firstPoint );
2732 size_t nextIdx = aSegment + 1;
2734 if( nextIdx >
m_shapes.size() - 1 )
2763 size_t prevIndex = aIndex - 1;
2767 else if( aIndex >
m_points.size() -1 )
bool Intersects(const BOX2< Vec > &aRect) const
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Represent basic circle geometry with utility geometry functions.
std::vector< VECTOR2I > Intersect(const CIRCLE &aCircle) const
Compute the intersection points between this circle and aCircle.
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
ecoord SquaredDistance(const SEG &aSeg) const
VECTOR2I::extended_type ecoord
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
int Length() const
Return the length (this).
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
static SEG::ecoord Square(int a)
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
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.
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.
int Intersect(const SHAPE_ARC &aArc, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aArc.
static double DefaultAccuracyForPCB()
const VECTOR2I & GetP0() const
const VECTOR2I & GetCenter() const
POINT_INSIDE_TRACKER(const VECTOR2I &aPoint)
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual BOX2I * GetCachedBBox() const
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
virtual bool IsClosed() const =0
virtual const SEG GetSegment(int aIndex) const =0
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const override
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
const std::optional< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
bool Parse(std::stringstream &aStream) override
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Check if point aP is closer to (or on) an edge or vertex of the line chain.
std::vector< SHAPE_ARC > m_arcs
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
ClipperLib::Path convertToClipper(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
const VECTOR2I PointAlong(int aPathLength) const
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
std::vector< VECTOR2I > m_points
array of vertices
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
SHAPE_LINE_CHAIN()
Initialize an empty line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
bool IsArcEnd(size_t aIndex) const
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
void TransformToPolygon(SHAPE_POLY_SET &aBuffer, int aError, ERROR_LOC aErrorLoc) const override
Fills a SHAPE_POLY_SET with a polygon representation of this shape.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
BOX2I m_bbox
cached bounding box
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
bool m_closed
is the line chain closed?
const std::vector< SHAPE_ARC > & CArcs() const
const std::optional< INTERSECTION > SelfIntersectingWithArcs() const
Check if the line chain is self-intersecting.
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both).
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
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...
const std::string Format(bool aCplusPlus=true) const override
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.
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
static const ssize_t SHAPE_IS_PT
bool OffsetLine(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, SHAPE_LINE_CHAIN &aLeft, SHAPE_LINE_CHAIN &aRight, bool aSimplify=false) const
Creates line chains aLeft and aRight offset to this line chain.
Represent a set of closed polygons.
bool HasHoles() const
Return true if the polygon set has any holes.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
int OutlineCount() const
Return the number of outlines in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
An abstract shape on 2D plane.
VECTOR2I::extended_type ecoord
static constexpr extended_type ECOORD_MAX
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
CORNER_STRATEGY
define how inflate transform build inflated polygon
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
std::optional< VECTOR2I > OPT_VECTOR2I
@ SH_LINE_CHAIN
line chain (polyline)
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
std::vector< FAB_LAYER_COLOR > dummy
BOX2I_MINMAX(const SEG &aSeg)
bool Intersects(const BOX2I_MINMAX &aOther) const
BOX2I_MINMAX(const SHAPE_ARC &aArc)
BOX2I_MINMAX(const BOX2I &aBox)
BOX2I_MINMAX(int aLeft, int aTop, int aRight, int aBottom)
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)
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.
bool TestSegmentHitFast(const VECTOR2I &aRefPoint, const VECTOR2I &aStart, const VECTOR2I &aEnd, int aDist)
Test if a point hits a line segment within a given distance.
double EuclideanNorm(const VECTOR2I &vector)
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< double > VECTOR2D