從查詢點按地理距離有效排序位置

Question

我試圖找到一種有效的方法，可能O（log（n））在給定地理座標的情況下查找給定數量的最靠近查詢位置的位置（ lat，lon）。

查詢點未預先知道，但我可以提前組織其他位置以優化查詢。

有沒有這樣的方法，還是必須訂購和裁剪所有同行的列表？

Answer 1

如果您的表面滿足三角形不等式，即是一個euklidian空間，那麼對空間索引重新排序的最佳算法是空間填充曲線或怪物曲線。它將二維問題簡化爲一維問題，並離散化並解決空間的適應問題。類似位置的查找類似於O（log（n））。你可以在尼克空間索引希爾伯特曲線四叉樹博客中找到一篇好文章。我也建議看看n元單調的灰色代碼。我寫了一個php實現，包括4個方向的希爾伯特曲線和摩爾曲線。