ギフト包装法のソースを表示

[[Image:Jarvis march convex hull algorithm diagram.svg|thumb|280px|right|ギフト包装法]]
'''ギフト包装法'''（{{lang-en-short|Gift wrapping algorithm}}）や'''Jarvisの行進法'''（{{lang-en-short|Jarvis's march}}）とは、[[計算幾何学]]における点の[[集合]]の[[凸包]]を求める[[アルゴリズム]]。

== 2次元の場合 ==
2次元の場合、Jarvisの行進法とも呼ばれ、R. A. Jarvis が[[1973年]]に発表した<ref>{{cite journal
 | author = Jarvis, R. A.
 | title = On the identification of the convex hull of a finite set of points in the plane
 | journal = Information Processing Letters
 | volume = 2
 | year = 1973
 | pages = 18–21
 | doi = 10.1016/0020-0190(73)90020-3}}</ref>。計算量は O(nh) である。n は点の数、h は凸包の辺の数。n が小さかったり、h が n に比べて圧倒的に小さい場合は、他の凸包を求めるアルゴリズムと比較して計算量は良好。一般的な場合・最悪の場合は、他のアルゴリズムと比較して大きく劣る。

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

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

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

== 擬似コード ==
下記は2次元の場合の擬似コード。S は凸包を計算する点の配列。あらかじめ凸包の頂点に来ないことが確実な点は除去しておくと計算量が減る。L は[[可変長配列]]で、ここに凸包の頂点の座標が入る。A, B, C は点。|AB| は AB の距離。2次元の[[外積代数|外積]]は <math>x_1 y_2 - x_2 y_1</math> で計算する。

 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])

== 参照 ==
{{reflist}}

{{デフォルトソート:きふとほうそうほう}}
[[Category:凸包]]
[[Category:計算幾何学]]