6

我正在开展一个学校项目，该项目涉及获取纬度/经度点并在已知地点列表中找到前五个最近点。该列表将存储在内存中，但需要注意的是我们必须选择“适当的数据结构”——也就是说，我们不能简单地将所有位置存储在一个数组中并以线性方式逐个比较距离。老师建议按美国各州对地点数据进行分组，避免计算明显距离太远的地点的距离。我想我可以做得更好。

从我的在线研究看来，R-Tree 或其变体之一可能是一个很好的解决方案。不幸的是，这句话是我对实际技术的理解，因为对于我的非学术头脑来说，文献太密集了。

  • 有人可以给我一个非常高的概述，了解使用 lat/long 数据填充 R-Tree，然后遍历树以找到给定点的 5 个最近邻居的过程是什么？

  • 此外，该项目是用 C 语言编写的，我不必为此重新发明轮子，因此，如果您使用了 R 树的现有开源 C 实现，我会对您的经验感兴趣。

更新： 这篇博文描述了一种针对区域分区空间（如 PR 四叉树）的简单搜索算法。希望对未来的读者有所帮助。

4

2 回答 2

7

您是否考虑过替代数据结构？我相信，点四叉树代替 R-tree 会更有效地满足您的需求。Spatial Index Demos提供了一些可能的数据结构列表的演示，包括 R-tree 和 Point Quadtree。希望它提供一个见解。

于 2010-05-07T08:29:24.260 回答
5

四叉树

四叉树占用一个正方形空间并将其分成四个子节点，沿 X 轴和 Y 轴的尺寸为一半。

+---+---+
|   |   |  Each square is a child
|   |   |  of the parent; when you
+---+---+  get to leaves a node has
|   |   |  a single point or a list
|   |   |  of points.
+---+---+

这个数据结构是递归的，你通过检查哪个孩子持有这个点来搜索点，直到你到达叶子。一个叶子要么有一个成员（带有 X,Y 坐标的点），要么有一个成员列表，具体取决于实现。如果填满一个节点，则将其拆分为 4 个并分配子节点。本质上，数据结构是二叉树的泛化，所以不一定是平衡的。

平衡四叉树对于您的目的可能不是必需的，留给读者作为练习 - 尝试在网络上搜索“平衡四叉树”

请注意，此数据结构无法索引可以重叠的项目，但如果您只存储点，这将不是问题。

在四叉树中查找最近的邻居

在我的脑海中，这是一个快速而肮脏的算法，用于找到离你最近的“n”个邻居。它不一定最有效，但实现起来相当简单。如果有人有更好的链接，请随时在评论或答案中发布。

  • 找到包含您的点的四叉树节点，并保留其父节点的列表。

  • 根据它们与基点的距离（即根据毕达哥拉斯定理的斜边长度）将节点中的所有点推入优先队列。根据实现，每个节点可能有一个或多个。对于优先级队列数据结构的简单实现，请查找“二进制堆”。

  • 如果任何“n”个点比边界框的边缘更远，则添加其邻居的内容。即，如果您的基点靠近边界框的边缘，则相邻树节点可能包含比边界框内的点更近的点。您需要备份树来执行此操作，这就是您需要跟踪父节点的原因。

  • 当所有“n”个最近点都比边界框的边缘更近时，您就知道不可能有您错过的邻居。因此，此框中的“n”个最近点必须是您的“n”个最近邻居。

于 2010-05-07T09:20:18.660 回答