检查碰撞圈

Question

我有一些圆，我知道它们的 X、Y 和 r。我想检查其中是否有任何一个与其他任何碰撞......
检查方法很简单：

r₁+r₂ < sqrt((x₁-x₂) ² +(y₁-y₂)²)

但是我必须检查全部吗？它给了我 O(n²) 的复杂性，我想避免这种情况。

Answer 1

尝试查看 KD-tree acc-struct。首先，你必须将圆视为正方形，计算交集的复杂性要低得多，而不是将这些正方形放入修改后的 KD 树中，这需要一些思考，但希望没有太极端...... kd 树的工作方式是它抵消了基于每个树级别的某些标准的一半可能匹配。在维基百科上查一下吧。祝你的问题好运:)

Answer 2

您可以将空间划分为多个区域，例如：

1. 计算 2D AABB - 所有圆的轴对齐边界框
2. 将其分为四个子框
3. 给每个子框分配一个圆圈，如果圆圈稍微穿过该框，那么它必须放入该框内。这意味着圆圈可以分配给多个框。
4. 迭代每个圆，然后检查它被分配到哪个框，并仅计算与该框中的圆的碰撞。

在2.中，您可以根据空间大小进行多次细分，如果将多个圆圈分配给一个框，则可以进一步细分。

Answer 3

使用方形边界框作为简单的初始测试。然后才继续转圈子。

还有

r1+r2 < sqrt((x1-x2)² + (y1-y2)²)

可以重写为：

(r1+r2)² < (x1-x2)² + (y1-y2)²

这消除了讨厌的 sqrt()

Answer 4

有很多圆圈吗？ 我认为最好的事情是将你的圆圈设置为数组。 因此，您将拥有一组圆圈，不仅使它们更容易初始化，而且都在一个地方。

下一部分是获取圆并为其提供测试碰撞的函数。 例如

void isCol(Array [circles], 该圆所在的当前向量等);

如果有很多圆圈

创建一个 for 循环，遍历数组检查每个 X、Y 和半径值，看看它们是否在某个范围内 圆的空性。 但是，您应该始终检查是否 圆圈里你看着的就是你，如果是那就跳过那个圆圈。如果 他们在一个区域然后计算他们是否在 与您相撞并且（在此处插入碰撞后果）。

如果只有几个圆圈，则向右跳到检查碰撞。

我认为你要做的是检查所有圆圈是否在一个范围内，并且只处理那些在范围内的圆圈。

希望这有帮助。