Have a Question?

八叉树 | Octree

You are here:

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

Add a Comment

您的电子邮箱地址不会被公开。 必填项已用*标注

Table of Contents