快速圆形碰撞检测

Question

我正在尝试编写一个方法，用于计算两个圆是否重叠。我已经想出了以下方法，只是好奇是否有任何进一步的优化方式。

private static boolean isCollision(Point2D p1, float r1, Point2D p2, float r2)
{
    float a,dx, dy;
    a = (r1+r2) * (r1+r2);
    dx = (float) (p1.getX() - p2.getX());
    dy = (float) (p1.getY() - p2.getY());

    if (a > (dx*dx) + (dy*dy))
    {
        return true;
    }
    return false;
}

- Oli

---

我认为任何解决方案都无法提供当两个中心之间的距离小于一但大于零时的充分结果。 - Matthieu N.

Answer 1

看起来数学方面还不错。以下是一些关于如何让Java端更快、更简洁的小点建议：

• 如果你使用的是double而不是float作为半径，那么就不需要将double转换为float。
• 如果你明确要求使用Point2D.Double类型的参数，则可以使用它们的x和y公共字段，而不必使用getter方法。
• 再者，为什么要写 if (foo) { return true; } else { return false; }呢？直接写成return foo;就好了！

那么下面是改进后的代码：

private static boolean isCollision(Point2D.Double p1, double r1, Point2D.Double p2, double r2)
{
    final double a = r1 + r2;
    final double dx = p1.x - p2.x;
    final double dy = p1.y - p2.y;
    return a * a > (dx * dx + dy * dy);
}

（请注意，如果您的代码完全基于浮点数，则可以使用 Point2D.Float 和 float 进行相同的操作。）

- Zarkonnen

---

如果边界矩形不重叠，您可能还应考虑提前终止。实际上是否值得实现这一点，部分取决于有多少个圆和矩形重叠。 - Bill Michell

我一直在思考这个问题。我的直觉是，拥有分支比进行更多的浮点乘法对CPU来说会更耗时（需要在稍后验证）。 - Zarkonnen

虽然我知道不转换为浮点数会更快，但如果您只使用浮点数而不是双精度浮点数，是否会更有效率？ - Myer

可能吧，其实。只是在Java中几乎没有其他东西使用浮点数。还有一件值得测试的事情。 - Zarkonnen

我不确定使用getter和setter方法是否会导致性能损失。请参阅此帖子：https://dev59.com/7GAg5IYBdhLWcg3wI4HD - Mapsy

Answer 2

重叠还是相交？

如果是相交，不要忘记考虑圆内部不相交的情况。

如果是重叠，我不太清楚你如何进一步优化；你正在比较点距离与半径之和，使用距离平方来避免取平方根。看起来没有多余的东西需要削减。

- Jason S

Answer 3

你真的需要考虑到所有可能的Point2D实现吗？如果不需要，可以节省一个虚函数调用：

private static boolean isCollisionFloat (Point2D.Float p1, float r1, Point2D.Float p2, float r2)
{
    final float r = r1+r2;
    final float dx = p1.x - p2.x;
    final float dy = p1.y - p2.y;

    return (r*r) > (dx*dx) + (dy*dy);
}

测试1000x1000个点： 什么也不做花费了6毫秒 使用Point2D.Float进行isCollision检测花费了128毫秒 使用Point2D.Double进行isCollision检测花费了127毫秒 使用isCollisionFloat花费了71毫秒 使用isCollisionDouble花费了72毫秒

如果可能的话，请选择其中一个，而不是两者都考虑。

问题在于性能问题是你确实需要测量效果，这时候有人已经发表了与不支持的意见相同的答案。

- Pete Kirkham

---

嗯，现在我很好奇将r、dx和dy设置为final是否会对性能产生影响。这肯定不会有坏处。无耻地复制到自己的答案中 - Zarkonnen

可能不是，但我习惯于使任何不会改变的事情最终化。 - Pete Kirkham

这本身就是一件非常好的事情。我最近一直在推崇（稍微有些疯狂的）观点，即Java中的默认值应该是final，如果你想要一个变量，就必须使用“var”关键字... - Zarkonnen

Answer 4

我不知道这是否与你的情况相关，但如果你想检查你的圆与许多其他圆之间是否存在重叠（比如说成千上万个圆），你可以尝试将你的圆组织成四叉树（参见http://en.wikipedia.org/wiki/Quadtree），并在四叉树中进行树形查找（基于你的圆的边界矩形）。

- Patrick

Answer 5

您的算法可以通过计算每个圆的矩形边界并查看它们是否重叠来进一步优化。如果它们不重叠，则返回 false。这避免了对那些矩形边界不重叠（即它们彼此之间不接近）的圆进行乘法运算。相对于乘法，矩形边界计算中的加法/减法更便宜。

这是 Java 2D 使用的模式。请参见 Shape.getBounds()。

- Steve Kuo

---

我认为边界计算会失去大部分的优势。但是你为什么不试一下并发布结果呢？ - Michael Myers

Answer 6

这并不会让你的代码更快，但我更喜欢：

return a > (dx*dx + dy*dy);

- Peter