問題タブ [voronoi]

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

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

このプログラムにあるボロノイ/ドロネー図生成ライブラリを使用します。これは、フォーチュンのアルゴリズムの元の実装に基づいており、入力データとしてランダムなポイントのセットを使用して、次の出力データを取得できます。

1. Delaunay Triangulationからのエッジのリスト。つまり、各入力ポイントについて、どの入力ポイントが隣接しているかを確認できます。それらは特定の順序であるようには見えません。
2. ボロノイ図の頂点ペアのリスト。これを使用して、一度に1本の線でボロノイ図を描くことができます。繰り返しますが、明らかに特定の順序ではありません。
3. ポイントのペアの名前のないリスト。これは2と同じリストのようですが、順序が異なります。
4. ボロノイ図で形成された頂点のリスト。これも特定の順序ではないようです。

このライブラリを使用したプログラムのテスト実行からのデータの例を次に示します。

ボロノイ図とドロネー図を描くだけであれば上記のデータで十分ですが、これらの図で実際に作業するための情報は十分ではありません。必要なのは、ボロノイ頂点によって形成されたポリゴンの辞書であり、各ポリゴンが形成された入力ポイントによってインデックスが付けられています。好ましくは、各ポリゴンについて、これらのポイントは時計回りの順序でソートされます。

上記の情報を使用して、各領域に暗黙的にデータを割り当て、必要に応じてコーナーにデータを割り当て、どの領域がエッジを共有しているかを判断し（Delaunayエッジを使用）、それに応じて分析を行うことができます。

つまり、利用可能なデータを使用して、キーが入力ポイントの1つであり、そのキーによってインデックス付けされたデータが周囲のポリゴンを形成するボロノイ頂点のリストである辞書をまとめるにはどうすればよいでしょうか。あるいは、その情報は、私が与えられたデータのどこかに暗黙のうちに含まれていますか？

ボロノイ図を計算するためにフォーチュンのスイープライン アルゴリズムを実装しています。私の主な参考文献は、de Berg 氏らによる「Computational Geometry: Algorithms and Applications」です。トピックのカバー範囲は非常に明確ですが、私が自分で解決するのに苦労しているいくつかの小さいながらも重要な詳細を見逃しています。Web でヘルプを検索しましたが、他の Web サイトでは、教科書よりもさらに高度な概要が提供されているか、本で提供されているのとまったく同じ擬似コードが提供されています。

今後の円イベントを検出するために、ビーチ ライン上の 3 つのアークによって決定されるブレークポイントのペアが収束するか発散するかを判断する方法が必要です。決定を下すには、Fortune のアルゴリズムが進行するにつれてブレークポイントが追跡するボロノイ セルのエッジの形状に関する知識が必要になるようです。たとえば、ブレークポイントによってトレースされたエッジの勾配を見つけることができれば、ブレークポイントによって形成された 2 つの線とそれぞれの勾配が交差する場所を計算し、その結果に基づいてそれらが収束するかどうかを判断できます。ただし、斜面に関する情報を取得する方法はわかりません。ブレークポイントの現在の位置のみです。

作業する必要がある唯一の情報は、3 つのサイトの x、y 位置と、スイープラインの現在の y 座標です (水平スイープラインを使用しています)。

実は、収束を判断するためのアイデアが 1 つあります。2 つのサイトがある場合、それらが定義するビーチラインの 2 つのセクション間のブレークポイントは、スイープ ラインの現在の位置によってのみ制御されます。2 つのブレークポイントの位置を記録し、一時的にスイープ ラインを少し進めて、新しい位置を記録することを考えました。通常のボロノイ図のエッジは曲がらないため、ブレークポイントの新しいペア間の距離が古いペア間の距離よりも小さい場合、ブレークポイントは収束します。そうでなければ、それらは発散します。しかし、これは危険であり（常に機能するかどうかはわかりません）、醜いようです。きっともっと良い方法があるはずです。

