En 2D, ¿cómo encuentro eficientemente el objeto más cercano a un punto?

35

Tengo un motor de juego considerable y me gustaría tener una función para encontrar la lista de puntos más cercana.

Simplemente podría usar el teorema de Pitágoras para encontrar cada distancia y elegir la mínima, pero eso requiere iterar a través de todas ellas.

También tengo un sistema de colisión, donde esencialmente convierto objetos en objetos más pequeños en una cuadrícula más pequeña (algo así como un minimapa) y solo si los objetos existen en el mismo espacio de cuadrícula, verifico si hay colisiones. Podría hacer eso, solo agrandar el espacio de la cuadrícula para verificar la cercanía. (En lugar de verificar cada objeto). Sin embargo, eso requeriría una configuración adicional en mi clase base y desordenaría el objeto ya desordenado. ¿Vale la pena?

¿Hay algo eficiente y preciso que pueda usar para detectar qué objeto está más cerca, en base a una lista de puntos y tamaños?

ultifinitus
fuente
Almacene versiones cuadradas de las posiciones x e y para que pueda hacer el teorema de Pitágoras sin tener que hacer el costoso sqrt al final.
Jonathan Connell
3
Esto se llama una búsqueda de vecino más cercano . Hay un montón de escritos en internet al respecto. La solución habitual es utilizar algún tipo de árbol de partición espacial .
BlueRaja - Danny Pflughoeft

Respuestas:

38

El problema con un quad / octree en las búsquedas de vecino más cercano es que el objeto más cercano puede estar sentado en la división entre nodos. Para colisiones, esto está bien, porque si no está en el nodo, no nos importa. Pero considere este ejemplo 2D con un quadtree:

Ejemplo de Quadtree

Aquí, aunque el elemento negro y el elemento verde están en el mismo nodo, el elemento negro está más cerca del elemento azul. La respuesta de ultifinitus solo puede garantizar al vecino más cercano, solo cada elemento de su árbol se coloca en el nodo más pequeño posible que pueda contenerlo, o en un nodo único, lo que conduce a un cuadrilátero más ineficiente. (Tenga en cuenta que hay muchas formas diferentes de implementar una estructura que podría denominarse quad / octree; las implementaciones más estrictas pueden funcionar mejor en esta aplicación).

Una mejor opción sería un árbol kd . Los árboles Kd tienen un algoritmo de búsqueda de vecino más cercano muy eficiente que puede implementar, y puede contener cualquier cantidad de dimensiones (de ahí las dimensiones "k").

Una gran e informativa animación de Wikipedia: Búsqueda de vecino más cercano al árbol kd

El mayor problema con el uso de kd-trees, si no recuerdo mal, es que es más difícil insertar / eliminar elementos mientras se mantiene el equilibrio. Por lo tanto, recomendaría usar un árbol kd para objetos estáticos como casas y árboles que está altamente equilibrado, y otro que contenga jugadores y vehículos, que necesita equilibrarse regularmente. Encuentre el objeto estático más cercano y el objeto móvil más cercano, y compare esos dos.

Por último, los árboles kd son relativamente simples de implementar, y estoy seguro de que puedes encontrar una gran cantidad de bibliotecas C ++ con ellos. Por lo que recuerdo, los árboles R son mucho más complicados, y probablemente exageren si todo lo que necesitas es una simple búsqueda del vecino más cercano.

dlras2
fuente
1
Gran respuesta, pequeño detalle "una garantía única para el vecino más cercano: solo todos los elementos de su árbol se colocan en el nodo más pequeño posible", quise decir en mi respuesta iterando sobre todos los elementos en los mismos nodos y vecinos, por lo que debe recorrer 10 en lugar de 10.000.
Roy T.
1
Muy cierto, supongo que "solo" era una palabra bastante dura. Definitivamente, hay formas de convencer a los quadtrees en las búsquedas de vecinos más cercanos dependiendo de cómo los implemente, pero si ya no los está utilizando por otras razones (como la detección de colisiones), me quedaría con el árbol kd más optimizado.
dlras2
Quería señalar que hice una implementación que se ocupa del problema negro verde azul. Revisa el fondo.
clankill3r
18

sqrt() es monótono, o preservar el orden, para argumentos no negativos, entonces:

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

Y viceversa.

Entonces, si solo desea comparar dos distancias pero no está interesado en sus valores reales, simplemente puede cortar el paso sqrt()de sus cosas de Pitágoras:

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

No es tan eficiente como el oct-tree, pero es más fácil de implementar y aumenta la velocidad al menos un poco

HumanCatfood
fuente
1
Esa métrica también se conoce como la distancia euclidiana al cuadrado .
moooeeeep
10

Tiene que hacer una partición espacial, en este caso crea una estructura de datos eficiente (generalmente un octree). En este caso, cada objeto está dentro de uno o más espacios (cubos). Y si sabe en qué espacios se encuentra, puede buscar O (1) qué espacios son sus vecinos.

En este caso, se puede encontrar el objeto más cercano iterando primero sobre todos los objetos en su propio espacio mirando cuál es el más cercano allí. Si no hay nadie allí, puede verificar a sus primeros vecinos, si no hay nadie, puede verificar a sus vecinos, etc.

De esta manera, puede encontrar fácilmente el objeto más cercano sin tener que recorrer todos los objetos de su mundo. Como de costumbre, esta ganancia de velocidad requiere un poco de contabilidad, pero es realmente útil para todo tipo de cosas, por lo que si tienes un gran mundo definitivamente vale la pena implementar la partición espacial y un octree.

Como de costumbre, vea también el artículo de Wikipedia: http://en.wikipedia.org/wiki/Octree

Roy T.
fuente
77
@ultifinitus Para agregar a esto: si su juego es 2D, puede usar QuadTrees en lugar de Octrees.
TravisG 01 de
1

Tal vez intente organizar sus datos espaciales en un RTree, que es como un btree para cosas en el espacio y permite consultas como "N vecinos más cercanos", etc ... http://en.wikipedia.org/wiki/Rtree

Patrick Hughes
fuente
0

Aquí está mi implementación de Java para obtener la más cercana de un quadTree. Se trata del problema que dlras2 está describiendo:

ingrese la descripción de la imagen aquí

Creo que la operación es realmente eficiente. Se basa en la distancia a un quad para evitar buscar en quads más allá del actual más cercano.

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

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;

}
clankill3r
fuente
PD: Todavía creo que es mejor usar un árbol kd o algo así, pero esto podría ayudar a las personas.
clankill3r
también mira esto: bl.ocks.org/llb4ll/8709363
clankill3r