問題タブ [voronoi]

直線と長方形の平面領域内の特定のボロノイ分割のすべてのエッジとの交点を決定する計算効率の良い方法はありますか?

ありがとう

私が持っていたアイデアの 1 つについてお聞きしたいのですが、解決策がわかりません。私のアイデアは次のとおりです。

長方形で覆われた一連の GPS 座標ポイントを持って、その形状に従ってそれらのポイントを接続する方法、それらのポイントを接続するために Quick Hull を試したところ、凸状になり、期待した結果ではありませんでした。たとえば、「L」字型に沿った一連の点があるので、それらを接続すると「L」型になります。

voronoi と delaunay を試しましたが、まだ良い結果が得られませんでした!!

これに対する良い解決策を見つけるのを手伝ってくれてありがとう。

本当に感謝しています！

みんな、ありがとう

立方体のボックス内に単分散球のシステムがあります。ボロノイ テッセレーションと Delaunay テッセレーションのいずれかでテッセレーションした後、サンプル内の体積分布を調べています。テッセレーションに依存してはならないいくつかのプロパティに興味があります。

現在、Voronoi と Delaunay から得られた値と比較しています。別の空間分割アプローチに精通しているかどうかを知りたいです (個々のセルの最終的な合計が総体積になることが重要であり、セルはバラバラでなければなりません)。さらに、別の種類のテッセレーションを知っている場合、C/C++ または python で推奨される、既にそれを実装しているライブラリも知っていますか?

ラゲール分割のようないくつかのバリエーションは、球が単分散であるため、現在のボロノイ アプローチと一致します。もう 1 つの候補は重心ボロノイ テッセレーションですが、それを行うライブラリはまだ見つかっていません (ただし、システム内の無秩序を反映しない等間隔のセルになる可能性はありますが、これは望ましくありません)。

よろしくお願いいたします。

ボロノイ ポリゴンを使用してマップをレイアウトし、ポリゴンのエッジのリストを返す関数を使用しているため、描画するとエッジは次のようになります。これが私の目標でした。ただし、保持する地形のタイプなど、個々のポリゴンに関する情報を保存する必要がありますが、そのためには、エッジのリストのみを指定してポリゴンを構築する必要があります。私の質問は、これらのポリゴンをエッジのリストからどのように構築するのですか?

疑似コード、C++、または Objective-C を受け入れる

私はボロノイ テッセレーション アルゴリズム (フォーチュンのアルゴリズム; それ自体が非常に重要なタスクだと思います) のバイナリ検索ツリーを探しているので、もちろん、Boost を調べてみようと思いました。

Boost にはIntrusiveヘッダー ファイルがあり、そこには豊富な BST (AVL、Splay ツリー、Scapegoat ツリーなど) が含まれているようで、一見しただけで必要なもののように見えました。 .

1:何か足りないのでしょうか、それともツリーのルート ノードに直接アクセスする方法がありませんか?

2: AVL ツリーは Fortune アルゴリズムのビーチライン構造に適していますか?

くそー、これは簡単だと思った。

更新:おそらく、私が達成しようとしていることを述べたほうがよいでしょう: Fortune アルゴリズムの一部である放物線検索を実装したいと思います。これは、新しいサイトが検出され、放物線を真上で見つける必要がある部分です。正しい円弧を見つけるために、ルートからツリーをたどろうと思いました。

私が念頭に置いているこのアイデアを得るには、いくつかの参照が必要です。

最大の白丸問題を考えると、新しいモールをどこに配置するかを決定したい

私の問題: 海で 2 つに分割された地図がある場合、ボロノイ図は地理的制限を考慮せずにポイントを通過します (つまり、誰かが地図の左側に住んでいる場合、その人は横断したくないでしょう)。モールに行く海）

これに対処する可能性や参照はありますか?

ちなみにフォーチュンのアルゴリズムは以前読んだ

これは単純な質問かもしれませんが、私は疑問に思っていました：

ボロノイ図が利用可能なモデルをどのようにスケルトン化しますか?

何か案は？リンク？ありがとうございました！

ポリゴンを形成するポイントを取得して、色で塗りつぶそうとしています。一連の点があり、それに対してボロノイ図を計算します。結果は次のとおりです。

緑色の点は私が定義した点で、青色の点はボロノイ図の計算された頂点です。特定の緑色の点によって生成された多角形を塗りつぶしたいので、多角形を形成して塗りつぶすために、その周りにある点を知る必要があります。

Gift Wrapping AlgorithmとConvex Hullについて読みましたが、必要なものではないようです。このニーズに合うアルゴリズムはありますか? 私は C++ でプログラミングしていますが、Java または C# のヘルプがあれば役に立ちます。

2D電力線図を作成するためのアルゴリズムの適切な説明を見つけようとしましたが、これまでのところ空でした。Java 実装、または Scala または Python の (理解可能な) バージョン、または実装の基礎となる疑似コードのいずれかを教えてもらえますか?

私の目標はこれを Java アプリケーション内で使用することなので、ネイティブ ライブラリをバンドルすることは現実的ではありません。

AO(n log(n)) アルゴリズムは素晴らしいですが、私の目的にはおそらく O(n^2) で十分です。