所以,我正在实施一个KD-Tree http://en.wikipedia.org/wiki/Kd-tree进行最近邻搜索。我已经构建了树部分,但我认为我没有完全理解搜索部分。
关于遍历树来搜索邻居,维基百科文章如下:
Starting with the root node, the algorithm moves down the tree recursively, in the same
way that it would if the search point were being inserted (i.e. it goes right or left
depending on whether the point is greater or less than the current node in the split
dimension).
“大于或小于吐出维度中的当前节点是什么意思?我们是根据与查询的距离来比较点,还是根据分割维度来比较点?”
另外,有人可以解释一下有关超空间和超平面的部分吗?我觉得我明白了,但由于我不确定我想要更多解释。
Thanks!
每个节点沿一个轴将空间分成 2 个半空间。您可以查看所讨论的点相对于分割平面的位置,以决定要向下移动树的哪一侧。例如,如果您的点是 (4,7,12) 并且您有一个在 9 处切割 y 轴的分割平面,您会将 7 与 9 进行比较,并决定沿着该点的左侧(小于)向下移动首先是k-d树。找到左侧的最近邻居后,检查它是否小于 2(到分割平面的距离:9-7)。如果它比分割平面更近,则根本不需要遍历另一半树。这就是为什么它工作得这么好,大多数时候你只需要遍历一棵子树。
希望有帮助。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)