다각형의 넓이: 신발끈 공식과 픽의 정리

지난 글에서 스위프 라인으로 평면 문제를 효율적으로 처리하는 법을 봤습니다. 이번 글에서는 가장 고전적인 기하 측정 문제로 돌아옵니다. 좌표로 주어진 다각형의 넓이를 어떻게 구할까요? 답은 놀랍도록 간단합니다. 우리가 이미 익힌 외적을 정점 순서대로 더하기만 하면 됩니다. 여기에 격자점으로 넓이를 세는 픽의 정리까지 더하면 다각형 측정의 핵심이 완성됩니다.

신발끈 공식

다각형의 정점을 순서대로 P₀, P₁, …, Pₙ₋₁ 이라 하면, 넓이는 인접한 정점 쌍의 외적을 모두 더한 값의 절반입니다.

        1   n-1
Area = ─── · | Σ ( xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ ) |
        2   i=0

이 식을 신발끈 공식(shoelace formula)이라 부릅니다. 좌표를 위아래로 엇갈려 곱하는 모양이 신발끈을 묶는 것과 닮았기 때문입니다.

왜 이게 넓이가 될까요? 각 항 xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ는 원점·Pᵢ·Pᵢ₊₁이 이루는 삼각형 넓이의 2배(부호 포함)입니다. 다각형 경계를 따라 이 삼각형들을 더하면, 다각형 바깥 영역은 양수와 음수로 정확히 상쇄되고 내부만 남습니다. 볼록이든 오목이든 단순 다각형(변이 교차하지 않는)이면 항상 성립합니다.

def polygon_area2(pts):
    # 넓이의 2배 (부호 있음)
    n = len(pts)
    s = 0
    for i in range(n):
        j = (i + 1) % n
        s += pts[i][0]*pts[j][1] - pts[j][0]*pts[i][1]
    return s

def polygon_area(pts):
    return abs(polygon_area2(pts)) / 2

부호의 의미

신발끈의 합에 절댓값을 취하기 전, 부호 자체가 정보를 담습니다. 정점이 반시계(CCW) 순서면 양수, 시계(CW) 순서면 음수입니다. 따라서 같은 코드로 다각형의 정점 방향까지 알 수 있습니다.

s = polygon_area2(pts)
orientation = "CCW" if s > 0 else "CW"

이 성질은 다각형을 일관된 방향으로 정규화하거나, 구멍 있는 도형에서 외곽과 내부 경계를 구분할 때 유용합니다. 정수 좌표라면 polygon_area2는 정수이고, 홀수일 수 있어 2로 나누기 전까지 정수로 비교하는 것이 안전합니다.

픽의 정리

다각형의 모든 정점이 격자점(정수 좌표) 위에 있다면, 전혀 다른 방식으로 넓이를 구할 수 있습니다. 바로 픽의 정리(Pick’s theorem)입니다.

A = I + B/2 − 1

여기서 I는 다각형 내부의 격자점 수, B는 경계 위의 격자점 수입니다. 넓이를 좌표 계산이 아니라 “점 개수 세기”로 환원한다는 점이 아름답습니다.

실전에서는 보통 거꾸로 씁니다. 넓이 A는 신발끈으로 쉽게 구하고, 경계점 B도 아래 방법으로 구한 뒤, 내부점 I를 역산하는 것입니다.

I = A − B/2 + 1

경계 격자점 개수: gcd

한 변이 (x₁,y₁)에서 (x₂,y₂)로 갈 때, 그 변 위(끝점 제외)의 격자점 수는 gcd(|Δx|, |Δy|) − 1입니다. 모든 변에 대해 더하면 경계 격자점 B가 됩니다(각 정점은 한 번씩만 세도록 주의).

from math import gcd

def boundary_points(pts):
    n = len(pts)
    b = 0
    for i in range(n):
        j = (i + 1) % n
        dx = abs(pts[i][0] - pts[j][0])
        dy = abs(pts[i][1] - pts[j][1])
        b += gcd(dx, dy)        # 변마다 gcd, 정점 중복 없이 합산
    return b

이렇게 구한 A(신발끈)와 B(gcd 합)를 픽의 정리에 넣으면, “다각형 내부에 격자점이 몇 개냐” 같은 문제를 좌표 순회 없이 O(n)에 풉니다.

보너스: 점이 다각형 내부에 있는가

넓이와 함께 자주 묻는 질문이 “점 P가 다각형 안에 있는가”입니다. 가장 흔한 방법은 광선 던지기(ray casting)입니다. P에서 한쪽으로 반직선을 쏘아, 다각형의 변과 교차하는 횟수가 홀수면 내부, 짝수면 외부입니다.

def point_in_polygon(p, pts):
    n = len(pts)
    inside = False
    for i in range(n):
        a, b = pts[i], pts[(i+1) % n]
        # 변이 p의 y를 가로지르고, 교점 x가 p.x보다 오른쪽인가
        if (a[1] > p[1]) != (b[1] > p[1]):
            xint = (b[0]-a[0])*(p[1]-a[1])/(b[1]-a[1]) + a[0]
            if p[0] < xint:
                inside = not inside
    return inside

정리

다각형 측정의 도구를 정리하면 다음과 같습니다.

도구	구하는 것	복잡도
신발끈 공식	임의 단순 다각형 넓이	O(n)
신발끈 부호	정점 진행 방향(CCW/CW)	O(n)
픽의 정리	격자 다각형의 내부점 수	O(n)
gcd 합	경계 격자점 수	O(n)
광선 던지기	점의 내부 판정	O(n)

모두 외적 또는 격자라는 단순한 토대 위에 서 있다는 점이 핵심입니다. 이로써 계산기하 파트를 마무리합니다.

다음 글부터는 마지막 파트인 계산 복잡도 이론으로 넘어갑니다. 그 첫 글로, “이 문제는 본질적으로 어려운가?”라는 질문에 답하는 NP-완전성을 다룹니다.

---

지난 글: 스위프 라인: 평면을 쓸어 기하 문제를 풀다

다음 글: NP-완전성: 어려운 문제의 경계

읽어주셔서 감사합니다. 😊