그레이엄 스캔(Graham's Scan) 알고리즘 — 볼록 껍질 경계점 찾기

볼록 껍질(Convex Hull)이란?

볼록 껍질(Convex Hull)은 주어진 모든 데이터 점들을 포함할 수 있는 가장 작은 닫힌 영역을 말합니다. 쉽게 비유하자면, 평면 위에 못을 박아 두고 고무줄을 팽팽하게 둘렀을 때 고무줄이 만드는 형태와 같습니다.

그레이엄 스캔 알고리즘의 동작 원리

그레이엄 스캔(Graham's Scan)은 볼록 껍질의 꼭짓점, 즉 경계점을 효율적으로 찾는 대표적인 기하학 알고리즘입니다. 시간 복잡도는 O(n log n)으로, 정렬 단계가 지배합니다.

알고리즘은 다음 순서로 진행됩니다.

시작점 선택: y좌표가 가장 작은 점(같다면 x좌표가 더 작은 점)을 찾아 시작점으로 삼습니다.
각도 정렬: 나머지 n-1개의 점을 시작점을 기준으로 반시계 방향 각도 순서대로 정렬합니다.
중복 제거: 같은 각도를 이루는 점들이 여러 개라면, 시작점에서 가장 멀리 있는 점 하나만 남기고 모두 제거합니다.
스택 탐색: 정렬된 점들을 스택에 넣어가며 검사합니다. 스택 최상단 점, 그 아래 점, 새로 선택한 점 points[i]가 반시계 방향을 이루지 않으면 스택에서 요소를 하나씩 제거한 뒤, 확인이 끝나면 points[i]를 스택에 삽입합니다.

입력 및 출력 예시

입력:
점 집합: {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
출력:
볼록 껍질의 경계점:
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

알고리즘 의사 코드

findConvexHull(points, n)

입력 − 점들의 집합, 점의 개수 n

출력 − 볼록 껍질의 경계점들

Begin
    minY := points[0].y
    min := 0

    // 가장 아래(또는 가장 왼쪽)에 있는 점 찾기
    for i := 1 to n-1 do
        y := points[i].y
        if y < minY or minY = y and points[i].x < points[min].x, then
            minY := points[i].y
            min := i
    done

    swap points[0] and points[min]
    p0 := points[0]
    sort points from points[1] to end   // 각도 기준 정렬
    arrSize := 1

    // 일직선상(colinear)에 있는 중복 점 제거
    for i := 1 to n, do
        when i < n-1 and (p0, points[i], points[i+1]) are collinear, do
            i := i + 1
        done
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    done

    if arrSize < 3, then
        return cHullPoints   // 최소 3개의 점이 필요함

    push points[0] into stack
    push points[1] into stack
    push points[2] into stack

    // 나머지 점들을 스택으로 처리
    for i := 3 to arrSize, do
        while top of stack, item below the top and points[i] is not in
            anticlockwise rotation, do
            delete top element from stack
        done
        push points[i] into stack
    done

    while stack is not empty, do
        item stack top element into cHullPoints
        pop from stack
    done
End

C++ 구현 예제

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;

struct point {     // 2차원 평면의 점 정의
    int x, y;
};

point p0;          // 기준점(시작점)

// 스택의 두 번째 상단 요소를 반환하는 함수
point secondTop(stack<point>&stk) {
    point tempPoint = stk.top(); stk.pop();
    point res = stk.top();
    stk.push(tempPoint);
    return res;
}

// 두 점 사이 거리의 제곱
int squaredDist(point p1, point p2) {
    return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

// 세 점의 방향 판별 (0: 일직선, 2: 반시계, 1: 시계)
int direction(point a, point b, point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;      // 일직선상(colinear)
    else if(val < 0)
        return 2;      // 반시계 방향
    return 1;          // 시계 방향
}

// 각도 기준 비교 함수(qsort용)
int comp(const void *point1, const void*point2) {
    point *p1 = (point*)point1;
    point *p2 = (point*)point2;
    int dir = direction(p0, *p1, *p2);

    if(dir == 0)   // 각도가 같으면 더 가까운 점을 앞으로
        return (squaredDist(p0, *p2) >= squaredDist(p0, *p1))?-1 : 1;
    return (dir==2)? -1 : 1;
}

vector<point>findConvexHull(point points[], int n) {
    vector<point> convexHullPoints;
    int minY = points[0].y, min = 0;

    // 가장 아래 또는 가장 왼쪽에 있는 점 찾기
    for(int i = 1; i<n; i++) {
        int y = points[i].y;
        if((y < minY) || (minY == y) && points[i].x < points[min].x) {
            minY = points[i].y;
            min = i;
        }
    }

    swap(points[0], points[min]);   // 기준점을 0번 위치로 이동
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp);   // 각도순 정렬

    int arrSize = 1;
    for(int i = 1; i<n; i++) {
        // i번째와 (i+1)번째 점의 각도가 같으면 중복 제거
        while(i < n-1 && direction(p0, points[i], points[i+1]) == 0)
            i++;
        points[arrSize] = points[i];
        arrSize++;
    }

    if(arrSize < 3)
        return convexHullPoints;   // 최소 3개의 점 필요, 없으면 빈 리스트 반환

    // 스택 생성 후 처음 세 점 삽입
    stack<point> stk;
    stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);

    for(int i = 3; i<arrSize; i++) {   // 나머지 점들 처리
        // 왼쪽 회전(반시계)이 아니면 스택에서 제거
        while(direction(secondTop(stk), stk.top(), points[i]) != 2)
            stk.pop();
        stk.push(points[i]);
    }

    while(!stk.empty()) {
        convexHullPoints.push_back(stk.top());   // 결과 수집
        stk.pop();
    }
}

int main() {
    point points[] = {{-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},
                      {3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};
    int n = 18;
    vector<point> result;
    result = findConvexHull(points, n);
    cout << "볼록 껍질의 경계점:"<<endl;
    vector<point>::iterator it;

    for(it = result.begin(); it!=result.end(); it++)
        cout << "(" << it->x << ", " <<it->y <<") ";
}

실행 결과

볼록 껍질의 경계점:
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

정리

그레이엄 스캔 알고리즘은 기준점 선정 → 각도 정렬 → 스택 기반 방향 검사의 3단계로 볼록 껍질을 구성합니다. 특히 스택을 활용해 반시계 방향 조건을 위배하는 점을 즉시 제거하기 때문에, 전체 과정을 O(n log n)의 시간 안에 처리할 수 있다는 점이 가장 큰 장점입니다.