ギフト包装法

ギフト包装法

ギフト包装法（英: Gift wrapping algorithm）やJarvisの行進法（英: Jarvis's march）とは、計算幾何学における点の集合の凸包を求めるアルゴリズム。

2次元の場合

2次元の場合、Jarvisの行進法とも呼ばれ、R. A. Jarvis が1973年に発表した[1]。計算量は O(nh) である。n は点の数、h は凸包の辺の数。n が小さかったり、h が n に比べて圧倒的に小さい場合は、他の凸包を求めるアルゴリズムと比較して計算量は良好。一般的な場合・最悪の場合は、他のアルゴリズムと比較して大きく劣る。

アルゴリズム

ここでは話を簡単にするため、どの3点も一直線上にないとする。一直線上にある場合は、最も遠い点を選ぶか、凸包の辺上の全ての点を選べば良い。また、実装を完璧にするには、点が2つ以下の場合も取り扱う必要がある。

凸包に必ず含まれていることが確実な点 ${\displaystyle P_{0}}$ から始める。この点は例えば一番左端の点を選べば良い。そして、${\displaystyle P_{i+1}}$ は全ての点が直線 ${\displaystyle P_{i}P_{i+1}}$ の右側にあるように選べば良い。この点は ${\displaystyle P_{i}}$ を基点にした偏角を比較することで計算量 O(n) で求まる。そして、${\displaystyle P_{h}=P_{0}}$ となるまで、これを反復する。

この方法は3次元以上でも同様にできる。

擬似コード

下記は2次元の場合の擬似コード。S は凸包を計算する点の配列。あらかじめ凸包の頂点に来ないことが確実な点は除去しておくと計算量が減る。L は可変長配列で、ここに凸包の頂点の座標が入る。A, B, C は点。|AB| は AB の距離。2次元の外積は ${\displaystyle x_{1}y_{2}-x_{2}y_{1}}$ で計算する。

A = S の内、最もy座標が小さい点の集合から、その中で最もx座標が小さい点
do {
    L に A を追加
    B = S[0]
    for i = 1 to S の大きさ - 1 {
        C = S[i]
        if (B == A) {
            B = C
        } else {
            v = AB と AC の外積
            if (v > 0 または (v == 0 かつ |AC| > |AB|)) {
                B = C
            }
        }
    }
    A = B
} while (A != L[0])

参照

1. Jarvis, R. A. (1973). “On the identification of the convex hull of a finite set of points in the plane”. Information Processing Letters 2: 18–21. doi:10.1016/0020-0190(73)90020-3.