javascript - 检查大量对象的碰撞 JS

Question

我一直在使用数组 allShapes。该数组由具有相同类型属性的对象组成，例如每个对象都有一个 .x 值和一个 .y 值。

每个形状都有一个“半径”，因此可以轻松完成检测。对于每个物体，半径完全相同。它等于 10。

我怎样才能有效地创建一个函数来检查一个形状是否与另一个形状发生碰撞？提前致谢!

var allShapes = [{70,30},{40,90},{287,245}];
// allShapes[0].x = 70
// For each object, there is a .x and .y value

Answer 1

如果简单的 O(n^2) 解决方案(测试每个对象与所有其他对象)不够有效，请选择一种众所周知的空间分区算法。有 kd 树、八叉树、四叉树、BSP 树等。 也许你应该从一个简单的网格开始。将您的域划分为多个单元格，并按单元格对您的对象进行排序。对于给定的候选对象，使用相同和所有相邻单元格中的所有对象进行测试。