1

以下のコード セグメントが何をしているのか理解できません。これは、Henrik Wann Jensen 著『フォトン マッピングを使用したリアルな画像合成』という本から引用されています。それがやろうとしていること（またはコード内の場所を考えてやるべきだと思うこと）は、開始インデックスと終了インデックスの間の配列で中央値インデックスを計算することだと思います。

// 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 ツリーを構築する再帰的な各ステップで、(ある次元に関して) 中間点が選択され、新しい kd ツリーのルートになります。

このコードは、開始インデックスと終了インデックスの間の中央値インデックスを計算することになっていると思いますが、正しければ、なぜこの中央値インデックスが奇妙な方法で計算されるのかわかりません。

どんな助けや洞察もいただければ幸いです、ありがとう！

編集: Vaughn Cato のおかげで、この方法で中央値インデックスを計算する必要があることがわかりました。もともと、(end - start)/2 + start を実行できない理由について、私は混乱していました。このコードの目的は、ポイントのリストを取得し、それをヒープのようなデータ構造 (配列内のバイナリ ツリー全体) に格納できる完全でバランスの取れた kd ツリーに変換することです。単純な方法で中央値インデックスを計算しても、配列にフラット化できるツリーが得られるとは限りません。

今、私は誰かがどうやってそれを思いついたのか混乱しています. 誰かが私を説明したり、派生の方向に向けたりすることはできますか?

4

1 に答える 1

1

結果の中央値は、開始または終了から常に 2 の累乗です。ツリーを分割するために中央値が使用されると仮定すると、これはサイズが 2 のべき乗であるブランチにつながります。つまり、各ノードには 2 つまたはゼロの子が含まれます。これにより、ツリーの葉をたどる際の効率が向上する可能性があります。

于 2011-12-01T06:47:12.787 に答える