大量圆的碰撞检测

大量圆的碰撞检测

我假设您正在执行简单的硬球分子动力学模拟，对吗？我在蒙特卡洛（Monte
Carlo）和分子动力学模拟中多次遇到相同的问题。关于模拟的文献中经常提到这两种解决方案。我个人更喜欢 解决方案1 ，但稍加修改。

解决方案1
将您的空间划分为不重叠的矩形单元。因此，当您检查一个圆是否发生碰撞时，您会在第一个圆所在的单元格中查找所有圆，并在每个方向上查找X个单元格。我尝试了许多X值，发现X
= 1是最快的解决方案。因此，您必须在每个方向上将空间划分为等于：

Divisor = SimulationBoxSize / MaximumCircleDiameter;CellSize = SimulationBoxSize / Divisor;

除数应大于3，否则将导致错误（如果值太小，则应扩大仿真框）。
然后您的算法将如下所示：

1. 将所有圆圈放入框内
2. 创建单元格结构并存储指向单元格内圆的索引或指针（在数组或列表上）
3. 及时走动（移动所有内容）并更新单元格内部的圆圈位置
4. 环顾四周寻找碰撞。您应该在每个方向检查一个单元
5. 如果发生碰撞-采取措施
6. 转到3。

如果正确书写，则可能会带来 O（N） 复杂性，因为9个像元（在2D中）或27个像元（在3D中）内的最大圆数对于任何总数的圆都是恒定的。

解决方案2
通常，这是这样完成的：

1. 为每个圆创建一个距离较远的圆的列表

   R < R_max

   ，计算之后应更新列表的时间（大约

   T_update = R_max / V_max

   ；其中V_max是最大当前速度）
2. 及时行动
3. 用列表中的圆圈检查每个圆圈的距离
4. 如果发生碰撞-采取措施
5. 如果当前时间较大

   T_update

   ，请执行1。
6. 否则转到2。

通常，可以通过添加另一个列表

R_max_2 >R_max

以及带有其自身的

T_2

到期时间的列表来改进此解决方案。在此解决方案中，此第二列表用于更新第一列表。当然，在

T_2

您必须更新所有列表
O（N ^ 2）之后
。还要注意这一点

T

和

T_2

时间，因为如果碰撞可以改变速度，那么那些时间就会改变。同样，如果在系统中引入一些先兆，那么也会引起速度变化。

解决方案1 ​​+ 2
您可以将列表用于冲突检测，将单元格用于更新列表。一本书中写道，这是最好的解决方案，但是我认为，如果您创建小单元格（如我的示例），那么 解决方案1
会更好。但这是我的意见。

其他内容
您还可以执行其他 *** 作以提高仿真速度：

1. 计算距离时

   r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...)

   ，不必进行平方根运算。您可以比较

   r^2

   一些值-没关系。另外，您不必执行所有

   (x1-x2)*(x1-x2)

   *** 作（我的意思是，对于所有尺寸），因为如果

   x*x

   大于某个 *** 作，

   r_collision^2

   则所有其他 *** 作

   y*y

   等等，总之，会更大。
2. 分子动力学方法很容易并行化。您可以使用线程甚至在GPU上进行 *** 作。您可以计算不同螺纹中的每个距离。在GPU上，您可以轻松创建几乎无成本的线程数。

对于硬球，还有一种有效的算法，它不及时执行步长，而是在时间上寻找最近​​的碰撞并跳转到该时间并更新所有位置。对于不太可能发生碰撞的不密集系统，这可能会很好。