문제 개요
하나의 다각형과 한 점 P가 주어졌을 때, 이 점이 다각형의 내부에 있는지 아니면 외부에 있는지 판별하는 문제입니다. 컴퓨터 그래픽스, 지리 정보 시스템(GIS), 게임 충돌 판정 등 다양한 분야에서 자주 활용되는 기본적인 기하 알고리즘입니다.
해결 아이디어: 레이 캐스팅(Ray Casting)
이 문제는 레이 캐스팅(Ray Casting), 즉 광선 투사 기법으로 해결할 수 있습니다. 점 P에서 출발하여 무한히 뻗어나가는 수평선(x축에 평행한 반직선)을 하나 그리고, 이 선이 다각형의 변들과 몇 번 교차하는지 세는 것입니다.
- 교차 횟수가 홀수이면 → 점 P는 다각형 내부에 있습니다.
- 교차 횟수가 짝수이면 → 점 P는 다각형 외부에 있습니다.
- 점 P가 다각형의 변 위에 놓인 특수한 경우는 별도의 예외 처리를 통해 경계 위에 있음을 판별합니다.
이 원리는 직관적으로 이해할 수 있습니다. 어떤 점에서 오른쪽 끝까지 선을 그었을 때, 점이 닫힌 도형 안에 있다면 반드시 도형의 경계를 홀수 번 통과하게 되기 때문입니다.
입력 · 출력 예시
입력:
다각형의 꼭짓점 {(0, 0), (10, 0), (10, 10), (0, 10)}
확인할 점 P (5, 3)
출력:
점은 다각형 내부에 있습니다.알고리즘: checkInside(Poly, n, p)
입력: 다각형의 꼭짓점 배열 Poly, 꼭짓점의 개수 n, 확인할 점 p
출력: 점 p가 다각형 내부에 있으면 true, 그렇지 않으면 false
Begin
if n < 3 then
return false // 꼭짓점이 3개 미만이면 다각형이 아님
점 p에서 시작하는 기울기 0°(수평)인 반직선 exLine 생성
count := 0, i := 0
repeat
poly[i]와 poly[(i+1) mod n]을 잇는 변(side) 생성
if side와 exLine이 교차하면 then
if side와 exLine이 공선(일직선상)이면 then
if 점 p가 변 위에 있으면 then
return true
else return false
count := count + 1
i := (i + 1) mod n
until i = 0 // 모든 변을 검사할 때까지 반복
count가 홀수이면 true 반환
EndC++ 구현 예제
#include<iostream>
using namespace std;
struct Point {
int x, y;
};
struct line {
Point p1, p2;
};
bool onLine(line l1, Point p) { // 점 p가 선분 l1 위에 있는지 확인
if(p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y))
return true;
return false;
}
int direction(Point a, Point b, Point c) {
int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
if(val == 0)
return 0; // 세 점이 일직선상에 위치 (공선)
else if(val < 0)
return 2; // 반시계 방향
return 1; // 시계 방향
}
bool isIntersect(line l1, line l2) {
// 두 선분 각각에 대해 상대방 선분의 두 끝점에 대한 방향 값을 계산
int dir1 = direction(l1.p1, l1.p2, l2.p1);
int dir2 = direction(l1.p1, l1.p2, l2.p2);
int dir3 = direction(l2.p1, l2.p2, l1.p1);
int dir4 = direction(l2.p1, l2.p2, l1.p2);
if(dir1 != dir2 && dir3 != dir4)
return true; // 두 선분이 서로 교차함
if(dir1 == 0 && onLine(l1, l2.p1)) // l2의 끝점이 l1 위에 있는 경우
return true;
if(dir2 == 0 && onLine(l1, l2.p2)) // l2의 끝점이 l1 위에 있는 경우
return true;
if(dir3 == 0 && onLine(l2, l1.p1)) // l1의 끝점이 l2 위에 있는 경우
return true;
if(dir4 == 0 && onLine(l2, l1.p2)) // l1의 끝점이 l2 위에 있는 경우
return true;
return false;
}
bool checkInside(Point poly[], int n, Point p) {
if(n < 3)
return false; // 꼭짓점이 3개 미만이면 다각형이 아님
line exline = {p, {9999, p.y}}; // 점 p와 같은 y좌표의 먼 지점을 잇는 수평선
int count = 0;
int i = 0;
do {
line side = {poly[i], poly[(i+1)%n]}; // 인접한 두 꼭짓점을 잇는 변
if(isIntersect(side, exline)) { // 변이 수평선과 교차하는 경우
if(direction(side.p1, p, side.p2) == 0)
return onLine(side, p); // 점이 변 위에 있는지 확인
count++;
}
i = (i+1)%n;
} while(i != 0);
return count & 1; // 교차 횟수가 홀수이면 내부
}
int main() {
Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
Point p = {5, 3};
int n = 4;
if(checkInside(polygon, n, p))
cout << \"점은 다각형 내부에 있습니다.\";
else
cout << \"점은 다각형 외부에 있습니다.\";
}실행 결과
점은 다각형 내부에 있습니다.
복잡도 분석
이 알고리즘은 다각형의 모든 변을 한 번씩 검사하므로 시간 복잡도는 꼭짓점 개수에 비례하는 O(n)이며, 추가적인 저장 공간을 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 꼭짓점 개수가 많은 복잡한 다각형에 대해서도 효율적으로 동작합니다.