algorithm - 从树叶构建一棵八叉树？

Question

设置

假设我们有一个描述空间的 3D 立方体。我们将这个立方体分割为 8 个不同的较小立方体，这些立方体描述了八分之一的空间，我们继续这样做多次。

这是一棵树，其中根是整个空间，每个子节点都是更高分割级别的子部分，达到最大分辨率。

即第一层是完整空间，接下来是 8 个子空间，接下来的 64 个子空间……最多 8^n 个子空间。

这些节点中的每一个都可以存在于两种状态之一，占用或空。空节点没有任何子节点，占用节点至少有一个非空子节点，除非它们是叶子。

问题

我得到了一个最低分辨率级别的数组(最小的子空间，即叶子)。该数组包含占用叶的离散化 (x,y,z) 坐标。换句话说，这个数组中只有被占用的叶子，没有明确给出空叶子，所以如果在这个数组中没有找到叶子，我们可以认为它是空的。

信息未按任何特定顺序给出，但每个叶子自身通过其 (x,y,z) 坐标标识其在 3D 空间中的位置。

使用这些信息，我们想要构建所描述的树。换句话说，我们想要创建一棵空叶没有 child 的八叉树。

我怎样才能有效地构建上述树？

Answer 1

一种直接的方法是将叶子一个一个地插入到最初为空的八叉树中，并在插入时创建缺失的节点。

总成本大致与叶子数量乘以(平均)树高成正比。