Have a Question?

K-D 树 (K Dimensional Tree)

You are here:

1 定义

在计算机科学里,K-D 树( k-维树的缩写)是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索)。k-d树是空间二分树(Binary space partitioning)的一种特殊情况。K-D 树中的特征是 n 维向量:\{x_1, x_2, \cdots, x_n\}

K-D 树通常记录了如下信息:

2 创建

以一个二维点云创建过程举例:假设我们要处理的二维 (x, y) 点云集合为:(30,40), (5,25), (10,12), (70,70), (50,30), (35,45)

1)按照 x 维进行划分,找到中位数节点 (30,40),x 坐标比 30 小的放入左子树集合 (5,25), (10,12),大的放入右子树集合 (70,70), (50,30), (35,45)
2)对左右子树集合,按照 y 维度进行划分:
左子树集合,中位数节点为 (5,25),然后重复上面的划分步骤。
右子树集合,中位数节点为 (70,70),然后重复上面的划分步骤。
3)因为只有2个维度,依次迭代 x 和 y 维度即可创建。
划分的步骤示意图如下:

最终建好的 K-D 树如下:

伪代码如下:

参考文献

[1] https://zh.wikipedia.org/wiki/K-d%E6%A0%91
[2] https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/kdtrees.pdf
[3] https://www.joinquant.com/view/community/detail/c2c41c79657cebf8cd871b44ce4f5d97 (带图文方式详细演示)

Add a Comment

Your email address will not be published.

Table of Contents