如何实现纬度和经度值的邻近搜索？

我的应用程序（基于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

如何实现纬度和经度值的邻近搜索？

回答

相关问题