Быстрое обнаружение столкновения окружности - PullRequest
Новая
       6

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

14 голосов
/ 30 марта 2009

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

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

Ответы [ 6 ]

21 голосов
/ 30 марта 2009

Хм. Это выглядит довольно хорошо, насколько математика идет. Некоторые незначительные замечания о том, как сделать Java-версию более быстрой и краткой:

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

9 голосов
/ 30 марта 2009

Перекрываются или пересекаются?

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

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

6 голосов
/ 30 марта 2009

Вам действительно нужно обслуживать любую возможную реализацию 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

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

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

3 голосов
/ 14 февраля 2010

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

2 голосов
/ 30 марта 2009

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

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

1 голос
/ 30 марта 2009

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

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