actionscript-3 - 如何将四叉树单元格的空间索引(二进制索引)转换为位置和维度值？

Question

很抱歉在这个问题中没有使用任何术语，但基本上我正在研究创建一个使用二进制索引的四叉树，如下所示:

正如您在上面的两个插图中看到的，如果每个单元格都被赋予一个二进制 ID(例如:1010、1011)，那么每个 ODD 二进制索引控制 X 偏移，每个 EVEN 二进制索引控制 Y 偏移量。

例如，在 Level 2 网格(16 个单元格)的情况下，1010(单元格 #10)可以说是 4th 和 2nd 索引，因此它们将执行两个 Y 偏移。第一个“1###”(在最左侧)将指示一个单元格高度的偏移量，然后第二个“##1#”将另外偏移单元格高度的两倍。

如:

// If Cell Height = 64pixels
  1### = 64 pixels
+ ##1# = 128 pixels
__________________
  1#1# = 192 pixels

同样可以应用于 X 轴，只是它使用奇数代替(例如:#1#1)。

现在，当我初始化我的 QuadTree 时，我开始计算如果使用所有单元格和所有深度它可能包含的最大节点数。我用每个深度的 4 次方的总和计算了这一点:

_totalNodes =   0;

var t:int=0, tLen:int=_maxLevels;
for (; t<tLen; t++) {
    _totalNodes += Math.pow(4, t); //Adds 1, 4, 16, 64, 256, etc...
}

然后，我创建另一个循环(从 0 迭代到 _totalNodes)，它实例化节点并将其存储在一个长数组中。它将当前迭代整数传递给节点构造函数，并将其存储为索引。

到目前为止，我已经能够通过确定节点的索引最高有效位来确定节点将存储在哪个深度(又名:级别):

public static function MSB( pValue:uint ):int {
    var bits:int =      0;

    while ( pValue >>= 1) {
        bits++;
    }

    return bits;
}

但现在，我一直在努力弄清楚如何将索引从二进制形式转换为实际的单元格 X 和 Y 位置。就像我上面说的，找到每个单元格的尺寸。这只是对整个索引进行一些逻辑操作的问题(或者“位代码”是我在代码中引用的名称)

如果您知道一个使用逻辑运算(二进制级别)将二进制索引值转换为 X 和 Y 位置的好示例，您能否在此处发布链接或解释？

谢谢!

---

这是我从中得到这个想法的引用资料(注意:不同的编程语言):

L. Spiro 发动机 - http://lspiroengine.com/?p=530

虽然我不熟悉那篇文章中使用的语言，所以我不能真正理解它并将其轻松转换为 ActionScript 3.0。

Answer 1

Hannan Samet 描述了您的任务。这通过首先构建四叉树，然后为每个四元单元分配相应的莫顿代码来工作。 (比特交织码)。
获得代码后，将其分配给四边形中的对象。然后你可以删除四叉树。然后，您可以通过将坐标转换为相应的 morton 代码来进行搜索，并对 morton 索引进行 bin 搜索。除了 morton(也称为 z 阶)，您还可以使用希尔伯特代码或格雷代码。