C++로 구현하는 2차원 선물 포장(Gift Wrapping) 알고리즘

이 글에서는 2차원 평면에서 선물 포장 알고리즘(Gift Wrapping Algorithm)을 구현하는 C++ 프로그램을 다룹니다. 선물 포장 알고리즘은 주어진 점(point) 집합의 볼록 껍질(Convex Hull)을 계산하는 대표적인 기하 알고리즘으로, 선물 상자를 포장할 때 끈을 감싸듯이 가장 바깥쪽 점들을 순서대로 찾아가는 방식이라는 의미에서 이런 이름이 붙었습니다.

알고리즘 개요

선물 포장 알고리즘의 동작 과정은 다음과 같습니다.

시작
    n개의 점 집합에 대한 볼록 껍질을 구하는 convexHull() 함수 정의:
    볼록 껍질을 구성하려면 최소 3개 이상의 점이 필요하다.
    결과를 저장할 배열을 초기화한다.
    가장 왼쪽에 있는 점을 찾는다.
    가장 왼쪽 점에서 시작하여,
    다시 시작점에 도달할 때까지 반시계 방향으로 이동한다.
    결과를 출력한다.
끝

핵심 아이디어

알고리즘의 핵심은 세 점의 방향(orientation)을 판별하는 것입니다. 점 a, b, c에 대해 외적(cross product)의 부호를 이용하면 세 점이 일직선상에 있는지, 시계 방향인지, 반시계 방향인지를 판별할 수 있습니다. 현재 점에서 다음 점을 선택할 때, 모든 점에 대해 반시계 방향으로 가장 바깥쪽에 있는 점을 골라 연결하면 볼록 껍질이 완성됩니다.

예제 코드

#include <iostream>
using namespace std;
#define INF 10000
struct P {
    int x;
    int y;
};
int orient(P a, P b, P c) {
    int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if (v == 0)
        return 0; // 세 점이 일직선상에 있음
    return (v > 0) ? 1 : 2; // 1: 시계 방향, 2: 반시계 방향
}
void convexHull(P points[], int m) {
    if (m < 3) // 최소 3개의 점이 필요함
        return;
    int n[m];
    for (int i = 0; i < m; i++)
        n[i] = -1;
    int l = 0; // 결과 초기화
    for (int i = 1; i < m; i++)
        if (points[i].x < points[l].x)
            l = i; // 가장 왼쪽 점 찾기
    int p = l, q;
    do {
        q = (p + 1) % m;
        for (int i = 0; i < m; i++)
            if (orient(points[p], points[i], points[q]) == 2)
                q = i;
        n[p] = q;
        p = q;
    } while (p != l);
    for (int i = 0; i < m; i++) {
        if (n[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}
int main() {
    P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
    cout << "볼록 껍질에 포함되는 점들: ";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

실행 결과

볼록 껍질에 포함되는 점들: (0, 4)
(4, 1)
(3, 0)
(1, 1)
(7, 6)

시간 복잡도

선물 포장 알고리즘의 시간 복잡도는 O(nh)입니다. 여기서 n은 전체 점의 개수, h는 볼록 껍질을 이루는 점의 개수입니다. 각 볼록 껍질 정점을 찾을 때마다 모든 점을 한 번씩 검사하기 때문입니다. 따라서 볼록 껍질의 크기가 작은 경우에는 효율적이지만, 최악의 경우 O(n²)까지 증가할 수 있습니다. 이러한 특성 덕분에 선물 포장 알고리즘은 출력 민감(output-sensitive) 알고리즘으로 분류됩니다.