algorithm - 大量圆圈的碰撞检测

Question

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

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

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

速度是恒定的，但方向可以改变。

我提出了两种解决方案，但也许还有一些更好的解决方案。

方案一
将整个空间划分为重叠的正方形，并仅检查与同一正方形中的圆圈是否发生碰撞。正方形需要重叠，这样当圆从一个正方形移动到另一个正方形时就不会出现问题。

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

Mark Byers 问题的答案

1. 是为了游戏吗？
   是模拟的，但也可以当做游戏
2. 是否要每 n 毫秒重新计算一次新位置，并同时检查碰撞？
   是的，更新之间的时间是恒定的。
3. 您想知道第一次/每次碰撞发生的时间吗？
   不，我想找到每一次碰撞并在它发生时做一些“事情”。
4. 准确性有多重要？
   这取决于你所说的准确性是什么意思。我需要检测所有碰撞。
5. 如果非常小的快速移动的圆圈偶尔会相互穿过，这是一个大问题吗？
   可以假设速度很小，不会发生。

Answer 1

有“spatial index”数据结构用于存储您的圈子以便稍后进行快速比较；四叉树、r 树和 kd 树就是例子。

解决方案 1 似乎是一个空间索引，而解决方案 2 会在您每次重新计算对时受益于空间索引。

使事情复杂化的是，您的对象正在移动 - 它们具有速度。

在游戏和模拟中为对象使用空间索引是正常的，但主要用于静止对象，通常是不会通过移动对碰撞使用react的对象。

是normal in games这样你就可以在设定的时间间隔(离散)计算所有的东西，所以可能是两个物体穿过彼此但你没有注意到因为它们移动得太快了。许多游戏实际上甚至不按严格的时间顺序评估碰撞。它们具有静止物体的空间索引，例如墙壁，以及他们详尽检查的所有移动物体的列表(尽管如我概述的那样进行了宽松的离散检查)。

准确的连续碰撞检测以及对象在模拟中对碰撞使用react的位置通常要求更高。

您概述的配对方法听起来很有希望。您可以将这些对按下一次碰撞排序，并在它们碰撞到适当的新位置时重新插入它们。您只需为两个对象对新生成的碰撞列表 (O(n lg n)) 进行排序，然后合并两个列表(每个对象的新碰撞，以及现有的碰撞列表；插入新的碰撞，删除那些列出碰撞的两个对象的陈旧碰撞)是 O(n)。

另一种解决方案是调整您的空间索引，使对象不严格存储在一个扇区中，而是存储在自上次计算以来它经过的每个扇区中，并离散地执行操作。这意味着在您的空间结构中存储快速移动的对象，您需要针对这种情况对其进行优化。

请记住，链表或指针列表非常 bad for caching在现代处理器上。我建议您将圆圈的副本(无论如何它们对于碰撞检测的重要属性)存储在任何空间索引的每个扇区中的数组(顺序存储器)中，或者存储在上面概述的成对数组中。

正如 Mark 在评论中所说，并行化计算可能非常简单。