C++로 삼각형의 외심 구하는 프로그램 만들기

C++에서 삼각형의 외심(Circumcenter) 구하기

이 튜토리얼에서는 C++를 활용해 삼각형의 외심을 구하는 프로그램을 살펴봅니다. 외심은 삼각형의 세 꼭짓점으로부터 거리가 모두 같은 점으로, 세 변의 수직 이등분선이 만나는 지점입니다. 외심을 중심으로 하면 세 꼭짓점을 모두 지나는 원, 즉 외접원을 그릴 수 있습니다.

문제의 조건은 다음과 같습니다. 일직선상에 있지 않은(non-collinear) 세 점 P, Q, R이 주어질 때, 이 점들이 형성하는 삼각형의 외심 좌표를 계산하는 것이 우리의 과제입니다.

풀이 접근 방식

기하학적으로 외심은 두 수직 이등분선의 교점과 같습니다. 따라서 다음과 같은 순서로 문제를 해결할 수 있습니다.

두 점 P와 Q를 지나는 직선의 방정식을 ax + by = c 형태로 구합니다.
같은 방법으로 두 점 Q와 R을 지나는 직선의 방정식을 구합니다.
각 직선을, 선분의 중점을 지나면서 기울기가 서로 수직이 되도록 수직 이등분선의 방정식으로 변환합니다.
두 수직 이등분선의 연립방정식을 풀어 교점을 구합니다. 이 교점이 바로 삼각형의 외심입니다.

예제 코드

#include <iostream>
#include <cfloat>
using namespace std;
// X좌표와 Y좌표를 저장하기 위한 pair 정의
#define pdd pair<double, double>
void lineFromPoints(pdd P, pdd Q, double &a, double &b, double &c){
    a = Q.second - P.second;
    b = P.first - Q.first;
    c = a*(P.first)+ b*(P.second);
}
void perpendicularBisectorFromLine(pdd P, pdd Q, double &a, double &b, double &c){
    pdd mid_point = make_pair((P.first + Q.first)/2, (P.second + Q.second)/2);
    c = -b*(mid_point.first) + a*(mid_point.second);
    double temp = a;
    a = -b;
    b = temp;
}
pdd lineLineIntersection(double a1, double b1, double c1, double a2, double b2, double c2){
    double determinant = a1*b2 - a2*b1;
    if (determinant == 0){
        return make_pair(FLT_MAX, FLT_MAX);
    } else {
        double x = (b2*c1 - b1*c2)/determinant;
        double y = (a1*c2 - a2*c1)/determinant;
        return make_pair(x, y);
    }
}
void findCircumCenter(pdd P, pdd Q, pdd R){
    double a, b, c;
    lineFromPoints(P, Q, a, b, c);
    double e, f, g;
    lineFromPoints(Q, R, e, f, g);
    perpendicularBisectorFromLine(P, Q, a, b, c);
    perpendicularBisectorFromLine(Q, R, e, f, g);
    pdd circumcenter = lineLineIntersection(a, b, c, e, f, g);
    if (circumcenter.first == FLT_MAX && circumcenter.second == FLT_MAX){
        cout << "The two perpendicular bisectors "
            "found come parallel" << endl;
        cout << "Thus, the given points do not form "
            "a triangle and are collinear" << endl;
    } else {
        cout << "The circumcenter of the triangle PQR is: ";
        cout << "(" << circumcenter.first << ", "
            << circumcenter.second << ")" << endl;
    }
}
int main(){
    pdd P = make_pair(6, 0);
    pdd Q = make_pair(0, 0);
    pdd R = make_pair(0, 8);
    findCircumCenter(P, Q, R);
    return 0;
}

실행 결과

The circumcenter of the triangle PQR is: (3, 4)

코드 상세 설명

lineFromPoints() : 두 점을 지나는 직선을 ax + by = c 꼴로 나타낼 때 필요한 계수 a, b, c를 계산합니다.
perpendicularBisectorFromLine() : 주어진 직선을, 선분의 중점을 통과하면서 원래 직선에 수직인 직선 즉 수직 이등분선의 방정식으로 변환합니다. 계수 a와 b를 서로 맞바꾸고 부호를 뒤집어 수직 관계를 만듭니다.
lineLineIntersection() : 행렬식(determinant)을 이용해 두 직선의 교점을 계산합니다. 행렬식이 0이라면 두 직선이 평행하다는 의미이므로 특수 값 FLT_MAX를 반환합니다.
findCircumCenter() : 앞의 함수들을 조합해 외심을 최종적으로 계산하고 출력합니다. 만약 두 수직 이등분선이 평행하다면 세 점이 일직선상에 존재하여 삼각형이 성립하지 않는다는 메시지를 대신 출력합니다.

예제에서 사용된 세 점 (6, 0), (0, 0), (0, 8)은 원점에서 직각을 이루는 직각삼각형을 만듭니다. 직각삼각형의 외심은 빗변의 중점과 일치하므로, 빗변 양 끝점인 (6, 0)과 (0, 8)의 중점인 (3, 4)가 외심이 됩니다. 실제 실행 결과 역시 동일한 좌표를 출력하는 것을 확인할 수 있습니다.