如何對地理數據進行排序以便快速搜索

我有一些地理定位的對象（每個對象都有緯度+經度）。我的應用程序需要顯示圍繞移動設備的GPS位置3公里的物體。我有幾千個物體，它們在大面積的地方（例如，幾個美國州，幾個小國），意思是在我的物品清單中我可以有一個位於紐約，另一個位於邁阿密，但我也可以非常接近的物體（幾米）。如何對地理數據進行排序以便快速搜索

目前，我的應用程序執行迭代搜索。對於每個對象，我計算與GPS位置的距離，如果距離爲< = 3KM，則我保留該對象，否則我忽略它。這個算法效率不高，我正在尋找一種能夠提供更好性能的算法。

我想有一種方法可以使用地理座標對我的對象進行排序，然後更快找到位於GPS位置周圍的對象。

我目前的想法只是用「極端點」，北/南/東/西（從GPS位置3公里）計算矩形來限制搜索區域。接下來，我將只計算這個盒子裏面的物體的距離。我認爲更好的東西可以做，但我沒有這個想法...

任何提議可以理解;-) 謝謝，

SEB。

來源

2012-07-12 sebastien

聽起來nearest neighbor search，但不具有最大數目鄰居的（如在KNN），但具有最大距離閾值。

一種常見的方法是將對象放入特殊數據結構中，以便快速排除大部分搜索空間。但是，這些通常是在考慮歐幾里德空間的情況下制定的，而不是球形（緯度/經度）平面（環繞式問題）。因此，你可能需要將座標轉換爲三維座標笛卡爾相對於球體的中心繫統，您可以將以下數據結構的一個前爲對象有效地搜索：

來源

2012-07-12 20:43:28 moooeeeep

我認爲直接在lat/lon中的四叉樹適用於幾乎所有的情況。如果經度爲0-360，那麼我會改變它，以便數據中的「接縫」位於日期線上而不是零（因此，所有問題將只在北極，南極和太平洋）。 – 2012-07-13 07:16:29

非常感謝，我將學習八叉樹和kd-tree。如果我的小腦袋不太複雜，它可能會用它做點什麼！ – sebastien 2012-07-13 18:40:51

其他的答案提的空間索引是正確的，但不一定適合你的最簡單的解決方案。

我會考慮一些更簡單的方法：按國家，然後按州，地區，城市，最後 - 在密集城市（您有很多物體）的幾個地標進行分組。

然後，您只需執行一些查詢（檢查我處於哪個國家/地區，哪個州/地區等），即可將自己限制爲一小組對象，而無需在移動應用程序中實施高級數據結構。

來源

2012-07-12 20:47:18

如果我靠近地區邊界怎麼辦？ – smocking 2012-07-12 21:02:06

@smocking：全部搜索。這可能很少見，不會太慢。 – 2012-07-12 21:44:01

沒有專門的數據結構這樣做的一種方法似乎是排序數據的兩個副本 - 一次是經度，一次是緯度。任何二進制搜索關閉拉特和長，是接近。

同樣，您可以使用通常的樹木（快速）或紅黑樹（低變異性）。

但是使用r-tree或kd-tree可能有好處。我所描述的可能只是爲了避免採用新的依賴關係或避免從頭開始編寫新的數據結構。

來源

2012-07-12 21:28:30 user1277476

如何對地理數據進行排序以便快速搜索

回答

相關問題