我正在研究一个学校项目,该项目涉及获取一个纬度/长点并找到已知地点列表中的前五个最近点.该列表将存储在内存中,需要注意的是我们必须选择"适当的数据结构" - 也就是说,我们不能简单地将所有位置存储在数组中并以线性方式逐个比较距离.老师建议将美国州的地点数据分组,以防止计算显然距离太远的地方的距离.我想我可以做得更好.
从我在网上的研究看来,似乎R-Tree或其变体之一可能是一个简洁的解决方案.不幸的是,这句话是我理解实际技术的原因,因为文学对于我的非学术头脑来说太过密集了.
有人能给我一个非常高的概述,用于填充具有纬度/长度数据的R树的过程是什么,然后遍历树以找到给定点的那5个最近邻居？
此外,该项目是在C中,我不必重新发明这个,所以如果你使用了R Tree的现有开源C实现,我会对你的经历感兴趣.
更新: 此博客文章描述了区域分区空间(如PR四叉树)的简单搜索算法.希望有助于未来的读者.
您是否考虑过其他数据结构？我相信,Point Quadtree不是R-tree,而是更有效地满足您的需求.Spatial Index Demos为可能的数据结构列表提供了一些演示,包括R-tree和Point Quadtree.希望它能给出洞察力.
四叉树
四叉树占用一个正方形的空间,并将其划分为四个子节点,沿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"个最近邻居.