1

我的应用程序（基于 Qt 的移动应用程序）以下列格式从服务器获取数据：纬度、经度、描述。

我需要将此数据存储在数据结构中，以便以后快速检索。现在我有一张地图，当用户点击地图中的一个点时，我得到该点的纬度，经度。使用这两个值，我需要快速扫描我的数据结构并检索相关描述。我的问题是..我在地图上单击时得到的纬度和经度是一个近似值（它是一个触摸设备，所以我永远不会得到确切的纬度 + 经度），所以如果我对数据结构进行线性搜索，我永远找不到这些价值观。此外，如果数据太多，线性搜索会很慢。

  1. 我应该使用什么数据结构来存储 lat+long+description（我想到了一个哈希......但我不知道如何组合 long+lat 来形成一个键）

  2. 如何对数据结构进行近似搜索？

谢谢！

4

2 回答 2

1

由于您的问题仅包含二维，我们可以使用二叉树。每个叶子最多可以有“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
}

动态生成二叉树并在插入更多点时划分节点。如果节点的高度是偶数，则根据纬度划分它，否则根据经度划分。

搜索输入点时，找到相关的叶节点，该叶节点中的所有点都将是离输入点最近的点。

这是一个流行的问题 - http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

于 2011-03-25T11:31:41.770 回答
1

您正在寻找的数据结构是kd-tree。如果你真的想要散列，并且一些小错误是可以接受的，你可以查看这篇论文（pdf），它描述了一种基于距离的散列方法。

您将不得不尝试哪一种更适合您。我在那篇论文中实现了算法，但它并不能很好地解决我的问题（可能是因为我的数据点分布不是很均匀）。这在您的情况下可能会有所不同，因此您将不得不尝试。

于 2011-03-24T12:06:46.470 回答