Détection de collision rapide

Je suis en train d'écrire une méthode qui permettra de calculer si les deux cercles se chevauchent. Je suis venu avec le suivant et je suis juste curieux de savoir si il est de toute façon il pourrait être optimisée en outre.

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

source d'informationauteur Oli

  1. 21

    Hmm. Cela semble assez bien dans la mesure où le calcul. Quelques petits points sur la façon de faire la Java côté d'elle la plus rapide et terser:

    • Si vous avez utilisé doubles à la place de flotteurs pour les rayons, vous n'auriez pas à lancer le double de flotteurs.
    • Si vous demandez spécifiquement pour Point2D.Double paramètres, vous pouvez utiliser leurs x et y des champs publics au lieu d'utiliser les accesseurs.
    • Aussi, pourquoi le if (foo) { return true; } else { return false; }? il suffit de ne return foo;!

    Une version améliorée, alors:

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

    (Notez que si votre code est entièrement flotteur de base, vous pouvez faire la même chose avec Point2D.Float et floats.)

  2. 9

    Se chevauchent ou se croisent?

    Si se croisent, ne pas oublier le cas où les cercles ne se coupent parce qu'ils sont à l'intérieur les uns des autres.

    Si c'est le chevauchement, je ne vois vraiment pas comment vous pouvez optimiser davantage; vous êtes en comparant le point de distances à la somme des rayons, en utilisant le carré de la distance pour éviter de prendre une racine carrée. Ne semble pas comme il y a de la graisse de gauche à garniture.

  3. 6

    Avez-vous vraiment besoin pour répondre à d'éventuelles Point2D mise en œuvre? Si vous n'avez pas, il vous fera économiser un appel virtuel:

    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);
}
    tests de 1000x1000 points: 
Ne rien faire a fallu 6 ms 
Faire isCollision passant Point2D.Flotteur a eu 128 ms 
Faire isCollision passant Point2D.Double a pris 127 ms 
Faire isCollisionFloat a eu 71 ms 
Faire isCollisionDouble a pris 72 ms

    Si vous le pouvez, choisir l'un ou l'autre, plutôt que de la restauration pour les deux.

    Le problème avec les perf des questions, c'est que vraiment vous n'avez pas à mesurer les effets, par laquelle quelqu'un a posté la même réponse que la non prise en charge de l'opinion.

  4. 3

    Je ne sais pas si sa pertinent dans votre cas, mais si vous souhaitez vérifier les chevauchements entre votre cercle d'amis et beaucoup d'autres cercles (disons des milliers de cercles), vous pouvez essayer d'organiser vos cercles en quad-arbres (voir http://en.wikipedia.org/wiki/Quadtree) et de faire un arbre de recherche (basé sur le rectangle de délimitation de votre cercle) dans le processeur quad-tree.

  5. 2

    Votre algorithme peut être optimisée par le calcul des limites rectangulaires de chaque cercle et de voir si elles se chevauchent. Si elles ne se chevauchent pas puis il suffit de retourner false. Cela évite la multiplication de ces milieux, qui est rectangulaire limites ne se chevauchent pas (c'est à dire, ils ne sont pas proches les uns des autres). Addition/soustraction de l'rectangulaire lié calcul est moins cher que la multiplication.

    C'est le modèle que Java 2D utilise. Voir Forme.getBounds()

  6. 1

    Il n'est pas de rendre votre code plus rapide, mais je préfère:

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