彻底理解quadtree四叉树、Octree八叉树 —— 点云的空间划分的标准做法

1.参考文章：

（1）https://www.zhihu.com/question/25111128

这里面的第一个回答，有一幅图：

只要理解的四叉树的构建，对于八叉树的构建原理类比方法完全一样：对于二维平面内的随机分布的这些点，如何将它们用某种数据结构组织起来？四叉树是一种非常巧妙的方法，类似于一维序列中的二分法，这里就是直到分割每个方块里面只剩下1个点为止（当然，可能它的兄弟方块是没有点的，这一点很自然）。这里我说一下上面这幅图的顺序，首先，它的颜色对应关系很清楚；其次，你看，其实树的子结点从左往右，对应的是正方形从3-4-1-2象限的顺序！

最后：

还有一个需要思考清楚的是，如何从树恢复成点云？以及，如何从树展平成序列？

答：师兄的论文里面figure5 和 figure6 绘制了 八叉树到byte（8bit）序列，以及从byte序列构建回到八叉树的示意图，很清楚！至于如何从点云转换到八叉树，上面那个图那也很清楚了。而从八叉树到点云的话，我觉得除非把点云的偏移存储到树的节点中，不然的会就只能把每个节点当作体素处理，然后从八叉树恢复回到点云就只能把点云放到这个体素的中心位置。——当然，虽然这里存在偏移，可以算是有一点点的损失，不过我们当它是lossless的应该也没问题，——如果完全无损的话，也可以，就是把偏移信息额外存储起来罢了，这个信息不用处理，只要在reconstruction的过程中加回去即可。

2.理解总结：

如上，nice