66#ifdef USE_ALTERNATE_CENTER_ALGO
72 double bc = ( b.
x*b.
x + b.
y*b.
y ) / 2.0;
73 double cd = ( -d.
x*d.
x - d.
y*d.
y ) / 2.0;
74 double det = -b.
x*d.
y + d.
x*b.
y;
76 if( fabs(det) < 1.0e-6 )
80 aCenter->
x = ( -bc*d.
y - cd*b.
y ) * det;
81 aCenter->
y = ( b.
x*cd + d.
x*bc ) * det;
91 VECTOR2I vectSeg = aSegEnd - aSegStart;
92 VECTOR2I vectPoint = aTestPoint - aSegStart;
95 if( (
long long) vectSeg.
x * vectPoint.
y - (
long long) vectSeg.
y * vectPoint.
x )
98 if( ( (
long long) vectSeg.
x * vectPoint.
x + (
long long) vectSeg.
y * vectPoint.
y ) <
99 ( (
long long) vectPoint.
x * vectPoint.
x + (
long long) vectPoint.
y * vectPoint.
y ) )
114 int64_t dX_a, dY_a, dX_b, dY_b, dX_ab, dY_ab;
115 int64_t num_a, num_b, den;
123 dX_a = int64_t{ a_p2_l1.
x } - a_p1_l1.
x;
124 dY_a = int64_t{ a_p2_l1.
y } - a_p1_l1.
y;
125 dX_b = int64_t{ a_p2_l2.
x } - a_p1_l2.
x;
126 dY_b = int64_t{ a_p2_l2.
y } - a_p1_l2.
y;
127 dX_ab = int64_t{ a_p1_l2.
x } - a_p1_l1.
x;
128 dY_ab = int64_t{ a_p1_l2.
y } - a_p1_l1.
y;
130 den = dY_a * dX_b - dY_b * dX_a ;
136 num_a = dY_ab * dX_b - dY_b * dX_ab;
137 num_b = dY_ab * dX_a - dY_a * dX_ab;
140 if( aIntersectionPoint )
142 *aIntersectionPoint = a_p1_l1;
143 aIntersectionPoint->
x +=
KiROUND( dX_a * (
double )num_a / (
double )den );
144 aIntersectionPoint->
y +=
KiROUND( dY_a * (
double )num_b / (
double )den );
184 std::swap( xmax, xmin );
187 std::swap( ymax, ymin );
190 if( ( ymin - aRefPoint.
y > aDist ) || ( aRefPoint.
y - ymax > aDist ) )
193 if( ( xmin - aRefPoint.
x > aDist ) || ( aRefPoint.
x - xmax > aDist ) )
197 if( aStart.
x == aEnd.
x && aRefPoint.
y > ymin && aRefPoint.
y < ymax )
200 if( aStart.
y == aEnd.
y && aRefPoint.
x > xmin && aRefPoint.
x < xmax )
203 SEG segment( aStart, aEnd );
211 VECTOR2I startVector = aStart - aCenter;
212 VECTOR2I endVector = aEnd - aCenter;
216 EDA_ANGLE midPointRotAngle = ( startAngle - endAngle ).Normalize180() / 2;
254 double sinus = angle.
Sin();
255 double cosinus = angle.
Cos();
257 pt.
x =
KiROUND( ( *pY * sinus ) + ( *pX * cosinus ) );
258 pt.
y =
KiROUND( ( *pY * cosinus ) - ( *pX * sinus ) );
320 double sinus = angle.
Sin();
321 double cosinus = angle.
Cos();
323 pt.
x = ( *pY * sinus ) + ( *pX * cosinus );
324 pt.
y = ( *pY * cosinus ) - ( *pX * sinus );
341 std::swap( start, end );
347 std::swap( start, end );
352 double r = ( chord / 2.0 ) / ( angle / 2.0 ).Sin();
353 double d_squared = r * r - chord* chord / 4.0;
356 if( d_squared > 0.0 )
357 d = sqrt( d_squared );
364 return VECTOR2D( start + vc + vec2 );
372 double yDelta_21 = aMid.
y - aStart.
y;
373 double xDelta_21 = aMid.
x - aStart.
x;
374 double yDelta_32 = aEnd.
y - aMid.
y;
375 double xDelta_32 = aEnd.
x - aMid.
x;
380 if( ( ( xDelta_21 == 0.0 ) && ( yDelta_32 == 0.0 ) ) ||
381 ( ( yDelta_21 == 0.0 ) && ( xDelta_32 == 0.0 ) ) )
383 center.
x = ( aStart.
x + aEnd.
x ) / 2.0;
384 center.
y = ( aStart.
y + aEnd.
y ) / 2.0 ;
389 if( xDelta_21 == 0.0 )
390 xDelta_21 = std::numeric_limits<double>::epsilon();
392 if( xDelta_32 == 0.0 )
393 xDelta_32 = -std::numeric_limits<double>::epsilon();
395 double aSlope = yDelta_21 / xDelta_21;
396 double bSlope = yDelta_32 / xDelta_32;
401 if( aSlope == bSlope )
407 center.
x = ( aStart.
x + aMid.
x ) / 2.0;
408 center.
y = ( aStart.
y + aMid.
y ) / 2.0 ;
416 aSlope += std::numeric_limits<double>::epsilon();
417 bSlope -= std::numeric_limits<double>::epsilon();
420#ifdef USE_ALTERNATE_CENTER_ALGO
422 CircleCenterFrom3Points( aStart, aMid, aEnd, ¢er );
443 double abSlopeStartEndY = aSlope * bSlope * ( aStart.
y - aEnd.
y );
444 double dabSlopeStartEndY = abSlopeStartEndY *
445 std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
446 + ( dbSlope / bSlope * dbSlope / bSlope )
447 + ( M_SQRT1_2 / ( aStart.
y - aEnd.
y )
448 * M_SQRT1_2 / ( aStart.
y - aEnd.
y ) ) );
450 double bSlopeStartMidX = bSlope * ( aStart.
x + aMid.
x );
451 double dbSlopeStartMidX = bSlopeStartMidX * std::sqrt( ( dbSlope / bSlope * dbSlope / bSlope )
452 + ( M_SQRT1_2 / ( aStart.
x + aMid.
x )
453 * M_SQRT1_2 / ( aStart.
x + aMid.
x ) ) );
455 double aSlopeMidEndX = aSlope * ( aMid.
x + aEnd.
x );
456 double daSlopeMidEndX = aSlopeMidEndX * std::sqrt( ( daSlope / aSlope * daSlope / aSlope )
457 + ( M_SQRT1_2 / ( aMid.
x + aEnd.
x )
458 * M_SQRT1_2 / ( aMid.
x + aEnd.
x ) ) );
460 double twiceBASlopeDiff = 2 * ( bSlope - aSlope );
461 double dtwiceBASlopeDiff = 2 * std::sqrt( dbSlope * dbSlope + daSlope * daSlope );
463 double centerNumeratorX = abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX;
464 double dCenterNumeratorX = std::sqrt( dabSlopeStartEndY * dabSlopeStartEndY
465 + dbSlopeStartMidX * dbSlopeStartMidX
466 + daSlopeMidEndX * daSlopeMidEndX );
468 double centerX = ( abSlopeStartEndY + bSlopeStartMidX - aSlopeMidEndX ) / twiceBASlopeDiff;
469 double dCenterX = centerX * std::sqrt( ( dCenterNumeratorX / centerNumeratorX *
470 dCenterNumeratorX / centerNumeratorX )
471 + ( dtwiceBASlopeDiff / twiceBASlopeDiff *
472 dtwiceBASlopeDiff / twiceBASlopeDiff ) );
475 double centerNumeratorY = ( ( aStart.
x + aMid.
x ) / 2.0 - centerX );
476 double dCenterNumeratorY = std::sqrt( 1.0 / 8.0 + dCenterX * dCenterX );
478 double centerFirstTerm = centerNumeratorY / aSlope;
479 double dcenterFirstTermY = centerFirstTerm * std::sqrt(
480 ( dCenterNumeratorY/ centerNumeratorY *
481 dCenterNumeratorY / centerNumeratorY )
482 + ( daSlope / aSlope * daSlope / aSlope ) );
484 double centerY = centerFirstTerm + ( aStart.
y + aMid.
y ) / 2.0;
485 double dCenterY = std::sqrt( dcenterFirstTermY * dcenterFirstTermY + 1.0 / 8.0 );
487 double rounded100CenterX = std::floor( ( centerX + 50.0 ) / 100.0 ) * 100.0;
488 double rounded100CenterY = std::floor( ( centerY + 50.0 ) / 100.0 ) * 100.0;
489 double rounded10CenterX = std::floor( ( centerX + 5.0 ) / 10.0 ) * 10.0;
490 double rounded10CenterY = std::floor( ( centerY + 5.0 ) / 10.0 ) * 10.0;
497 if(
std::abs( rounded100CenterX - centerX ) < dCenterX &&
498 std::abs( rounded100CenterY - centerY ) < dCenterY )
500 center.
x = rounded100CenterX;
501 center.
y = rounded100CenterY;
503 else if(
std::abs( rounded10CenterX - centerX ) < dCenterX &&
504 std::abs( rounded10CenterY - centerY ) < dCenterY )
506 center.
x = rounded10CenterX;
507 center.
y = rounded10CenterY;
522 VECTOR2D dStart(
static_cast<double>( aStart.
x ),
static_cast<double>( aStart.
y ) );
523 VECTOR2D dMid(
static_cast<double>( aMid.
x ),
static_cast<double>( aMid.
y ) );
524 VECTOR2D dEnd(
static_cast<double>( aEnd.
x ),
static_cast<double>( aEnd.
y ) );
529 iCenter.
x =
KiROUND( Clamp<double>(
double( std::numeric_limits<int>::min() + 100 ),
531 double( std::numeric_limits<int>::max() - 100 ) ) );
533 iCenter.
y =
KiROUND( Clamp<double>(
double( std::numeric_limits<int>::min() + 100 ),
535 double( std::numeric_limits<int>::max() - 100 ) ) );
ecoord SquaredDistance(const SEG &aSeg) const
static SEG::ecoord Square(int a)
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.
static constexpr EDA_ANGLE ANGLE_0
static constexpr EDA_ANGLE ANGLE_90
static constexpr EDA_ANGLE ANGLE_270
static constexpr EDA_ANGLE ANGLE_360
static constexpr EDA_ANGLE ANGLE_180
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
const VECTOR2I CalcArcMid(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aMinArcAngle)
Return the middle point of an arc, half-way between aStart and aEnd.
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.
bool SegmentIntersectsSegment(const VECTOR2I &a_p1_l1, const VECTOR2I &a_p2_l1, const VECTOR2I &a_p1_l2, const VECTOR2I &a_p2_l2, VECTOR2I *aIntersectionPoint)
Test if two lines intersect.
bool IsPointOnSegment(const VECTOR2I &aSegStart, const VECTOR2I &aSegEnd, const VECTOR2I &aTestPoint)
Test if aTestPoint is on line defined by aSegStart and aSegEnd.
const VECTOR2D CalcArcCenter(const VECTOR2D &aStart, const VECTOR2D &aEnd, const EDA_ANGLE &aAngle)
double EuclideanNorm(const VECTOR2I &vector)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
VECTOR2< double > VECTOR2D