C++ 자비스 알고리즘(Jarvis's Algorithm)으로 볼록 껍질(Convex Hull) 구현하기

이 글에서는 자비스 알고리즘(Jarvis's Algorithm)을 사용하여 주어진 점 집합의 볼록 껍질(Convex Hull)을 찾는 방법을 C++ 코드와 함께 살펴봅니다.

볼록 껍질(Convex Hull)이란?

볼록 껍질은 주어진 모든 점을 경계 위에 포함하거나 내부에 담을 수 있는 가장 작은 볼록 다각형을 의미합니다. 쉽게 비유하면, 평면 위에 여러 개의 못을 박고 고무줄을 팽팽하게 늘어뜨렸을 때 만들어지는 외곽 형태라고 생각하면 이해하기 쉽습니다.

자비스 알고리즘(선물 포장 알고리즘)의 동작 원리

자비스 알고리즘은 선물을 포장하듯 점들을 하나씩 감싸 나간다고 하여 선물 포장(Gift Wrapping) 알고리즘이라고도 불립니다. 동작 과정은 다음과 같습니다.

가장 왼쪽에 있는 점을 시작점으로 선택합니다.
시계 방향으로 회전하면서 각 단계마다 가장 바깥쪽에 있는 점을 차례로 선택해 감싸 줍니다.
다시 시작점으로 돌아올 때까지 이 과정을 반복하면 볼록 껍질이 완성됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 점(point)의 구조체
struct Point {
    int x, y;
};

// 세 점의 위치 관계(방향)를 계산하는 함수
int cal_orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;      // 세 점이 일직선상에 있음
    return (val > 0) ? 1 : 2;    // 시계 또는 반시계 방향
}

// 볼록 껍질을 계산하고 출력하는 함수
void convexHull(Point points[], int n) {
    if (n < 3) return;           // 점이 3개 미만이면 껍질을 만들 수 없음

    vector<Point> hull;

    // 가장 왼쪽에 있는 점 찾기
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    // 시계 방향으로 이동하며 껍질 구성
    int p = l, q;
    do {
        // 현재 점을 결과에 추가
        hull.push_back(points[p]);
        q = (p + 1) % n;
        for (int i = 0; i < n; i++) {
            // 더 바깥쪽에 있는 점을 선택
            if (cal_orientation(points[p], points[i], points[q]) == 2)
                q = i;
        }
        p = q;
    } while (p != l);            // 시작점으로 돌아올 때까지 반복

    for (int i = 0; i < hull.size(); i++)
        cout << "(" << hull[i].x << ", "
             << hull[i].y << ")\n";
}

int main() {
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

실행 결과

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

시간 복잡도

자비스 알고리즘의 시간 복잡도는 O(nh)입니다. 여기서 n은 전체 점의 개수, h는 볼록 껍질을 이루는 점의 개수입니다. 최악의 경우 O(n²)까지 느려질 수 있기 때문에, 점의 개수가 많은 상황에서는 O(n log n)의 성능을 보이는 그레이엄 스캔(Graham Scan) 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.