볼록 껍질 ① — 정의, CCW, 그리고 Package Wrapping

평면에 못을 여러 개 박아 두고 고무줄을 크게 벌려 감싼 뒤 놓으면, 고무줄은 바깥쪽 못들에 걸쳐 팽팽한 다각형이 된다. 이 다각형이 볼록 껍질(convex hull) 이다. 계산 기하의 가장 기본적인 문제이자, 여러 알고리즘의 출발점이 된다.

이 포스트에서 다루는 내용

볼록 껍질의 정의와 “가장 작다”는 말의 모호함
설명을 단순하게 하는 네 가지 가정
모든 선분을 검사하는 브루트포스 $O(N^3)$
세 점의 회전 방향을 정수 연산으로 판정하는 CCW
포장지로 감싸듯 껍질을 찾는 Package Wrapping $O(NH)$

볼록 껍질이란

평면에 $N$ 개의 점이 흩어져 있다. 볼록 껍질은 이 점들을 모두 포함하는 가장 작은 볼록 다각형이다.

흩어진 점들과 이를 감싸는 볼록 껍질 — 바깥쪽 점들이 다각형의 꼭짓점이 되고, 안쪽 점들은 내부에 담긴다.

여기서 “가장 작다”는 말은 넓이로 재도, 둘레로 재도 같은 다각형을 가리킨다. 모든 점을 감싸는 볼록 다각형 중 넓이가 최소인 것이 볼록 껍질이고, 이 다각형은 점들을 감싸는 어떤 다각형(볼록이 아니어도)보다도 둘레가 짧다. 그래서 두 기준이 충돌하지 않고 답이 하나로 정해진다. (기하에서 엄밀한 정의는 까다로우므로 여기서는 이 정도로 넘어간다.)

“볼록(convex)“이라는 조건이 핵심이다. 볼록 다각형은 어떤 두 내부 점을 이어도 그 선분이 다각형을 벗어나지 않는다. 우리는 이 볼록 조건을 먼저 고정한 뒤, 그 안에서 모든 점을 감싸는 가장 작은 다각형을 찾는다. 오목한 다각형까지 허용하면 점들 사이로 파고들어 넓이를 더 줄일 수도 있지만, 그런 것은 볼록 껍질이 아니다.

볼록 다각형과 오목 다각형 — 볼록은 내부 두 점을 잇는 선분이 항상 내부에 있고, 오목은 선분이 밖으로 나간다.

가정

현업에서는 온갖 예외가 생기지만, 그것까지 전부 처리하면 알고리즘의 본질이 가려진다. 그래서 설명하는 동안은 다음 네 가지를 가정한다.

점이 3개 이상이다 ( $N \ge 3$ ).
모든 점의 x좌표가 서로 다르다.
모든 점의 y좌표가 서로 다르다.
한 직선 위에 점이 3개 이상 있는 경우는 없다.

첫 가정은 「다각형」이라는 말이 성립하게 해 준다. 점이 0개면 감쌀 것이 없고, 1개면 점 하나, 2개면 선분이라 넓이가 0인 도형이 나온다. 이런 입력에서는 볼록 껍질을 무엇으로 정의할지부터 따로 정해야 하므로, 이 글은 $N \ge 3$ 만 다룬다. 뒤에 나오는 코드도 같은 전제 위에 있어서 빈 입력을 넣으면 없는 원소를 읽는다.

네 번째 가정이 특히 편하다. 세 점이 일직선 위에 있으면 “회전 방향”이 정의되지 않아(뒤에서 볼 CCW가 0이 된다) 경계 처리가 복잡해지는데, 이를 배제하면 모든 세 점이 명확히 좌회전이나 우회전 중 하나가 된다.

브루트포스 — $O(N^3)$

가장 단순한 접근은 정의를 그대로 옮기는 것이다. 껍질은 결국 몇 개의 변(선분) 으로 이루어진다. 그러니 “어떤 선분이 껍질의 변인가?”를 판정할 수 있으면 된다.

판정 기준은 간단하다. 두 점을 잇는 선분을 직선으로 무한히 늘렸을 때, 나머지 모든 점이 그 직선의 한쪽에만 있다면 그 선분은 껍질의 변이다. 반대로 점들이 직선의 양쪽으로 갈리면, 그 선분은 껍질 내부를 가로지르는 것이므로 변이 아니다.

브루트포스 판정 — 왼쪽: 나머지 점이 모두 한쪽에 있어 껍질의 변. 오른쪽: 점이 양쪽으로 갈려 변이 아님.

가능한 선분은 $\binom{N}{2} = O(N^2)$ 개다. 각 선분마다 나머지 $O(N)$ 개의 점이 모두 같은 쪽인지 확인해야 하므로, 전체 비용은

