3

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

在此处输入图像描述 在此处输入图像描述

正如您在上面的两个插图中看到的那样，如果每个单元格都有一个二进制 ID（例如：1010、1011），那么每个奇数二进制索引控制 X 偏移量，每个偶数二进制索引控制 Y 偏移量。

例如，在2 级网格（16 个单元）的情况下，1010（单元#10）可以说在它的第 4和第 2索引处有 1，因此它们将执行两个 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），它实例化节点并将其存储在一个长数组中。它将当前迭代整数传递给 Node构造函数，并将其存储为索引。

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

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

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

    return bits;
}

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

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

谢谢！

这是我从中得到这个想法的参考（注意：不同的编程语言）：

L. Spiro 引擎 - http://lspiroengine.com/?p=530

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

4

1 回答 1

1

您的任务由 Hannan Samet 描述。这首先构建四叉树，然后为每个四元单元分配对应的 morton 代码。（位交织代码）。
获得代码后，将其分配给四边形中的对象。然后你可以删除四叉树。然后，您可以通过将坐标转换为对应的 morton 代码进行搜索，并对 morton 索引进行 bin 搜索。您也可以使用希尔伯特或格雷码代替 morton（也称为 z 顺序）。

于 2013-04-13T03:03:36.920 回答