クイック検索のために地理データを並べ替える方法

Question

私は地理的にローカライズされたオブジェクトをいくつか持っています（私はオブジェクトごとに緯度+経度を持っています）。 私のアプリケーションは、モバイルデバイスのGPS位置から3キロメートル離れたオブジェクトを表示する必要があります。 私は数千ものオブジェクトを持っていて、広い地域（例えば、いくつかの米国の州、いくつかの小さな国など）にローカライズされています。オブジェクトのリストには、NYCとマイアミに別の場所があります。非常に近い（数メートル）物体。

現在、私のアプリケーションは反復検索を実行します。各オブジェクトについて、私はGPS位置との距離を計算し、距離が< = 3KMならば、私はそれを無視してオブジェクトを保持します。このアルゴリズムはあまり効率的ではありません。私は、より良いパフォーマンスをもたらすアルゴリズムを探しています。

地理座標を使用してオブジェクトを並べ替える方法があり、次にGPS位置の周囲にあるオブジェクトをすばやく見つける方法があるとします。

私の現在のアイデアは、「極端な点」、北/南/東/西（GPS位置から3km）の矩形を計算して検索ゾーンを制限することです。次に、このボックス内のオブジェクトの距離だけを計算します。任意の提案は;-) おかげで、

SEBを理解されるであろう

... は、私はより良い何かを行うことができると思いますが、私はアイデアを持っていません。

Answer 1

はなく、（k最近傍のように）近隣の最大数と、nearest neighbor searchように聞こえるが、最大距離閾値と。

一般的なアプローチは、オブジェクトを特別なデータ構造に入れて、検索スペースの大部分を迅速に除外できるようにすることです。 しかし、これらは通常、ユークリッド空間を念頭に置いて作成され、球面（緯度/経度）平面（ラップアラウンドの問題）では作成されません。 そのため、あなたはおそらく、あなたのオブジェクトを効率的に検索するために、次のデータ構造の1つを適用することができます前に、球の中心にデカルトシステムに相対3D座標にあなたの座標を変換する必要があると思います：

• Octree空間インデックスを言及
• kd-tree

Answer 2

他の答えは正しいですが、あなたのために必ずしも最も簡単な解決策。

私はもっと単純なものと考えています： 国、州、地域、都市、そして最終的には密集した都市のいくつかのランドマーク（オブジェクトが多い場所）でアイテムをグループ化します。

次に、モバイルアプリケーションに高度なデータ構造を実装せずに、ごくわずかなオブジェクトに限定するために、いくつかのクエリ（ある国、地域、地域などを確認する）を行うだけで済みます。

Answer 3

特殊なデータ構造なしでこれを行う方法の1つは、緯度で1度、緯度で1度、データの2つのコピーをソートするようです。バイナリ検索が緯度と経度の両方で終了するものはどれも近いです。

同様に、通常のトレパ（速い）ツリーや赤黒のツリー（低いばらつき）を使用できます。

しかし、おそらくr-treeまたはkd-treeを使用することに利点があります。私が記述したことは、おそらく新しい依存関係を避けたり、新しいデータ構造を最初からコーディングするのを避けるためだけだったのです。