이 글에서는 볼록 껍질(Convex Hull)의 대표적인 예제를 다룹니다. 주어진 점들의 집합이 있을 때, 가능한 한 적은 수의 점만 사용하여 모든 점을 포함하는 다각형을 만들어야 하는 상황입니다. 이를 해결하기 위해 널리 알려진 자비스 마치(Jarvis March) 알고리즘, 즉 선물 포장(Gift Wrapping) 기법을 살펴보겠습니다.
자비스 마치 알고리즘이란?
자비스 마치 알고리즘은 주어진 데이터 점들의 집합으로부터 볼록 껍질의 꼭짓점(경계 점)들을 찾아내는 알고리즘입니다.
기본 동작 원리는 다음과 같습니다.
- 데이터 집합에서 가장 왼쪽에 있는 점부터 시작합니다.
- 현재 점에서 시작하여 반시계 방향으로 회전하면서 볼록 껍질에 포함될 점들을 차례로 선택합니다.
- 다음 점은 현재 점을 기준으로 각 후보 점들의 방향(orientation)을 검사하여 결정합니다.
- 회전 각도가 가장 커지는 지점, 즉 외곽에 있는 점이 선택됩니다.
- 모든 점을 순회한 뒤 다음 점이 다시 시작점이 되면 알고리즘을 종료합니다.
입력 및 출력 예시
입력 — 점들의 집합: {(-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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)
알고리즘 의사코드
findConvexHull(points, n)
입력: 점들의 배열 points, 점의 개수 n
출력: 볼록 껍질의 꼭짓점들
시작
start := points[0]
각 점 i에 대해 반복
if points[i].x < start.x then // 가장 왼쪽 점 찾기
start := points[i]
done
current := start
결과 집합에 시작점 추가
일직선상(colPts)의 점들을 저장할 집합 정의
while true do // 무한 루프 시작
next := points[0]
0번째 점을 제외한 모든 점 i에 대해 반복
if points[i] = current then
아래 부분 건너뛰고 다음 반복 진행
val := current, next, points[i]의 외적(cross product)
if val > 0 then
next := points[i]
colPts 배열 초기화
else if val = 0 then // 세 점이 일직선상에 있을 때
if next가 current에 points[i]보다 가까우면
next를 colPts에 추가
next := points[i]
else
points[i]를 colPts에 추가
done
colPts의 모든 항목을 결과에 추가
if next = start then
루프 탈출
next를 결과에 삽입
current := next
done
결과 반환
끝C++ 구현 예제
#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point{ // 2차원 평면의 점 정의
int x, y;
bool operator==(point p2){
if(x == p2.x && y == p2.y)
return 1;
return 0;
}
bool operator<(const point &p2)const{ // set 정렬용 더미 비교 함수
return true;
}
};
int crossProduct(point a, point b, point c){ // c가 ab 벡터 기준 어느 위치인지 판별
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
return y2*x1 - y1*x2; // 결과 < 0이면 c는 왼쪽, > 0이면 오른쪽, = 0이면 세 점 일직선
}
int distance(point a, point b, point c){
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
int item1 = (y1*y1 + x1*x1);
int item2 = (y2*y2 + x2*x2);
if(item1 == item2)
return 0; // b와 c가 a로부터 같은 거리일 때
else if(item1 < item2)
return -1; // b가 a에 더 가까울 때
return 1; // c가 a에 더 가까울 때
}
set<point> findConvexHull(point points[], int n){
point start = points[0];
for(int i = 1; i<n; i++){ // 시작할 가장 왼쪽 점 찾기
if(points[i].x < start.x)
start = points[i];
}
point current = start;
set<point> result; // 중복 점 방지를 위해 set 사용
result.insert(start);
vector<point> *collinearPoints = new vector<point>;
while(true){
point nextTarget = points[0];
for(int i = 1; i<n; i++){
if(points[i] == current) // 선택된 점이 현재 점이면 나머지 무시
continue;
int val = crossProduct(current, nextTarget, points[i]);
if(val > 0){ // i번째 점이 왼쪽에 있을 때
nextTarget = points[i];
collinearPoints = new vector<point>; // 일직선 점 목록 초기화
}else if(val == 0){ // 세 점이 일직선상에 있을 때
if(distance(current, nextTarget, points[i]) < 0){ // 더 가까운 점을 목록에 추가
collinearPoints->push_back(nextTarget);
nextTarget = points[i];
}else{
collinearPoints->push_back(points[i]); // i번째 점이 더 가깝거나 같을 때
}
}
}
vector<point>::iterator it;
for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){
result.insert(*it); // 일직선상의 모든 점을 결과 집합에 추가
}
if(nextTarget == start) // 다음 점이 시작점이면 영역 순회 완료
break;
result.insert(nextTarget);
current = nextTarget;
}
return result;
}
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;
set<point> result;
result = findConvexHull(points, n);
cout << "Boundary points of convex hull are: "<<endl;
set<point>::iterator it;
for(it = result.begin(); it!=result.end(); it++)
cout << "(" << it->x << ", " <<it->y <<") ";
}실행 결과
Boundary points of convex hull are: (-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)
정리
자비스 마치 알고리즘은 직관적인 구조 덕분에 이해하기 쉬우며, 볼록 껍질의 경계 점을 하나씩 감싸듯이 찾아간다는 점에서 '선물 포장'이라는 별칭으로도 불립니다. 시간 복잡도는 O(nh)(n은 전체 점의 개수, h는 볼록 껍질 꼭짓점의 개수)로, 점이 많고 껍질의 꼭짓점이 적은 경우 효율적으로 동작합니다. 위 예제처럼 외적(cross product)을 활용해 방향을 판단하고, 일직선상에 놓인 점들까지 처리하면 견고한 볼록 껍질 계산을 구현할 수 있습니다.