問題タブ [voronoi]

テリトリー マップを生成する簡単な、または少なくとも適度に簡単な方法はありますか (リスクなど)?

私は過去に調べたことがありますが、ボロノイ図への漠然とした参照が見つかりました。ボロノイ図の例は次のとおりです。

.

これらは有望ですが、これらをレンダリングする簡単な方法は見たことがないと思います。ましてや、各領域をオブジェクトとして扱うための何らかの形式のデータ構造でそれらを保持することは言うまでもありません。

有望なもう 1 つのアプローチはフラッド フィルですが、このアプローチを開始する最善の方法については確信が持てません。

アドバイスをいただければ幸いです。

私は州のランダム マップを作成するゲームに取り組んでいます (リスクまたは外交)。そのマップを作成するには、まず一連の半ランダムな点を生成し、次にそれらの点の Delaunay 三角形分割を計算します。

これが完了したら、州境の開始点として機能するポイントのボロノイ図を作成しようとしています。この時点での私のデータ (しゃれは意図していません) は、元の一連の点と Delaunay 三角形のコレクションで構成されています。

ウェブ上でこれを行う方法をいくつか見てきましたが、そのほとんどは Delaunay がどのように導出されたかに関係しています。Delaunay に統合する必要はなく、データだけに基づいて機能するものを見つけたいと思っています。それに失敗すると、最適な速度とは対照的に、相対幾何学​​の初心者にわかりやすいものを探しています。ありがとう！

球面上の一連の点のボロノイ図を見つけるための単純な (存在する場合) アルゴリズムを探しています。ソースコードは素晴らしいでしょう。私は Delphi マニアですが (はい、知っています...)、C コードも食べます。

Newsgraphのような統計データのボロノイ ツリーマップを作成したい

Perl、PHP、Ruby、または Python でそれを行う方法を知っていますか?

ボロノイ図を実装する簡単なアルゴリズムは何ですか?

特に疑似形式のアルゴリズムは見つかりませんでした。ボロノイ図アルゴリズム、チュートリアルなどのリンクをいくつか共有してください。

ボロノイ図を実装して、マップ内の最も近い場所を視覚的に見つけます。現在、キャンバス内でのみ整数座標 (x,y) を使用してこれを行いたいと考えています。

問題は-私はこのアルゴリズムについて本当に混乱しています。フォーチュンのアルゴリズムに関するいくつかの理論を含む、計算幾何学の本を読みました。そして今、私は本当に混乱しています。私がコーディングしようとしているとき、それは私にとって非常に複雑に思えます。

ボロノイ図の非常に単純な実装（指定された座標を使用）についてアドバイスしてください。ハッシュ、マルチスレッド、Delaunay Traingulation、派手な色などを使用しないで、単純なJavaまたはPythonまたはスキームコードをアドバイスしてください。

マルチスレッドやハッシュマップなしで Fortune のアルゴリズムを使用してボロノイ図を実装することはできませんか?

2点のグリッドを取得しました。各ポイントが他のポイントよりも先に到達できる正方形の量を計算したいと思います。現在、私は FloodFill-Algoritm を実装しています。これは、1 つのポイントが到達できる正方形の量を計算できます。

そのアルゴリズムを変更して、両方のポイントに対して同時に、または少なくとも 1 つずつ「フラッディング」を行うにはどうすればよいですか?

フォーチュンのアルゴリズムを使用して、一連の点のボロノイ図を見つけました。返されるのは線分のリストですが、どの線分が閉じた多角形を形成しているかを知り、それらを囲む元の点によってハッシュされたオブジェクトにまとめる必要があります。

これらを見つけるための最速の方法は何ですか?? アルゴリズムからいくつかの重要な情報を保存する必要がありますか? もしそうなら何？

これは、C++ 実装から移植された Java でのフォーチュンのアルゴリズムの実装です。

（コンパイルできないこと、データ構造を初期化する必要があること、およびインポートが欠落していることはわかっています）

私が欲しいのはこれです：

これを行うために私が考えることができる最も直接的な強引な方法は、ダイアグラム内のポイント (エッジのエンドポイント) の無向グラフを作成することです。次に、このグラフ内のすべてのループを探し、3 つ以上のポイントを共有するループの各セットについて、最短のループ以外をすべて破棄します。ただし、これは遅すぎるでしょう。

緯度/経度のいくつかのペアでボロノイ図を作成したいのですが、(不正確な) ピタゴラス距離ではなく、それらの間の大円距離を使用したいと考えています。

qhull/qvoronoi または他の Linux プログラムでこれを行うことはできますか?

点を 3D にマッピングし、qvoronoi で 3D ボロノイ図 [1] を作成し、その結果を単位球と交差させることを検討しましたが、簡単ではありません。

[1] 2 つの緯度/経度 (「地球を通過する」パス) 間の 3D 距離は大圏距離と同じではないことは認識していますが、この変換が相対距離を維持することを証明するのは簡単です。ボロノイ図の場合。

O(n) のポイントのボロノイ図からポイント セットの凸包を計算するためのアルゴリズムが必要です。ボロノイ図はバウンディング ボックスに含まれ、二重接続エッジ リストとして格納されます。入力は、境界ボックス上に原点があるハーフ エッジです。

無限に長いボロノイ エッジを共有する場合、2 つの点が凸包上で隣接していることはわかっています。