ジャービスマーチアルゴリズムとは？凸包の境界点を求める手順とC++実装例を解説

ジャービスマーチアルゴリズムとは

ジャービスマーチ（Jarvis March）アルゴリズムは、与えられた点群から凸包（convex hull）の頂点となる境界点を検出するためのアルゴリズムです。包装紙を包むように凸包の外周を辿っていくことから、「ギフト包装法（Gift Wrapping Algorithm）」とも呼ばれています。

データセットの中で最も左（x座標が最小）にある点を出発点とし、そこから反時計回りに点を辿りながら凸包に含まれる点を順に確定していきます。現在の点から見た各点の向き（外積の符号）を調べることで次の点を選び、最も外側に位置する点を採用します。すべての点を巡り、次の候補が再び出発点に戻った時点でアルゴリズムを終了します。

入力と出力

入力:
点の集合: {(-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)

入力: 点の集合と点の個数。

出力: 凸包の角点（頂点）。

Begin
    start := points[0]
    for each point i, do
        if points[i].x < start.x, then        // 最も左にある点を取得
            start := points[i]
    done

    current := start
    出発点を結果集合に追加する
    同一直線上の点を格納するためのcolPts集合を定義する

    while true, do                             // 無限ループを開始
        next := points[i]
        for all points i except 0th point, do
            if points[i] = current, then
                以下の処理をスキップし、次の反復へ
            val := current, next, points[i] の外積

            if val > 0, then
                next := points[i]
                colPts配列をクリアする
            else if val = 0, then
                if nextがpoints[i]よりcurrentに近い, then
                    nextをcolPtsに追加する
                    next := points[i]
                else
                    points[i]をcolPtsに追加する
        done

        colPts内の全要素を結果に追加する
        if next = start, then
            ループを抜ける
        nextを結果に挿入する
        current := next
    done
    return result
End

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;    // 結果が負ならcは左側、正なら右側、0ならa,b,cは同一直線上
}

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) {          // 3点が同一直線上にある場合
                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 は凸包に含まれる頂点の数を表します。凸包の頂点数 h が小さい場合には効率的に動作しますが、すべての点が凸包上に並ぶような最悪ケースでは O(n²) に近づきます。考え方がシンプルで直感的なため、学習用途や小規模な点群の処理に特に適したアルゴリズムといえます。