C++で凸包を求める：グラハムスキャンアルゴリズムの実装と解説

本記事では、与えられた点集合から凸包（Convex Hull）を求めるプログラムについて、C++での実装を交えながら詳しく解説します。

凸包とは？

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

グラハムスキャン（Graham Scan）の流れ

グラハムスキャンは、凸包を効率的に求める代表的なアルゴリズムです。処理の大まかな流れは以下の通りです。

1. 基準点の選択： y座標が最も小さい点（複数ある場合はx座標も小さい方）を基準点 p0 として選びます。
2. 点のソート： 基準点 p0 を中心に、他のすべての点を極角（反時計回りの角度）の昇順でソートします。
3. 走査と判定： ソートされた順に点を走査し、左回り（反時計回り）の向きになる点だけをスタックに残します。右回りになる点は棄却されます。

このとき、3点の並び方向（時計回りか反時計回りか）は外積の符号で判定できます。

C++での実装例

#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;

struct Point {
    int x, y;
};

// 他の点をソートする際の基準点
Point p0;

// スタックのトップの次の要素を取得
Point nextToTop(stack<Point> &S) {
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

// 2点を交換
void swap(Point &p1, Point &p2) {
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

// 距離の2乗を計算
int distSq(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) +
           (p1.y - p2.y) * (p1.y - p2.y);
}

// 3点の並び方向を判定（0: 同一直線上, 1: 時計回り, 2: 反時計回り）
int 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;
    return (val > 0) ? 1 : 2;
}

// 基準点 p0 からの極角で比較するための関数
int compare(const void *vp1, const void *vp2) {
    Point *p1 = (Point *)vp1;
    Point *p2 = (Point *)vp2;
    int o = orientation(p0, *p1, *p2);
    if (o == 0)
        return (distSq(p0, *p2) >= distSq(p0, *p1)) ? -1 : 1;
    return (o == 2) ? -1 : 1;
}

// 凸包を出力
void convexHull(Point points[], int n) {
    // y座標が最小の点（同値ならx座標も小さい方）を探す
    int ymin = points[0].y, min = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        if ((y < ymin) || (ymin == y &&
            points[i].x < points[min].x))
            ymin = points[i].y, min = i;
    }

    // 基準点を先頭に移動
    swap(points[0], points[min]);
    p0 = points[0];

    // 残りの点を極角順にソート
    qsort(&points[1], n - 1, sizeof(Point), compare);

    // 同一直線上の点を除去しながら配列を詰める
    int m = 1;
    for (int i = 1; i < n; i++) {
        while (i < n - 1 && orientation(p0, points[i],
               points[i + 1]) == 0)
            i++;
        points[m] = points[i];
        m++; // 修正後の配列サイズを更新
    }

    // 凸包を構成できる点が3つ未満の場合は終了
    if (m < 3) return;

    stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);

    // 残りの点を順に処理し、反時計回りを維持
    for (int i = 3; i < m; i++) {
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }

    // 結果の出力
    while (!S.empty()) {
        Point p = S.top();
        cout << "(" << p.x << ", " << p.y << ")" << endl;
        S.pop();
    }
}

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

実行結果

(0, 3)
(4, 4)
(3, 1)
(0, 0)

コードのポイント

• orientation 関数： 外積の値によって3点の並び方向を判定します。戻り値が 2 の場合、点は反時計回りに配置されていることを意味します。
• nextToTop 関数： スタックのトップを pop せずに、その下の要素を参照するための補助関数です。
• compare 関数： qsort 用の比較関数で、極角が同じ場合は基準点からの距離が近い方を優先します。
• 計算量： グラハムスキャン全体の計算量は O(n log n) であり、ソート部分が支配的です。

このように、グラハムスキャンは「ソート」と「スタック」を組み合わせることで、点集合の凸包をシンプルかつ効率的に求められるアルゴリズムです。競技プログラミングや幾何計算の基礎として、ぜひマスターしておきましょう。