凸包（Convex Hull）とは？ジャービス・マーチ法による求め方とC++実装例

本記事では、計算幾何学における重要な概念である凸包（Convex Hull）について、具体的な例を通じて解説します。平面上に与えられた点集合に対して、すべての点を包含する最小の多角形を、できるだけ少ない点で構成する問題を考えます。この問題を解く代表的な手法の一つがジャービス・マーチ法（Jarvis March）、別名「ギフト包装法」です。

ジャービス・マーチ法の概要

ジャービス・マーチ法は、与えられた点集合から凸包の頂点（角となる点）を検出するためのアルゴリズムです。基本的な考え方はシンプルで、点集合の中で最も左にある点を出発点とし、そこから反時計回りに回転しながら凸包に含まれる点を順番に選んでいきます。

現在の点から次の点を選ぶ際には、各候補点の方位（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
    add start point to the result set.
    define colPts set to store collinear points
    while true, do // 無限ループを開始
        next := points[i]
        for all points i except 0th point, do
            if points[i] = current, then
                skip the next part, go for next iteration
            val := cross product of current, next, points[i]
            if val > 0, then
                next := points[i]
                clear the colPts array
            else if cal = 0, then
                if next is closer to current than points[i], then
                    add next in the colPts
                    next := points[i]
                else
                    add points[i] in the colPts
        done
        add all items in the colPts into the result
        if next = start, then
            break the loop
        insert next into the result
        current := next
    done
    return result
End

C++による実装例

以下は、上記アルゴリズムを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番目の点が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 は凸包の頂点数）であり、点数が多く凸包の頂点が少ない場合に効率的に動作します。一方、最悪ケースでは O(n²) となるため、大規模なデータセットにはグラハム・スキャン法（O(n log n)）などの選択肢も検討するとよいでしょう。