重新排列四叉树/八叉树的数据

我正在执行体素八叉树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