c++ - このボロノイ図のデータからセルの辞書を取得するにはどうすればよいですか？

Question

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

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

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

Input points:
0   (426.484, 175.16)
1   (282.004, 231.388)
2   (487.891, 353.996)
3   (50.8574, 5.02996)
4   (602.252, 288.418)

Vertex Pairs: 
0   (387.425, 288.533)  (277.142, 5.15565)
1   (387.425, 288.533)  (503.484, 248.682)
2   (277.142, 5.15565)  (0, 288.161)
3   (387.425, 288.533)  (272.213, 482)
4   (503.484, 248.682)  (637.275, 482)
5   (503.484, 248.682)  (642, 33.7153)
6   (277.142, 5.15565)  (279.477, 0)

Voronoi lines?: 
0   (279.477, 0)    (277.142, 5.15565)
1   (642, 33.7153)  (503.484, 248.682)
2   (503.484, 248.682)  (637.275, 482)
3   (387.425, 288.533)  (272.213, 482)
4   (277.142, 5.15565)  (0, 288.161)
5   (387.425, 288.533)  (503.484, 248.682)
6   (277.142, 5.15565)  (387.425, 288.533)

Delaunay Edges: 
0   (282.004, 231.388)  (487.891, 353.996)
1   (602.252, 288.418)  (487.891, 353.996)
2   (426.484, 175.16)   (487.891, 353.996)
3   (426.484, 175.16)   (602.252, 288.418)
4   (50.8574, 5.02996)  (282.004, 231.388)
5   (426.484, 175.16)   (282.004, 231.388)
6   (50.8574, 5.02996)  (426.484, 175.16)

Vertices: 
0   (277.142, 5.15565)
1   (503.484, 248.682)
2   (387.425, 288.533)
3   (0, 288.161)
4   (272.213, 482)
5   (637.275, 482)
6   (642, 33.7153)
7   (279.477, 0)

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

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

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

Answer 1

FortuneのアルゴリズムはO（n log n）ですが、Alinkによって提案されたようにセルをブルートフォース方式で再構築しようとすると、コードはO（n ^ 2）になります。

私の答えの出発点は、セルを生成するために使用しているのはライブラリではなく、Fortune自身が最初に提示したコードをきちんとまとめるために作成されたクラスであり、実際には成熟したライブラリではないということです。したがって、実際、作成者はあなたのニーズを予測していません。また、必要な情報は計算されていますが、アクセスできません。

内部的には、入力ポイントは「サイト」構造体のインスタンスとして保存され、アルゴリズムはハーフエッジの作成に進みます。各ハーフエッジは、それが囲むサイトへのポインタである参照「頂点」を維持します。ハーフエッジに沿って歩むと、囲まれたサイトを自然に一周します。まさに必要なものです。

このデータにアクセスするには、VoronoiDiagramGeneratorクラスを変更または拡張することをお勧めします。これを行うには、サイトポインターをキーとして、単一のHalfEdgeポインターを値としてハッシュテーブルを作成します。次に、generateVoroniメソッドを変更し、voronoiの呼び出しの直後に新しいコードを挿入します。

For each HalfEdge in ELHash
         Get table entry for current half edge's Site
         If site in table has null HalfEdge reference
            set current HalfEdge reference
         End If
End For each

...そしてあなたの辞書があります。その単一のハーフエッジにより、関連するサイトを囲むポリゴンの周囲を「歩く」ことができます。これは、あなたが求めていたものだと思います。次の問題は、どのポリゴンが新しいデータポイントを囲んでいるかを効率的に発見することですが、それは別の質問です:-)。完成したクラスを共有することを検討していただければ幸いです。基本クラスよりもはるかに便利なはずです。

編集：これは、上記のすべてを写真で説明している優れたプレゼンテーションです： http : //ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt ：

• ボロノイ図の定義
• ハーフエッジの木（下の写真を参照）
• 写真の幸運のアルゴリズム

そして、上記で提案したように、辞書を取得するのに役立つC＃実装があります：http：//www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Answer 2

エッジのリストはどういうわけか不完全です。ライブラリ呼び出しに提供された包含長方形の境界にエッジを追加する必要があります（ここでは642,482のようです）。技術的には、ボロノイ細分割はいくつかの無限エッジを使用する必要がありますが、それらはすべて有限です。これらの「開いた」ポリゴンも、この例ではすべて同じであるため、この境界の近くに配置する必要があると思います。

これらの境界エッジを追加するのは難しいことではなく、面倒です。おそらく、メインの長方形の各辺について、その上のすべての頂点を見つけ（コーナーを無視して）、それらを並べ替え（水平の場合はx、垂直の場合はy）、これらの値を使用してその辺を分割します。これにより、欠落しているエッジが生成されますが、2つのセルを分離していないのはエッジだけであるため、これらは特別であるため、メインリストに直接追加しないでください。

したがって、質問自体については、次のようになります。エッジのメインリスト（ライブラリによって提供される）では、各エッジが2つのセルを分離し、どちらのセルが見つかった場合は、そのエッジをこれらの各セルに割り当てることができます。セル。セルは入力ポイントと同等であるため、頂点の代わりにエッジのリストを除いて、必要な辞書がありますが、変換は簡単です。

次に、これら2つのセルを取得します。エッジの中点を計算し、これから、2つの最小距離を維持しながらリストを反復処理することにより、最も近い2つの入力点を見つけます。ボロノイ構造の特性により、これら2つは2つのセルを形成するものです。これらの2つの距離は等しくなければなりませんが、フロートの不正確さはおそらくわずかな違いをもたらすことに注意してください。

最後に、メインの長方形に沿って生成した境界エッジを追加しますが、それらは1つのセルにのみ隣接しているため、最初に最も近い入力ポイントを使用します。

最後に、エッジの各リストを頂点のリストに変換できます（各エンドポイントをセットにダンプします）。時計回りに並べ替える場合は、入力ポイントが内部にある凸多角形であることに注意してください。したがって、入力ポイントから各頂点に向かうベクトルを生成し、1つの軸からその角度を計算し（std :: atan2（x、y）を使用）、この角度をコンパレータ値として使用して並べ替えることができます（std ::を参照）。選別）。

Answer 3

Dalaunay三角形分割を生成するためにTriangleパッケージを使用しました：http ：//www.cs.cmu.edu/~quake/triangle.html

これは、a）triangulate.exeユーティリティとして、およびb）Cライブラリとして2つのモードで動作します。ユーティリティとしてコンパイルするには、triangle.cをコンパイルして実行する必要があります。

   triangulate -vZ input.poly 
   #v -voronoy, Z - starting from 0 index

ボロノイ図を取得するには（.poly形式についてはマニュアルを参照してください）このような.polyファイルの入力データを使用して実験を行いました。

# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)> 
5 2 0 0
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker]
0 426.484 175.16
1 282.004 231.388
2 487.891 353.996
3 50.8574 5.02996
4 602.252 288.418
#One line: <# of segments> <# of boundary markers (0 or 1)>
5 0
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker]
0 0 1
1 1 2
2 2 3
3 3 4
4 4 0

ただし、入力データエラーを報告するだけです。

• このパッケージを使用すると、エラーを報告する入力データでは機能しないことがよくあります。入力ポリゴン（ランダムポイントではない）のみを受け入れます。ここでの問題は、自己交差する入力ポリゴンがあることです。
• それはあなたの質問に答えず、辞書ではなく、ポイントのセットだけを報告します

Answer 4

Triangleを使用できます：http ：//www.cs.cmu.edu/~quake/triangle.html

Answer 5

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py

Carson FarmerによるこのPython実装は、トポロジ情報を提供します