35 return (
T( 0 ) < aVal ) - ( aVal <
T( 0 ) );
44 const T mid = (lo + hi + 1) / 2;
46 return sqrt_helper<T>(x, lo, mid - 1);
54 return sqrt_helper<T>(x, 0, x / 2 + 1);
63 T sqrt_max = sqrt_max_typed<T>;
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() );
109 return std::min(
ANGLE_180 - angle, angle );
135 const ecoord pts_dist[4] =
137 ( pts_origin[0] -
A ).SquaredEuclideanNorm(),
138 ( pts_origin[1] -
B ).SquaredEuclideanNorm(),
139 ( pts_origin[2] - aSeg.
A ).SquaredEuclideanNorm(),
140 ( pts_origin[3] - aSeg.
B ).SquaredEuclideanNorm()
145 for(
int i = 0; i < 4; i++ )
147 if( pts_dist[i] < pts_dist[min_i] )
151 return *pts_out[min_i];
189 const ecoord pts_dist[4] =
191 ( pts_origin[0] -
A ).SquaredEuclideanNorm(),
192 ( pts_origin[1] -
B ).SquaredEuclideanNorm(),
193 ( pts_origin[2] - aSeg.
A ).SquaredEuclideanNorm(),
194 ( pts_origin[3] - aSeg.
B ).SquaredEuclideanNorm()
199 for(
int i = 0; i < 4; i++ )
201 if( pts_dist[i] < pts_dist[min_i] )
205 aPtA = *pts_a_out[min_i];
206 aPtB = *pts_b_out[min_i];
207 aDistSq = pts_dist[min_i];
226 if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
229 if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
232 if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
240 if( abs( result.
x ) > std::numeric_limits<VECTOR2I::coord_type>::max()
241 || abs( result.
y ) > std::numeric_limits<VECTOR2I::coord_type>::max() )
246 *aPt =
VECTOR2I( (
int) result.
x, (
int) result.
y );
263 if(
intersects( aSeg, aIgnoreEndpoints, aLines, &ip ) )
275 return SEG( aP, endPoint );
284 return SEG( aP, endPoint );
298 if(
ccw(
A, aSeg.
A, aSeg.
B ) !=
ccw(
B, aSeg.
A, aSeg.
B ) &&
310 auto checkCollision =
320 else if( dist_sq < clearance_sq )
326 *aActual = int(
isqrt( dist_sq ) );
345 if( checkCollision(
false ) )
350 if( checkCollision(
false ) )
355 if( checkCollision(
false ) )
360 return checkCollision(
true );
374 d.
x =
static_cast<int64_t
>(
B.x ) -
A.x;
375 d.
y =
static_cast<int64_t
>(
B.y ) -
A.y;
384 pa.
x =
static_cast<int64_t
>( aP.
x ) -
A.x;
385 pa.
y =
static_cast<int64_t
>( aP.
y ) -
A.y;
391 else if( t > l_squared )
456 ab.
x =
static_cast<int64_t
>(
B.x ) -
A.x;
457 ab.
y =
static_cast<int64_t
>(
B.y ) -
A.y;
458 ap.
x =
static_cast<int64_t
>( aP.
x ) -
A.x;
459 ap.
y =
static_cast<int64_t
>( aP.
y ) -
A.y;
471 bp.
x =
static_cast<int64_t
>( aP.
x ) -
B.x;
472 bp.
y =
static_cast<int64_t
>( aP.
y ) -
B.y;
482 if( g < 0 || g >
static_cast<double>( std::numeric_limits<ecoord>::max() ) )
485 return KiROUND<double, ecoord>( g );
495 ecoord det = p * aP.
x + q * aP.
y + r;
500 dist_sq =
rescale( det, det, l );
505 return static_cast<int>( aDetermineSide ?
sgn( det ) * dist :
std::abs( dist ) );
532 aD1 =
sgn( det1 ) * dsq1;
533 aD2 =
sgn( det2 ) * dsq2;
546 return std::abs( d1_sq ) <= thresholdSquared &&
std::abs( d2_sq ) <= thresholdSquared;
558 return std::abs( d1_sq - d2_sq ) <= thresholdSquared;
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 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
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 ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
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.
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< 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 constexpr EDA_ANGLE ANGLE_180
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
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
VECTOR2< int32_t > VECTOR2I