检查相交的圆圈

Question

我有一些圆，知道它们的 X、Y 和 r 值，想要检查它们中的任何两个是否相交... 检查的方式很简单：

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

但是我必须逐个检查吗？这会给我带来 O(n²) 的复杂度，而我想避免这种情况 :/

- noisy cat

---

循环是移动的还是静止的？ - wildplasser

Answer 1

尝试查看KD树数据结构。首先，您必须将圆形视为正方形，计算交集的复杂度要小得多，然后将这些正方形放入修改后的KD树中，这需要一些思考，但希望不会太极端... KD树的工作方式是基于每个树级别的某些标准取消可能匹配的一半。在维基百科上查找它。祝你好运 :)

- Peter Kottas

---

我完全不理解这个kd-tree...但也许有更简单的方法...总的来说，我想检查我的rts中是否有任何单位足够接近以进行攻击，我认为我可以将范围改变为点数...请参见"http://imageshack.us/photo/my-images/4/sthsm.png/"。那么也许有更好的方法吗？ - noisy cat

Answer 2

在编程中，使用正方形边界框作为简单的初始测试。然后才能使用圆形。

另外

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

可以被重写为：

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

这将消除那个讨厌的sqrt()

- trapper

Answer 3

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

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

在第2步中，您可以进行许多细分，具体取决于您的空间大小，如果有太多圆分配给一个框，则进一步细分。

- marcinj

Answer 4

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

下一步是将圆形赋予一个测试碰撞的函数。 例如：

void isCol（Array [circles]，当前向量所在的圆等）;

如果有很多圆

制作一个for循环，遍历数组，检查每个圆的X、Y和半径值，看它们是否在某个圆周附近。 但是，您应该始终检查您正在查看的圆是否是您自己，如果是，则跳过该圆。如果它们在区域内，则计算它们是否与您发生碰撞，并进行（插入碰撞后果）。

如果只有几个圆，则直接跳到检查碰撞。

我认为您想要的是检查所有圆是否在范围内，并仅处理那些在范围内的圆。

希望这可以帮助您。

- SD1990