두 원의 공통 접선 구하기¶
두 원이 주어집니다. 두 원의 모든 공통 접선, 즉 두 원에 동시에 접하는 모든 직선을 구해야 합니다.
여기서 설명하는 알고리즘은 한 원(또는 두 원 모두)이 점으로 퇴화하는 경우에도 동작합니다. 따라서 이 알고리즘은 주어진 점을 지나는 원의 접선을 구하는 데에도 사용할 수 있습니다.
공통 접선의 개수¶
두 원의 공통 접선의 개수는 0,1,2,3,4개이거나 무한히 많을 수 있습니다. 여러 경우에 대한 그림을 살펴보십시오.
여기서는 퇴화 경우, 즉 두 원이 일치하는 경우(이때는 공통 접선이 무한히 많습니다)나 한 원이 다른 원의 내부에 있는 경우(이때는 공통 접선이 없으며, 두 원이 접한다면 공통 접선이 하나 있습니다)는 고려하지 않습니다.
대부분의 경우 두 원은 네 개의 공통 접선을 가집니다.
두 원이 접하면 공통 접선이 세 개가 되지만, 이는 두 접선이 일치한 것과 같은 퇴화 경우로 이해할 수 있습니다.
게다가 아래에서 설명하는 알고리즘은 한 원 또는 두 원 모두의 반지름이 0인 경우에도 동작하며, 이때 공통 접선은 각각 두 개 또는 한 개가 됩니다.
정리하면, 접선이 무한히 많은 경우를 제외한 모든 경우에 대해 항상 네 개의 접선을 찾습니다(접선이 무한히 많은 경우는 별도로 처리해야 하며 여기서는 다루지 않습니다). 퇴화 경우에는 일부 접선이 일치하지만, 그럼에도 이러한 경우 역시 전체 틀 안에 들어맞습니다.
알고리즘¶
알고리즘을 단순하게 하기 위해, 일반성을 잃지 않고 첫 번째 원의 중심 좌표가 $(0, 0)$이라고 가정하겠습니다. (그렇지 않은 경우에는 전체 그림을 단순히 평행 이동하고, 해를 구한 뒤 얻은 직선들을 다시 원래대로 이동하면 됩니다.)
첫 번째 원과 두 번째 원의 반지름을 각각 $r_1$과 $r_2$로, 두 번째 원의 중심 좌표를 $(v_x,v_y)$로 나타내고, 이 점 $v$는 원점과 다르다고 합시다. (참고: 두 원이 같은 경우는 고려하지 않습니다.)
이 문제를 풀기 위해 순수하게 대수적으로 접근합니다. 좌표 원점으로부터 거리 $r_1$만큼 떨어져 있고, 점 $v$로부터 거리 $r_2$만큼 떨어져 있는 $ax + by + c = 0$ 형태의 직선을 모두 찾아야 합니다. 또한 직선에 정규화 조건을 부여합니다. 즉, 계수들의 제곱의 합이 1이 되어야 합니다(이 조건이 필요한 이유는, 그렇지 않으면 같은 직선이 $ax + by + c = 0$ 꼴의 무한히 많은 표현에 대응되기 때문입니다). 결국 구하고자 하는 $a, b, c$에 대해 다음과 같은 연립방정식을 얻습니다:
절댓값을 없애기 위해, 이 연립방정식에서 절댓값을 푸는 방법은 네 가지뿐이라는 점에 주목하십시오. 절댓값을 푸는 것을 우변의 계수에 -1이 곱해질 수 있다는 사실로 이해하면, 이 모든 방법을 하나의 일반적인 경우로 함께 다룰 수 있습니다. 다시 말해, 다음 연립방정식으로 넘어갑니다:
$d_1 = \pm r_1$과 $d_2 = \pm r_2$라는 표기를 도입하면, 이 연립방정식이 네 개의 해를 가져야 한다는 결론에 이릅니다:
이 연립방정식의 풀이는 이차방정식을 푸는 문제로 귀결됩니다. 번거로운 계산은 모두 생략하고 곧바로 최종 답을 제시하겠습니다:
결국 네 개가 아니라 여덟 개의 해를 얻었습니다. 그러나 불필요한 해가 어디서 생기는지는 쉽게 이해할 수 있습니다. 사실 마지막 연립방정식에서는 해를 하나(예를 들어 첫 번째 해)만 취하면 충분합니다. 실제로 $\pm r_1$과 $\pm r_2$를 취하는 것의 기하학적 의미는 분명합니다. 이는 사실상 직선이 각 원의 어느 쪽에 있는지를 모두 따져 보는 것입니다. 따라서 마지막 연립방정식을 풀 때 생기는 두 가지 방법은 중복됩니다. 두 해 중 하나만 선택하면 충분합니다(물론 네 가지 경우 모두에서 같은 해의 계열을 선택해야 합니다).
아직 다루지 않은 마지막 사항은 첫 번째 원이 원래 원점에 있지 않았던 경우에 직선을 어떻게 평행 이동하는가입니다. 하지만 이는 간단합니다. 직선 방정식의 선형성으로부터, 계수 $c$에서 값 $a \cdot x_0 + b \cdot y_0$(여기서 $x_0$과 $y_0$은 첫 번째 원의 원래 중심 좌표입니다)을 빼야 한다는 것이 도출됩니다.
구현¶
먼저 필요한 모든 자료 구조와 그 밖의 보조 정의를 기술합니다.
struct pt {
double x, y;
pt operator- (pt p) {
pt res = { x-p.x, y-p.y };
return res;
}
};
struct circle : pt {
double r;
};
struct line {
double a, b, c;
};
const double EPS = 1E-9;
double sqr (double a) {
return a * a;
}
void tangents (pt c, double r1, double r2, vector<line> & ans) {
double r = r2 - r1;
double z = sqr(c.x) + sqr(c.y);
double d = z - sqr(r);
if (d < -EPS) return;
d = sqrt (abs (d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back (l);
}
vector<line> tangents (circle a, circle b) {
vector<line> ans;
for (int i=-1; i<=1; i+=2)
for (int j=-1; j<=1; j+=2)
tangents (b-a, a.r*i, b.r*j, ans);
for (size_t i=0; i<ans.size(); ++i)
ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
return ans;
}