21

ポイントのセットが与えられS (x, y, z)ます。convex hullそれらのポイントを見つける方法は？

ここからアルゴリズムを理解しようとしましたが、あまり得られませんでした。

それは言います：

最初にすべてのポイントを xy 平面に投影し、y 座標が最も高いポイントを選択して、エッジのもう一方の端点を決定するためにギフト ラッピングを 1 回繰り返して、確実に船体上にあるエッジを見つけます。これは未完成の船体の最初の部分です。その後、船体を繰り返し構築します。この最初のエッジを考えてみましょう。ここで、船体の最初の三角形の面を形成するために別の点を見つけます。これは、他のすべての点がこの三角形の右側にあるようにポイントを選択することによって行われます (適切に表示された場合) (ギフトラッピングのアルゴリズムと同様に、他のすべての点が三角形の右側にあるようにエッジを選択しました)。その端）。船体には 3 つのエッジがあります。続行するには、それらのいずれかを任意に選択します。もう一度すべてのポイントをスキャンして別のポイントを見つけ、このエッジで新しい三角形を作成し、エッジがなくなるまでこれを繰り返します。(新しい三角形の面を作成するとき、プールに 2 つのエッジを追加します。ただし、最初にそれらが既にハルに追加されているかどうかを確認する必要があります。その場合、それらは無視されます。) O(n) 個の面があり、残りのすべてのポイントをスキャンする必要があるため、各反復には O(n) 時間がかかり、O(n2) が得られます。

誰かがそれをより明確に説明したり、より単純な代替アプローチを提案したりできますか?

4

3 に答える 3

21

3D 凸包の実装は簡単ではありませんが、多くのアルゴリズムが実装されており、コードは広く利用可能です。使用する品質と時間の投資の上限にあるのはCGALです。両方の測定値の下限にあるのは、私自身の C コードです 。その間に、QuickHull のこの実装を
     DCGカバー
含む、Web 全体のコードがあります。

于 2013-08-25T19:18:05.003 に答える
14

まず、クイックハルのような簡単なアプローチを試すことをお勧めします。(ちなみに、ギフトラッピングの順序は O(n2) ではなく O(nh) です。h はハル上のポイントで、クイックハルの順序は O(n log n) です)。

平均的な状況では、クイック ハルは非常にうまく機能しますが、対称性が高い場合や円の円周上にあるポイントの場合は通常、処理が遅くなります。クイック ハルは、次のステップに分けることができます。

  1. 最小および最大の x 座標を持つ点を見つけます。それらは凸面の一部になるはずです。

  2. 2 つのポイントによって形成される線を使用して、セットをポイントの 2 つのサブセットに分割します。これは再帰的に処理されます。 ここに画像の説明を入力

  3. 線の片側で、線からの距離が最大になる点を決定します。この 1 つと一緒に前に見つけた 2 つの点は、三角形を形成します。

  4. その三角形の内側にあるポイントは、凸包の一部になることはできないため、次の手順で無視できます。

  5. 三角形によって形成される 2 つの線 (最初の線ではない) で、前の 2 つの手順を繰り返します。 ここに画像の説明を入力

  6. ポイントがなくなるまでこれを続けます。再帰が終了し、選択されたポイントが凸包を構成します。 ここに画像の説明を入力

クイック ハル アルゴリズムを使用した 3D 凸包については、この実装と説明を参照してください。

ギフト包装アルゴリズム:

Jarvis の一致アルゴリズムは、ポイントの周りに文字列を巻き付けるようなものです。左端の点は凸包の頂点でなければならないことがわかっているため、最初に左端の点 l を計算します。頂点は元の左端のポイントです。

アルゴリズムは、連続する凸包の頂点を次のように見つけます。点 p の直後の頂点は、p に立っている人が他の点を見ているときに最も右に見える点です。言い換えると、q が p に続く頂点であり、r が他の入力ポイントである場合、トリプル p、q、r は反時計回りの順序になります。一連の O(n) 反時計回りのテストを実行することで、線形時間で連続する各頂点を見つけることができます。

アルゴリズムは凸包頂点ごとに O(n) 時間を費やすため、最悪の場合の実行時間は O(n2) です。ただし、凸包の頂点数が非常に少ない場合、Jarvis の進行は非常に高速です。実行時間を記述するより良い方法は、O(nh) です。ここで、h は凸包の頂点の数です。最悪の場合、h = n で、古い O(n2) 時間の制約を受けますが、最良の場合、h = 3 で、アルゴリズムは O(n) 時間しか必要としません。これはいわゆる出力依存アルゴリズムで、出力が小さいほどアルゴリズムは高速になります。

次の画像は、より多くのアイデアを提供するはずですここに画像の説明を入力

于 2013-08-24T11:40:35.553 に答える
5

3D 凸包を見つけるための GPL C++ コードはhttp://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gzで入手でき、O(n log(n)) アルゴリズムの説明はhttp://www.newtonapplesで入手できます。 .net/NewtonAppleWrapper.html

于 2016-02-15T12:25:39.237 に答える