如何實現緯度和經度值的鄰近搜索？

我的應用程序（基於Qt的移動應用程序）以以下格式從服務器獲取數據：緯度，經度，說明。如何實現緯度和經度值的鄰近搜索？

我需要將此數據存儲在數據結構中以便稍後快速檢索。現在我有一張地圖，當用戶點擊地圖上的一個點時，我得到了該點的緯度，經度。使用這兩個值我需要快速掃描我的數據結構並檢索相關的描述。我的問題是...我在地圖上點擊的緯度和經度是一個近似值（它是一個觸摸設備，所以我從來沒有得到確切的經緯度+長），所以如果我對數據結構進行線性搜索，我從來沒有找到這些值。此外，如果數據太多，線性搜索將非常緩慢。

數據結構，我應該使用什麼樣的存儲緯度+長+說明書（哈希來我mind..but我不知道怎麼長+緯度相結合，形成一個鍵）
我如何對數據結構進行近似搜索？

謝謝！

來源

2011-03-24 maxpayne

您正在查找的數據結構是kd-tree。如果你真的想要哈希，並且可以接受一些小錯誤，你可以查看this paper(pdf)，它描述了一種基於距離的哈希方法。

你將不得不嘗試哪一個更適合你。我在該論文中實現了該算法，但對於我的問題並不適用（可能是因爲我的數據點分佈不均勻）。這可能與你的情況有所不同，所以你必須嘗試。

來源

2011-03-24 12:06:46

由於您的問題只包含2個維度，所以我們可以使用二叉樹。每個葉子最多可以有「N」個點（以緯度，經度爲點）。只有葉節點有點。點的

數據類型

class Point 
{ 
    float Latitude; 
    float Longitude; 
    string Description; 
}

內部節點（非葉節點）的葉節點的

class Node 
{ 
    Float MaxLatitude; 
    Float MinLatitude; 
    Float MaxLongitude; 
    Float MinLongitude; 
}

數據類型

class LeafNode 
{ 
    Point points[K]; // Array of points 
}

動態生成二進制樹和分割的數據類型節點插入更多點。如果節點的高度均勻，則根據緯度e對其進行分割根據經度劃分。

當搜索輸入點時，找到相關的葉節點，並且該葉節點中的所有點將是距輸入點最近的點。

這是一個受歡迎的問題 - http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

來源

2011-03-25 11:31:41 siddardha

如何實現緯度和經度值的鄰近搜索？

回答

相關問題