O(N^2) \times O(N) = O(N^3)

이다. “한쪽에 있는가”를 어떻게 계산하는지가 다음 주제인 CCW다.

CCW — 세 점의 회전 방향

CCW(Counter-ClockWise) 는 세 점 $A \to B \to C$ 를 차례로 따라갈 때 왼쪽으로 도는가(반시계), 오른쪽으로 도는가(시계) 를 판정한다. 계산 기하의 거의 모든 알고리즘이 이 하나의 연산 위에 세워진다.

CCW — 세 점을 A→B→C로 따라갈 때 왼쪽으로 꺾이면 반시계(좌회전), 오른쪽으로 꺾이면 시계(우회전).

어떻게 계산할까? 직관은 기울기 비교에서 나온다. $x$ 가 증가하는 방향으로 세 점이 놓인 경우로 한정해 보면, $A \to B$ 의 기울기 $m_{AB}$ 보다 $B \to C$ 의 기울기 $m_{BC}$ 가 더 크면(더 가파르게 위로 꺾이면) 왼쪽으로 도는 것이다.

m_{AB} = \frac{y_B - y_A}{x_B - x_A}, \quad m_{BC} = \frac{y_C - y_B}{x_C - x_B}

$m_{BC} > m_{AB}$ 의 양변에 분모를 곱해 정리하면,

(x_B - x_A)(y_C - y_B) > (y_B - y_A)(x_C - x_B)

양변을 모두 좌변으로 옮겨 전개하면 깔끔한 식 하나가 남는다. (기울기 비교는 위 배치에서의 직관일 뿐이고, 분모 부호에 따라 부등호가 뒤집힐 수 있다. 그래서 실제 판정은 아래 식의 부호로 하며, 이 부호 판정은 점 배치에 상관없이 언제나 옳다.)

\text{ccw}(A, B, C) = x_A y_B + x_B y_C + x_C y_A - x_A y_C - x_B y_A - x_C y_B

이 값의 부호가 회전 방향이다.

CCW 부호의 의미

$\text{ccw}(A,B,C) > 0$ → 반시계(좌회전)
$\text{ccw}(A,B,C) < 0$ → 시계(우회전)
$\text{ccw}(A,B,C) = 0$ → 세 점이 일직선 (가정으로 배제)

이 식은 사실 벡터 $\vec{AB}$ 와 $\vec{AC}$ 의 외적(cross product) 이고, 그 절댓값은 두 벡터가 만드는 평행사변형의 넓이(부호 있는 넓이의 2배)와 같다. 부호는 $\vec{AC}$ 가 $\vec{AB}$ 의 어느 쪽에 있는지를 알려 준다.

CCW와 부호 있는 넓이 — 두 벡터 AB, AC가 만드는 평행사변형의 부호 있는 넓이가 CCW 값이며, 부호가 회전 방향을 준다.

왜 각도가 아니라 CCW인가

회전 방향을 각도( $\arctan$ )로 재면 삼각함수 때문에 결과가 double이 되고, 부동소수점 오차로 미세하게 가까운 점들이 구별되지 않을 수 있다. 반면 CCW 식은 덧셈과 곱셈뿐이라, 좌표가 정수면 결과도 정수다. 오차 없이 부호만 보면 되므로 훨씬 안전하다. 다만 곱셈이 있으므로 오버플로 범위를 따져야 한다. 좌표 절댓값이 약 $10^9$ 이하이면 CCW 값이 최대 $8 \times 10^{18}$ 규모라 long long( $\approx 9.2 \times 10^{18}$ ) 안에 들어간다. 좌표가 이보다 크면 곱셈 단계에서 넘칠 수 있으므로 __int128로 계산해야 한다.

코드로 옮기면 한 줄이다.

struct P { long long x, y; };

