ボロノイ図を実装して、マップ内の最も近い場所を視覚的に見つけます。現在、キャンバス内でのみ整数座標 (x,y) を使用してこれを行いたいと考えています。
問題は-私はこのアルゴリズムについて本当に混乱しています。フォーチュンのアルゴリズムに関するいくつかの理論を含む、計算幾何学の本を読みました。そして今、私は本当に混乱しています。私がコーディングしようとしているとき、それは私にとって非常に複雑に思えます。
ボロノイ図の非常に単純な実装（指定された座標を使用）についてアドバイスしてください。ハッシュ、マルチスレッド、Delaunay Traingulation、派手な色などを使用しないで、単純なJavaまたはPythonまたはスキームコードをアドバイスしてください。
マルチスレッドやハッシュマップなしで Fortune のアルゴリズムを使用してボロノイ図を実装することはできませんか?
ボロノイ図は単なる図であり、データ構造やアルゴリズムではありません。セット内の最も近い点を見つけるのには適していないと思います。ダイアグラムを作成しても、問題の漸近的な複雑さは変わりませんが、問題がより複雑になり、メモリ効率が低下します。ポイントを四分木などに配置する方がよいでしょう。アルゴリズムを探している場合、解決しようとしている問題の名前は「空間インデックス」です。「最近点」は、四分木やその他の空間インデックスによって解決される問題の 1 つです。
複雑だから難しそう！ハッシュテーブルやスレッドは必要ありませんが、プライオリティ キュー (通常はヒープとして実装され、java と python の両方の標準ライブラリで利用可能) と、O(log n) で範囲クエリを実行できるツリーが必要になります。 (標準ライブラリにあるものは、内部を理解できないため、あまり適していません。AA ツリーを実装することをお勧めします)。そして、アルゴリズム自体はまだかなり複雑です。
外部プログラムを実行できますか? もしそうなら、ボロノイ図に非常に優れたQHullに重労働を任せることを本当にお勧めします。悲しいことに、私たちのどちらかがこれまでよりもはるかに優れています。
視覚化を含む、Ruby と C での別の実装を次に示します。
明らかに、フォーチュンのアルゴリズムを実装するのは簡単ではありません。特に、数値の堅牢性の問題のタイムラインを考慮する場合。それを実装するためにどのプログラミング言語を使用したいかは言いません。それが C++ の場合、GSoC 2010プロジェクトのフレームで Boostのために行われた Andriy Sydorchuk の作業を見つけることができます: Sweepline Algorithm。Andriy の実装はBoost.Polygonライブラリに基づいています。Voronoi 実装と Boost.Polygon はどちらも、数値の堅牢性を提供するために整数座標に依存しています。
平面内の点、線分、および多角形の内側軸のボロノイ図のスイープライン アルゴリズムに関する BoostCon ビデオ レクチャーは、アイデア、問題、および落とし穴について非常に適切な説明を提供します。
このボロノイ プロジェクトに関連して、かなり多くの議論が行われました。2010/2011 年に Boost メーリング リストで発生しました。