八叉树与空间搜索

Posted by Ada on November 1, 2018

八叉树与空间搜索

最近正好在看。就谈一下数据结构。

八叉树特别适合进行空间划分。在需要邻近点信息做参考时,利用八叉树做搜索会非常高效。

八叉树必备的元素:

  • 尺寸:一般就是自己限定的空间(有的地方也叫bounding box 包围盒)大小。
  • 深度:八叉树划分的层级
  • 源点:一般就是(xmin,ymin,zmin)了
  • 节点:就像下图划分的一个一个的小立方体(有的会叫voxel,或者cell)

这个带颜色的示意图很清楚的解释了八叉树的结构。每一个小立方体(voxel)都是一个子节点。只子节点可以被继续划分。

octree.png

构建八叉树

因为最近用PCL中的八叉树比较多,对于空间搜索邻域划分,也是常常用到八叉树的。

Functions for serialization and deserialization enable to efficiently encode the octree structure into a binary format.

构建的方式最通用的莫过于线性八叉树了。具体做法是对每个节点进行二进制编码。

这样做的好处是:快速定位和搜索


引申: 线性编码构建二叉树

不同维度的编码具有独立性。先简单的以二叉树为例:

binary_encode.jpg

首先是树状:

  • 根节点编码为0000,左节点与根节点相同,所以是0000.
  • 若右节点的高度为height,所以将该节点的第(height -1)位置为1. 下图的例子也就是把第三位置换1.之后就是1000
  • 沿着左右子树采取上面的规则进行编码。

如果是一维:

对于待搜索的数据,比如7.1。二进制编码就是(7.1/10)(2^4)=(0.71*16) =binary(11) = 1011.

线性八叉树的构建和应用

而对于三维空间的八叉树的建树。原理是一样的。对x,y, z 的每个维度都进行编码。

最后不同的结点都会有自己特定的一串二进制编码:

octree_encode.jpg

octree_encode2.jpg

采取这样的方式以后定位和搜索就会变得非常高效。

定位会定位到叶子结点,空间想象一下的话就是一个大立方体中的小立方体(想象一下魔方)。

而每一个叶节点(小立方体voxel)中存放的就是很多点了。

在获取的时候,可以通过反序列化的方式。获取点的位置和索引。

在获取临近点的信息以后,对于图形三维中的很多计算来说就很有价值了。比如滤波,法线计算等等。进而影响到数据量的压缩,渲染等等。

参考文献:

Frisken S F, Perry R N. Simple and efficient traversal methods for quadtrees and octrees[J]. Journal of Graphics Tools, 2002, 7(3): 1-11.


本站总访问量: