相关疑难解决方法(0)

检查大量圈子碰撞的最佳方法是什么？
检测两个圆之间的碰撞非常容易,但是如果我们检查每个组合,则它是O(n ²),这绝对不是最佳解决方案.

我们可以假设circle对象具有以下属性:

• 坐标
• 半径
• 速度
• 方向

速度是恒定的,但方向可以改变.

我想出了两个解决方案,但也许有更好的解决方案.

解决方案1将
整个空间划分为重叠的正方形,并仅检查与同一正方形的圆形的碰撞.正方形需要重叠,因此当圆从一个方格移动到另一个方格时不会出现问题.

解决方案2
在开始时,需要计算每对圆之间的距离.
如果距离很小,那么这些对存储在一些列表中,我们需要检查每次更新中的冲突.
如果距离很大,那么我们存储后更新可能会发生碰撞(可以计算,因为我们知道距离和速度).它需要存储在某种优先级队列中.在先前计算的更新数量之后,需要再次检查距离,然后我们执行相同的过程 - 将其放在列表中或再次放入优先级队列中.

Mark Byers的答案问题

1. 是游戏吗？
   这是为了模拟,但也可以作为游戏来对待
2. 您想要每n毫秒重新计算一次新位置,还要检查此时的碰撞情况吗？
   是的,更新之间的时间是不变的.
3. 您想找到发生第一次/每次碰撞的时间吗？
   不,我想找到每一次碰撞,并在碰撞时做"有所作为".
4. 准确性有多重要？
   这取决于你的准确度是什么意思.我需要检测所有碰撞.
5. 如果非常小的快速移动的圆圈偶尔会相互穿过,这是一个大问题吗？
   可以假设速度太小而不会发生.