C++でジャービスマーチ（Jarvis March）を実装して凸包を求める方法

ジャービスマーチ（Jarvis March）アルゴリズムは、与えられた点の集合から凸包（Convex Hull）の頂点、すなわち境界となる角の点を検出するための手法です。

まずデータセットの中で最も左側にある点を起点とし、そこから反時計回りに回転しながら凸包に含まれる点を順番に選んでいきます。現在の点から次の点を選ぶ際には、各候補点の方向（向き）を外積によって判定し、角度が最大になる点を採用します。すべての点を巡り、次の点が再び始点に戻った時点でアルゴリズムを終了します。

入力：点の集合 {(-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)}
出力：凸包の境界点は以下の通り
(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

アルゴリズム

findConvexHull(points, n)

入力：点の配列、点の個数 n。

出力：凸包の頂点（角となる点）の集合。

Begin
    start := points[0]
    for each point i, do
        if points[i].x < start.x, then   // 最も左にある点を取得
            start := points[i]
    done
    current := start
    始点を結果集合に追加する。
    共線点を格納するための colPts 集合を定義する。
    while true, do   // 無限ループを開始
        next := points[i]
        0番目以外のすべての点 i について、
        if points[i] = current, then
            以降の処理をスキップして次の反復へ
            val := current, next, points[i] の外積
        if val > 0, then
            next := points[i]
            colPts 配列をクリアする
        else if val = 0, then
            if next が points[i] より current に近い場合, then
                next を colPts に追加
                next := points[i]
            else
                points[i] を colPts に追加
    done
    colPts 内のすべての要素を結果に追加する。
    if next = start, then
        ループを抜ける
    next を結果に挿入する。
    current := next
    done
    return result
End

サンプルコード

#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point {    // 2次元平面上の点を定義
    int x, y;
    bool operator==(point p2) {
        if(x == p2.x && y == p2.y)
            return 1;
        return 0;
    }
    bool operator<(const point &p2)const {    // set内でソートするためのダミー比較関数
        return true;
    }
};
int crossProduct(point a, point b, point c) {    // ベクトルabに対するcの位置を求める
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    return y2*x1 - y1*x2; // 結果が負ならcは左側、正なら右側、0ならa,b,cは同一直線上（共線）
}
int distance(point a, point b, point c) {
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    int item1 = (y1*y1 + x1*x1);
    int item2 = (y2*y2 + x2*x2);
    if(item1 == item2)
        return 0; // bとcがaから等距離の場合
    else if(item1 < item2)
        return -1; // bの方がaに近い場合
        return 1; // cの方がaに近い場合
}
set<point> findConvexHull(point points[], int n) {
    point start = points[0];
    for(int i = 1; i<n; i++) {    // 開始用に最も左の点を探す
        if(points[i].x < start.x)
            start = points[i];
    }
    point current = start;
    set<point> result;    // 重複した点の登録を避けるためにsetを使用
    result.insert(start);
    vector<point> *collinearPoints = new vector<point>;
    while(true) {
        point nextTarget = points[0];
        for(int i = 1; i<n; i++) {
            if(points[i] == current) // 選択された点が現在の点なら以降を無視
                continue;
                int val = crossProduct(current, nextTarget, points[i]);
                if(val > 0) {    // i番目の点が左側にある場合
                    nextTarget = points[i];
                    collinearPoints = new vector<point>; // 共線点をリセット
                }else if(val == 0) {    // 3点が同一直線上にある場合
                    if(distance(current, nextTarget, points[i]) < 0) {    // 近い方を共線リストに追加
                        collinearPoints->push_back(nextTarget);
                        nextTarget = points[i];
                    }else{
                        collinearPoints->push_back(points[i]); // i番目の点がnextTargetと同じかより近い場合
                    }
                }
        }
        vector<point>::iterator it;
        for(it = collinearPoints->begin(); it != collinearPoints->end(); it++) {
            result.insert(*it); // 共線点をすべて結果集合に追加
        }
        if(nextTarget == start) // 次の点が始点なら一周したことを意味する
            break;
        result.insert(nextTarget);
        current = nextTarget;
    }
    return result;
}
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;
    set<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: "<<endl;
    set<point>::iterator it;
    for(it = result.begin(); it!=result.end(); it++)
        cout << "(" << it->x << ", " <<it->y <<") ";
}

出力結果

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