R树50,000英尺的概述？

我正在参与一个学校项目，该项目涉及到一个经纬度点，并在已知的地点列表中找到前五个最接近的点。该列表将被存储在内存中，但必须选择一个“合适的数据结构” - 也就是说，我们不能简单地将所有位置存储在一个数组中，并以线性方式逐一比较距离。老师建议将美国州的地点数据分组，以防止计算距离显然太远的地方的距离。我想我可以做得更好。R树50,000英尺的概述？

从我的在线研究看来，R-Tree或其变种之一似乎是一个很好的解决方案。不幸的是，就我理解实际技术而言，这句话就像我已经掌握的那样，因为文献对于我的非学术性头脑来说太简单了。

有人可以给我什么样的过程是填入一R-树与纬度/经度数据，然后遍历树找到一个给定的点的那些5个最近的邻居一个非常高的概述？
此外，该项目是在C中，我不必在此重新发明轮子，所以如果您已经使用R树的现有开源C实现，我会对您的体验感兴趣。

UPDATE：This blog post描述了一个简单的搜索算法用于区域划分空间（如PR四叉树）。希望对未来的读者有所帮助。

来源

2010-05-07 roufamatic

看看http://www.rtreeportal.org/，有一些指向一些实现。请注意，我还没有看到一个不是垃圾的C实现。 – avakar 2010-05-07 08:32:52

废话低效，或废话，因为在不会编译？前者适合我的目的。 :-) – roufamatic 2010-05-07 15:35:11

废话如“不检查malloc和其他类似违规的结果”。我不知道作业是否合适。 :) – avakar 2010-05-07 17:04:42

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

来源

2010-05-07 08:29:24 tafa

+1 - 如果你只需要存储点，那么四叉树就可以完成这项工作，而且实现起来相当简单。 R-Trees允许重叠的边界框用于任意形状，而OP似乎并不需要。 – ConcernedOfTunbridgeWells 2010-05-07 08:52:29

空间索引演示确实帮助我了解这些东西，谢谢！ – roufamatic 2010-05-08 06:32:41

据我所知，一个rtree索引可以直接回答k-最近邻居查询，而四叉树则不能。既然这是OP的既定目的，难道不是更直接吗？ – 2013-09-02 10:40:26

四树

四叉树需要的空间中的正方形，并将其与沿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-07 09:20:18 ConcernedOfTunbridgeWells

R树50,000英尺的概述？

回答

相关问题