22

x,y 座標を持つ数百万点のセットが与えられた場合、ある場所から最も近い上位 1000 点をすばやく見つけるための最適なアルゴリズムは何ですか? ここでの「すばやく」とは、家庭用コンピューターで約 100 ミリ秒を意味します。

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

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

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

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

4

7 に答える 7

20

quadtreeを使用するのはどうですか？

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

次に、その場所の近くにある四角形の点を見始め、1000 個の点が見つかるまで外側に移動します。

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

于 2009-05-08T05:27:06.977 に答える
13

四分木は優れていますが、BSP ツリーは O(log n) 時間で実行されることが保証されています。四分木には有限のバウンディング ボリュームが必要だと思います。また、多数のポイントが同じ比較的小さな空間を占有する場合など、四分木が惨めに失敗する縮退したケースがいくつかあります。

そうは言っても、Quadtrees は間違いなく実装が簡単で、ほとんどの一般的な状況で非常に効果的です。これは、UPS がルーティング アルゴリズムで使用するものです。これは、おそらく都市が対象地域に分散する傾向があるため、実際には重大な問題を引き起こさないという欠点があるためです。

于 2009-05-08T05:34:40.483 に答える
7

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

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

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

このようなパッケージ化された実装については知りません。私は最近、(提供された境界ボックスを介して) 一括読み込みと検索のみをサポートする 2 次元で独自の RTree を実装しました。

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

于 2009-05-08T06:24:26.883 に答える
4

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

于 2009-05-08T06:42:39.307 に答える
1

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

于 2009-05-08T06:41:26.080 に答える
0

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

次に、y >= b AND y <= d AND x >= a AND x <=c である点について where クエリを実行します。x座標とy座標に別々にインデックスがあるとすれば、これは簡単です。(左上の原点が 0,0 であると仮定します)。

次に、結果セット内のポイント数が >= 1000 になるまで、この範囲を z ずつ増やす (または結果が大きい場合は減らす) ことができます。開始する長方形のサイズを決定するのに役立ちます。プログラムは、取得した結果に基づいて、これに合わせて自己調整することもできます。

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

于 2009-05-08T05:50:03.707 に答える
0

Google からこの投稿を見つけたのを見て、本当に本当に速い結果が必要な場合は、最速ではないと言われていることを知っています。ストアド プロシージャの形式で、少し前に使用した SQL ソリューションを追加すると思いました。a 座標に近い場所を探し、それらを距離で返します。

私はそれが誰かを助けることを願っています:)

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

注：これは、おそらく私のようにグーグルでこれを見つけた人にとって、この質問に対する最良の解決策ではないことをすでに述べました

于 2010-01-21T04:02:49.963 に答える