Geometry & Recognition

삼각형의 외접원을 기하학적인 방법이 아닌 대수적인 방법을 이용해서 구해보자. 중심이 $(x_c, y_c)$이고 반지름이 $R$인 원의 방정식은

$$(x-x_c)^2 + (y- y_c)^2 = R^2$$

으로 주어진다. 이 식에서 세 개의 변수 $x_c$, $y_c$, $R$를 결정해야는데, 각 변수에 대해서 2차 방정식의 형태로 주어져 있으므로 좀 더 쉬운 1차식 형태가 되도록 변형을 해보자. 방정식을 전개하면

$$(2x) x_c + (2y) y_c + R^2 - x_c^2 - y_c^2 = x^2 + y^2  \\ \longrightarrow ~(2x) x_c + (2y) y_c +d = x^2 +y^2,\quad\quad d=R^2 -x_c^2 -y_c^2.$$

이제 원의 방정식은 $x_c$, $y_c$, $d$에 대한 1차식으로 정리되었다. 삼각형의 외접원의 방정식은 세 꼭짓점을 통과하므로 세 꼭지 짐 $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$을 위의 식에 넣으면 3개의 방정식을 얻는다. 이 방정식을 행렬로 표현하면

따라서, Cramer의 규칙을 적용하면 다음과 같이 외접원의 중심 (또한 $d$을 구해서 외접원의 반지름을 구할 수 있다)을 얻을 수 있다.

determinant를 정리하면,

을 얻을 수 있다. 이 식의 분모는 세 꼭짓점이 일직선 위에 있지 않으면 0이 아니다. 한 꼭짓점과 다른 꼭짓점 간 좌표의 차이 4개 $(x_2-x_1, y_2-y_1, x_3-x_1, y_3-y_1)$와 좌표의 합 4개 $(x_1+x_2, y_1+y_2, x_1+x_3, y_1+y_3)$를 계산하여 중심점의 좌표를 얻을 수 있다.

구현된 코드는 http://kipl.tistory.com/113; 또는

int circumcenter2(CPoint P, CPoint Q, CPoint R, double *xc, double *yc) {
    double A = Q.x - P.x, B = Q.y - P.y;
    double C = R.x - P.x, D = R.y - P.y;
    double E = A * (P.x + Q.x) + B * (P.y + Q.y);
    double F = C * (P.x + R.x) + D * (P.y + R.y);
    double G = 2. * ( A * D - B * C);
    if (G != 0.) { // 세 점이 일직선에 놓이지 않는 경우; 이 경우만 외접원이 정의된다;
        *xc = (D * E - B * F) / G;
        *yc = (A * F - C * E) / G;
        return 1;
    } else return 0;
}

분모 $G$의 계산을 $G = 2 ( A  (R.y - Q.y) - B  (R.x - Q.x))$ 로 쓰는 경우가 많다. 위의 행렬식을 보면 같은 결과지만 식을 좀 더 대칭적으로 보이게 한다: $G = 2.(A  (D - B) - B  (C - A)) = 2 (A D - B C)$.