【C++】単調チェーン（Monotone Chain）アルゴリズムで点群の凸包を求める

この記事では、C++を使って与えられた点群の凸包（Convex Hull）を求める「単調チェーンアルゴリズム（Andrew's Algorithm）」について詳しく解説します。

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

単調チェーンアルゴリズムの概要

単調チェーンアルゴリズムは、次の手順で凸包を構築します。

1. すべての点を、x座標・同じならy座標の順で辞書式順序にソートする。
2. ソート済みの点を先頭から走査し、「下側の凸包」を構築する。
3. 逆順に走査し、「上側の凸包」を構築する。
4. 両者を連結して完全な凸包を得る。

計算量はソートが支配的となり、全体で O(n log n) で動作します。実装がシンプルで安定しているため、競技プログラミングや実務でも広く使われている手法です。

C++での実装例

#include <bits/stdc++.h>
#define llu long long int
using namespace std;

// 点を表す構造体
struct Point {
    llu x, y;
    bool operator<(Point p){
        return x < p.x || (x == p.x && y < p.y);
    }
};

// ベクトルOAとOBの外積を計算する
llu calc_crossproduct(Point O, Point A, Point B){
    return (A.x - O.x) * (B.y - O.y)
        - (A.y - O.y) * (B.x - O.x);
}

// 凸包の境界上の点を求める
vector<Point> convex_hull(vector<Point> A){
    int n = A.size(), k = 0;
    if (n <= 3)
        return A;
    vector<Point> ans(2 * n);

    // 点を辞書式順序にソート
    sort(A.begin(), A.end());

    // 下側の凸包を構築
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && calc_crossproduct(ans[k - 2],
            ans[k - 1], A[i]) <= 0)
            k--;
        ans[k++] = A[i];
    }

    // 上側の凸包を構築
    for (size_t i = n - 1, t = k + 1; i > 0; --i) {
        while (k >= t && calc_crossproduct(ans[k - 2],
            ans[k - 1], A[i - 1]) <= 0)
            k--;
        ans[k++] = A[i - 1];
    }

    // 結果配列のサイズを調整
    ans.resize(k - 1);
    return ans;
}

int main(){
    vector<Point> points;
    points.push_back({ 0, 3 });
    points.push_back({ 2, 2 });
    points.push_back({ 1, 1 });
    points.push_back({ 2, 1 });
    points.push_back({ 3, 0 });
    points.push_back({ 0, 0 });
    points.push_back({ 3, 3 });

    vector<Point> ans = convex_hull(points);
    for (size_t i = 0; i < ans.size(); i++)
        cout << "(" << ans[i].x << ", "
            << ans[i].y << ")" << endl;
    return 0;
}

実行結果

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

コードの解説

Point 構造体

各点の座標 (x, y) を long long 型で保持し、比較演算子 operator< を定義することで、sort() による辞書式順序のソートを可能にしています。

外積の計算（calc_crossproduct 関数）

3点 O, A, B からなるベクトル OA と OB の外積を計算します。外積の符号を調べることで、3点が反時計回り・時計回り・同一直線上のどれに当たるかを判定できます。この判定こそが、凸包から「内側に折れ込む点」を取り除く処理の中核となります。

凸包の構築（convex_hull 関数）

点数が3以下の場合は、それ自体が凸包となるためそのまま返します。以降は点をソートしたうえで、前半のループで下側のチェーンを、後半のループで上側のチェーンを構築します。各ステップで外積が0以下（＝左に曲がる、または直線上にある）である限りチェーンの末尾を取り除くことで、常に凸な形状が保たれます。最後に、始点と終点が重複してカウントされる分を除いて結果を返します。

※ この実装では外積が0の場合（3点が同一直線上にある場合）に中間の点を削除するため、頂点のみからなる最小の凸包が得られます。境界上の点もすべて残したい場合は、条件式を <= 0 ではなく < 0 に変更してください。

まとめ

単調チェーンアルゴリズムを使えば、O(n log n) で点群の凸包を効率的に求められます。実装が簡潔でミスが起きにくいため、計算幾何学の問題に取り組む際の強力な選択肢となります。ぜひ本記事のコードを参考に、ご自身でも実装してみてください。