data-structures - 用于2D碰撞检测的四叉树

我正在尝试使用四叉树进行2D碰撞检测，但是我对如何实现它有些困惑。首先，我要有一个四叉树，其中包含四个子树(一个代表每个象限)，以及一组不适合单个子树的对象的集合。

当检查对象在树中是否存在冲突时，我会做类似这样的事情(感谢QuadTree for 2D collision detection):

检查对象是否与当前节点中的任何对象发生冲突。

对于其空间与对象重叠的任何子树，请递归。

要查找四叉树中的所有碰撞，请执行以下操作:

将当前节点中的每个对象与当前节点中的其他对象进行对照。

针对每个子树检查当前节点中的每个对象。

插入四叉树:

如果对象适合多个子树，则将其添加到当前节点，然后返回。

否则，递归到包含它的任何子树中。

要更新四叉树:

递归到每个子树中。

如果当前节点中的任何元素不再完全适合当前树，则将其移至父树。

如果当前节点中的任何元素都适合子树，则将其插入子树。

这样好吗可以改善吗？

最佳答案

您的四叉树结构不是最佳的。您每个节点存储4个子树是正确的，但是实际对象仅应存储在叶子内部，而不是内部节点。因此，保存实际对象的集合需要移动到叶子上。

让我们看一下这些操作的实现:

将对象插入四叉树:
检查对象是否与当前节点相交。如果是这样，请递归。如果您已经达到叶子级别，则将对象插入集合中。

从四叉树中删除一个对象:
执行与插入对象完全相同的步骤，但是当到达叶级别时，将其从集合中删除。

测试对象是否与四叉树内部的任何对象相交:
执行与插入对象完全相同的步骤，但是当到达叶级别时，检查与集合中所有对象的碰撞。

测试四叉树内部所有对象之间的所有碰撞:
对于四叉树中的每个对象，执行单个对象碰撞测试。

更新四叉树:
从已更改位置的四叉树中删除所有对象，然后再次插入它们。

这有几个优点:

通过仅将对象存储在叶子中，在四叉树上处理操作非常容易(特殊情况较少)

该四叉树可以具有不同深度的叶子，因此允许您根据其覆盖的空间区域来调整四叉树的密度。这种适应可以在运行时发生，从而使对象/节点之比保持最佳状态。

唯一的缺点:

对象可以属于四叉树内的几个集合。您将需要在四叉树之外的一个额外的线性集合来枚举每个没有重复的对象。

关于data-structures - 用于2D碰撞检测的四叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4981866/