任意のアイデアを歓迎します。疑似コード (可能であれば C# のような構文) は特にそうです。また、ボロノイ図を取得するために使用できる計算幾何学ライブラリがあることも認識していますが、これは個人的な学習課題であるため、アルゴリズムのすべての部分を自分で実装したいと考えています。

私は何千ものポイントのセットで作業します。Fortunesアルゴリズムの既存の実装を実装または使用して、ポイントのボロノイ図を作成できますが、アプリケーションでは、各ボロノイセルに関する隣接関係を知る必要もあります。

より具体的には、ボロノイセルについては、これに隣接するセルを知る必要があります。この時点では、実装をマッサージして自分に有利に働く可能性があるため、出力方法や保存方法については気にしません。

誰かがアルゴリズムを知っていますか、またはセル隣接の決定を達成できる実装されたアルゴリズムをもっとよく知っていますか？私が行う作業はPythonですが、コードを簡単に翻訳できるので、何でも素晴らしいでしょう。

ありがとう！

長方形のサーフェスを N 個の点でボロノイ分割したいとしましょう。ボロノイ分割により、N 個の点に対応する N 個の領域が生成されます。各領域について、その面積を計算し、それを表面全体の総面積で割ります。これらの数値を a1、...、aN と呼びます。それらの合計は 1 に等しくなります。

ここで、N 個の数値 b1、...、bN のプリセット リストがあり、それらの合計が 1 に等しいとします。

a1==b1、a2==b2、...、aN==bN のように、ボロノイ分割の N 点の座標の選択肢 (任意の) を見つけるにはどうすればよいでしょうか?

編集：

これについて少し考えてみると、Voronoi 分割は最適な解決策ではないかもしれません。N 領域が適切なサイズになるように、サーフェスをランダムに不規則に分割することが重要です。ボロノイは論理的な選択のように思えましたが、間違っているかもしれません。

matlab で各ボロノイ セルの面積を計算しようとしていますが、スタックしています。このコードをオンラインで見つけました：

v の点の 1 つが [Inf,Inf] であるため、このコードは機能しません。これは無限の点です。どうすればこの問題を回避できますか?

新しい scipy (0.10 を使用) から scipy.spatial.Delaunay を実行した 3D には約 50,000 のデータ ポイントがあり、非常に便利な三角形分割が得られます。

基: http://en.wikipedia.org/wiki/Delaunay_triangulation (セクション「ボロノイ図との関係」)

...ボロノイ分割であるこの三角形分割の「デュアルグラフ」に到達する簡単な方法があるかどうか疑問に思っていました。

手がかりはありますか？これを調べてみると、組み込みの scipy 関数が表示されないようです。これはほとんど奇妙です!

ありがとう、エドワード

私は次のことを行うアルゴリズムを考え出そうとしています:

点の集合が与えられた場合、集合からの点を含まない最大の円 (クエリ点を中心とする) をクエリ点として見つけます。

これまでのところ、集合のサイト ポイントに最も近いポイントを含む領域 (セル) を見つけるためにボロノイ図を使用し、次にボロノイからのエッジ リストを使用して台形分解を構築することを考えてきました。分解から、クエリ ポイントがどのセルにあるかを見つけることができます。円の半径は、クエリ ポイントからそのセルのポイント (サイト) までの距離になります。ボロノイには O(n) ストレージが必要であり、ボロノイからの台形分解の作成も O(n) ストレージで実行できるため、このようなものを作成するために必要なストレージは線形であると思います。

*編集: クエリ時間は O(logn) でなければなりません。つまり、セットのすべてのポイントを一度に 1 つずつ反復処理することはできません。

これは正しいと思いますか、それともここで何かが欠けていますか?

また、このアルゴリズムに関して参照できる参考文献があれば教えてください。ありがとう ：）

以下のFCMメソッドでボロノイ図をどのように表示/プロットするのか疑問に思いましたか？また、MATLABの各ポイントを配置して計算するときに、図からプログラムを見ることができる方法はありますか？まるでランニングトレーラーのようです。

私は C++ で Voronoi Tessellation ライブラリを探していますが、Voro++ は法案に完全に適合しているようです。たとえば、セル自体のプロパティへの簡単なアクセスなど、Voro++ が非常に優れた機能を提供する必要があります。ただし、Voro++ は 3D 作業用に調整されているようです。2D モードで Voro++ を使用することは可能ですか?

3Dですべてを行うだけで、zコンポーネントがゼロのポイントのみを持つとうまくいくと思います（「ボックス」のz範囲が-0.5 - 0.5である限り）が、これは大規模なやり過ぎのようです。