3d - 3D 平面のボロノイ図の計算

Question

3D で平面 (平行四辺形) のボロノイ図を計算できるコード/ライブラリはありますか? Qhullをチェックしたところ、ポイントでしか機能しないようです。その例では、Voro ++はさまざまなサイズの球で機能しますが、ポリゴンについては何も見つかりませんでした。

この画像(3D のサンプル平面) では、平行四辺形は厚みがあるため 3D ですが、この場合、厚みはゼロになります。

Answer 1

ボロノイ セルは平行四辺形ではありません。ここで投稿した画像に混乱しています。ボロノイ セルの境界は、個々の平均を分離する超平面の一部です。

3D ボロノイ図の説明と視覚化については、次の Web サイトをご覧ください。

http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/

ボロノイ セルを計算するための一般的な方法は、最初に Delaunay Triangulation を作成することです。2D でこれを行うアルゴリズムは多数ありますが、3D ではかなり複雑になります。しかし、それでも何かを見つけることができるはずです。qhull適切な方法かもしれません。

Delaunay 三角形分割を取得したら、各 tetraeder の中心を計算します。これらは、描画する必要があるポリゴンの角です。Delaunay 三角形分割の任意のエッジについて、隣接する中心を結ぶ多角形を描画します。これは超平面でなければなりません。あとは、凸包の一部であるエッジの超平面を描画するだけです。このためには、既にあるはずの超平面を内側から無限の外側まで継続する必要があります。

最初は 2d から始めることを強くお勧めします。2D で動作するコードを作成したら、3D で同じことを行う方法を確認してください。高速にしたい場合、これは2Dではすでにかなりトリッキーです。

これは、ドローネ図とボロノイ図の両方を視覚化したウィキペディアの図です。

黒い線はドロネー三角形分割です。茶色の線はこれと直交しており、ボロノイ図を形成しています。Delaunay 三角形分割は、凸包、ボロノイ図、アルファ形状の計算など、さまざまなクールな視覚化に使用できます。

Answer 2

Bowyer-Watson は通常、推奨されるアルゴリズムです。ほとんどの論文/アルゴリズムの問​​題は、空間内で点が互いに接近している場合 (つまり四面体が薄い場合)、ボロノイ セルがほとんど平らになる必要がある場合、および複数の点がオンになっている場合に発生するトリッキーな状況に対処していないことです。同じ球体。それに加えて、不正確な計算と丸めを処理するという数値上の複雑さが加わり、エンドレスなデバッグのレシピができあがります。許容できる場合は、最初にデータをフィルタリングすることをお勧めします。そうしないと、アルゴリズムで膨大な量の特殊なケースをコーディングすることになります。

少し前に、ドロネー三角形分割から始めてボロノイ セルを計算することによって、これらの状況を解決するための別のアプローチがあると主張する日本の論文もありましたが、それにも欠陥がありました。幅広いアルゴリズムを考え出し、研究助手に詳細を心配させることは、研究者にとって素晴らしいことです...