¿Cómo funcionan las formas (rectángulos) en árboles cuádruples?

10

Me han dicho que un árbol cuádruple es la estructura de datos ideal para mi juego, pero tengo problemas para entender cómo funcionan exactamente las formas dentro de los árboles cuádruples.

Estoy haciendo esto en JavaScript, pero creo que estas preguntas podrían aplicarse a los árboles cuádruples en cualquier idioma.

Creo que entiendo principalmente cómo funcionan los puntos básicos (x, y) y la inserción de puntos en los árboles cuádruples, y que podría hacerlo en papel.

Aquí hay un JSfiddle de mi experimentación con puntos.

puntos de árbol cuádruple

Aparte de un caso, mis pruebas con puntos funcionan como se esperaba.

Pero mi confusión comienza cuando están involucradas formas como rectángulos. Cuando está recuperando de un árbol cuádruple con formas, ¿verifica cada punto de la forma y en qué nodos caen? ¿Y cómo funcionan incluso las inserciones de formas, cuando acepta parámetros (x, y, ancho, alto) para cada forma? ¿Utiliza el ancho / alto desde el punto de partida para calcular otros puntos de esquina, que luego se distribuyen en los nodos apropiados? Si una forma insertada se extiende en cuatro nodos, ¿se guardan los datos de esa forma en los cuatro nodos?

Y cuando un método de recuperación acepta una forma como parámetro (x, y, ancho, alto), ¿qué está pasando realmente? ¿Es primero ver a qué nodos abarcaría la forma si se insertara y luego recuperar todos los objetos de esos nodos?

Tengo un JSfiddle que trabaja con formas , pero estoy completamente confundido con los resultados de mis pruebas. ¡Me devuelven objetos duplicados!

formas de árboles cuádruples

Por ejemplo, el cuadrado rojo es un equivalente dibujado de los parámetros que estoy ingresando en mi método de recuperación. ¡Creo que, dado que este cuadrado rojo abarca los cuatro nodos, debería devolver cada objeto en el árbol cuádruple! Pero no lo hace, y estoy teniendo problemas para racionalizar lo que devuelve. Tengo una serie de otras pruebas que actualmente están comentadas, pero puedes descomentarlas y ejecutarlas para ver resultados más confusos.

Como digo, si quiero devolver todos los puntos en un árbol cuádruple, ¿cómo lo haría? ¿Un método de recuperación usando una forma del tamaño completo de los límites? Por ejemplo, recuperar (0, 0, canvas.width, canvas.height)?

La biblioteca de JavaScript árbol cuádruple estoy usando ha sido mencionado por varias otras fuentes, así que supongo que la implementación real es correcta y de buena reputación.

Creo que gran parte de mi confusión puede deberse a un malentendido de la terminología del árbol cuádruple. Por ejemplo, ¿por qué dicen límites en lugar de dimensiones, cuando un "punto" también tiene parámetros de ancho / alto? ¿Es una cuestión de convención / abreviatura, o son conceptos completamente diferentes?

¡Gracias por tu tiempo!

