Jarvis March(자비스 행진) 알고리즘은 주어진 점(point) 집합으로부터 볼록 껍질(convex hull)의 꼭짓점을 찾아내는 대표적인 계산 기하학 알고리즘입니다.
이 알고리즘은 데이터 집합에서 가장 왼쪽에 있는 점에서 출발하여, 반시계 방향으로 회전하면서 볼록 껍질에 속하는 점들을 하나씩 선택해 나갑니다. 현재 점을 기준으로 나머지 점들의 방향(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)
입력: 점들의 배열, 점의 개수 n
출력: 볼록 껍질의 꼭짓점들
Begin
start := points[0]
for each point i, do
if points[i].x < start.x, then // 가장 왼쪽에 있는 점 찾기
start := points[i]
done
current := start
결과 집합(result)에 시작점 추가
일직선상의 점들을 저장할 colPts 집합 정의
while true, do // 무한 루프 시작
next := points[0]
for all points i except 0th point, do
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가 points[i]보다 current에 더 가까우면, then
colPts에 next 추가
next := points[i]
else
colPts에 points[i] 추가
done
colPts의 모든 항목을 결과에 추가
if next = start, then // 시작점으로 돌아왔다는 것은 영역 순회가 끝났음을 의미
break the loop
insert next into the result
current := next
done
return result
End여기서 외적(cross product)의 부호는 세 점의 상대적 위치를 판별하는 데 사용됩니다. 결과가 음수면 세 번째 점은 왼쪽에, 양수면 오른쪽에, 0이면 세 점이 일직선상에 있다는 뜻입니다.
예제 코드
#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) { // ab 벡터를 기준으로 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;
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번째 점이 nextTarget과 같거나 더 가까울 때
}
}
}
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)
참고로 Jarvis March 알고리즘의 시간 복잡도는 O(nh)입니다. 여기서 n은 전체 점의 개수, h는 볼록 껍질을 이루는 꼭짓점의 개수입니다. 따라서 껍질을 이루는 점의 수가 적을 때 효율적으로 동작하며, 구현이 직관적이라는 장점이 있습니다.