四叉树对象移动

Question

所以我需要一些头脑 Storm 方面的帮助，从理论的角度来看。现在我有一些代码可以绘制一些对象。对象位于四叉树的叶子中。现在随着对象的移动，我想将它们放置在四叉树的正确叶子中。

现在我只是在改变对象的位置后重建对象的四叉树。我试图找出一种方法来纠正树而不完全重建它。我能想到的就是有一堆指向相邻叶节点的指针。

有没有人知道如何找出对象移动到的节点，而无需到处都有大量指针或指向相关文章的链接？我所能找到的只是构建四叉树的不同方法，与更新它无关。

Answer 1

如果我理解你的问题。您需要某种方式在空间坐标和四叉树上的叶子之间进行映射。

这是我一直在寻找的一种可能的解决方案:

为简单起见，让我们先处理一维情况。假设我们在 x 中有 32 个网格点。然后每个网格点对应于深度为五的四叉树上的一些叶子。 (深度 0 = 整个网格，深度 1 = 2 个点，深度 2 = 4 个点...深度 5 = 32 个点)。

每片叶子都可以由通往叶子的分支索引表示。在每一层都有两个分支，我们可以标记为 A 和 B。因此，一个特定的叶子可能被标记为 BBAAB，这意味着，沿着 B 分支向下，然后是 B 分支，然后是 A 分支，然后是 B 分支，然后B分支。

那么，你如何映射，例如BBABB 到 0..31 之间的 x 网格点？只需将其转换为二进制，以便 BBABB->11011 = 27。因此，从网格点到叶节点的映射只是将字母 A 和 B 转换为 0 和 1，然后将结果解释为二进制数。

对于 2D 情况，只是稍微复杂一点。现在每个节点都有四个分支，所以我们可以使用四个字母的字母表标记每个分支路径，例如从根开始，取第三个分支，然后是第四个分支，然后是第一个分支，然后是第二个分支，然后再次是第二个分支，我们将生成字符串 CDABB。

现在将字符串(例如'CDABB')转换为一对网格值(x，y)。

假设 A 是左下角，B 是右下角，C 是左上角，D 是右上角。然后，我们可以用符号表示，A.x=0,​​ A.y=0/B.x=1, B.y=0/C.x=0,​​ C.y=1/D.x=1, D.y=1。

以 CDABB 为例，我们首先查看其 x 值 (CDABB).x = (01011)，它为我们提供了 x 网格点。对于 y 也是如此。

最后，如果您想了解例如CDABB 右侧的节点，然后简单地将其转换为 x 和 y 中的一对二进制数，将 x 值加 +1 并将新的二进制数对转换回字符串。

我确定这一切都被发现了，但我还没有在网上找到这些信息。