java - 快速圆碰撞检测

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;
}

Answer 1

唔。就数学而言，这看起来相当不错。关于如何使 Java 方面更快、更简洁的一些小问题：

• 如果您使用双精度数而不是浮点数作为半径，则不必将双精度数向下转换为浮点数。
• 如果您特别要求 Point2D.Double 参数，您可以使用它们的 x 和 y 公共字段而不是使用 getter。
• 另外，为什么if (foo) { return true; } else { return false; }?Just do 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.Floatand floats 做同样的事情。）

Answer 2

重叠还是相交？

如果相交，不要忘记圆圈不相交的情况，因为它们在彼此内部。

如果它是重叠的，我真的不知道如何进一步优化；您正在将点距离与半径之和进行比较，使用距离平方来避免取平方根。似乎没有任何脂肪可以修剪。

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 毫秒
执行 isCollision 传递 Point2D.Float 耗时 128 毫秒
执行 isCollision 传递 Point2D.Double 耗时 127 毫秒
执行 isCollisionFloat 耗时 71 毫秒
执行 isCollisionDouble 耗时 72 毫秒

如果可以，请选择其中之一，而不是同时满足两者。

---

性能问题的问题在于，您确实必须衡量效果，到那时有人发布了与不受支持的意见相同的答案。

Answer 4

我不知道它是否与您的情况相关，但如果您想检查您的圈子与许多其他圈子（假设有数千个圈子）之间的重叠，您可以尝试在四叉树中组织您的圈子（参见http: //en.wikipedia.org/wiki/Quadtree）并在四叉树中进行树查找（基于圆的边界矩形）。

Answer 5

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

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

Answer 6

它不会使您的代码更快，但我更喜欢：

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