我如何儲存GPS座標，以便輕鬆找到哪些靠近彼此？

假設您有地球上每家餐廳的gps座標列表，並且您有當前位置的座標。你想找到最近的n家餐館。顯然，它可能需要永久搜索未排序的列表，他們需要以某種方式進行索引。我如何儲存GPS座標，以便輕鬆找到哪些靠近彼此？

他們應該如何存儲/索引以便能夠輕鬆找到最接近的？我正在考慮用緯度和經度的雙字典，或者某種類型的雙重字典，但我確信之前已經解決了這個問題，而且我想知道是否有「最佳」解決方案。

來源

2013-10-28 NathanTempelman

我相信KD-Tree是這些查詢的一般方法。

Wikipedia entry on KD-Tree.

Nearest neighbor search info on Wikipedia.

Previous question on SO about NNS.

實現：

PCL

KdTree in Java

來源

2013-10-28 20:13:44 Justin

這看起來很有希望，雖然我想知道是否沒有更好的方法來做到這一點，看到的位置不會分佈在整個3d空間，而是在球體的2D表面。思考？ – NathanTempelman

@NathanTempelman那麼，從我所瞭解的KD-Trees來看，它們的表現更好，尺寸更小。但我不期待在NNS領域，所以可能會有更好的數據結構。 – Justin

@NathanTempelman我已經添加了一個新的鏈接到SO上的前一個NNS問題。 – Justin

你可以使用四叉樹，特別是quadkey。它可以非常有效，因爲您可以更改網格大小。還有許多不同的四鍵，例如morton曲線，hilbert曲線，h-tree，moore曲線。

來源

2013-10-28 20:26:50 Bytemain

如果您正在尋找Java或Android中的KDTree實現，請參閱我對類似SO問題following this link的回答。我在同樣的SO問題中也發佈了2D實現，但如果點分佈在很大範圍的緯度上，則這可能會返回錯誤的結果。（經度的絕對距離轉換爲整個可能的東西距離，取決於緯度，以米爲單位）。我仍然使用2D算法，因爲我只對小於1000米距離的航點感興趣。到目前爲止，2D版本運行良好。

來源

2013-10-28 20:34:08 user2808624

我如何儲存GPS座標，以便輕鬆找到哪些靠近彼此？

回答

相關問題