与二维碰撞有关的四叉树

Quad trees pertaining to 2d collision

本文关键字：四叉树 碰撞 二维      更新时间：2023-09-26

我一直在研究这个：

https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js

我相信我理解关于四叉树的一般概念，尽管我对它们的工作原理和上面的实现有两个问题：

  1. 你不是每隔几毫秒就要重建整棵树吗？在Javascript中，这不是很慢吗？

  2. 如果我有这样的东西：http://davzy.com/screenshots/skitched-20120318-180324.png，那么很容易在同一个四边形中找到其他点，但我有一个矩形，它击中了3个不同的四边形，有没有办法让它显示为所有3个四边形的子对象？

  3. 在上面示例的144中，它显示了Node.protype_classConstructor=Node；，我只是好奇到底发生了什么。我认为原型是一种定义函数或变量的方法，以供将来在类中使用，所以我不确定这一行是做什么的。

1。你不是每隔几毫秒就要重建整棵树吗？在Javascript中，这不是很慢吗？

我想这取决于你用它做什么；但是，是的，作者在关于QuadTree实现的博客文章中的碰撞检测示例将清除树，并大约每秒重新填充24次（因此，大约每40ms一次）。你可以自己判断这是否"极其缓慢"；在我的机器上，它看起来很光滑。（即使没有，我也希望重建QuadTree实际上比重新绘制画布上的所有圆圈更便宜/更快。）

2。[…]我有一个矩形，它击中了3个不同的四边形，有没有办法让它显示为所有3个四边形的子对象？

我不知道你所说的"显示"是什么意思，但是：如果你调用pointQuad参数设置为false的构造函数，那么项目是二维的（即，除了x和y之外，它们还有width和height），并且每个项目都将是它完全适合内部的最小四边形的子项。在您的示例中，由于矩形与画布的垂直中线相交，因此它将是根四边形的直接子对象。

3。在上面示例的144中，它显示了Node.protype_classConstructor=Node；，我只是好奇发生了什么事

Node"类"有一个名为BoundsNode的"子类"（当项目是二维的时使用），BoundsNode.prototype._classConstructor设置为BoundsNode（覆盖继承的Node.prototype._classConstructor）。这允许Node的subdivide方法写入new this._classConstructor(...)，以便在this是BoundsNode的情况下构造新的BoundsNode，并且在this是纯Node的情况下构建新的纯Node。

相关文章：