我一直在研究这个:
https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js
我相信我理解四叉树的一般概念，尽管我对它们的工作原理和上面的实现有两个问题:
难道你不需要每隔几毫秒重建整个树吗？在 Javascript 中，这不会非常慢吗？
如果我有这样的东西:http://davzy.com/screenshots/skitched-20120318-180324.png ，那么很容易找到同一个四边形中的其他点，但我有一个矩形与 3 个不同的四边形相交，有没有办法让它显示为所有 3 个四边形的子元素？
<在上面示例的第 144 处，它说这个 Node.prototype._classConstructor = Node;，我很好奇发生了什么。我认为原型(prototype)是一种定义函数或变量以供将来在类中使用的方法，所以我不确定这一行的作用。
最佳答案
1. Wouldnt you have to rebuild the entire tree every several ms? In Javascript wouldnt this be extremely slow to do?
我想这取决于您使用它的目的；但是，是的，作者在 his blog post about his QuadTree implementation 中的碰撞检测示例将清除树并重新填充它大约每秒 24 次(因此，大约每 40 毫秒一次)。您可以自己判断这是否“非常慢”；在我的机器上它看起来很流畅。 (即使没有，我希望四叉树的重建实际上比重新绘制 Canvas 上的所有圆圈更便宜/更快。)
2. […] I have a rectangle that hits 3 different quads, is there a way I can make it display as a child of all 3 of those quads?
我不确定你所说的“显示”是什么意思，但是:如果你调用构造函数时将 pointQuad 参数设置为 false，那么项目是两个 -维度(即，除了 x 和 y 之外，它们还有 width 和 height)，并且每个项目都将是它完全适合内部的最小四边形的 child 。在您的示例中，由于矩形穿过 Canvas 的垂直中线，因此它将是根四边形的直接子元素。
3. On 144 of the above example it says this Node.prototype._classConstructor = Node;, I'm just curious what's going on. […]
Node“类”有一个名为BoundsNode 的“子类”(当项目是二维时使用)，BoundsNode.prototype._classConstructor 设置为 BoundsNode(覆盖继承的 Node.prototype._classConstructor)。这允许 Node 的 subdivide 方法编写 new this._classConstructor(...) 以构造一个新的 BoundsNode 如果 this 是一个 BoundsNode，如果 this 是一个普通的 则一个新的普通 .Node节点
关于javascript - 与二维碰撞有关的四叉树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9762476/