usuario2736286
fuente
Se almacenan en el árbol cuádruple de forma normal, por su posición. Por lo general, esos están en el centro, pero pueden estar en la esquina como usted lo ha definido. Su pregunta puede ser un duplicado de esta: QuadTree: ¿almacenar solo puntos o regiones?
MichaelHouse
He leído esa pregunta, pero aún no entiendo completamente las respuestas :(. "Debe almacenarla en el nodo más pequeño que la contenga por completo, incluso si esto excede la capacidad (use un contenedor de tamaño variable)". dice que el nodo más pequeño que lo contiene COMPLETAMENTE, si el objeto es muy grande, ¿ese nodo no sería a menudo un nodo no hoja? ¿Como en un nodo superior que consiste en solo otros nodos? Eso no parece correcto me, ya que eso significaría el nodo que contiene tendría 1 hoja y los 4 nodos más pequeños dentro de ella.
user2736286
1
@ user2736286 Si observa el código de la lib de quadtree (no es muy largo), puede ver que almacena rectángulos en nodos de nivel superior para evitar que se extiendan entre los bordes de los nodos. Vea las referencias al _stuckChildrencampo en el código. También puede ver esto en la muestra de "recuperación de elementos con límites": siempre resalta en rojo los nodos que se extienden a horcajadas en los bordes de los nodos en los que hizo clic, hasta el nodo raíz.
Nathan Reed
@ user2736286 Además, la lib de quadtree parece tener un error al recuperar elementos con límites: si le da una consulta rect que se extiende a ambos lados de los bordes de los nodos, no devuelve todos los rect en los nodos que toca la consulta. También puede ver esto fácilmente en la "recuperación de elementos con límites", haciendo clic cerca de los bordes del nodo.
Nathan Reed
@NathanReed Anteriormente intenté comprender el código, pero no tengo la habilidad suficiente para entenderlo sin una base conceptual. Gracias al pseudocódigo de John McDonald, ahora entiendo cómo se insertan los rectángulos en los nodos, pero creo que todavía no tengo claro cómo funciona la recuperación. En cuanto a la "recuperación de elementos con límites", estoy completamente confundido por el ejemplo. Por ejemplo, cuando hago clic en un rect que encaja perfectamente en uno de los nodos más pequeños, ¿por qué también se resaltan todos estos otros rectificadores fuera de ese nodo?
user2736286

Respuestas:

10

Los quadtrees generalmente almacenan y recuperan rectángulos. Un punto es un caso específico donde el ancho y la altura son cero. La siguiente lógica se utiliza para encontrar el hogar de nuevos rectángulos en el árbol, comenzando con el nodo raíz:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Tenga en cuenta que los rectángulos se pueden almacenar a cualquier profundidad, no tiene que ser un quad de hoja. Si el rectángulo se extiende a ambos lados del límite en el nivel raíz, el quad raíz almacenará el rectángulo.

Por ejemplo, el cuadrado rojo es un equivalente dibujado de los parámetros que estoy ingresando en mi método de recuperación. ¡Creo que, dado que este cuadrado rojo abarca los cuatro nodos, debería devolver cada objeto en el árbol cuádruple! Pero no lo hace, y estoy teniendo problemas para racionalizar lo que devuelve.

Al consultar el quadtree, solo devolverá los rectángulos que contiene la consulta. En su ejemplo, obliga a que cada uno de los 4 quads secundarios se mire con más detalle porque el rectángulo de consulta rojo cruza cada quad secundario. Como los niños no tienen más hijos, cada uno de los rectángulos en estos quads infantiles se comparará con el rectángulo rojo. Como ninguno de los rectángulos del árbol choca con el rectángulo rojo de consulta, no se debe devolver nada.

Realmente comienzas a ver los beneficios de los árboles cuádruples cuando tienes muchos objetos y mucho espacio para que existan los objetos en comparación con el área o áreas de consulta. En estos casos, un área de consulta pequeña puede eliminar rápidamente grandes porciones del árbol cuádruple de la consideración. Solo los quads que se cruzan con el rectángulo de consulta se verán con más detalle.

EDITAR

La recuperación generalmente se realiza de la siguiente manera:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

Sin embargo, en su biblioteca, no parece verificar si los rectángulos que está regresando se cruzan con la consulta, por lo que deberá agregarlo usted mismo.

John McDonald
fuente
Después de mirar su biblioteca con más detalle, su biblioteca está devolviendo una lista de todos los posibles candidatos de colisión para el rectángulo de consulta que especifique. Parece que es su trabajo comparar su rectángulo de consulta con cada candidato para ver si hay una colisión real. La mayoría de las bibliotecas hacen el último paso por usted y solo devuelven las colisiones reales con el área de consulta. Entonces, todo lo que necesita hacer es agregar algo de lógica en su retrievemétodo para podar la lista. Puedes ver lo que está haciendo un poco más claramente aquí: mikechambers.com/html5/javascript/QuadTree/examples/…
John McDonald
1
@ user2736286 En caso de que no lo haya detectado, es importante tomar nota de la recurrencia en las funciones de consulta y almacenamiento que JohnMcDonald escribió. No tendrá mucho sentido si no entiendes esa parte. Para ambos, cada recursión se profundiza en el árbol, es decir, en las ramas y finalmente en las hojas.
TASagent
Gracias John, tu pseudocódigo es muy útil. Cuando dice "if (queryRect se cruza con los límites childNode)", ¿eso significa básicamente si queryRect está contenido dentro de los límites, parcial o totalmente? Solo quiero ser 100% claro. Además, en el ejemplo "Recuperar elemento por límites" que se analiza, tengo una imagen del resultado de mi clic. Pic El punto azul es donde hice clic. Entonces, ¿por qué no solo se resaltan los dos rectanges dentro de ese nodo? ¿Por qué también se resaltan los rectángulos alejados? Creo que eso es lo que realmente me confunde.
user2736286
Parcial o completo. Si los dos se tocan, o cualquiera de ellos está completamente contenido por el otro. Desea leer el wiki en Quadtrees , pero he tomado su foto y la he codificado por colores para representar los diferentes límites secundarios. Todos los rectángulos azules se cruzan con los límites de los primeros quads secundarios, luego el magenta es una capa más profunda y el verde una capa más profunda aún. Los rectángulos rojos se cruzan con el quad en el que se hace clic. Su biblioteca devuelve todos los rectificadores en los límites secundarios más todos los contenidos en el último cuadrante
John McDonald
Ok, hice todo lo posible para repasar el código fuente de la biblioteca y finalmente entiendo el comportamiento de los Niños atrapados, y que todos esos rectificadores adicionales en mi foto son simplemente los Niños atrapados. Originalmente pensé que cualquier rectificación que abarque múltiples nodos solo tendría sus datos duplicados e insertados en cada nodo más pequeño. Ahora me doy cuenta de que stuckChildren no se inserta en los nodos que abarca, sino que simplemente permanece en el único nodo que lo contiene, por lo que también tengo que verificar todos los nodos principales, y no solo el nodo más pequeño que contiene mi consulta rect. Gracias por la foto; tiene mucho más sentido ahora :)
user2736286