볼록 껍질: 그레이엄 스캔과 모노톤 체인

지난 글에서 외적으로 세 점의 회전 방향을 판별하는 법을 익혔습니다. 이제 그 외적을 본격적으로 쓰는 첫 알고리즘을 만날 차례입니다. 평면에 흩어진 점들을 고무줄로 감싸면 어떤 모양이 될까요? 그 답이 볼록 껍질(convex hull) — 모든 점을 포함하는 가장 작은 볼록 다각형입니다. 충돌 판정, 최원점 쌍, 다각형 단순화 등 수많은 기하 문제의 전처리로 쓰입니다.

볼록 껍질이란

점 집합이 주어졌을 때, 볼록 껍질은 모든 점을 안에 담으면서 오목한 곳이 없는 가장 작은 다각형입니다. 직관적으로는 점들 바깥에 고무줄을 둘러 놓아 줄이는 모습입니다.

껍질의 꼭짓점은 입력 점들 중 일부이고, 나머지 점은 모두 그 내부에 들어갑니다. 핵심 성질은 껍질의 경계를 따라가면 항상 같은 방향(반시계)으로만 꺾인다는 것입니다. 우회전이 나타나는 순간 그 점은 껍질 꼭짓점이 될 수 없습니다. 바로 이 성질을 외적으로 검사합니다.

앤드류 모노톤 체인

여러 알고리즘 중 구현이 가장 깔끔하고 실수가 적은 것이 앤드류 모노톤 체인(Andrew’s monotone chain)입니다. 아이디어는 다음과 같습니다.

1. 점들을 (x, y) 사전순으로 정렬한다.
2. 왼쪽에서 오른쪽으로 훑으며 아래쪽 체인을 만든다.
3. 오른쪽에서 왼쪽으로 훑으며 위쪽 체인을 만든다.
4. 두 체인을 이어붙이면 전체 껍질이 된다.

각 체인은 스택으로 쌓되, 새 점을 넣을 때 직전 두 점과 함께 우회전(또는 일직선)을 만들면 가운데 점을 pop 합니다.

def ccw(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def convex_hull(pts):
    pts = sorted(set(pts))
    if len(pts) <= 2:
        return pts

    def half(points):
        st = []
        for p in points:
            while len(st) >= 2 and ccw(st[-2], st[-1], p) <= 0:
                st.pop()           # 우회전/일직선 제거
            st.append(p)
        return st

    lower = half(pts)
    upper = half(pts[::-1])
    # 양 끝점은 중복이므로 하나씩 제거하고 결합
    return lower[:-1] + upper[:-1]

정렬이 O(n log n), 스캔은 각 점이 한 번씩 push/pop 되므로 O(n)입니다. 따라서 전체 복잡도는 O(n log n), 정렬이 지배합니다.

그레이엄 스캔과의 관계

고전적인 그레이엄 스캔(Graham scan)은 가장 아래(같으면 가장 왼쪽) 점을 기준으로 나머지 점을 각도순으로 정렬한 뒤, 같은 방식으로 우회전을 pop 합니다. 모노톤 체인과 본질은 동일하지만, 각도 정렬에 외적 비교자를 써야 하고 동일 각도·일직선 처리가 까다롭습니다. 실무에서는 정렬 기준이 단순한 모노톤 체인을 더 많이 씁니다.

비교 항목	모노톤 체인	그레이엄 스캔
정렬 기준	좌표 사전순	기준점 각도순
일직선 처리	쉬움	까다로움
복잡도	O(n log n)	O(n log n)
구현 난이도	낮음	중간

일직선 점을 어떻게 다룰까

미묘하지만 중요한 결정이 하나 있습니다. 껍질 변 위에 놓인(일직선) 점을 꼭짓점에 포함할 것인가입니다. 위 코드의 ccw(...) <= 0 은 일직선 점도 제거해 최소 꼭짓점만 남깁니다. 만약 경계 위의 모든 점을 포함하고 싶다면 < 0 으로 바꿔 일직선을 유지합니다. 문제의 요구사항에 맞춰 등호 처리를 정확히 정하는 것이 흔한 버그 지점입니다.

# 최소 꼭짓점만        :  ccw(...) <= 0  → pop
# 경계 위 점 모두 포함  :  ccw(...) <  0  → pop

실전 주의점

• 중복 점: set으로 제거하지 않으면 ccw가 0을 반환해 꼬일 수 있습니다.
• 점이 2개 이하: 껍질이 다각형을 이루지 못하므로 별도 처리합니다.
• 오버플로: 외적은 좌표 제곱 규모까지 커집니다. C++이면 long long을 씁니다.
• 모든 점이 일직선: 결과가 선분이 되므로 호출 측에서 가정에 유의합니다.

볼록 껍질은 그 자체로도 쓰이지만, 회전하는 캘리퍼스(rotating calipers)로 최원점 쌍·최소 너비를 구하는 등 다양한 후속 알고리즘의 입구가 됩니다.

다음 글에서는 다시 기본으로 돌아가, 외적을 활용해 두 선분이 교차하는지를 정확히 판정하는 법을 다룹니다.

---

지난 글: 외적과 방향 판별: CCW의 모든 것

다음 글: 선분 교차 판정: 외적과 바운딩 박스

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