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)$.

평면 위 세 점 $A$, $B$, $C$가 삼각형을 만들 때 외접원 중심을 구해보자. 점 $C$을 원점으로 하면, $A$, $B$는 각각

의 두 벡터로 표현이 된다 (원점을 $C$점으로 평행 이동했다고 생각하면 된다). 이 두 벡터에 각각 수직이고 삼각형과 같은 평면에 놓인 ($\vec a$, $\vec b$를 각각 시계 방향으로 회전시켜 만든) 두 벡터 $\vec m$, $\vec n$를 다음과 같이 정의하자.

그러면, 변 $CA$의 중점을 지나면서 수직인 직선의 방정식은

또, $CB$의 중점을 지나면서 수직인 직선의 방정식은 

이 두 직선의 교점이 외접원의 중심이 된다. 매개변수 $s$, $t$를 구하기 위해서 두 식을 빼면

 매개변수 $s$는 $\vec b$와 $\vec n$이 수직인 조건을 이용하면

따라서, 외접원의 중심은  

여기서, 3개 벡터의 외적의 성질을 이용해서 (평면에서 외적은 숫자이다)

가 항등식으로 성립하고, 또한 $\vec a$, $\vec m$이 서로 수직이면서 길이가 같고, $\vec m$ 도 $\vec b$에 수직이면 길이가 같으므로

따라서, 

여기서, 윗 식의 분모를 보면

이므로, 이 값이 0이 아니려면 세 점이 일직선에 있지 않으면 된다.

그런데 이 벡터는 점 $C$를 원점으로 하여서 계산을 한 것이므로, 원래의 좌표계에 대한 식으로 바꾸려면 $(C_x, C_y)$를 더해 주어야 한다.

또는, 성분으로 표현하면

int circumcenter ( CPoint A, CPoint B, CPoint C, double *xc, double *yc) {
    double ax = A.x - C.x, ay = A.y - C.y ;
    double bx = B.x - C.x, by = B.y - C.y ;
    double asq = ax * ax + ay * ay;
    double bsq = bx * bx + by * by;
    double ccw = ax * by - ay * bx;
    if ( ccw != 0. ) { //세 점임 일직선 위에 있지 않는 경우; 이 경우만 외접원이 정의됨;
        *xc = C.x + ( by * asq - ay * bsq ) / ( 2 * ccw ) ;
        *yc = C.y + ( -bx * asq + ax * bsq ) / ( 2 * ccw ) ;
        return 1;
    } else return 0;
}