35 return (
T( 0 ) < aVal ) - ( aVal <
T( 0 ) );
44 const T mid = (lo + hi + 1) / 2;
68 T r = (
T) std::sqrt( (
double) x );
70 while( r < sqrt_max && r * r < x )
73 while( r > sqrt_max || r * r > x )
95 for(
int i = 0; i < 4; i++ )
96 m = std::min( m, pts[i].SquaredEuclideanNorm() );
107 return std::abs( ( thisAngle - otherAngle ).Normalize180() );
133 const ecoord pts_dist[4] =
135 ( pts_origin[0] -
A ).SquaredEuclideanNorm(),
136 ( pts_origin[1] -
B ).SquaredEuclideanNorm(),
137 ( pts_origin[2] - aSeg.
A ).SquaredEuclideanNorm(),
138 ( pts_origin[3] - aSeg.
B ).SquaredEuclideanNorm()
143 for(
int i = 0; i < 4; i++ )
145 if( pts_dist[i] < pts_dist[min_i] )
149 return *pts_out[min_i];
187 const ecoord pts_dist[4] =
189 ( pts_origin[0] -
A ).SquaredEuclideanNorm(),
190 ( pts_origin[1] -
B ).SquaredEuclideanNorm(),
191 ( pts_origin[2] - aSeg.
A ).SquaredEuclideanNorm(),
192 ( pts_origin[3] - aSeg.
B ).SquaredEuclideanNorm()
197 for(
int i = 0; i < 4; i++ )
199 if( pts_dist[i] < pts_dist[min_i] )
203 aPtA = *pts_a_out[min_i];
204 aPtB = *pts_b_out[min_i];
205 aDistSq = pts_dist[min_i];
214 int seg1_start, seg1_end, seg2_start, seg2_end;
215 int coord1_start, coord1_end;
219 seg1_start =
A.x; seg1_end =
B.x;
220 seg2_start = aSeg.
A.
x; seg2_end = aSeg.
B.
x;
221 coord1_start =
A.y; coord1_end =
B.y;
225 seg1_start =
A.y; seg1_end =
B.y;
226 seg2_start = aSeg.
A.
y; seg2_end = aSeg.
B.
y;
227 coord1_start =
A.x; coord1_end =
B.x;
231 const int seg1_min = std::min( seg1_start, seg1_end );
232 const int seg1_max = std::max( seg1_start, seg1_end );
233 const int seg2_min = std::min( seg2_start, seg2_end );
234 const int seg2_max = std::max( seg2_start, seg2_end );
237 const bool overlaps = seg1_max >= seg2_min && seg2_max >= seg1_min;
242 if( aIgnoreEndpoints )
245 const int overlap_start = std::max( seg1_min, seg2_min );
246 const int overlap_end = std::min( seg1_max, seg2_max );
249 if( overlap_start == overlap_end )
253 bool isEndpointTouch =
false;
256 if( overlap_start == seg1_min || overlap_start == seg1_max )
259 if( overlap_start == seg2_min || overlap_start == seg2_max )
261 isEndpointTouch =
true;
265 if( isEndpointTouch )
274 const int overlap_start = std::max( seg1_min, seg2_min );
275 const int overlap_end = std::min( seg1_max, seg2_max );
276 const int intersection_proj = ( overlap_start + overlap_end ) / 2;
279 int intersection_other;
280 if( seg1_end != seg1_start )
283 intersection_other = coord1_start +
static_cast<int>(
284 rescale( intersection_proj - seg1_start, coord1_end - coord1_start, seg1_end - seg1_start ) );
289 intersection_other = coord1_start;
294 *aPt =
VECTOR2I( intersection_proj, intersection_other );
296 *aPt =
VECTOR2I( intersection_other, intersection_proj );
309 const int this_min_x = std::min(
A.x,
B.x );
310 const int this_max_x = std::max(
A.x,
B.x );
311 const int this_min_y = std::min(
A.y,
B.y );
312 const int this_max_y = std::max(
A.y,
B.y );
314 const int other_min_x = std::min( aSeg.
A.
x, aSeg.
B.
x );
315 const int other_max_x = std::max( aSeg.
A.
x, aSeg.
B.
x );
316 const int other_min_y = std::min( aSeg.
A.
y, aSeg.
B.
y );
317 const int other_max_y = std::max( aSeg.
A.
y, aSeg.
B.
y );
319 if( this_max_x < other_min_x || other_max_x < this_min_x ||
320 this_max_y < other_min_y || other_max_y < this_min_y )
334 if( determinant == 0 )
338 const ecoord collinear_test = dir1.
Cross( offset );
340 if( collinear_test != 0 )
351 if( aSeg.
A == aSeg.
B )
383 if( determinant > 0 )
386 if( param1_num < 0 || param1_num > determinant ||
387 param2_num < 0 || param2_num > determinant )
393 if( param1_num > 0 || param1_num < determinant ||
394 param2_num > 0 || param2_num < determinant )
399 if( aIgnoreEndpoints &&
400 ( param1_num == 0 || param1_num == determinant ) &&
401 ( param2_num == 0 || param2_num == determinant ) )
411 rescale( param1_num, dir2.
y, determinant ) );
415 constexpr ecoord max_coord = std::numeric_limits<VECTOR2I::coord_type>::max();
416 constexpr ecoord min_coord = std::numeric_limits<VECTOR2I::coord_type>::min();
441 if(
intersects( aSeg, aIgnoreEndpoints, aLines, &ip ) )
452 const VECTOR2L segDir = segB - segA;
458 const double intersect_y = aSlope *
A.x + aOffset;
459 const int intersect_y_int =
KiROUND( intersect_y );
462 const int seg_min_y = std::min(
A.y,
B.y );
463 const int seg_max_y = std::max(
A.y,
B.y );
465 if( intersect_y_int >= seg_min_y && intersect_y_int <= seg_max_y )
467 aIntersection =
VECTOR2I(
A.x, intersect_y_int );
473 const VECTOR2L lineDir( 1000,
static_cast<ecoord>( aSlope * 1000 ) );
479 const double expected_y = aSlope *
A.x + aOffset;
480 const double diff =
std::abs(
A.y - expected_y );
485 aIntersection = (
A +
B ) / 2;
499 const double numerator = aSlope * segA.
x + aOffset - segA.
y;
500 const double denominator = segDir.
y - aSlope * segDir.
x;
502 const double t = numerator / denominator;
505 if( t >= 0.0 && t <= 1.0 )
507 const double intersect_x = segA.
x + t * segDir.
x;
508 const double intersect_y = segA.
y + t * segDir.
y;
523 return SEG( aP, endPoint );
532 return SEG( aP, endPoint );
556 const ecoord clearance_sq =
static_cast<ecoord>( aClearance ) * aClearance;
559 auto checkDistance = [&](
ecoord dist,
ecoord& min_dist ) ->
bool
569 min_dist = std::min( min_dist, dist );
583 if( min_dist_sq < clearance_sq )
586 *aActual =
static_cast<int>(
isqrt( min_dist_sq ) );
592 *aActual =
static_cast<int>(
isqrt( min_dist_sq ) );
608 d.
x =
static_cast<int64_t
>(
B.x ) -
A.x;
609 d.
y =
static_cast<int64_t
>(
B.y ) -
A.y;
618 pa.
x =
static_cast<int64_t
>( aP.
x ) -
A.x;
619 pa.
y =
static_cast<int64_t
>( aP.
y ) -
A.y;
625 else if( t > l_squared )
710 if( g < 0 || g >
static_cast<double>( std::numeric_limits<ecoord>::max() ) )
723 ecoord det = p * aP.
x + q * aP.
y + r;
728 dist_sq =
rescale( det, det, l );
733 return static_cast<int>( aDetermineSide ?
sgn( det ) * dist :
std::abs( dist ) );
760 aD1 =
sgn( det1 ) * dsq1;
761 aD2 =
sgn( det2 ) * dsq2;
774 return std::abs( d1_sq ) <= thresholdSquared &&
std::abs( d2_sq ) <= thresholdSquared;
786 return std::abs( d1_sq - d2_sq ) <= thresholdSquared;
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
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
bool IntersectsLine(double aSlope, double aOffset, VECTOR2I &aIntersection) const
Check if this segment intersects a line defined by slope aSlope and offset aOffset.
bool intersects(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false, VECTOR2I *aPt=nullptr) const
VECTOR2I::extended_type ecoord
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
bool Intersects(const SEG &aSeg) const
bool checkCollinearOverlap(const SEG &aSeg, bool useXAxis, bool aIgnoreEndpoints, VECTOR2I *aPt) const
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 Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
SEG()
Create an empty (0, 0) segment.
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
ecoord SquaredLength() const
bool ApproxPerpendicular(const SEG &aSeg) const
bool ApproxCollinear(const SEG &aSeg, int aDistanceThreshold=1) const
bool mutualDistanceSquared(const SEG &aSeg, ecoord &aD1, ecoord &aD2) const
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
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Define a general 2D-vector/point.
constexpr extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
static constexpr extended_type ECOORD_MAX
VECTOR2_TRAITS< int32_t >::extended_type extended_type
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
static coord2_t cross_product(const VECTOR2I &O, const VECTOR2I &A, const VECTOR2I &B)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
constexpr T sqrt_helper(T x, T lo, T hi)
static constexpr T sqrt_max_typed
std::optional< VECTOR2I > OPT_VECTOR2I
wxString result
Test unit parsing edge cases and error handling.
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I
VECTOR2< int64_t > VECTOR2L