kdツリーを使用して2次元空間のポイントを検索するアプリを作成しています。開発中に、各ポイントを囲む最も近いゾーンを「見る」ことができれば便利です。
添付の画像では、赤い点はkdツリー内の点であり、各点を囲む青い線は、最近傍探索が含まれている点を返すゾーンを境界付けています。
画像は次のように作成されました。
for each point in the space:
da = distance to nearest neighbor
db = distance to second-nearest neighbor
if absolute_value(da - db) < 4:
draw blue pixel
このアルゴリズムには2つの問題があります。
この一連のポイントの「視覚化」とは何ですか？
そのような視覚化を作成するためのいくつかの良いアルゴリズムは何ですか？
これはボロノイ図と呼ばれ、それらを効率的に生成するための優れたアルゴリズムが多数あります。私が最もよく耳にするのは、時間O（n log n）で実行されるFortuneのアルゴリズムですが、この問題には他のアルゴリズムも存在します。
お役に立てれば！
ジェイコブ、
ねえ、あなたはこのボロノイ図を生成する興味深い方法を見つけましたが、それはそれほど効率的ではありません。
最初にそれほど重要ではない問題：あなたが得るさまざまな厚さの境界、それらの蝶の形は、実際には双曲線の2つの枝の間の領域です。正確には、方程式| da--db|によって与えられる双曲線 = 4.代わりに太い線を取得するには、この基準を変更して、2つの最も近い隣接する二等分線までの距離に置き換える必要があります。AとBとします。ベクトル計算を使用して、| PA.AB/ || AB || -|| AB || / 2 | <4。
より重要な問題：一連の点のボロノイ図の構築には、2つのよく知られた効率的なソリューションがあります。Fortuneのスイープアルゴリズム（templatetypedefで言及）とPreparata＆ShamosのDivide＆Conquerソリューションです。どちらもNポイントに対して最適な時間O（N.Lg（N））で実行されますが、実装はそれほど簡単ではありません。
これらのアルゴリズムは、ボロノイ図を線分と半直線のセットとして作成します。http://en.wikipedia.org/wiki/Voronoi_diagramを確認してください。
このペーパー「一般的な細分化の操作とボロノイの計算のためのプリミティブ」では、すべての実装の詳細に注意を払いながら、やや高レベルのフレームワークを使用して両方のアルゴリズムについて説明します。記事は難しいですが、アルゴリズムは実装可能です。
また、私が試したことのない「平面ボロノイ図の単純な反復アルゴリズム」もご覧ください。
まったく異なるアプローチは、たとえばダイクストラのアルゴリズムを使用して、指定されたポイントから距離マップを直接作成することです。指定されたポイントから開始して、すべてのポイントから指定された距離内でエリアの境界を拡大し、2つの境界で拡大を停止します。会う。[詳細な説明が必要です。] http://1.bp.blogspot.com/-O6rXggLa9fE/TnAwz4f9hXI/AAAAAAAAAPk/0vrqEKRPVIw/s1600/distmap-20-seed4-fin.jpgを参照してください
（距離マップを効率的に計算するための）もう1つの良い出発点は、「線形時間で距離変換を計算するための一般的なアルゴリズム」です。
個人的な経験から：フォーチュンのアルゴリズムは実装するのが面倒です。GuibasとStolfiによって提示された分割統治アルゴリズムはそれほど悪くはありません。それらは、手続き型プログラミング言語に簡単に変換できる詳細な擬似コードを提供します。入力がほぼ縮退していて浮動小数点を使用している場合は両方とも爆発しますが、プリミティブは2次式であるため、座標を32ビット整数として表すことができる場合は、64ビットを使用して行列式の計算を実行できます。
動作するようになったら、シータ（√n）の最悪のケースを持つkdツリーアルゴリズムを、平面サブディビジョンで動作するアルゴリズムに置き換えることを検討してください。
D3.jsライブラリでその優れた実装を見つけることができます：http：//mbostock.github.com/d3/ex/voronoi.html
