문제 개요
데카르트 좌표계의 점들로 구성된 리스트 [(x1, y1), (x2, y2), ..., (xn, yn)]가 하나의 다각형(polygon)을 나타낸다고 가정해 봅시다. 여기에 두 값 x와 y가 추가로 주어졌을 때, 점 (x, y)가 이 다각형의 내부 또는 경계선 위에 존재하는지 판별하는 것이 목표입니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
점 (3, 1)은 다각형 내부에 위치하므로 출력은 True가 됩니다.
풀이 접근 방법
이 문제는 컴퓨터 그래픽스와 지리 정보 시스템(GIS)에서 널리 사용되는 레이 캐스팅(Ray Casting) 기법, 즉 홀짝 교차 규칙(even-odd rule)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 해당 점에서 한 방향으로 반직선을 그었을 때, 다각형의 변과 몇 번 교차하는지 세는 것입니다. 교차 횟수가 홀수라면 점은 내부에 있고, 짝수라면 외부에 있습니다.
구체적인 단계는 다음과 같습니다.
- 결괏값 ans를 False로 초기화합니다.
- i를 0부터 다각형 크기 - 1까지 순회하며 다음을 수행합니다.
- (x0, y0) := polygon[i]
- (x1, y1) := polygon[(i + 1) mod 다각형 크기] — 현재 꼭짓점과 다음 꼭짓점을 연결하는 한 변을 구성합니다.
- 만약 pt[1](y 좌표)이 min(y0, y1)과 max(y0, y1) 사이 범위에 속하지 않으면, 이 변은 검사 대상이 아니므로 다음 반복으로 넘어갑니다.
- 만약 pt[0](x 좌표)이 min(x0, x1)보다 작으면 역시 다음 반복으로 넘어갑니다.
- cur_x를 계산합니다. x0 == x1이면 cur_x := x0이고, 그렇지 않으면 선형 보간 공식인 x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)를 사용합니다.
- pt[0] > cur_x가 참이면 1, 거짓이면 0으로 하여 ans를 XOR 연산합니다. 이를 통해 교차 횟수의 홀짝 여부를 추적합니다.
- 최종적으로 ans를 반환합니다.
아래 예제 구현을 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, polygon, pt):
ans = False
for i in range(len(polygon)):
x0, y0 = polygon[i]
x1, y1 = polygon[(i + 1) % len(polygon)]
if not min(y0, y1) < pt[1] <= max(y0, y1):
continue
if pt[0] < min(x0, x1):
continue
cur_x = x0 if x0 == x1 else x0 + (pt[1] - y0) * (x1 - x0) / (y1 - y0)
ans ^= pt[0] > cur_x
return ans
ob = Solution()
points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)]
pt = (3, 1)
print(ob.solve(points, pt))
입력
[(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)], (3, 1)
출력
True
정리
이 알고리즘은 다각형의 모든 변을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 여기서 n은 다각형의 꼭짓점 개수입니다. 볼록 다각형뿐 아니라 오목 다각형에도 정확하게 동작하며, 점이 경계선 위에 있는 경우에도 올바른 결과를 반환합니다. 좌표 기반 충돌 감지, 지도 영역 판정 등 다양한 실무 상황에서 유용하게 활용할 수 있습니다.