近くの点を見つけるためのアルゴリズム？

StackOverflow https://stackoverflow.com/questions/838344

質問

x、y座標を持つ数百万のポイントのセットを考えると、ある場所から上位1000の最も近いポイントをすばやく見つけるためのアルゴリズムは何ですか？ <！> quot;すばやく<！> quot;ここでは、自宅のコンピューターで約100ミリ秒を意味します。

ブルートフォースとは、何百万もの乗算を実行してからソートすることを意味します。単純なPythonアプリでも1分未満でそれを実行できますが、インタラクティブなアプリケーションにはまだ長すぎます。

ポイントの境界ボックスは既知であるため、スペースを単純なグリッドに分割できます。ただし、ポイントはやや不均一に分布しているため、ほとんどのグリッドスクエアが空になり、突然、それらの一部にポイントの大部分が含まれることになると思われます。

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

編集：ポイントのセットはめったに変更されません。

役に立ちましたか？

解決

quadtree の使用はどうですか？

エリアを長方形に分割します。エリアのポイントの密度が低い場合、長方形は大きく、エリアのポイントの密度が高い場合、長方形は小さくなります。長方形が十分に小さくなるか、ポイントが少なくなるまで、各長方形を4つのサブ長方形に再帰的に細分化します。

その後、その場所の近くにある長方形のポイントを見始め、1000ポイントを見つけるまで外側に移動できます。

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

他のヒント

クアッドツリーは便利ですが、 BSPツリーはO（log n）時間で実行されることが保証されています。クワッドツリーには有限のバウンディングボリュームが必要だと思います。また、多数のポイントが同じ比較的小さなスペースを占有している場合など、クワッドツリーが悲惨に失敗する縮退したケースもあります。

とはいえ、クアッドツリーは間違いなく実装が簡単で、ほとんどの一般的な状況で非常に効果的です。 UPSはルーティングアルゴリズムで使用します。これは、都市が関心のある地域に広がる傾向があるため、実際には重大な問題を引き起こさないという欠点があるためです。

クアッドツリーまたはRTreeのような構造を使用します。これらは多次元インデックス構造です。

重要なのは、適切な<！> quot; space fill curve <！> quot;を使用することです。これは、ポイントの近さを定義するのに役立ちます。単純な空間充填曲線はZorderですが、ヒルベルト曲線のようなものにもっと興味があるでしょう。

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

このパッケージの実装済みパッケージは知りません。最近、バルクロードと検索のみをサポートする2次元で独自のRTreeを実装しました（提供された境界ボックスを使用）。

ここでの欠点の1つは、ポイントを有限領域に含める必要があることです。有限ではない空間で機能する空間充填曲線があることはわかっていますが、それらについては何も知りません。

QuadTreeおよびBSPツリーの提案に加えて、最近傍検索を調べる必要があります。 。アルゴリズムの選択は、ベースデータセットに追加する頻度に基づいています。頻繁に追加および削除する場合は、ツリーソリューションが優れています。データがより静的である場合、最近傍検索およびボロノイ図ははるかに高速で、スケーリングが向上します。

ポイントのセットがめったに変化しない場合は、ボロノイ図の使用を検討することもできます。それが最初のポイントをより速く見つけるのに役立つかどうかはわかりませんが、次の999ポイントを見つけるのがずっと簡単になるはずです。

ポイントはデータベースまたは検索可能なインデックス付きの場所にあると思いますか？もしそうなら、それはかなり速いはずです。指定されたポイントから、x軸とy軸に範囲を設定し、その範囲内のすべての位置を取得できます（つまり、左上隅x（a）とy（b）および右下隅x（c）とyを指定します（d））。

次に、y <！> gt; = b AND y <！> lt; = d AND x <！> gt; = a AND x <！> lt; = cのポイントを検索します。これは、x座標とy座標に別々にインデックスがあると仮定すると、迅速になります。 （原点が左上0,0と仮定）。

その後、結果セット内のポイント数が<！> gt; = 1000になるまで、この範囲をzずつ増やす（または結果が大きい場合は減らす）ことができます。いくつかの試行を実行することで、開始する長方形のサイズを決定するのに役立つ標準偏差およびその他の統計値。プログラムは、取得した結果に基づいて、このために自己調整することもできます。

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

私は、Googleからこの投稿を見つけて本当に高速な結果が必要な場合、最速ではないと言われていることを知っています。座標に近い場所を探し、距離によってそれらを返します。

それが誰かを助けることを願っています：）

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

注：これは、これがこの質問の最善の解決策ではないことを既に述べました。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top