四叉树对象移动

Question

所以，我需要一些理论方面的帮助来进行头脑风暴。现在，我有一些代码只是绘制一些对象。这些对象位于四叉树的叶子节点中。当对象移动时，我希望将它们保留在四叉树的正确叶子节点中。

目前，我只是在更改其位置后重构对象上的四叉树。我试图想出一种纠正树而不完全重建它的方法。我能想到的就是拥有大量相邻叶子节点的指针。

有没有人知道如何找到一个物体移动到哪个节点，而不是随处放置大量指针，或者有关此问题的文章链接？我只能找到不同构建四叉树的方式，没有更新它的任何信息。

- user926914

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，然后将结果解释为二进制数即可。

对于二维情况，它只稍微复杂一些。现在，每个节点有四个分支，因此我们可以使用四个字母的字母表来标记每个分支路径，例如从根开始，沿着第三个分支、第四个分支、第一个分支、第二个分支和第二个分支依次走的路径生成字符串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，并将新的一对二进制数转换回字符串即可。

我相信这些都已经被发现过了，但我还没有在网络上找到这些信息。

- Christian J. B.

Answer 2

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

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

从四叉树中删除可以首先从叶节点中删除该元素，然后如果叶节点变为空，则从其父节点中删除。如果父节点变为空，则从其父节点中删除，依此类推。

只要有效实现四叉树（例如使用节点的自由列表），这种简单的方法就足够高效地处理每帧移动的对象的复杂世界。不应该需要对每个节点进行堆分配来插入它，也不应该涉及到删除每个单个节点的堆释放。大多数节点分配/释放应该是一个简单的恒定时间操作，仅涉及一些整数或指针的操作。

您还可以使其稍微复杂一些。您可以首先存储对象的先前位置，然后移动它。如果新位置占据的节点与先前位置不同，则从不再占据的节点中删除对象，并将其插入新节点中。否则，只需将其保留在相同的节点中。

更新

通常我会尽量避免链接到我的以前的回答，但在这种情况下，我最终撰写了一篇非常全面的文章，很难在其他地方复制。这是链接：https://dev59.com/NFgQ5IYBdhLWcg3w9Yzk#48330314

- user4842163