1

2D では、凸包は基本的にポイントのツアーとして表されます。この表現は 2 次元を超えて崩壊する可能性があるようです。もうすぐ彼らと仕事をする予定なので、船体は他の人が使用する可能性があるので、そうするための「標準」があれば、事前に知りたい.

明確化: 私が言及していた標準は、出力フォーマットに関するもので、その出力から、プログラムは他の目的のためにハルを利用できます。

4

1 に答える 1

4

任意のハルを完全に指定するには、ポイントのコレクションで常に十分ですが、実際には、ポイントの接続性を調べるには、ハル アルゴリズムを再度実行する必要があります。

編集：エッジまたはフェース データが必要な場合は、quickhull などのアルゴリズムで無料で取得できます。N次元と仮定します。基本的に、関連付けられた法線ベクトルを使用して、N 点で定義された平面を常に見つけています。法線ベクトルによって指定された平面の側面にまだ点がある場合は、最も遠い点によって定義された新しい平面を作成し、新しい平面セットの反対側にあるものを削除します。これらの平面は (N-1) セル (3D では面、2D ではエッジ) を定義し、アルゴリズムのこの時点でハルの最高次元表現を提供します。このアルゴリズムは、間違った側に点を持つ平面がなくなるまで続きます。最終的な平面は最終的な船体の (N-1) セルを与え、その定義点は頂点です。http://www.qhull.org/は多くの戦略を使用していますが、その中で最も明白なのは Delaunay 三角形分割を使用することです (これは、凸包アルゴリズムを取得したらコードを取得します)。

2 次元では、点のリストといくつかのエッジがあります。必要に応じて、ツアーを注文することができます。どのハルにもエッジとポイントの両方が必要です。

3D では、点とエッジ、または面とエッジ、または点と面が最小限の表現として必要です。しかし、場合によっては 3 つすべてを使用する方が効率的かもしれません。面を構成するエッジ、点、またはその両方で面を表現したい場合があります。これは、メモリと時間またはアクセシビリティの間のトレードオフです。

高次元でも同じことができますが、セル (3D+ 面) と面、エッジ、点があります。次元が高くなると、セル データを格納するために必要なスペースが非常に大きくなる可能性があるため、ポイントとエッジのコレクションが望ましいものになる可能性があります。このパターンの証拠は、http: //en.wikipedia.org/wiki/Hypercube#で確認できます。要素。

次に、ポイント、エッジ、面、低次元のセル、高次元のセルを参照するために、高次元のセルを表現する方法を選択できます。問題は、異なる次元のセル間のすべての関係を追跡することです (面とエッジの間の関係のように、しかしより高い次元)? または、これらの関係のタイプの数は超直線的に増加します。これは、表現される各タイプの関係の数と同様に、追加の組み合わせです。それで、あなたはそれをすべて捨てて、その場で計算しますか。中程度の大きさの問題でもスペースと時間の要件が重要になる可能性があるため、表現の選択は実際に何をしているかに依存します。

個人的には、通常、それらを参照するエッジを持つポイントのコレクションを使用します。

ND ジオメトリ: http://en.wikipedia.org/wiki/Polytope

于 2012-11-24T11:34:09.047 に答える