代码之家 › 专栏 › 技术社区 › roufamatic RichardJohnn

R树50000英尺概述?

r-tree gis c

roufamatic RichardJohnn · 技术社区 · 16 年前

我正在做一个学校项目,包括在一个已知的地点列表中找出最接近的五个点。该列表将存储在内存中,但需要注意的是,我们必须选择“适当的数据结构”——也就是说,我们不能简单地将所有位置存储在一个数组中,并以线性方式逐个比较距离。老师建议按美国州对地点数据进行分组,以防止计算明显太远的地点的距离。我想我能做得更好。

从我在网上的研究来看,r树或其变体可能是一个很好的解决方案。不幸的是,这句话是我对实际技巧的理解所得到的,因为对于我的非学术头脑来说,文献实在太密集了。

有人能给我一个很高的概述吗?用长/长数据填充一个r树,然后遍历该树,找到给定点的5个最近邻。
另外,这个项目是用C语言编写的,我不需要在这方面重新设计,所以如果您使用了R树的现有开源C实现,我会对您的经验感兴趣。

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

2 回复 | 直到 13 年前

tafa 16 年前

你考虑过其他的数据结构吗? 我相信,点四叉树代替r-树会更有效地满足你的需要。 Spatial Index Demos 为可能的数据结构列表(包括R树和点四叉树)提供一些演示。希望它能给我们一个启示。

ConcernedOfTunbridgeWells 16 年前

四叉树

四叉树取一个正方形的空间,并将其分成四个子空间,其中一半的维度沿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个并分配子节点。从本质上讲,数据结构是二叉树的泛化,因此不一定是平衡的。

平衡四叉树对于你的目的来说可能不是必需的,它留给读者作为一个练习-尝试在web上搜索“平衡四叉树”

请注意,此数据结构不能索引可以重叠的项,但如果您只存储点,这不会是一个问题。

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

在我的头顶上,有一个快速而肮脏的算法,可以找到离你点最近的“n”个邻居。它不一定是最优的效率,但是实现起来相当简单。如果有人有一个更好的链接,请随时在评论或回答中发布。

找到包含你的观点,列个清单父母。
按中的所有点基于他们离你的基点的距离 (即斜边的长度根据毕达哥拉斯定理)。依靠在实施过程中每个节点一个或多个。对于一个简单的优先级队列的实现数据结构,查找二进制堆。
如果任何“n”点离边界框的边缘更远,请添加其相邻点的内容。即,如果基点靠近边界框的边缘,则相邻的树节点可能包含比边界框中找到的点更近的点。为此,需要备份树,这就是为什么需要跟踪父节点的原因。
当所有“n”最近的点都比边界框的边更近时,您知道不可能有您错过的邻居。因此,此框中的“n”最近点必须是您的“n”最近邻居。