八叉树 | Octree

1 定义

八叉树是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。每一个八叉树的节点代表一定范围内的空间。
八叉树的节点通常有三种类型：

• 灰节点： 它对应的立方体部分的为查找元素所占据；
• 白节点： 它对应的立方体没有查找元素的内容；
• 黑节点： 它对应的立方体全部为查找元素所占据。

2 作用

八叉树通常用来存储三维点云，每个节点可以保存一定的点云信息方便快速在空间中进行检索。
基于八叉树的搜索方式有：Neighbors within Voxel Search (体素近邻搜索), K Nearest Neighbor Search (K近邻搜索) 以及 Neighbors within Radius Search (半径近邻搜索)。具体实现在常见的 PCL 等点云库中均有实现。

参考文献

[1] https://zh.wikipedia.org/wiki/%E5%85%AB%E5%8F%89%E6%A0%91
[2] https://zhuanlan.zhihu.com/p/534943654
[3] https://pcl.readthedocs.io/projects/tutorials/en/latest/octree.html