グラハムスキャンアルゴリズムとは？凸包を求める仕組みとC++実装例を解説

凸包（Convex Hull）とは

凸包とは、与えられたすべてのデータ点を覆うことができる最小の閉領域のことです。平面上に打たれた点をすべて内側に含むように輪ゴムをかけたとき、輪ゴムが引っかかる外側の点を結んでできる多角形をイメージすると分かりやすいでしょう。

グラハムスキャン（Graham's Scan）は、この凸包を構成する角の点（境界点）を効率的に見つけ出す古典的なアルゴリズムで、計算量は O(n log n) です。

アルゴリズムの基本的な流れ

1. 基準点の決定：まず、最も下にある点（y座標が最小の点）を選びます。y座標が等しい点が複数ある場合は、x座標がより小さい方を採用します。この点が凸包の開始点となります。
2. 反時計回りでのソート：残りの n-1 個の頂点を、開始点から見た反時計回りの角度（極角）に基づいてソートします。
3. 同角度の点の整理：2つ以上の点が開始点から同一の角度をなす場合は、開始点から最も遠い点を除いて、それ以外をすべて削除します。
4. スタックによる走査：残った点を順次スタックにプッシュしていきます。スタックのトップの点・その直下の点・新しく選択した points[i] の3点が反時計回りになっていない場合には、スタックから要素を1つずつ取り除きます。判定を通過した時点で points[i] をスタックに挿入します。

入力と出力

Input:
Set of points: {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
Output:
Boundary points of convex hull are:
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

アルゴリズム（擬似コード）

findConvexHull(points, n)

入力 − 点の集合、点の個数

出力 − 凸包の境界点

Begin
    minY := points[0].y
    min := 0

    for i := 1 to n-1 do
        y := points[i].y
        if y < minY or minY = y and points[i].x < points[min].x, then
            minY := points[i].y
            min := i
    done

    swap points[0] and points[min]
    p0 := points[0]
    sort points from points[1] to end
    arrSize := 1

    for i := 1 to n, do
        when i < n-1 and (p0, points[i], points[i+1]) are collinear, do
            i := i + 1
        done
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    done

    if arrSize < 3, then
        return cHullPoints
    push points[0] into stack
    push points[1] into stack
    push points[2] into stack

    for i := 3 to arrSize, do
        while top of stack, item below the top and points[i] is not in
            anticlockwise rotation, do
            delete top element from stack
        done
        push points[i] into stack
    done

    while stack is not empty, do
        item stack top element into cHullPoints
        pop from stack
    done
End

C++による実装例

以下は、グラハムスキャンをC++で実装したコード例です。2次元平面の点を表す構造体、スタック操作用の補助関数、3点の向きを判定する関数、ソート用の比較関数などを組み合わせて凸包を求めています。

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;

struct point {     //define points for 2d plane
    int x, y;
};

point p0;     //used to another two points

point secondTop(stack<point>&stk) {
    point tempPoint = stk.top(); stk.pop();
    point res = stk.top();     //get the second top element
    stk.push(tempPoint);     //push previous top again
    return res;
}

int squaredDist(point p1, point p2) {
    return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

int direction(point a, point b, point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;      //colinear
    else if(val < 0)
        return 2;     //anti-clockwise direction
        return 1;     //clockwise direction
}

int comp(const void *point1, const void*point2) {
    point *p1 = (point*)point1;
    point *p2 = (point*)point2;
    int dir = direction(p0, *p1, *p2);

    if(dir == 0)
        return (squaredDist(p0, *p2) >= squaredDist(p0, *p1))?-1 : 1;
    return (dir==2)? -1 : 1;
}

vector<point>findConvexHull(point points[], int n) {
    vector<point> convexHullPoints;
    int minY = points[0].y, min = 0;

    for(int i = 1; i<n; i++) {
        int y = points[i].y;
        //find bottom most or left most point
        if((y < minY) || (minY == y) && points[i].x < points[min].x) {
            minY = points[i].y;
            min = i;
        }
    }

    swap(points[0], points[min]);     //swap min point to 0th location
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp);     //sort points from 1 place to end

    int arrSize = 1;     //used to locate items in modified array
    for(int i = 1; i<n; i++) {

        //when the angle of ith and (i+1)th elements are same, remove points
        while(i < n-1 && direction(p0, points[i], points[i+1]) == 0)
            i++;
        points[arrSize] = points[i];
        arrSize++;
    }

    if(arrSize < 3)
        return convexHullPoints;     //there must be at least 3 points, return empty list.
        
        //create a stack and add first three points in the stack
        stack<point> stk;
        stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);

        for(int i = 3; i<arrSize; i++) {     //for remaining vertices
            while(direction(secondTop(stk), stk.top(), points[i]) != 2)
                stk.pop();     //when top, second top and ith point are not making left turn, remove point
            stk.push(points[i]);
        }

        while(!stk.empty()) {
            convexHullPoints.push_back(stk.top());     //add points from stack
            stk.pop();
        }
}

int main() {
    point points[] = {{-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},
                    {3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};
    int n = 18;
    vector<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: "<<endl;
    vector<point>::iterator it;

    for(it = result.begin(); it!=result.end(); it++)
        cout << "(" << it->x << ", " <<it->y <<") ";
}

実行結果

Boundary points of convex hull are:
(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

このように、グラハムスキャンは「基準点の選択 → 極角ソート → スタックによる反時計回り判定」というシンプルな手順で凸包を求められます。点群の外周分析や幾何学処理、コンピュータグラフィックスなど、幅広い分野で応用される重要な基本アルゴリズムです。