[GIS] Point In Polygon (PIP) 문제 :: 폴리곤 내부에 점 존재 판별 문제

Point in Polygon (PIP) 문제는 주어진 다각형 (Polygon) 내부에 특정 점 (Point)이 존재하는지 판별하는 문제입니다. 이는 컴퓨터 그래픽스, 지리정보 시스템 (GIS), 게임 개발 등의 다양한 분야에서 매우 중요하게 사용됩니다. 다음은 PIP 문제를 해결하기 위한 몇 가지 대표적인 알고리즘입니다:

1. Ray-Casting Algorithm (Ray Crossing Method)

이 방법은 점에서 임의의 방향으로 반직선을 그어 다각형의 변과 몇 번 교차하는지를 세는 방법입니다. 교차 횟수가 홀수이면 점은 다각형 내부에 있고, 짝수이면 외부에 있습니다.

Steps:

1. 점에서 임의의 방향으로 반직선을 그립니다.
2. 반직선이 다각형의 변과 교차하는 횟수를 셉니다.
3. 교차 횟수가 홀수이면 점은 다각형 내부에 있습니다.
4. 교차 횟수가 짝수이면 점은 다각형 외부에 있습니다.

2. Winding Number Algorithm

이 방법은 점을 중심으로 하는 벡터가 다각형의 각 변을 따라 회전하는 각도를 이용합니다. 벡터가 다각형의 변을 따라 회전하는 횟수를 나타내는 winding number를 계산합니다.

Steps:

1. 다각형의 각 변에 대해 점을 기준으로 하는 벡터를 계산합니다.
2. 벡터들이 시계방향 또는 반시계방향으로 얼마나 회전하는지를 계산하여 winding number를 구합니다.
3. winding number가 0이 아니면 점은 다각형 내부에 있습니다.

3. Even-Odd Rule (Parity Rule)

이 방법은 Ray-Casting Algorithm과 유사하지만, 반직선을 임의의 방향이 아닌 x축과 평행한 방향으로 그려 교차 횟수를 세는 방법입니다.

Steps:

1. 점에서 x축과 평행한 방향으로 반직선을 그립니다.
2. 반직선이 다각형의 변과 교차하는 횟수를 셉니다.
3. 교차 횟수가 홀수이면 점은 다각형 내부에 있습니다.
4. 교차 횟수가 짝수이면 점은 다각형 외부에 있습니다.

Python 예제 (Ray-Casting Algorithm)

def is_point_in_polygon(point, polygon):
    x, y = point
    n = len(polygon)
    inside = False

    p1x, p1y = polygon[0]
    for i in range(n + 1):
        p2x, p2y = polygon[i % n]
        if y > min(p1y, p2y):
            if y <= max(p1y, p2y):
                if x <= max(p1x, p2x):
                    if p1y != p2y:
                        xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x, p1y = p2x, p2y

    return inside

# 사용 예시
polygon = [(1, 1), (1, 10), (10, 10), (10, 1)]
point = (5, 5)
print(is_point_in_polygon(point, polygon))  # True

이 예제는 주어진 점이 다각형 내부에 있는지를 Ray-Casting Algorithm을 통해 판단합니다. 이 알고리즘은 단순하면서도 대부분의 경우에 효과적으로 작동합니다.

PIP 문제는 다양한 응용 분야에서 필수적인 문제로, 위의 알고리즘들 외에도 상황에 맞춰 최적화된 다양한 방법들이 존재합니다. 상황에 따라 적절한 알고리즘을 선택하여 사용하면 됩니다.