重新排列四叉樹/八叉樹的數據

我正在執行體素八叉樹raycaster，唯一剩下的就是重新排列數據以填充八叉樹的葉級別，以便可以對數據進行平均以構建樹的較低級別。

爲了方便起見，我最初在2D（四叉樹）中思考問題。我已經按照圖中左側的順序排列了數據，而且我現在可以重新排列它，如右圖所示。例子是8x8。

Current

但是，我發現我需要訂購在節點順序的數據，如下面的圖中：

Wanted

換句話說，我想從一個陣列到去其中數據對應於如下索引：

[0 1 2 3 4 5 6 7 8 9 ... 63]

將數據按以下順序排列：

[0 1 4 5 16 17 20 21 2 3 ... 63]

對於8x8四叉樹示例。

我不知道該怎麼做。我的主要問題是處理任意樹大小。如果我事先知道尺寸，我可能會硬編碼一組嵌套循環，但它顯然不是一個很好或優雅的解決方案。我在想可能有一個遞歸的方式來實現它。

這是我用圖片一中描述的方式排序數據的快速和骯髒的草圖。它基本上是通過跟蹤原始數據中的四個位置，然後在新數組被填充時向前移動這些位置。據我所知，這工作正常，但不能擴展到我的需要。

int w = 8; 
    int[] before = new int[w*w*w]; 
    int[] after = new int[w*w*w]; 
    for (int i=0; i<w*w*w; i++) { 
    before[i] = i; 
    } 
    int toFill = 0; 
    int front = 0; 
    int back = w; 
    int frontZ = w*w; 
    int backZ = w*w + w; 
    do { 
    for (int i=0; i<w/2; i++) { 
     for (int j=0; j<w/2; j++) { 
     after[toFill++] = front++; 
     after[toFill++] = front++; 
     after[toFill++] = back++; 
     after[toFill++] = back++; 

     after[toFill++] = frontZ++; 
     after[toFill++] = frontZ++; 
     after[toFill++] = backZ++; 
     after[toFill++] = backZ++; 
     }  
     front += w; 
     back += w; 
     frontZ += w; 
     backZ += w; 
    } 
    front += w*w; 
    back += w*w; 
    frontZ += w*w; 
    backZ += w*w; 
    } while (toFill < w*w*w); 
    for (int i=0; i<w*w*w; i++) { 
    println("after " + i + " " + after[i]); 
    }

任何想法讚賞！

來源

2013-03-26 Victor Sand

向我們展示您試過的東西。 – 2013-03-27 03:58:15

看起來有點像Z-階曲線（http://en.wikipedia.org/wiki/Z-order_curve），這是有道理的，因爲你在談論四/八十樹。這就是說，我不確定你在問什麼。 – phs 2013-03-27 07:06:04

添加了我嘗試過的以及一些進一步的說明。它看起來像一個Z階曲線！我也在想，創建代理樹可能會更容易，遍歷它並使用該順序來填充新結構。 – 2013-03-27 16:44:25