C++로 배우는 볼록 껍질(Convex Hull) 모노톤 체인 알고리즘

이 튜토리얼에서는 주어진 점들의 집합에 대한 볼록 껍질(Convex Hull)을 구하는 프로그램을 다룹니다.

볼록 껍질이란, 주어진 모든 점들을 경계선 위 또는 내부에 포함하는 가장 작은 볼록 다각형을 의미합니다. 이를 효율적으로 계산하기 위해 널리 사용되는 방법이 바로 모노톤 체인(Monotone Chain) 알고리즘, 즉 Andrew의 알고리즘입니다.

알고리즘의 핵심 아이디어

모노톤 체인 알고리즘은 다음과 같은 순서로 동작합니다.

1. 모든 점을 x좌표, 그다음 y좌표 기준으로 사전순(lexicographically) 정렬합니다.
2. 정렬된 점들을 순회하며 아래쪽 볼록 껍질(lower hull)을 만듭니다. 이때 외적(cross product)을 계산하여 시계 방향으로 꺾이는 점들은 제거합니다.
3. 반대 방향으로 순회하며 위쪽 볼록 껍질(upper hull)을 만듭니다.
4. 두 결과를 합치면 전체 볼록 껍질이 완성됩니다.

외적 값이 0 이하라면 세 점이 일직선상에 있거나 시계 방향으로 꺾였다는 의미이므로, 해당 중간 점은 볼록 껍질에서 제외됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
#define llu long long int
using namespace std;
// 주어진 점을 나타내는 구조체
struct Point {
    llu x, y;
    bool operator<(Point p){
        return x < p.x || (x == p.x && y < p.y);
    }
};
// 직접 만든 벡터의 외적(cross product) 계산
llu calc_crossproduct(Point O, Point A, Point B){
    return (A.x - O.x) * (B.y - O.y)
    - (A.y - O.y) * (B.x - O.x);
}
// 경계 위의 점들 계산
vector<Point> convex_hull(vector<Point> A){
    int n = A.size(), k = 0;
    if (n <= 3)
        return A;
    vector<Point> ans(2 * n);
    // 점들을 사전순으로 정렬
    sort(A.begin(), A.end());
    // 아래쪽 볼록 껍질(lower hull) 생성
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && calc_crossproduct(ans[k - 2],
        ans[k - 1], A[i]) <= 0)
            k--;
        ans[k++] = A[i];
    }
    // 위쪽 볼록 껍질(upper hull) 생성
    for (size_t i = n - 1, t = k + 1; i > 0; --i) {
        while (k >= t && calc_crossproduct(ans[k - 2],
        ans[k - 1], A[i - 1]) <= 0)
            k--;
        ans[k++] = A[i - 1];
    }
    // 배열 크기 조정
    ans.resize(k - 1);
    return ans;
}
int main(){
    vector<Point> points;
    points.push_back({ 0, 3 });
    points.push_back({ 2, 2 });
    points.push_back({ 1, 1 });
    points.push_back({ 2, 1 });
    points.push_back({ 3, 0 });
    points.push_back({ 0, 0 });
    points.push_back({ 3, 3 });
    vector<Point> ans = convex_hull(points);
    for (int i = 0; i < ans.size(); i++)
        cout << "(" << ans[i].x << ", "
        << ans[i].y << ")" << endl;
    return 0;
}

실행 결과

(0, 0)
(3, 0)
(3, 3)
(0, 3)

시간 복잡도

모노톤 체인 알고리즘의 시간 복잡도는 정렬 단계가 지배하므로 O(n log n)입니다. 정렬 이후의 볼록 껍질 생성 과정은 각 점이 최대 두 번씩만 처리되므로 선형 시간 O(n)에 완료됩니다. 이 덕분에 Graham 스캔 등 다른 알고리즘과 함께 계산 기하학 분야에서 가장 널리 쓰이는 볼록 껍질 알고리즘 중 하나로 자리 잡았습니다.