Быстрое обнаружение столкновений

Я пытаюсь написать метод, который будет вычислять, если два круга перекрываются. Я придумал следующее, и мне просто интересно узнать, есть ли в дальнейшем его можно оптимизировать.

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

Ответы

Ответ 1

Хм. Это выглядит довольно хорошо, насколько математика идет. Некоторые второстепенные моменты о том, как ускорить и упростить сторону Java:

Если вы использовали удвоения вместо поплавков радиусов, вам не пришлось бы опускать дубли для плавания.
Если вы специально задаете параметры Point2D.Double, вы можете использовать свои общедоступные поля x и y вместо использования геттеров.
Кроме того, почему 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.Float и float s.)

Ответ 2

Перекрыть или пересечь?

Если пересекаться, не забывайте о случае, когда круги не пересекаются, потому что они находятся внутри друг друга.

Если он перекрывается, я не вижу, как вы могли бы оптимизировать дальше; вы сравниваете точки расстояния до суммы радиусов, используя квадрат расстояния, чтобы избежать квадратного корня. Кажется, что нет жира, оставшегося для обрезки.

Ответ 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);
}

testing 1000x1000 points:
Doing nothing took 6 ms
Doing isCollision passing Point2D.Float took 128 ms
Doing isCollision passing Point2D.Double took 127 ms
Doing isCollisionFloat took 71 ms
Doing isCollisionDouble took 72 ms

Если вы можете, выберите тот или иной, а не обедать.

Проблема с первыми вопросами заключается в том, что вам действительно нужно измерять эффекты, и к тому времени кто-то отправил тот же ответ, что и неподтвержденное мнение.

Ответ 4

Я не знаю, соответствует ли это вашему делу, но если вы хотите проверить наложение совпадений между вашим кругом и многими другими кругами (допустим, тысячи кругов), вы можете попытаться организовать круги в квадроциклах ( см. http://en.wikipedia.org/wiki/Quadtree) и выполните поиск по дереву (на основе ограничивающего прямоугольника вашего круга) в квадратном дереве.

Ответ 5

Ваш алгоритм может быть дополнительно оптимизирован путем вычисления прямоугольных границ каждого круга и наблюдения, если они перекрываются. Если они не перекрываются, просто верните false. Это позволяет избежать умножения для тех кругов, которые прямоугольные границы не перекрываются (т.е. Они не близки друг к другу). Сложение/вычитание для вычисления прямоугольной границы дешевле, чем умножение.

Это шаблон, который использует Java 2D. См. Shape.getBounds()

Ответ 6

Это не делает ваш код быстрее, но я бы предпочел:

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