볼록 껍질(Convex Hull)이란?
볼록 껍질(Convex Hull)은 주어진 모든 데이터 점들을 포함할 수 있는 가장 작은 닫힌 영역을 의미합니다. 쉽게 말해, 평면 위에 흩어져 있는 점들을 고무줄로 감쌌을 때 고무줄이 만드는 외곽선이라고 생각하면 이해하기 쉽습니다.
그레이엄 스캔(Graham's Scan) 알고리즘은 이러한 볼록 껍질의 꼭짓점(경계점)을 효율적으로 찾아내는 대표적인 기하학 알고리즘입니다.
그레이엄 스캔 알고리즘의 동작 원리
그레이엄 스캔은 다음과 같은 단계로 진행됩니다.
- 시작점 선택: 가장 아래에 있는 점(y 좌표가 가장 작은 점)을 선택하고, y값이 같다면 x 좌표가 더 작은 점을 선택합니다. 이 점이 볼록 껍질의 시작점이 됩니다.
- 각도 정렬: 나머지 n-1개의 점을 시작점 기준으로 반시계 방향 각도 순서대로 정렬합니다.
- 중복 각도 제거: 두 개 이상의 점이 동일한 각도를 형성하는 경우, 시작점에서 가장 먼 점 하나만 남기고 나머지는 제거합니다.
- 스택 처리: 남은 점들을 스택에 차례대로 넣습니다. 이때 스택의 최상단(top), 그 아래(second top), 새로 선택된 점 points[i]가 반시계 방향을 이루지 않으면 스택에서 요소를 제거(pop)하고, 검사를 통과하면 points[i]를 스택에 삽입(push)합니다.
입력 및 출력 예시
입력: 점 집합 {(-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 또는 minY = y이고 points[i].x < points[min].x이면
minY := points[i].y
min := i
done
points[0]과 points[min] 교환
p0 := points[0]
points[1]부터 끝까지 정렬
arrSize := 1
for i := 1 to n do
i < n-1이고 (p0, points[i], points[i+1])가 일직선상에 있는 동안
i := i + 1
done
points[arrSize] := points[i]
arrSize := arrSize + 1
done
if arrSize < 3이면
cHullPoints 반환
points[0], points[1], points[2]를 스택에 push
for i := 3 to arrSize do
스택 최상단, 그 아래 요소, points[i]가 반시계 방향 회전이 아니면
스택에서 최상단 요소 삭제
done
points[i]를 스택에 push
done
스택이 빌 때까지
스택 최상단 요소를 cHullPoints에 저장 후 pop
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); // 원래 최상단 요소 다시 push
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));
}
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; // 시계 방향
}
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); // 1번부터 끝까지 정렬
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)
정리
그레이엄 스캔 알고리즘은 정렬 단계에서 O(n log n), 스택 처리 단계에서 O(n)의 시간 복잡도를 가지므로 전체적으로 O(n log n)의 효율성을 보입니다. 이는 볼록 껍질 문제를 해결하는 가장 널리 사용되는 방법 중 하나로, 컴퓨터 그래픽스, 지리 정보 시스템(GIS), 충돌 감지 등 다양한 분야에서 활용됩니다.