クイックハル

クイックハルは、 n次元空間における有限の点集合の凸包を計算する手法です。クイックソートに似た分割統治法を用いており、その名前の由来となっています。2次元および3次元空間における最悪ケースの時間計算量は ですが、入力精度がビットに制限されている場合、最悪ケースの時間計算量は と推定されます。ここで、は入力点の数、は処理される点の数（最大）です。[ 1 ]O（n2）{\displaystyle O(n^{2})}O（ログ⁡n）{\displaystyle O(\log n)}O（nログ⁡r）{\displaystyle O(n\log r)}n{\displaystyle n}r{\displaystyle r}n{\displaystyle n}

N次元クイックハルは、1996年にC.ブラッドフォード・バーバー、デビッド・P・ドブキン、ハンヌ・フダンパーによって発明されました。[ 1 ]これは、ジョナサン・スコット・グリーンフィールドの1990年の平面クイックハルアルゴリズムの拡張でしたが、1996年の著者はグリーンフィールドの手法を知りませんでした。[ 2 ]代わりに、バーバーらはこれをクラークソンとショアの1989年のアルゴリズムの決定論的変種として説明しています。[ 1 ]

このアニメーションは、クイックハル アルゴリズムを 2 次元で表したものです。

アルゴリズム

ステップ1～2：点を2つのサブセットに分割します。

2次元アルゴリズムは、以下のステップに分解できます。[ 2 ]

  1. 凸包を構成するX座標の最小値と最大値を持つ点を求めます。これらの点は常に凸包の一部となります。同じX座標の最小値／最大値を持つ点が複数存在する場合は、それぞれY座標の最小値／最大値を持つ点を使用します。
  2. 2点によって形成される直線を用いて、集合を2つの点のサブセットに分割します。これらのサブセットは再帰的に処理されます。次に、直線より上の部分の殻の決定方法を説明します。直線より下の部分の殻も同様に決定できます。
  3. 直線から最も遠い直線上の点を求めます。この点は、直線上の2点と三角形を形成します。
  4. その三角形の内側にある点は凸包の一部にはなり得ないため、次の手順では無視できます。
  5. 三角形の 2 つの新しい辺によって形成される 2 本の線に対して、前の 2 つの手順を再帰的に繰り返します。
  6. 残りのポイントがなくなり、再帰が終了し、選択されたポイントが凸包を構成するまで続けます。
手順 3 ～ 5: 最大距離の点を見つけ、三角形内の点を無視して再帰します。
ステップ 6: ポイントがなくなるまで再帰します。

高次元の場合、包は多くの面から構成されるため、問題はより複雑になります。データ構造はそれを考慮し、隣接する面が共有する直線／平面／超平面（尾根）も記録する必要があります。d次元の場合：[ 1 ]

  1. 集合から、平面または超平面を共有しないd + 1 個の点を選択する。これにより、面Fs[]を持つ初期包が形成される。
  2. Fs[]内の各Fについて、その「上」、つまり包の中心から離れた方向を指している未割り当ての点をすべて見つけ、それらをFに関連付けられた「外側」の集合FOに割り当てます。このアルゴリズムは、包に追加されていないが、潜在的にその頂点となる可能性のあるすべての点が、正確に1つの外側の集合に割り当てられるという不変条件を維持します。
  3. 空でないFOを持つ各Fについて:
    1. FOにおいてFからの距離が最大となる点pを探し、それを包に追加します。pは後で削除される可能性があるため、必ずしも最終的な包の頂点になるわけではないことに注意してください。
    2. 可視集合Vを作成し、それをFで初期化します。Vを隣接する面Fvの全方向に拡張し、 pからそれ以上の面が見えなくなるまで拡張します。pからFv が見えるということは、 pが Fv の上にあることを意味します。
    3. そして、 Vの境界は地平線の尾根の集合Hを形成します。
    4. Fnew[]をpとH内のすべての尾根から作成されたファセットの集合とします。
    5. Vの面の外側の集合にあるすべての点の割り当てを解除する。Fnew []の新しい面ごとに、これらの新しく割り当てを解除した点のみを考慮して手順 (2) を実行し、その外側の集合を初期化する。この処理の最後に割り当てを解除したままの点はすべて、現在の包の内側にあることに注意する。
    6. Fs[]からV内の現在内部にあるファセットを削除します。 Fnew[]の新しいファセットをFs[]に追加し、反復処理を続行します。

2次元点集合の擬似コード

入力 = n点の集合S 入力点集合Sには少なくとも2つの点があると仮定する。 function QuickHull( S ) is // n点の集合Sから凸包を求める 凸包 := {} 左端と右端の点（例えばAとB）を見つけ、AとBを凸包に追加する 線分ABは残りの（n −2）点を2つのグループS1とS2に分割する。 ここでS1はAからBへの有向線の右側にあるS内の点である。S2 はS内の点であり、 BからAへの有向線の右側にある 。FindHull( S1 , A , B ) FindHull( S2 , B , A ) 出力 := 凸包 関数終了関数FindHull( Sk , P , Q )は、点の集合 Sk から、P から Q への有向線の右側にある凸包上の点を検索します。Sk に点がない場合は、次の式を返します。Sk 内の点の集合から、線分PQから最も遠い点（例えばC ）を検索します。 点Cを凸包のPとQの間の位置に追加します。3 つの点P、Q、Cは、 Skの残りの点を3 つの部分集合S0、S1、S2に分割します。 ここで、 S0は三角形 PCQ 内の点、S1は有向線の右側にある点ですPからCへの 直線、およびS2 はCからQへの有向直線の右側にある点です。 FindHull( S1 , P , C ) FindHull( S2 , C , Q ) 終了関数

3次元の場合に特化した擬似コードはJordan Smithから入手可能です。このコードには、開始時の包を選択するための同様の「最大点」戦略が含まれています。これらの最大点が退化している場合、点群全体も同様に退化します。[ 3 ]

参照

参考文献

  1. ^ a b c d Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1996年12月1日). 「凸包のためのクイックハルアルゴリズム」(PDF) . ACM Transactions on Mathematical Software . 22 (4): 469– 483. doi : 10.1145/235815.235821
  2. ^ a bグリーンフィールド、ジョナサン・S. (1990年4月1日). 「QuickHullアルゴリズムの証明」 .電気工学とコンピュータサイエンス - 技術レポート.
  3. ^ Smith, Jordan. 「QuickHull 3D」 . algolist.ru . 2019年10月22日閲覧。
「 https://en.wikipedia.org/w/index.php?title=クイックハル&oldid= 1311319752」より取得