近くの点を見つけるアルゴリズムですか？

Question

x、y座標で数百万点のセットが与えられた場合、ある場所から最も近い1000点を素早く見つけるための選択アルゴリズムは何ですか？ここで「すばやく」とは、自宅のコンピュータで約100msを意味します。

ブルートフォースは何百万回もの乗算をしてからソートすることを意味します。シンプルなPythonアプリケーションでも1分もかからずに済みますが、インタラクティブなアプリケーションでは長すぎます。

ポイントの境界ボックスがわかるため、スペースを単純なグリッドに分割することも可能です。しかし、ポイントは幾分不均等に分布しているので、ほとんどのグリッドの正方形は空であると思われ、突然一部のポイントに大きなポイントが含まれていると思われます。

編集：正確である必要はありませんが、実際には非常に不正確な場合があります。トップ1000が、実際にはトップ2000からのランダムなポイントのほんの一部であるならば、それは大したことではありません。

編集：ポイントのセットはほとんど変わりません。

Answer 1

quadtreeについてはどうですか？

面積を矩形に分割します。面積が小さい場合は矩形、矩形が大きい場合は面積が大きい場合は矩形が小さくなります。矩形が十分に小さくなるか、または十分な数のポイントが含まれなくなるまで、各矩形を4つのサブ矩形に再帰的に細分します。

あなたは、その場所の近くの長方形の点を見ることができます。そして、1000点を見つけるまで、外側に移動します。

コードは多少複雑になる可能性があります。そのため、単純なグリッドを試して、十分に速いかどうかを確認する必要があります。

Answer 2

Quadtreeはいいですが、BSP treesはO（log n）時間で動作することが保証されています。私は、クォドツリーは有限のバウンディングボリュームを必要とすると考えています。そして、クォドツリーが偶然に失敗するいくつかの縮退したケースがあります。例えば、多数のポイントが同じ比較的小さなスペースを占める場合です。

言われているように、Quadtreesはおそらく実装が容易であり、ほとんどの一般的な状況で非常に効果的です。これはUPSがルーティングアルゴリズムで使用しているものです。実際のところ問題点はありません。おそらく、都市は関心のある地域に広がっている傾向があるからです。

Answer 3

ポイントがデータベースまたは検索可能なインデックスされた場所にあるとしますか？もしそうなら、それはかなり速くなければなりません。与えられた点から、x軸とy軸の範囲を持つことができ、その範囲内のすべての位置を取得することができます（つまり、左上の最隅x（a）とy（b）と最右下の隅x（c）とy （d）参照）。

次に、y> = bかつy < = d AND x> = a AND x < = cの点についてクエリを実行します。これはxとy座標を別々にインデックスしていると仮定すると素早くなります。 （原点が左上で0,0であると仮定します）。

結果セット内のポイント数が> = 1000になるまで、この範囲をzで増やす（または結果が巨大である場合）ことができます。いくつかの試行では、標準偏差と開始する矩形のサイズを決定するのに役立つ他の統計的な数値。あなたのプログラムは、それが得た結果に基づいて自分自身を調整することもできます。

大まかなデータを設定したら、各ポイントとソースポイント間の距離を計算する非常に簡単な数式を設定します。

Answer 4

クワッドツリーやRTreeのような構造を使いたいと思っています。これらは多次元インデックス構造です。

キーは、ポイントの近さを定義するのに役立つ良い「スペース塗りつぶしカーブ」を使用しています。シンプルなスペース塗りつぶし曲線はZorderですが、ヒルベルト曲線のようなものにもっと興味があります。

http://en.wikipedia.org/wiki/Space_filling_curve

私はこのようなもののいずれかのパッケージ化された実装を知りません。私は最近、（バウンディングボックスを介して）一括読み込みと検索のみをサポートする独自のRTreeを2次元で実装しました。

ここでの欠点の1つは、ポイントを有限の領域に含める必要があることです。限られていないスペースで動作するスペースフィルカーブがあることは分かっていますが、私はそれらについて何も知らないのです。

Answer 5

ポイントの集合がほとんど変わらない場合は、ボロノイ図の使用を検討することもできます。 最初にポイントを見つけるのに役立つかどうかはわかりませんが、次の999ポイントを見つけるのがずっと簡単になります。

Answer 6

QuadTreeおよびBSPツリーの提案に加えて、nearest neighbour searchingを参照する必要があります。アルゴリズムの選択は、ベースデータセットに追加する頻度に基づいています。頻繁に追加したり削除したりする場合は、ツリーソリューションが優れています。データがより静的である場合、最近傍探索およびボロノイ図は、はるかに速くなり、より良くスケールすることができる。

Answer 7

私はあなたが本当に本当に速い結果がほしいと思えば、私は私が私のSQLソリューションを追加すると思いますproc。それは、coordの近くの場所を探し、距離によってそれを返します。

私はそれが誰か:)

CREATE PROCEDURE [dbo].[getstores] @lat float, @lng float AS 
DECLARE @radius float, @DegToRad float 
SET @DegToRad = 57.29577951 
SET @radius = 25000 
SELECT TOP 10 
    name 
    ,sto_lat 
    ,sto_lng 
    ,postcode 
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance 
FROM store 
WHERE (sto_lat >= @lat - (@radius/111)) 
And (sto_lat <= @lat + (@radius/111)) 
AND (sto_lng >= @lng - (@radius/111)) 
AND (sto_lng <= @lng + (@radius/111)) 
AND (
    ISNUMERIC(sto_lat) = 1 
    AND 
    ISNUMERIC(sto_lat) = 1 
) 
ORDER BY distance 

NOTEに役立ちます願っています：私はすでにこれが私