クエリポイントからの地理的距離によって位置を効率的に並べる

Question

私は効率的に、おそらくO（log（n））、その地理的座標が与えられたクエリー位置に最も近い特定の数の場所を見つけようとします緯度、経度）。

クエリポイントはあらかじめわかっていませんが、クエリを最適化するために他の場所を事前に整理できます。

このような方法がありますか、またはすべてのピアのリストを注文してトリミングする必要がありますか？

Answer 1

あなたのサーフェスが三角不等式を満たしている場合、つまり真理値空間である場合、空間インデックスを並べ替える最適なアルゴリズムは、空間塗りつぶし曲線またはモンスター曲線です。 2次元問題を1次元問題に還元し、空間の離散化と解法を行う。類似した場所の検索は、O（log（n））のようなものです。あなたはニック空間インデックスヒルベルト曲線quadtreeブログで良い記事を見つけることができます。私は、単調な単調なグレイコードも見てみることをお勧めします。私は、4方向にヒルベルト曲線を含むPHP実装とmoore曲線を書いています。