자비스 행진(Jarvis March) 알고리즘 – 볼록 껍질 꼭짓점 찾기

자비스 행진 알고리즘이란?

자비스 행진(Jarvis March) 알고리즘은 주어진 데이터 포인트 집합에서 볼록 껍질(convex hull)의 꼭짓점을 찾아내는 대표적인 계산 기하학(computational geometry) 알고리즘입니다. 포장지로 물건을 감싸듯 외곽 점들을 따라가며 볼록 껍질을 만든다고 하여 '선물 포장(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)

알고리즘 동작 과정

입력: 점들의 배열, 점의 개수 n

출력: 볼록 껍질의 꼭짓점들

시작
    start := points[0]
    각 점 i에 대해 반복
        만약 points[i].x < start.x 이면        // 가장 왼쪽에 있는 점을 찾음
            start := points[i]
    반복 종료

    current := start
    시작점을 결과 집합(result)에 추가
    일직선상의 점들을 저장할 집합(colPts) 정의

    무한 루프 시작                             // true 조건의 while 루프
        next := points[i]
        0번째 점을 제외한 모든 점 i에 대해 반복
            만약 points[i] = current 이면
                아래 내용을 건너뛰고 다음 반복으로 진행
            val := current, next, points[i]의 외적(cross product)

            만약 val > 0 이면                  // i번째 점이 왼쪽에 위치
                next := points[i]
                colPts 배열 초기화
            그렇지 않고 val = 0 이면           // 세 점이 일직선상에 위치
                만약 next가 points[i]보다 current에 더 가까우면
                    next를 colPts에 추가
                    next := points[i]
                그렇지 않으면
                    points[i]를 colPts에 추가
        반복 종료

        colPts의 모든 항목을 결과에 추가
        만약 next = start 이면                 // 시작점으로 돌아왔다는 것은 영역 순회 완료
            루프 탈출
        next를 결과에 삽입
        current := next
    루프 종료
    result 반환
종료

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) {   // 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)

시간 복잡도

자비스 행진 알고리즘의 시간 복잡도는 O(nh)입니다. 여기서 n은 전체 점의 개수, h는 볼록 껍질을 이루는 꼭짓점의 개수를 의미합니다. 최악의 경우(h ≈ n)에는 O(n²)까지 증가할 수 있으므로, 점들이 볼록 껍질 경계에 많이 분포해 있는 데이터에서는 성능이 저하될 수 있습니다. 반면 볼록 껍질을 이루는 점이 적은 데이터에서는 매우 효율적으로 동작합니다.