問題タブ [voronoi]

Voronoi を使用してマップを作成する Java プログラムに取り組んでいます。Voronoi を生成する Java ライブラリを使用していますが、非常に高速です ( http://sourceforge.net/projects/simplevoronoi/ )。

私が直面している問題は、各ポイントを含むポリゴンを作成するために、エッジの左右にあるポイントを知るために、すべてのボロノイ エッジをスキャンする必要があることです。すべてのボロノイ エッジを含むクラスです。

座標x1, y1, x2, y2はエッジの開始座標と終了座標であり、site1とsite2はエッジの左右にある点のインデックスです。したがって、すべてのポイントを含むポリゴンを作成するには、次のようにします。

どこxValuesとyValuesは、ボロノイ図を生成するためのポイント座標であり、GPolygonから拡張して作成した Polygon クラスですjava.awt.Polygon。これらは私が測定した時間です：

• ボロノイ時間: 283 mS (ボロノイ図を生成する時間)
• ポリゴン検索時間: 34589 ミリ秒 (ポリゴンを生成する for ループを完了する時間)
• ポリゴンの塗りつぶし時間: 390 ミリ秒 (オプションで、ポリゴンを塗りつぶして画像に保存する時間)
• ポイント数: 26527 (ボロノイが生成されるポイントの数)
• マップ生成完了
• ポリゴン数: 26527 (ポリゴン数、各ポイントに 1 つ)

ご覧のとおり、他のループに比べて非常に時間がかかります。どうすれば for ループを高速化できますか? 他にどのような選択肢がありますか? 事前にどうもありがとうございました。

ボロノイ図の境界ボックスを作成する必要があります。私の問題は、「それに半無限のエッジを付ける方法」です。

Fortune のアルゴリズムを使用してダイアグラムを計算し、de Berg、Cheong、van Kreveld、Overmars による「Computional Geometry」に従います。

おそらく、私の幾何学の知識は非常に悪いですが、それを行う方法がわかりません!

誰かが境界ボックスを構築するためのアルゴリズムを知っていますか?

私は現在、サブ問題として 2D ポイント セットの変更を含むプロジェクトの研究を行っています。ポイント セット自体には、いくつかのポイントのクラスターが含まれます。これをどうにかして互いに分離し、クラスター ハル内のポイントを緩和する必要があります。あるいは、クラスターのハルポイントを取得し、それらをドメインとして使用し、それらの内部に (ほぼ) 等間隔にポイントを分散するだけで十分です。したがって、緩和はスキップされる可能性があります。最悪のシナリオとして、最大 10 万個の頂点を含むいくつかのポイント セットを処理する必要があるため、使用するアルゴリズムは高速である必要があります。私はこの問題の複雑さを知っています。そのため、車輪を再発明したくなく、可能であれば既存のコードを使用したいと考えています。これまでのところ、次のことがわかりました。

1. 点集合緩和: Fortunes/Sullivans "Sweep Line" アルゴリズム: 最速のシングル スレッド ボロノイ ダイアグラム コンストラクターと言われています。ただし、コードを拡張するのは非常に難しいようで、デフォルトで抽出可能な情報には、少なくとも重心を計算して次の緩和反復を実行する必要があるボロノイ セル ハル データ (それらの頂点位置) が含まれていません。さらに、長方形以外のドメインは使用できません。

2. CVT: ボロノイ図を作成するための多目的ライブラリの束。ポイントの緩和と、ユーザーが指定した領域内のポイント セットもサポートしています。

3. CGAL: 基本的な MP サポートを備えた広範なフレームワークですが、明らかに統合された緩和方法はありません。各ポイント セットのサブクラスターの delaunay 三角形分割を作成し、これをボロノイ アダプターにフィードする必要があります。ボロノイ アダプターは、さらに緩和するためにボロノイ セル ハル データをクエリするイテレータを提供します。私がドキュメントを読んでいる限り、ドメインをサポートする必要があります（数千ページ:)

