【C++】ジャービスのアルゴリズム（ギフトラッピング法）で凸包を求める方法

はじめに

この記事では、ジャービスのアルゴリズム（Jarvis's Algorithm、別名：ギフトラッピング法）を用いて、与えられた点集合の凸包（Convex Hull）を求めるプログラムをC++で解説します。

凸包とは、与えられたすべての点を「内部」または「境界上」に含む最小の凸多角形のことです。計算幾何学における基本的な問題の一つであり、画像処理や衝突判定など幅広い分野で応用されています。

ジャービスのアルゴリズムでは、まず最も左（x座標が最小）の点を選択し、そこから時計回りの方向に外周の点を順番にたどっていくことで、あたかも紙で点群を包み込むように凸包を構築します。

アルゴリズムの流れ

1. x座標が最小となる点（最左点）を見つけ、起点とします。
2. 現在の点から見て、他のすべての点の中で最も反時計回り側（＝時計回り走査時に次に来る点）にある候補点を探索します。
3. その候補点を次の頂点として結果に追加し、同様の手順を繰り返します。
4. 再び起点に戻った時点で処理を終了します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 点の構造体
struct Point {
    int x, y;
};

// 3点の位置関係（進行方向）を計算する
int cal_orientation(Point p, Point q, Point r) {
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;      // 3点は同一直線上
    return (val > 0) ? 1 : 2;    // 1: 時計回り, 2: 反時計回り
}

// 凸包を求めて出力する
void convexHull(Point points[], int n) {
    if (n < 3) return;           // 凸包を形成するには3点以上必要
    vector<Point> hull;

    // 最も左にある点を探す
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    // 時計回り方向に点をたどる
    int p = l, q;
    do {
        // 現在の点を結果に追加
        hull.push_back(points[p]);
        q = (p + 1) % n;
        for (int i = 0; i < n; i++) {
            if (cal_orientation(points[p], points[i], points[q]) == 2)
                q = i;
        }
        p = q;
    } while (p != l);            // 起点に戻るまで繰り返す

    // 凸包の頂点を出力
    for (int i = 0; i < hull.size(); i++)
        cout << "(" << hull[i].x << ", "
             << hull[i].y << ")\n";
}

int main() {
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

実行結果

(0, 3)
(0, 0)
(3, 0)
(3, 3)

計算量について

このアルゴリズムの時間計算量は O(n × h) です。ここで n は入力点の数、h は凸包を構成する頂点の数です。凸包の頂点数が少ない場合には効率的ですが、最悪ケースでは O(n²) となるため、点数が非常に多い場合はAndrewのモノトーンチェーン法（O(n log n)）などの利用も検討するとよいでしょう。