C++で実装する二次元ギフト包装アルゴリズム：凸包計算の基本とサンプルコード

二次元ギフト包装アルゴリズムとは

本記事では、C++を用いて二次元平面におけるギフト包装アルゴリズム（Gift Wrapping Algorithm）を実装する方法を詳しく解説します。このアルゴリズムは「Jarvisの行進法」とも呼ばれ、与えられた点集合から凸包（Convex Hull）を求めるための代表的な手法の一つです。

凸包とは、平面上に散らばるすべての点を内側に含む最小の凸多角形のことです。釘で打った点の周囲に輪ゴムを引っ掛けたとき、輪ゴムが描く形を思い浮かべると理解しやすいでしょう。外側の点を順に結んでいく様子がプレゼントを包む作業に似ていることから、「ギフト包装」という名前が付きました。

アルゴリズムの流れ

1. 前提条件：点の数は最低でも3点必要です。
2. 初期化：結果を格納する配列を用意して初期化します。
3. 左端の探索：x座標が最小となる点（最も左の点）を見つけます。
4. 反時計回りに移動：左端の点から出発し、反時計回りに出発点へ戻ってくるまで点をたどります。
5. 結果の出力：凸包を構成する点をすべて出力します。

C++による実装例

以下が実際に動作するC++のサンプルコードです。コメントも日本語で補足しているので、処理の流れが追いやすくなっています。

#include <iostream>
using namespace std;
#define INF 10000

struct P {
    int x;
    int y;
};

// 3点の位置関係（方向）を判定する関数
int orient(P a, P b, P c) {
    int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if (v == 0)
        return 0;              // 同一直線上（共線）
    return (v > 0) ? 1 : 2;    // 1: 時計回り / 2: 反時計回り
}

// 凸包を求める関数
void convexHull(P points[], int m) {
    if (m < 3)                 // 最低3点が必要
        return;

    int n[m];
    for (int i = 0; i < m; i++)
        n[i] = -1;             // 結果の初期化

    int l = 0;
    for (int i = 1; i < m; i++)
        if (points[i].x < points[l].x)
            l = i;             // 最も左の点を検索

    int p = l, q;
    do {
        q = (p + 1) % m;
        for (int i = 0; i < m; i++)
            if (orient(points[p], points[i], points[q]) == 2)
                q = i;         // 反時計回り側の点を選択
        n[p] = q;              // 凸包上の次の点を記録
        p = q;
    } while (p != l);          // 出発点に戻るまで継続

    for (int i = 0; i < m; i++) {
        if (n[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main() {
    P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
    cout << "凸包に含まれる点:\n";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

コードのポイント

orient関数：3点a・b・cの位置関係を外積の符号で判定します。戻り値が0なら3点は同一直線上にあり、1なら時計回り、2なら反時計回りであることを示します。次にどの点へ進むべきかを決める重要な役割を担います。

convexHull関数：点の数が3未満なら凸包が定義できないため処理を終了します。まずx座標が最小の点を探して出発点とし、do-whileループ内で現在位置から見て最も反時計回り側にある点を次の候補として選択。これを繰り返し、出発点に戻れば凸包の完成です。

計算量の目安

ギフト包装アルゴリズムの時間計算量はO(n×h)です（nは全点数、hは凸包の頂点数）。凸包の頂点が少ないデータでは高速に動作しますが、最悪ケースではO(n²)に近づきます。大量の点を扱う場合は、O(n log n)で動作するAndrewの単調連鎖法などの選択肢も検討するとよいでしょう。

実行結果

凸包に含まれる点:
(0, 4)
(4, 1)
(3, 0)
(1, 1)
(7, 6)

入力した7点のうち、凸包を構成する5点だけが出力されていることが確認できます。

まとめ

今回はC++による二次元ギフト包装アルゴリズムの実装を紹介しました。直感的で実装もシンプルなアルゴリズムなので、計算幾何学の入門題材として最適です。まずは小さなデータセットで動作を確かめながら、凸包の考え方をしっかり身につけてください。