在我的wip游戏中，我必须实现圆圈-圆圈碰撞。为了实现这一点，我只需计算其中心之间的平方距离 (x1-x2)² + (y1-y2)² .如果这个半径更小，那么它们(r1+r2)²发生碰撞时的平方半径。但是今天我看到了这个链接：圆圈-圆圈碰撞
在这里，他们首先使用AABB碰撞来注意圆圈是否靠近。但是我为什么要这样做呢？圆-圆碰撞是一个简单且并不昂贵的计算。当我第一次使用 AABB 时，我至少执行相同数量的计算，如果圆圈接近更多。
让我解释一下：
我对每个圆圈进行AABB碰撞检测。所以我必须做n! / (n-2)!计算。n = 要测试的圆圈数。对于每个 AABB 碰撞圆对，如果它们真的发生碰撞，我必须再做一次计算。
如果没有AABB碰撞检测，我只做n! / (n-2)!计算，我认为这种计算不会那么昂贵。你觉得怎么样？
我认为这是您可以在平均情况下在 O（NlogN） 中执行此操作的方法，但在最坏的情况下可以在 O（N^2） 中执行此操作： -
将每个圆视为 2R*2R 的矩形，中心位于圆心。
对矩形使用扫描线算法，即 O（NlogN + R），其中是交点数。
可以使用 O（R^2） 中的算法将相交的矩形对检查为相交的圆。
注意：如果R很小，那么它是O（NlogN），但如果R = O（N），那么它是O（N^2）
这个评论是正确的答案。这取决于您的硬件和编译器。如果您首先使用 AABB 检测，则有 8 个加法 + 4 个比较操作。如果您比较平方距离和平方半径，则进行 6 加/减 + 3 乘 + 1 比较。也许您的硬件和编译器使用比较比乘法更快。但这不应该是性能上的大差异。如果您不是使用平方根来比较平方根（无论出于何种原因），您应该首先进行 AABB 比较，因为平方根计算需要一些时间。在这个答案中也有更好的解决方案。如果必须在许多对象之间进行许多检测，则可以考虑其中一种解决方案。