1

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

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

让我解释：

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

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

4

2 回答 2

1

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

  1. 将每个圆视为 2R*2R 的矩形，圆心位于圆心。

  2. 对 O(NlogN + R) 的矩形使用扫描线算法，其中是交叉点的数量。

  3. 可以使用 O(R^2) 中的算法将相交的矩形对检查为相交的圆。

注意：如果 R 很小，则为 O(NlogN)，否则如果 R = O(N)，则为 O(N^2)

于 2014-01-15T11:05:09.713 回答
0

这条评论是正确的答案。这取决于您的硬件和编译器。如果您首先使用 AABB 检测，则您有 8 个添加 + 4 个比较操作。如果比较平方距离和平方半径，则进行 6 加/减 + 3 乘 + 1 比较。也许您的硬件和编译器与乘法相比更快。但是性能上应该差别不大。如果您不比较平方而是使用平方根（无论出于何种原因），您应该首先进行 AABB 比较，因为平方根计算需要一些时间。在这个答案中也有更好的解决方案。如果您必须在许多对象之间进行多次检测，您可以考虑其中一种解决方案。

于 2014-01-20T08:52:05.557 回答