c - R 树 50,000 英尺概览？

Question

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

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

• 谁能给我一个非常全面的概述，说明用经纬度数据填充 R 树，然后遍历树以找到给定点的 5 个最近邻居的过程是什么？

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

更新: This blog post描述了区域分区空间(如 PR 四叉树)的直接搜索算法。希望对 future 的读者有所帮助。

Answer 1

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