Monotone Chain（Andrew's Algorithm）の実装解説

概要

今回は、競プロや図形の生成でよく見られる凸包 (Convex Hull) のアルゴリズム のひとつであるMonotone Chain Algorithm（アンドリューのアルゴリズム）
について解説します。

ここではC 言語でシンプルに高速に実装し、ゲームやシミュレションにも活用できると思います。

凸包 (Convex Hull) とは？

与えられた点群をすべて含む最小の凸多角形のことです。

例：点群 {(0,0), (1,1), (2,0), (0.5,0.3)} があるとき → 凸包は {(0,0), (2,0), (1,1)} の三角形 (0.5,0.3) は内部にあるので含まれません。

なぜ Monotone Chain を使うのか？

代表的な凸包アルゴリズムを比較すると次の通りです：

アルゴリズム	速度	特徴
Graham Scan	O(N log N)	角度ソートが必要。実装がやや面倒。
Jarvis March	O(NH)	直感的だが遅い。
Monotone Chain	O(N log N)	座標ソートだけでOK。実装が非常にシンプル。

C言語では角度計算 (atan2) が誤差や精度面でマイナスです。またハードウェア実装を踏まえた場合でも
外積だけで判定できる Monotone Chain が最も扱いやすいと考えられます。

実装

1. 点と外積の定義

まず2D点と 3 点 A,B,C の向きを判定する外積を定義します。

typedef struct {
    float x;
    float y;
} Point;

// 外積: 正 → 左回り, 負 → 右回り, 0 → 直線上
static float cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

この外積の値が負（右回り・時計回り）になると
凸包が内側に折れ曲がる（凹む） → 余計な点なので削除する
というシンプルな仕組みです。

2. 点を X→Y の順でソート

左から右へ、順番に点を処理します。

static int compare_points(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;

    if (p1->x != p2->x) return (p1->x < p2->x) ? -1 : 1;
    if (p1->y != p2->y) return (p1->y < p2->y) ? -1 : 1;
    return 0;
}

3. 下側の凸包（Lower Hull）を構築

左から右へ点を走査し、折れ曲がる点を削除します。

Point hull[2 * num_random_points];
int k = 0;

// 1. ソート
qsort(random_points, num_random_points, sizeof(Point), compare_points);

// 2. Lower-hull
for (int i = 0; i < num_random_points; i++) {
    while (k >= 2 && cross_product(hull[k-2], hull[k-1], random_points[i]) <= 0) {
        k--; // 右回りなので除外
    }
    hull[k++] = random_points[i];
}

4. 上側の凸包（Upper Hull）を構築

反対方向（右 → 左）に辿ります。

int lower_size = k;  // Lower hull の終端を記録

// 3. Upper-hull
for (int i = num_random_points - 2; i >= 0; i--) {
    while (k >= lower_size && cross_product(hull[k-2], hull[k-1], random_points[i]) <= 0) {
        k--;
    }
    hull[k++] = random_points[i];
}

// 最後の点が重複するので削除
k--;

プログラム全体

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    float x, y;
} Point;

static double cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

static int compare_points(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    if (p1->x != p2->x) return (p1->x < p2->x) ? -1 : 1;
    return (p1->y < p2->y) ? -1 : ((p1->y > p2->y) ? 1 : 0);
}

int convex_hull(Point *points, int n, Point *hull) {
    if (n < 3) {
        memcpy(hull, points, n * sizeof(Point));
        return n;
    }
    
    qsort(points, n, sizeof(Point), compare_points);
    
    int k = 0;
    
    // Lower hull
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross_product(hull[k-2], hull[k-1], points[i]) <= 0)
            k--;
        hull[k++] = points[i];
    }
    
    // Upper hull
    int lower_size = k;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= lower_size && cross_product(hull[k-2], hull[k-1], points[i]) <= 0)
            k--;
        hull[k++] = points[i];
    }
    
    return k - 1;
}

得られた凸包の利用

• hull[0..k-1] が凸包の頂点（順番付き）

• k が点の数

• ポリゴンとして描画したり、障害物形状として使える

その他

実用では以下も考えるべきかもしれません：

• 点が 1〜2 個しかない場合 → そのまま返す

• 同一点が多数含まれる場合 → ソート時に除外する処理を追加

最後に

Monotone Chainは

• ソート + 外積判定のみ

• 実装が簡単

• 高速（O(N log N））

という特徴があり、C言語で凸包を求める最も実用的な方法のひとつだと考えられます。