En 2D, comment trouver efficacement l’objet le plus proche d’un point?

J'ai un moteur de jeu assez important et j'aimerais une fonctionnalité permettant de trouver le plus proche d'une liste de points.

Je pourrais simplement utiliser le théorème de Pythagore pour trouver chaque distance et choisir la distance minimale, mais cela nécessite une itération complète.

J'ai également un système de collision, où je transforme essentiellement des objets en objets plus petits sur une grille plus petite (un peu comme une mini-carte) et si des objets existent dans le même espace quadrillé, je vérifie les collisions. Je pouvais le faire, augmentant l’espacement de la grille pour vérifier la proximité. (Plutôt que de vérifier chaque objet.) Cependant, cela prendrait une configuration supplémentaire dans ma classe de base et encombrerait l'objet déjà encombré. Est-ce que ça vaut le coup?

Y at-il quelque chose d’efficace et de précis que je pourrais utiliser pour détecter l’objet le plus proche, sur la base d’une liste de points et de tailles?

Le problème avec un quad / octet dans les recherches du voisin le plus proche est que l'objet le plus proche peut se trouver juste au-delà de la division entre les nœuds. Pour les collisions, ça va, car si ce n'est pas dans le nœud, on s'en fiche. Mais considérons cet exemple 2D avec un quadtree:

Ici, même si l'élément noir et l'élément vert se trouvent dans le même nœud, l'élément noir est le plus proche de l'élément bleu. La réponse d’ultifinitus ne peut garantir que chez le voisin le plus proche, seul chaque élément de votre arborescence est placé dans le plus petit nœud possible pouvant le contenir, ou dans un nœud unique, ce qui conduit à des quadtrees plus inefficaces. (Notez qu'il existe de nombreuses façons d'implémenter une structure qui pourrait être appelée quad / octree - des implémentations plus strictes pourraient mieux fonctionner dans cette application.)

Une meilleure option serait un kd-tree . Les Kd-trees ont un algorithme de recherche très efficace que vous pouvez implémenter et peuvent contenir un nombre quelconque de dimensions (donc "k").

Une animation fantastique et informative de Wikipedia:

Si je me souviens bien, le plus gros problème lié à l’utilisation des kd-trees est qu’ils sont plus difficiles à insérer / supprimer tout en maintenant l’équilibre. Par conséquent, je recommanderais d'utiliser un arbre kd pour les objets statiques tels que les maisons et les arbres, qui est très équilibré, et un autre qui contient des joueurs et des véhicules, qui doivent être équilibrés régulièrement. Recherchez l'objet statique le plus proche et l'objet mobile le plus proche, puis comparez-les.

Enfin, les kd-trees sont relativement simples à implémenter, et je suis sûr que vous pourrez y trouver une multitude de bibliothèques C ++. D'après ce que je me souviens, les R-arbres sont beaucoup plus compliqués et probablement exagérés si tout ce dont vous avez besoin est une simple recherche du plus proche voisin.

sqrt() est monotone, ou préservant l'ordre, pour les arguments non négatifs, ainsi:

sqrt(x) < sqrt(y) iff x < y

Et vice versa.

Donc si vous voulez seulement comparer deux distances mais que leurs valeurs réelles ne vous intéressent pas, vous pouvez simplement couper le pas sqrt()de votre truc de Pythagore:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)²
pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)²
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Ce n'est pas aussi efficace que l'octogone, mais c'est plus facile à implémenter et ça augmente la vitesse au moins un peu

Vous devez faire un partitionnement spatial, dans ce cas, vous créez une structure de données efficace (généralement un octree). Dans ce cas, chaque objet se trouve dans un ou plusieurs espaces (cubes). Si vous savez dans quels espaces vous êtes, vous pouvez rechercher O (1) quels espaces sont vos voisins.

Dans ce cas, l'objet le plus proche peut être trouvé en parcourant d'abord tous les objets de votre propre espace en cherchant lequel est le plus proche. S'il n'y a personne, vous pouvez vérifier vos premiers voisins. S'il n'y a personne, vous pouvez vérifier leurs voisins, etc.

De cette façon, vous pouvez facilement trouver l'objet le plus proche sans avoir à parcourir tous les objets de votre monde. Comme d'habitude, ce gain de vitesse nécessite un peu de comptabilité, mais il est vraiment utile pour toutes sortes de choses, donc si vous avez un monde immense, il vaut vraiment la peine de mettre en œuvre un partitionnement spatial et un octree.

Comme d'habitude, voir aussi l'article de Wikipédia: http://en.wikipedia.org/wiki/Octree

Essayez peut-être d’organiser vos données spatiales dans un RTree, ce qui est un peu comme un arbre pour des éléments dans l’espace et permet des requêtes telles que "N voisins les plus proches", etc ... http://en.wikipedia.org/wiki/Rtree

Voici mon implémentation Java pour obtenir le plus proche d'un quadTree. Il traite du problème que dlras2 décrit:

Je pense que l'opération est vraiment efficace. Il est basé sur la distance à un quad pour éviter de chercher dans les quads plus loin que le courant le plus proche.

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}