4. さらに、主に 3D で動作するように見える Voro++ などがあります。三角形。領域の制約を使用して、指定されたドメインからドローネ三角形分割を作成し、三角形の頂点を結果の点として使用できるようにします。

わかりました、現時点では、これをすべて非常にシンプルに保ちながら、CVTが私のニーズに合うべきだと私には思えます。しかし、よくわからないので、質問: できればドメインを使用して、ポイントセット緩和の実装を経験した人はいますか? どの既存のコードが望ましいでしょうか?

毛皮の提案に感謝します！t

d3js Web サイトの 2 つの例:

簡単バージョン

より複雑

彼らのコードのいくつかは理解しにくいと思います。D3 参照 API は詳細な説明を提供しませんでした。簡単なバージョンでは、次のように Math.random() を使用して頂点が生成されました。

幅と高さはドキュメント サイズです。これにより、すべての頂点が SVG 要素の範囲内にあることが保証されます (svg タグには width および height 属性もこれらの値に設定されています)。

ただし、より複雑なバージョンでは、アルゴリズムを使用して頂点を生成します。

verticesコンソールで変数を調べるとき。二次元配列であることがわかりました。各サブ配列の長さは 3 で、最初と 2 番目の要素は数値で、最後の要素は x、y、インデックスなどのより多くのプロパティを含むオブジェクトです。

結果のボロノイ図は大きく異なります。何故ですか？どちらも を使用して生成されd3.geom.voronoi()、(うまくいけば理解できることから) 唯一の違いは、渡されるオブジェクトにあります。簡単な例では、各サブ配列に 2 つの数値を持つ単純な 2 次元配列でした。複雑な例の 2 行がどのように機能してこのような複雑なオブジェクトを作成し、それを各サブ配列の末尾に追加するのか、私にはわかりません。

頂点が親 SVG 要素の境界内にあることをどのように保証しますか?

私は本当に行き詰まっています。助けてくれてありがとう。

QtでCGALを使用してボロノイ図を描いています。CGAL::Voronoi_diagram_2<DT,AT,AP>顔が必要なので使いました。これはコード例です:

ソースまたはターゲットが無限にある光線をクリップする必要があります。Cropped_voronoi_from_delaunay を使用してボロノイを生成すると、面ではなくセグメントのみが得られます。これらはtypedefです：

Qhull を使用して、どのボロノイ セル (インデックスによる) が「適切な」(「既存の頂点」で構成されている) かを判断する方法

Lloyds アルゴリズムと scipy.spatial Voronoi (Qhull のラッパー) によって生成された入力を使用して、制約付き緩和を実行しようとしています。

コード的には次のようになります。

コードによって生成された出力グラフは問題ないように見えますが (以下を参照)、vor 構造体のデータはロイズ緩和を実行するのに十分ではありません。これは、有効なボロノイ セル (画像の #4) 内にあるポイントのみを移動する必要があるためです。もう一方はそのままにしておく必要があります。Qhull はポイント/リージョンの順序を乱すため、どのリージョンがどのポイントに属しているかを推定できません。

問題の図を次に示します。

これで、vor.regions[7] がポイント vor.points[4] に属する領域であることがわかります。これを達成する方法は？

私はGISで働いています。ポリゴンのセットがあります。ポリゴン セットが有効なボロノイ図であるかどうかを最初にチェックするアルゴリズムを作成したいと思います。はいの場合、同じボロノイ図を生成できる点のセットを返します。

誰かが私にそれをする方法を手伝ってもらえますか

ありがとう

エッジを共有するすべての三角形のリストがあります。ボロノイ図を描くにはどうすればよいですか？Delaunay 三角形をループして、頂点 1 = 頂点 2 および頂点 2 = 頂点 1 と比較します。同じエッジがある場合。また、頂点 1 = 頂点 1 および頂点 2 = 頂点 2 の場合もチェックします。方程式では、両側が異なる三角形です。Boywer watson アルゴリズムと同じループです。

scipy の Voronoi テッセレーションを使用しようとしています

http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.Voronoi.html

しかし、pythonはそれをインポートしません

ただし、scipy.spatial から他のクラスをインポートしても問題はありません