从树叶构建一棵八叉树？
Construct an oct tree from the leaves?
设置
假设我们有一个描述 space 的 3D 立方体。我们将这个立方体细分为 8 个不同的小立方体，这些立方体描述了 space 的八分之一，然后我们继续这样做几次。
这是一棵树，其中的根是完整的 space，每个 child 节点都是更高细分级别的子部分，达到最大分辨率。
即第一级是完整的 space，接下来是 8 个子 spaces，接下来的 64 个子 spaces... 最多 8^n 个子spaces.
这些节点中的每一个都可以存在于两种状态之一，占用或空。空节点没有任何 children，占用节点至少有一个非空 child 除非它们是叶子。
问题
我得到了一个最低分辨率级别的数组（最小的子spaces，即叶子）。该数组包含占用叶的离散化 (x,y,z) 坐标。换句话说，这个数组中只有被占用的叶子，没有明确给出空叶子，所以如果在这个数组中没有找到叶子，我们可以认为它是空的。
信息未按任何特定顺序给出，但每个叶子自身通过其 (x,y,z) 坐标识别其在 3D space 中的位置。
使用这些信息，我们要构建所描述的树。换句话说，我们要创建一个 oct-tree 空叶没有 children.
我怎样才能有效地构建上述树？
一种直接的方法是将叶子一个接一个地插入到最初为空的八叉树中，并在插入时创建缺失的节点。
总成本大致与树叶数量乘以（平均）树高成正比。
设置
假设我们有一个描述 space 的 3D 立方体。我们将这个立方体细分为 8 个不同的小立方体，这些立方体描述了 space 的八分之一，然后我们继续这样做几次。
这是一棵树，其中的根是完整的 space，每个 child 节点都是更高细分级别的子部分，达到最大分辨率。
即第一级是完整的 space，接下来是 8 个子 spaces，接下来的 64 个子 spaces... 最多 8^n 个子spaces.
这些节点中的每一个都可以存在于两种状态之一，占用或空。空节点没有任何 children，占用节点至少有一个非空 child 除非它们是叶子。
问题
我得到了一个最低分辨率级别的数组（最小的子spaces，即叶子）。该数组包含占用叶的离散化 (x,y,z) 坐标。换句话说，这个数组中只有被占用的叶子，没有明确给出空叶子，所以如果在这个数组中没有找到叶子，我们可以认为它是空的。
信息未按任何特定顺序给出，但每个叶子自身通过其 (x,y,z) 坐标识别其在 3D space 中的位置。
使用这些信息，我们要构建所描述的树。换句话说，我们要创建一个 oct-tree 空叶没有 children.
我怎样才能有效地构建上述树？
一种直接的方法是将叶子一个接一个地插入到最初为空的八叉树中，并在插入时创建缺失的节点。
总成本大致与树叶数量乘以（平均）树高成正比。