Schnell Kreis Kollisionserkennung

Ich versuche zu schreiben, eine Methode, die berechnet, ob sich zwei Kreise überschneiden. Ich habe kommen mit dem folgenden, und ich bin nur neugierig zu wissen, ob es trotzdem, könnte es sein, weiter optimieren.

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

InformationsquelleAutor der Frage Oli | 2009-03-30

  1. 21

    Hmm. Das sieht ziemlich gut so weit wie die Mathematik geht. Einige kleinere Punkte auf, wie man die Java-Seite schneller und terser:

    • Wenn Sie doubles anstelle der Schwimmer für die Radien, die Sie nicht haben, um nach unten zu werfen die doubles zu floats.
    • Wenn Sie nicht ausdrücklich darum gebeten Point2D.Doppelklicken Sie Parameter, die Sie verwenden können, Ihre x-und y-public-Felder anstelle der Verwendung der Getter.
    • Auch, warum die if (foo) { return true; } else { return false; }? Nur tun return foo;!

    Einer verbesserten version, dann:

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

    (Beachten Sie, wenn Ihr code ist ganz float-Basis, Sie können das gleiche tun mit Point2D.Float und floats).

    InformationsquelleAutor der Antwort Zarkonnen

  2. 9

    Überlappen oder schneiden?

    Wenn schneiden, vergessen Sie nicht über den Fall, wo die Kreise sich nicht überschneiden, weil Sie in jedem anderen.

    Wenn es überschneidungen, die ich nicht wirklich sehen, wie Sie konnte, optimieren Sie weiter; Sie sind zu vergleichen die Punkt-Abstände, die der Summe der Radien, mit Abstand quadriert, um zu vermeiden, eine Quadratwurzel. Scheint nicht, wie es keine Fetten Links zu trimmen.

    InformationsquelleAutor der Antwort Jason S

  3. 6

    Tun, die Sie wirklich brauchen, um gerecht für alle möglichen Point2D Umsetzung? Wenn Sie nicht haben, wird es sparen Sie ein virtuelles call:

    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);
}
    testen 1000x1000 Punkte: 
Nichts zu tun, dauerte 6 ms 
Dabei isCollision vorbei Point2D.Schwimmer nahmen 128 ms 
Dabei isCollision vorbei Point2D.Doppel nahmen 127 ms 
Dabei isCollisionFloat nahm 71 ms 
Dabei isCollisionDouble nahm 72 ms

    Wenn Sie können, das eine oder andere entscheiden, anstatt catering für beide.

    Das problem mit perf Fragen ist, dass Sie wirklich tun müssen, Messen die Wirkungen, von denen mal jemand gepostet hat, die gleiche Antwort, wie nicht unterstützte Meinung.

    InformationsquelleAutor der Antwort Pete Kirkham

  4. 3

    Ich weiß nicht ob das relevant ist in Ihrem Fall, aber wenn Sie überprüfen möchten, um überlappungen zwischen Ihrem Kreis und viele andere Kreisen (sagen wir mal Tausende von Kreisen), Sie können versuchen, Sie zu organisieren Sie Ihre Kreise im quad-trees (siehe http://en.wikipedia.org/wiki/Quadtree) und eine Baum-look-up (basierend auf dem Begrenzungsrechteck Ihre Kreis) im quad-Baum.

    InformationsquelleAutor der Antwort Patrick

  5. 2

    Ihren Algorithmus kann weiter optimiert werden durch die Berechnung der rechteckigen Grenzen der einzelnen Kreis und sehen, wenn Sie sich überschneiden. Wenn Sie nicht überlappen, dann nur false zurück. Dies vermeidet Multiplikation für diejenigen Kreise, die die rechteckigen Grenzen nicht überlappen (dh, Sie sind nicht nahe beieinander). Addition/Subtraktion für die rechteckige gebunden Berechnung günstiger ist als die Multiplikation.

    Dies ist das Muster, das Java-2D verwendet. Sehen Form.getBounds()

    InformationsquelleAutor der Antwort Steve Kuo

  6. 1

    Es nicht machen Ihren code schneller, aber ich würde bevorzugen:

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

    InformationsquelleAutor der Antwort Xn0vv3r

Schreibe einen Kommentar