半径に最も近い隣人を探す

Question

私は私の空間に a のセットを持っています（Geo Pointsが2D平面上にあると思います）。

私は別の点を持っています b 。

b のあらゆる点ごとに、の中心との中心とともに半径 r 内の a のあらゆる点を見つけたいです。 > B セット。

私はKDTreeでそれをやりました、これは私にデータ構造を作成し、隣人を見つけ、を見つけるために非常に速くそして簡単なアルゴリズムを提供しますこれは私の半径の要素を含みますが、半径中心の同じサブセットにはありません。

kdtreeの最小の例：

KDTREEの探索ターゲットポイント（赤）は、ポイント番号1の行の下にあります。これは、線の下の点の探査に進みます、これは赤い点の半径内の実際の点を見逃すでしょう。

href="https://i.stack.imgur.com/fcrwg.png" rel="nofollownoreferrer">

100％の正当性を可能にするのはどのようなアルゴリズムまたはデータ構造を可能にしますか？

私は確かに悪化しますが、私は検索速度と完全な正当性の間のバランスを探しています。

Answer 1

K-Dツリーはこれを解決するための良いデータ構造です。ただし、検索手順をセンターポイントにのみ盲目的に適用することはできません。

あなたのポイントのKDツリーを検索しながら、検索する毎回左または右の子供を選択する必要がある場合は、分割平面があなたの円の左側にあるかどうかを確認し、それに交差するか、円の右側にあるか。

分割面が円の左側にある場合は、右の子を検索し続ける必要があります。しかし、分割面がを交差するときは、の両方の子供たちを検索する必要があります。