四叉树与2d碰撞有关

Question

我一直在研究这个:

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. 在上面的例子中,它说这个Node.prototype._classConstructor = Node;,我只是好奇发生了什么.我认为原型是一种定义函数或变量以供将来在类中使用的方法,所以我不确定这行是做什么的.

Answer 1

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

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

2. [...]我有一个矩形,可以击中3个不同的四边形,有没有办法让它显示为所有3个四边形的孩子？

我不确定"display"是什么意思,但是:如果你用pointQuad参数set to来调用构造函数false,那么项目是二维的(即,它们有width和height除了x和之外y),并且每个项目都是完全适合内部的最小四边形的孩子.在您的示例中,由于矩形穿过画布的垂直中线,因此它将是根四边形的直接子项.

3.在上面的例子中,它说这个Node.prototype._classConstructor = Node;,我只是好奇发生了什么.[...]

的Node"类"具有"子类"命名BoundsNode(当物品是二维使用),并且BoundsNode.prototype._classConstructor被设置为BoundsNode(其覆盖继承Node.prototype._classConstructor).这允许Node的subdivide方法写入new this._classConstructor(...),以建立一个新的BoundsNode,如果this是BoundsNode,一个新的简单的Node,如果this是一个普通的Node.