quadtree - 四叉树对象移动

Question

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

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

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

Answer 1

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

这是我一直在研究的一种可能的解决方案：

为简单起见，让我们先做一维案例。假设我们在 x 中有 32 个网格点。然后每个网格点对应于深度为 5 的四叉树上的某个叶子。（深度 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是右上角。然后，象征性地，我们可以写，Ax=0, Ay=0 / Bx=1, By=0 / Cx=0, Cy=1 / Dx=1, Dy=1。

以 CDABB 为例，我们首先看一下它的 x 值 (CDABB).x = (01011)，它给了我们 x 网格点。同样对于 y。

最后，如果您想找出例如 CDABB 右侧的节点，则只需将其转换为 x 和 y 中的一对二进制数，将 x 值加 +1 并将新的二进制数对转换回一个字符串。

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

Answer 2

如果您首先拥有将元素插入四叉树所需的空间数据（例如：其点或矩形），那么您拥有删除它所需的相同数据。

一种简单的方法是在移动元素之前，使用最初插入它时使用的相同数据将其从四叉树中删除，然后移动它，然后重新插入。

从四叉树中移除可以首先从叶子节点中移除元素，然后如果叶子节点为空，则将它们从其父节点中移除。如果父母变得空虚，将他们从父母身上移除，依此类推。

只要您有效地实现四叉树，这种简单的方法对于每帧移动的复杂对象世界就足够有效（例如：为节点使用空闲列表）。不必在每个节点的基础上进行堆分配来插入它，也不必在删除每个节点时涉及堆释放。大多数节点分配/解除分配应该是一个简单的恒定时间操作，仅涉及例如对几个整数或指针的操作。

如果你愿意，你也可以让它变得更复杂一些。您可以开始存储对象的先前位置，然后移动它。如果新位置占用了先前位置以外的节点，则将对象从它不再占用的节点中移除，并将其插入新的节点。否则，只需将其保存在同一个节点中。

更新

我通常会尽量避免链接我以前的答案，但在这种情况下，我最终对这个主题进行了非常全面的撰写，这在其他任何地方都很难复制。这是：https ://stackoverflow.com/a/48330314/4842163