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];
216 int seg1_start, seg1_end, seg2_start, seg2_end;
217 int coord1_start, coord1_end;
221 seg1_start =
A.x; seg1_end =
B.x;
222 seg2_start = aSeg.
A.
x; seg2_end = aSeg.
B.
x;
223 coord1_start =
A.y; coord1_end =
B.y;
227 seg1_start =
A.y; seg1_end =
B.y;
228 seg2_start = aSeg.
A.
y; seg2_end = aSeg.
B.
y;
229 coord1_start =
A.x; coord1_end =
B.x;
233 const int seg1_min = std::min( seg1_start, seg1_end );
234 const int seg1_max = std::max( seg1_start, seg1_end );
235 const int seg2_min = std::min( seg2_start, seg2_end );
236 const int seg2_max = std::max( seg2_start, seg2_end );
239 const bool overlaps = seg1_max >= seg2_min && seg2_max >= seg1_min;
244 if( aIgnoreEndpoints )
247 const int overlap_start = std::max( seg1_min, seg2_min );
248 const int overlap_end = std::min( seg1_max, seg2_max );
251 if( overlap_start == overlap_end )
255 bool isEndpointTouch =
false;
258 if( overlap_start == seg1_min || overlap_start == seg1_max )
261 if( overlap_start == seg2_min || overlap_start == seg2_max )
263 isEndpointTouch =
true;
267 if( isEndpointTouch )
276 const int overlap_start = std::max( seg1_min, seg2_min );
277 const int overlap_end = std::min( seg1_max, seg2_max );
278 const int intersection_proj = ( overlap_start + overlap_end ) / 2;
281 int intersection_other;
282 if( seg1_end != seg1_start )
285 intersection_other = coord1_start +
static_cast<int>(
286 rescale( intersection_proj - seg1_start, coord1_end - coord1_start, seg1_end - seg1_start ) );
291 intersection_other = coord1_start;
296 *aPt =
VECTOR2I( intersection_proj, intersection_other );
298 *aPt =
VECTOR2I( intersection_other, intersection_proj );
311 const int this_min_x = std::min(
A.x,
B.x );
312 const int this_max_x = std::max(
A.x,
B.x );
313 const int this_min_y = std::min(
A.y,
B.y );
314 const int this_max_y = std::max(
A.y,
B.y );
316 const int other_min_x = std::min( aSeg.
A.
x, aSeg.
B.
x );
317 const int other_max_x = std::max( aSeg.
A.
x, aSeg.
B.
x );
318 const int other_min_y = std::min( aSeg.
A.
y, aSeg.
B.
y );
319 const int other_max_y = std::max( aSeg.
A.
y, aSeg.
B.
y );
321 if( this_max_x < other_min_x || other_max_x < this_min_x ||
322 this_max_y < other_min_y || other_max_y < this_min_y )
336 if( determinant == 0 )
340 const ecoord collinear_test = dir1.
Cross( offset );
342 if( collinear_test != 0 )
353 if( aSeg.
A == aSeg.
B )
385 if( determinant > 0 )
388 if( param1_num < 0 || param1_num > determinant ||
389 param2_num < 0 || param2_num > determinant )
395 if( param1_num > 0 || param1_num < determinant ||
396 param2_num > 0 || param2_num < determinant )
401 if( aIgnoreEndpoints &&
402 ( param1_num == 0 || param1_num == determinant ) &&
403 ( param2_num == 0 || param2_num == determinant ) )
413 rescale( param1_num, dir2.
y, determinant ) );
417 constexpr ecoord max_coord = std::numeric_limits<VECTOR2I::coord_type>::max();
418 constexpr ecoord min_coord = std::numeric_limits<VECTOR2I::coord_type>::min();
420 if( result.
x > max_coord || result.
x < min_coord ||
421 result.
y > max_coord || result.
y < min_coord )
426 *aPt =
VECTOR2I(
static_cast<int>( result.
x ),
static_cast<int>( result.
y ) );
443 if(
intersects( aSeg, aIgnoreEndpoints, aLines, &ip ) )
454 const VECTOR2L segDir = segB - segA;
460 const double intersect_y = aSlope *
A.x + aOffset;
461 const int intersect_y_int =
KiROUND( intersect_y );
464 const int seg_min_y = std::min(
A.y,
B.y );
465 const int seg_max_y = std::max(
A.y,
B.y );
467 if( intersect_y_int >= seg_min_y && intersect_y_int <= seg_max_y )
469 aIntersection =
VECTOR2I(
A.x, intersect_y_int );
475 const VECTOR2L lineDir( 1000,
static_cast<ecoord>( aSlope * 1000 ) );
481 const double expected_y = aSlope *
A.x + aOffset;
482 const double diff =
std::abs(
A.y - expected_y );
487 aIntersection = (
A +
B ) / 2;
501 const double numerator = aSlope * segA.
x + aOffset - segA.
y;
502 const double denominator = segDir.
y - aSlope * segDir.
x;
504 const double t = numerator / denominator;
507 if( t >= 0.0 && t <= 1.0 )
509 const double intersect_x = segA.
x + t * segDir.
x;
510 const double intersect_y = segA.
y + t * segDir.
y;
525 return SEG( aP, endPoint );
534 return SEG( aP, endPoint );
558 const ecoord clearance_sq =
static_cast<ecoord>( aClearance ) * aClearance;
561 auto checkDistance = [&](
ecoord dist,
ecoord& min_dist ) ->
bool
571 min_dist = std::min( min_dist, dist );
585 if( min_dist_sq < clearance_sq )
588 *aActual =
static_cast<int>(
isqrt( min_dist_sq ) );
594 *aActual =
static_cast<int>(
isqrt( min_dist_sq ) );
610 d.
x =
static_cast<int64_t
>(
B.x ) -
A.x;
611 d.
y =
static_cast<int64_t
>(
B.y ) -
A.y;
620 pa.
x =
static_cast<int64_t
>( aP.
x ) -
A.x;
621 pa.
y =
static_cast<int64_t
>( aP.
y ) -
A.y;
627 else if( t > l_squared )
712 if( g < 0 || g >
static_cast<double>( std::numeric_limits<ecoord>::max() ) )
715 return KiROUND<double, ecoord>( g );
725 ecoord det = p * aP.
x + q * aP.
y + r;
730 dist_sq =
rescale( det, det, l );
735 return static_cast<int>( aDetermineSide ?
sgn( det ) * dist :
std::abs( dist ) );
762 aD1 =
sgn( det1 ) * dsq1;
763 aD2 =
sgn( det2 ) * dsq2;
776 return std::abs( d1_sq ) <= thresholdSquared &&
std::abs( d2_sq ) <= thresholdSquared;
788 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.
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 coord2_t cross_product(const VECTOR2I &O, const VECTOR2I &A, const VECTOR2I &B)
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
VECTOR2< int64_t > VECTOR2L