需要幫助您計算出kd樹實現

Question

我有麻煩搞清楚什麼下面的代碼段是做C++代碼段。它是從書真實感圖形由亨利克·沃·詹森使用光子映射拍攝。我認爲它試圖做的事情（或者我認爲它應該試圖做的事情是在代碼中放置它的位置）是計算某個開始和結束索引之間數組中的中值索引。

// 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 

更多情況下，代碼來自於給定構建三維點列表的kd樹數據結構的部分。在構建kd樹的每個遞歸步驟中，中間點（相對於某個維度）被選擇爲新kd樹的根。

我覺得這個代碼應該計算一些起點和終點指數的平均指數，但如果我是正確的，那麼我想不通爲什麼這個平均指數以這種奇怪的方式來計算。

任何幫助或洞察力，將不勝感激，謝謝！

編輯：感謝Vaughn Cato我現在看到有必要以這種方式計算中值索引。起初我很困惑，爲什麼你不能做（結束 - 開始）/ 2 +開始。此代碼的目標是獲取點列表並將其轉換爲完全平衡的kd樹，該樹可以像數據結構（數組中的整個二叉樹）一樣存儲在堆中。以天真的方式計算中位數索引不一定會爲您提供一棵樹，您可以將其平鋪到陣列中。

現在我很困惑，怎麼有人想出了這一點。任何人都可以解釋或指出我的發展方向嗎？

Answer 1

得到的中值始終爲二的冪從開始或結束了。假設中值用於分割樹，這將導致分支的大小爲2的冪，這意味着每個節點將有兩個或零個子元素。這可以提供穿越樹葉的一些效率。