2

一連の場所とその X、Y 座標があるとします。

L1(X1, Y1) L2(X2, Y2) L3(X3, Y3) ... L10000(X10000, Y10000)

そして、2 つの場所の間の距離を返す関数があります: distance(L1, L2) = 5 マイル

特定の場所について、100 マイル以内にあるすべての場所を見つけるにはどうすればよいですか? または、より簡単な場合は、最も近い 50 の場所

セットアップは、場所とその郵便番号の SQL Server テーブルです。この関数は 2 つの郵便番号を受け取り、それぞれの緯度と経度を調べて距離を返します。結果は頻繁に変更されないため、結果をキャッシュできます。

4

4 に答える 4

1

すべての位置をメモリに格納できる場合は、Kd ツリーを使用します (lat/lon/id)。別の質問に対する私の回答を参照してください Kd-trees により、効率的な最近傍検索と k 最近傍検索が可能になります。平均時間の複雑さは O(log n) です。すべての場所をメモリに保存できない場合は、データベースが空間インデックスをサポートしているかどうかを確認してください。

于 2012-11-03T21:40:05.057 に答える
0

それらをループして、100 マイル離れたすべての場所を単純に破棄する必要があり、O(N) になります。

SELECT Location FROM Table WHERE (POWER(Location.X-Selected.X,2) + POWER(Location.Y-Selected.Y,2)) < POWER(Distance,2)

場所は、場所のエントリになります。選択された都市は、X と Y をそれぞれの場所に置き換えるだけです。

私の SQL は少しさびているので、間違いがあれば大声で言ってください。修正します。

于 2012-11-03T16:20:46.810 に答える
0

テーブル構造について多くの情報を提供していただけないため、正確な回答を提供することは困難です。ただし、ターゲットの郵便番号がパラメーター P1 としてクエリに提供されているとします。さらに、テーブル T に id、name、および zip フィールドがあるとします。100 マイル以内のすべての場所を見つけるには、次を使用できます

select id, name, zip, distance(zip,P1) as distance
from T
where distance(zip,P1) <= 100

トップ 50 クエリの場合

select top 50 id, name, zip, distance(zip,P1) as distance
from T
order by distance(zip,P1)

より良い解決策は、各場所の緯度と経度を計算してデータベースに保存することです。関数で緯度/経度のルックアップをスキップして、速度を劇的に向上させることができます。既存の関数で大圏距離を計算するコードが既にあると仮定します。

于 2012-11-03T16:22:06.357 に答える
0

One solution is to write a function like the following that is generic and will allow for cutstomization:

Location[] findLocationsWithinDist(Location L1, Integer dist, LocationsList locations){
    LocationList results;
    foreach(location : locations){
        if(dist(L1, location) <= dist)
            results.add(location);
    }
    return results;
}

You could have a data structure that stores each location with a list of locations within a certain range. Then, you would need to update this data structure everytime you added a new location. That seems like a separate problem though.

于 2012-11-03T16:23:22.617 に答える