// 세 점 a, b, c의 회전 방향
//  > 0 : 반시계(좌회전),  < 0 : 시계(우회전),  = 0 : 일직선
long long ccw(P a, P b, P c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

위 전개식과 이 코드는 같은 값이다. (b-a)와 (c-a) 두 벡터의 외적 형태로 쓰면 항이 줄어 실수를 덜 한다.

Package Wrapping — $O(NH)$

브루트포스의 $O(N^3)$ 은 너무 느리다. Package Wrapping(선물 포장, Jarvis march)은 이름 그대로 포장지로 점들을 한 변씩 감싸 나가는 방법이다.

시작점. y좌표가 가장 작은 점 $Y$ 에서 출발한다. 모든 점이 $Y$ 보다 위에 있으므로, $Y$ 는 반드시 껍질 위의 점이다.

한 걸음. 현재 점에서 다음 껍질 점을 찾는다. 각도를 직접 계산할 수도 있지만, 앞서 본 이유로 CCW를 쓴다. 현재 점에서 후보 선분을 하나 잡고, 나머지 모든 점을 돌며 더 바깥쪽(현재 선분 기준 더 시계 방향)에 있는 점이 나오면 후보를 그 점으로 바꾼다. 한 바퀴 다 돌면 남은 후보가 가장 바깥 점, 즉 다음 껍질 점이다.

Package Wrapping 한 걸음 — 현재 점에서 나머지 점들에 CCW를 돌려, 가장 바깥(모든 점을 왼쪽에 두는) 점을 다음 껍질 점으로 고른다.

반복. 이렇게 찾은 다음 점으로 이동해 같은 일을 되풀이한다. $Y \to Y' \to Y'' \to \cdots$ 로 껍질을 한 변씩 감싸다가 다시 시작점 $Y$ 로 돌아오면 껍질이 완성된다.

Package Wrapping 전체 흐름 — 시작점에서 시작해 한 변씩 바깥을 감싸며 시작점으로 돌아올 때까지 반복한다.

// pts: 점 목록, ccw(): 위에서 정의
vector<P> giftWrapping(vector<P> pts) {
    int n = pts.size();

    // 시작점: y가 가장 작은 점 (반드시 껍질 위의 점)
    int start = 0;
    for (int i = 1; i < n; i++)
        if (pts[i].y < pts[start].y) start = i;

    vector<P> hull;
    int cur = start;
    do {
        hull.push_back(pts[cur]);
        int next = (cur + 1) % n;                 // 임의의 후보 하나
        for (int i = 0; i < n; i++) {
            // cur→next 선분보다 i가 더 시계 방향(바깥)이면 후보 갱신
            if (ccw(pts[cur], pts[next], pts[i]) < 0)
                next = i;
        }
        cur = next;                               // 다음 껍질 점으로 이동
    } while (cur != start);                        // 시작점으로 돌아오면 종료

    return hull;
}

복잡도. 한 걸음은 나머지 점을 한 번씩 훑으므로 $O(N)$ 이다. 걸음 수는 껍질 위의 점 개수 $H$ 와 같다(한 걸음에 껍질 점 하나를 확정하므로). 따라서 전체는

O(N) \times H = O(NH)

이다. 껍질 위의 점이 적으면( $H$ 가 작으면) 매우 빠르지만, 최악의 경우 모든 점이 껍질 위에 있어( $H = N$ ) $O(N^2)$ 이 된다.

각도 정렬이 아니다

“각도가 가장 작은 점을 고른다”고 하면 매 걸음 정렬( $O(N \log N)$ )이 필요해 보이지만, 실제로는 다음 점 하나만 필요하다. 이는 정렬이 아니라 최댓값 찾기와 같은 선형 탐색( $O(N)$ )이다. 배열에서 최솟값 하나 찾는 데 전체를 정렬할 필요가 없는 것과 같다. 그래서 한 걸음이 $O(N \log N)$ 이 아니라 $O(N)$ 이다.

핵심 정리

볼록 껍질은 모든 점을 포함하는 가장 작은 볼록 다각형이다. “둘레 최소”와 “넓이 최소”가 같은 다각형을 가리킨다.
브루트포스는 모든 선분이 껍질의 변인지 검사한다. 선분 $O(N^2)$ 개 × 판정 $O(N)$ $= O(N^3)$ .
CCW는 세 점의 회전 방향을 $x_A y_B + x_B y_C + x_C y_A - x_A y_C - x_B y_A - x_C y_B$ 의 부호로 판정한다. 외적과 같으며, 정수 연산이라 오차가 없다.
Package Wrapping은 최하단 점에서 시작해 CCW로 다음 껍질 점을 선형 탐색하며 한 변씩 감싼다. $O(NH)$ , 최악 $O(N^2)$ .
다음 점 하나만 찾으면 되므로 매 걸음은 정렬이 아니라 선형 탐색 $O(N)$ 이다.

이어지는 글

Package Wrapping의 $O(NH)$ 는 껍질 점이 많을 때 $O(N^2)$ 까지 느려진다. 2편에서는 Graham Scan을 다룬다. 시작점 기준으로 각도 정렬을 한 번 한 뒤, 스택으로 좌회전만 남기며 훑어 $O(N \log N)$ 에 껍질을 구한다. 나아가 볼록 껍질이 정렬만큼 어렵다는 $\Omega(N \log N)$ 하한도 살펴본다.

계산 기하의 다른 문제인 가장 가까운 점 쌍도 함께 보면 좋다.