碰撞检测的圈数很多
检查大量圆圈的碰撞的最佳方法是什么？
检测两个圆圈之间的碰撞非常容易，但是如果我们检查每个组合，那么它就是O（n2） ，这绝对不是最佳解决方案。
我们可以假设圆对象具有以下属性：
速度是恒定的，但方向可以改变。
我提出了两种解决方案，但也许有一些更好的解决方案。
解决方案1
将整个空间分成重叠的正方形，并仅检查与同一方形中的圆形相撞。 正方形需要重叠，所以当一个圆从一个正方形移动到另一个正方形时不会出现问题。
解决方案2
开始时需要计算每对圆之间的距离。
如果距离很小，那么这些对存储在某个列表中，我们需要在每次更新时检查是否存在冲突。
如果距离很大，那么在更新之后我们会存储一个碰撞（可以计算出来，因为我们知道距离和速度）。 它需要存储在某种优先级队列中。 在先前计算的更新距离数量需要再次检查之后，然后我们执行相同的过程 - 将其放在列表中或再次放入优先级队列中。
马克·拜尔斯问题的答案
这是为了模拟，但它也可以被视为游戏
是的，更新之间的时间是恒定的。
不，我想找到每一次碰撞，并在发生碰撞时做一些事情。
这取决于你的准确性是什么。 我需要检测所有的碰撞。
可以假定速度很小以至于不会发生。
我假设你正在做简单的硬球分子动力学模拟，对吧？ 我在Monte Carlo和分子动力学模拟中多次提到同样的问题。 有关模拟的文献经常提到您的两种解决方案。 Personaly我更喜欢解决方案1 ，但略有修改。
解决方案1
将你的空间分成不重叠的矩形单元格。 所以当你检查一个圆的碰撞情况时，你会发现你的第一个圆是一个单元格内的所有圆，并在每个方向上看X个单元。 我已经尝试了许多X值，并发现X = 1是最快的解决方案。 所以你必须在每个方向上将空间分成单元大小等于：
Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;
除数应该大于3，否则会引起错误（如果它太小，则应该放大模拟盒）。
那么你的算法将如下所示：
如果你会正确地写出来，那么你会有一些关于O（N）的复杂性，因为9个单元（2D）或27个单元（3D）内的圆的最大数目对于任何总数的圆都是恒定的。
解决方案2
Ususaly这样做是这样的：
R < R_max的圆形列表，计算应该更新列表的时间（有关T_update = R_max / V_max ;其中V_max是最大当前速度） T_update ，则转到1。 带有列表的这种解决方案经常通过添加具有R_max_2 > R_max和其自己的T_2过期时间的另一个列表来改进。 在此解决方案中，此第二个列表用于更新第一个列表。 当然，在T_2之后，你必须更新所有O（N ^ 2）的列表 。 还要小心这T和T_2次，因为如果碰撞可以改变速度，那么这些时间会改变。 此外，如果您向系统引入某些前端，那么它也会导致速度变化。
解决方案1 + 2您可以使用列表进行冲突检测和单元格更新列表。 在一本书中写道这是最好的解决方案，但我认为如果你创建小型单元格（就像我的例子），那么解决方案1会更好。 但这是我的意见。
其他的东西
您还可以做其他事情来提高模拟速度：
r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...)您不必做平方根运算。 您可以将r^2与某些值进行比较 - 没关系。 你也不必做所有的(x1-x2)*(x1-x2)操作（我的意思是，对于所有维数），因为如果x*x大于某个r_collision^2那么所有其他y*y等等总结起来，会更大。 对于硬球体来说，也有一种有效的算法，它不会及时执行步骤，而是在时间上寻找最近的碰撞，并跳到这个时间并更新所有位置。 对于不太可能发生碰撞的密度不高的系统来说，这可能是件好事。
有“空间索引”数据结构用于存储您的圈子以便稍后进行快速比较; 四叉树，r树和kd树都是例子。
解决方案1似乎是一个空间索引，每当您重新计算您的配对时，解决方案2将从空间索引中受益。
使事情复杂化，你的物体在移动 - 它们有速度。
在游戏和模拟中使用物体的空间索引是正常的，但大多数情况下是用于静止物体，通常是通过移动不会对碰撞作出反应的物体。
在游戏中这是正常的，所以你可以按照设定的时间间隔（离散的）计算所有的东西，所以它可能是两个对象相互通过，但你没有注意到，因为它们移动得太快了。 许多游戏实际上甚至没有按照严格的时间顺序评估碰撞。 它们具有静止物体（例如墙壁）的空间索引，并列出所有移动物体的详细信息（尽管如我所概述的那样，使用了放松的离散检查）。
精确的连续碰撞检测以及物体在模拟中对碰撞的反应通常要求更高。
你所描述的对方法听起来很有希望。 您可能会将这些对保留在下一次碰撞排序中，并在碰撞到相应的新位置时重新插入它们。 您只需对两个对象的新生成的碰撞列表（O（n lg n））进行排序，然后合并两个列表（每个对象的新碰撞和现有碰撞列表;插入新碰撞，删除这些碰撞陈列碰撞的两个物体的陈旧碰撞）是O（n）。
解决这个问题的另一个办法是调整你的空间索引，以便将对象不是严格地存储在一个扇区中，而是存储在自上次计算以来所经过的每一个扇区中，并且以独立的方式执行。 这意味着将快速移动的对象存储在空间结构中，并且您需要针对这种情况对其进行优化。
请记住，链接列表或指针列表对于现代处理器上的缓存非常不利。 我建议您将任何空间索引的每个扇区中的数组（顺序存储器）或上面列出的对中存储的圆的副本（它们的重要属性用于碰撞检测）。
正如马克在评论中所说的那样，将计算并行化可能相当简单。
一种可能的技术是在你的圆圈中心使用Delaunay三角测量。
考虑每个圆的中心并应用delaunay三角测量。 这会将你的表面镶嵌成三角形。 这允许您构建一个图形，其中每个节点存储三角形的中心，并且每个边都连接到相邻圆的中心。 上面运行的tesselation将邻居的数量限制在一个合理的值（平均6个邻居）
现在，当一个圆圈移动时，你有一组有限的圈子要考虑碰撞。 那么您必须再次将tesselation应用于受移动影响的一组圆，但此操作仅涉及一小部分圆（移动圆的邻居和邻居的一些邻居）
关键部分是第一次tesselation，这将需要一些时间来执行，后来tesselations不是一个问题。 当然你需要在时间和空间方面有效地实现一个图表......
链接地址: http://www.djcxy.com/p/84943.html上一篇: Collision detection of huge number of circles
下一篇: Find smallest circle with maximum density of points from a given set