점이 삼각형 내부에 있는지 판별하는 방법 (C++ 구현)

문제 개요

삼각형의 세 꼭짓점이 주어져 있고, 또 하나의 점 P가 주어졌을 때 이 점이 삼각형의 내부에 있는지 아닌지를 판별하는 문제입니다.

해결 원리

삼각형의 꼭짓점을 각각 A, B, C라고 하겠습니다. 점 P가 삼각형 내부에 있다면, 삼각형 ABC는 점 P를 기준으로 세 개의 작은 삼각형으로 나눌 수 있습니다. 따라서 다음 등식이 성립합니다.

ΔABC = ΔABP + ΔPBC + ΔAPC

만약 이 등식이 성립하지 않는다면 점 P는 삼각형 외부에 있는 것입니다. 삼각형의 넓이는 좌표를 이용한 신발끈 공식(Shoelace Formula)으로 계산할 수 있습니다.

넓이 = |x₁(y₂ − y₃) + x₂(y₃ − y₁) + x₃(y₁ − y₂)| / 2

입력 및 출력

입력:
삼각형의 꼭짓점 {(0, 0), (20, 0), (10, 30)}과 검사할 점 p(10, 15)

출력:
점은 삼각형 내부에 있습니다.

알고리즘

isInside(p1, p2, p3, p)

입력: 삼각형의 세 꼭짓점, 검사할 점 p

출력: p가 삼각형 내부에 있으면 true, 아니면 false

Begin
    area := 삼각형(p1, p2, p3)의 넓이
    area1 := 삼각형(p, p2, p3)의 넓이
    area2 := 삼각형(p1, p, p3)의 넓이
    area3 := 삼각형(p1, p2, p)의 넓이
    if area = (area1 + area2 + area3), then
        return true
    else return false
End

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
};

float triangleArea(Point p1, Point p2, Point p3) {  // p1, p2, p3로 이루어진 삼각형의 넓이 계산
    return abs((p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y) + p3.x*(p1.y-p2.y)) / 2.0);
}

bool isInside(Point p1, Point p2, Point p3, Point p) {  // p가 내부에 있는지 확인
    float area = triangleArea(p1, p2, p3);   // 삼각형 ABC의 넓이
    float area1 = triangleArea(p, p2, p3);   // 삼각형 PBC의 넓이
    float area2 = triangleArea(p1, p, p3);   // 삼각형 APC의 넓이
    float area3 = triangleArea(p1, p2, p);   // 삼각형 ABP의 넓이

    return (area == area1 + area2 + area3);  // 세 삼각형의 넓이 합이 전체 넓이와 같은 경우
}

int main() {
    Point p1={0, 0}, p2={20, 0}, p3={10, 30};
    Point p = {10, 15};
    if (isInside(p1, p2, p3, p))
        cout << "Point is inside the triangle.";
    else
        cout << "Point is not inside the triangle";
}

실행 결과

Point is inside the triangle.

참고 사항

실수 연산에서는 부동소수점 오차로 인해 == 비교가 정확히 일치하지 않을 수 있습니다. 실전 코드에서는 전체 넓이와 세 삼각형 넓이의 합의 차이가 충분히 작은 값(예: 1e-9) 이내인지 확인하는 방식이 더 안전합니다. 또한 이 방법의 시간 복잡도는 O(1)로, 단일 점에 대한 판별에는 매우 효율적입니다.