원과 직선의 교점¶
원의 중심 좌표와 반지름, 그리고 직선의 방정식이 주어질 때 교점을 구해야 합니다.
풀이¶
두 방정식으로 이루어진 연립방정식을 푸는 대신 이 문제에 기하학적으로 접근하겠습니다. 이렇게 하면 수치적 안정성 측면에서 더 정확한 해를 얻을 수 있습니다.
일반성을 잃지 않고 원의 중심이 원점에 있다고 가정합니다. 그렇지 않다면 원을 원점으로 평행이동하고 직선 방정식의 상수 $C$를 보정합니다. 따라서 중심이 $(0,0)$이고 반지름이 $r$인 원과 방정식이 $Ax+By+C=0$인 직선이 주어집니다.
먼저 직선 위에서 원점에 가장 가까운 점 $(x_0, y_0)$를 찾는 것부터 시작합시다. 첫째, 이 점은 원점으로부터 다음 거리에 있어야 합니다
둘째, 벡터 $(A, B)$가 직선에 수직이므로 이 점의 좌표는 이 벡터의 좌표에 비례해야 합니다. 이 점과 원점 사이의 거리를 알고 있으므로 벡터 $(A, B)$를 이 길이로 조정하기만 하면 다음을 얻습니다:
음수 부호는 자명하지 않지만, 직선의 방정식에 $x_0$와 $y_0$를 대입하면 쉽게 확인할 수 있습니다.
이 단계에서 교점의 개수를 판별할 수 있으며, 교점이 하나이거나 없는 경우에는 해까지 구할 수 있습니다. 실제로 $(x_0, y_0)$에서 원점까지의 거리 $d_0$가 반지름 $r$보다 크면 답은 교점 없음입니다. $d_0=r$이면 답은 한 점 $(x_0, y_0)$입니다. $d_0<r$이면 교점이 두 개 있으며, 이제 그 좌표를 구해야 합니다.
따라서 점 $(x_0, y_0)$가 원 내부에 있음을 알 수 있습니다. 두 교점 $(a_x, a_y)$와 $(b_x, b_y)$는 직선 $Ax+By+C=0$ 위에 있어야 하고 $(x_0, y_0)$로부터 같은 거리 $d$만큼 떨어져 있어야 하며, 이 거리는 쉽게 구할 수 있습니다:
벡터 $(-B, A)$는 직선과 평행하므로, 길이 $d$로 조정한 벡터 $(-B,A)$를 점 $(x_0, y_0)$에 더하고 빼서 구하려는 점들을 찾을 수 있다는 점에 유의하십시오.
마지막으로, 두 교점의 방정식은 다음과 같습니다:
원래의 연립방정식을 대수적 방법으로 풀었다면 아마도 오차가 더 큰 다른 형태의 답을 얻었을 것입니다. 여기에서 설명한 기하학적 방법이 더 직관적이고 더 정확합니다.
구현¶
처음에 밝힌 대로 원의 중심이 원점에 있다고 가정하므로, 프로그램의 입력은 원의 반지름 $r$과 직선 방정식의 매개변수 $A$, $B$, $C$입니다.
double r, a, b, c; // given as input
double x0 = -a*c/(a*a+b*b), y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
puts ("no points");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
puts ("1 point");
cout << x0 << ' ' << y0 << '\n';
}
else {
double d = r*r - c*c/(a*a+b*b);
double mult = sqrt (d / (a*a+b*b));
double ax, ay, bx, by;
ax = x0 + b * mult;
bx = x0 - b * mult;
ay = y0 - a * mult;
by = y0 + a * mult;
puts ("2 points");
cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}