algorithm - 为什么我应该使用 AABB 进行 Circle-Circle 碰撞

Question

在我的 wip 游戏中，我必须实现 Circle-Circle 碰撞。为了实现这一点，我只需计算它们的中心 (x1-x2)² + (y1-y2)² 之间的平方距离。如果它小于它们的平方半径 (r1+r2)²，就会发生碰撞。但是今天我看到了这个链接: Circle-Circle collision

在这里，他们首先使用 AABB 碰撞来判断圆圈是否靠近。但我为什么要这样做？圆与圆的碰撞是一个简单且并不昂贵的计算。当我首先使用 AABB 时，我至少会进行相同数量的计算，如果圆圈更接近的话。

让我解释一下:

我对每个圆圈与其他圆圈进行 AABB 碰撞检测。所以我必须做 n!/(n-2)! 计算。 n = 要测试的圆圈数。对于每个 AABB 碰撞圆对，如果它们真的发生碰撞，我必须进行另一次计算。

没有 AABB 碰撞检测，我只做 n!/(n-2)! 计算，我不认为这种计算如此昂贵。你怎么看？

Answer 1

我认为这是你可以在平均情况下在 O(NlogN) 中执行此操作的方法，但在最坏的情况下为 O(N^2) :-

1. Consider each circle as rectangle of 2R*2R with center at center of circle.

2. Use sweep line algorithm for rectangles which is O(NlogN + R) where is number of intersections.

3. The intersecting pairs of rectangles can be checked as circles for intersection using your algorithm in O(R^2).

注意:如果 R 很小那么它是 O(NlogN) 但如果 R​​ = O(N) 那么它是 O(N^2)