1

我无法弄清楚下面的代码段在做什么。它取自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-tree 数据结构的部分。在构建 kd-tree 的每个递归步骤中，选择中点（相对于某个维度）作为新 kd-tree 的根。

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

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

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

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

4

1 回答 1

1

产生的中值始终是距离起点或终点的 2 次方。假设中值用于划分树，这将导致分支的大小为 2 的幂，这意味着每个节点将有两个或零个子节点。这可以在遍历树的叶子时提供一些效率。

于 2011-12-01T06:47:12.787 回答