c++ - 需要帮助找出 kd-tree 实现中的 C++ 代码段

Question

我无法弄清楚下面的代码段在做什么。它取自 Henrik Wann Jensen 的Realistic Image Synthesis Using Photon Mapping一书。我认为它正在尝试做的事情(或者我认为鉴于它在代码中的位置，它应该尝试做的事情)是计算某个开始索引和结束索引之间的数组中的中值索引。

// inputs are an array, start and end indices that define a subset of the array
int median = 1;
while((4*median) <= (end-start+1))
  median += median;

if ((3*median) <= (end - start + 1)) {
   median += median;
   median += start - 1;
} else
  median = end - median + 1

有关更多上下文，代码来自在给定 3D 点列表的情况下构建 kd 树数据结构的部分。在构建 kd 树的每个递归步骤中，选择中点(相对于某个维度)作为新 kd 树的根。

我认为这段代码应该计算一些开始和结束索引之间的中值索引，但如果我是正确的，那么我无法弄清楚为什么以这种奇怪的方式计算这个中值索引。

任何帮助或见解将不胜感激，谢谢!

编辑:感谢 Vaughn Cato，我现在明白有必要以这种方式计算中值指数。最初我对为什么你不能只做 (end - start)/2 + start 感到困惑。这段代码的目标是获取点列表并将其转换为完整的平衡 kd 树，该树可以存储在类似堆的数据结构中(数组中的整个二叉树)。以天真的方式计算中值索引不一定能让你得到一棵可以展平成数组的树。

现在我很困惑有人是怎么想出来的。任何人都可以解释或指出推导的方向吗？

Answer 1

生成的中值始终是距离起点或终点的 2 的幂。假设使用中值来划分树，这将导致分支大小为 2 的幂，这意味着每个节点将有两个或零个子节点。这可以提高遍历树叶的效率。