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

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 его быстрее и terser:

• Если вы использовали двойники вместо поплавков для радиусов, то не было бы вниз отливки двойники к поплавкам.
• Если вы задаете параметры 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 с)

Answer 2

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

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

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

Answer 3

Это Безразлично не делайте свой код быстрее, но я бы предпочел:

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

Answer 4

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

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

---

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

Answer 5

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

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

Answer 6

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