Quadtree con duplicados

Estoy implementando un quadtree. Para aquellos que no conocen esta estructura de datos, incluyo la siguiente pequeña descripción:

Un Quadtree es una estructura de datos y está en el plano euclídeo lo que es un Octree en un espacio tridimensional. Un uso común de los quadtrees es la indexación espacial.

Para resumir cómo funcionan, un quadtree es una colección, digamos de rectángulos aquí, con una capacidad máxima y un cuadro delimitador inicial. Cuando se trata de insertar un elemento en un árbol cuádruple que ha alcanzado su capacidad máxima, el árbol cuadriculado se subdivide en 4 cuadrados (una representación geométrica que tendrá un área cuatro veces menor que el árbol antes de la inserción); cada elemento se redistribuye en los subárboles según su posición, es decir. el límite superior izquierdo al trabajar con rectángulos.

Por lo tanto, un árbol cuádruple es una hoja y tiene menos elementos que su capacidad, o un árbol con 4 cuadrúpedos como niños (por lo general, noroeste, noreste, sudoeste, sudeste).

Mi preocupación es que si intentas agregar duplicados, puede ser el mismo elemento varias veces o varios elementos diferentes con la misma posición, los cuadrúteros tienen un problema fundamental con el manejo de los bordes.

Por ejemplo, si trabaja con un quadtree con una capacidad de 1 y el rectángulo unitario como el cuadro delimitador:

[(0,0),(0,1),(1,1),(1,0)]

E intente insertar dos veces un rectángulo cuyo límite superior izquierdo sea el origen: (o de manera similar si intenta insertarlo N + 1 veces en un quadtree con una capacidad de N> 1)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

El primer inserto no será un problema:

Pero la primera inserción activará una subdivisión (porque la capacidad es 1):

Ambos rectángulos se colocan en el mismo subárbol.

Por otra parte, los dos elementos llegarán al mismo árbol cuádruple y desencadenarán una subdivisión ...

Y así sucesivamente, el método de subdivisión se ejecutará indefinidamente porque (0, 0) siempre estará en el mismo subárbol de los cuatro creados, lo que significa que se produce un problema de recursión infinita.

¿Es posible tener un quadtree con duplicados? (Si no, uno puede implementarlo como a Set)

¿Cómo podemos resolver este problema sin romper por completo la arquitectura de un quadtree?

Está implementando una estructura de datos, por lo que debe tomar decisiones de implementación.

A menos que el quadtree tenga algo específico que decir sobre la unicidad, y no sé si lo tiene, esta es una decisión de implementación. Es ortogonal a la definición de un árbol cuádruple y puede elegir manejarlo como lo desee. El quadtree le indica cómo insertar y actualizar claves, pero no si tienen que ser únicas o qué puede adjuntar a cada nodo.

Tomar decisiones de implementación no es reinventar la rueda , al menos no más que escribir su propia implementación en primer lugar.

A modo de comparación, la biblioteca estándar de C ++ ofrece un conjunto único, un conjunto múltiple no único, un mapa único (esencialmente un conjunto de pares clave-valor ordenados y comparados solo por la clave) y un mapa múltiple no único. Todos se implementan típicamente usando el mismo árbol rojo-negro y ninguno está rompiendo la arquitectura , simplemente porque la definición del árbol rojo-negro no tiene nada que decir sobre la unicidad de las claves o los tipos almacenados en los nodos hoja.

Finalmente, si crees que hay investigaciones sobre esto, encuéntralo y luego podemos discutirlo. Tal vez haya pasado por alto alguna invariante quadtree, o alguna restricción adicional que permita un mejor rendimiento.

Creo que hay una mala interpretación aquí.

Según tengo entendido, cada nodo quadtree contiene un valor indexado por un punto. En otras palabras, contiene el triple (x, y, valor).

También contiene 4 punteros a nodos secundarios, que pueden ser nulos. Existe una relación algorítmica entre las claves y los enlaces secundarios.

Tus inserciones deberían verse así.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

La primera inserción crea un nodo (principal) e inserta un valor en él.

La segunda inserción crea un nodo hijo, se vincula a él e inserta un valor en él (que puede ser el mismo que el primer valor).

El nodo secundario que se instancia depende del algoritmo. Si el algoritmo tiene la forma [x) y el espacio de coordenadas se encuentra en el rango [0,1), cada elemento secundario abarcará el rango [0,0.5) y el punto se colocará en el elemento secundario NO.

No veo una recursión infinita.

La resolución común que he encontrado (en problemas de visualización, no en juegos) es deshacerse de uno de los puntos, ya sea siempre reemplazando o nunca reemplazando.

Supongo que el punto principal a favor es que es fácil de hacer.

Supongo que está indexando elementos que tienen aproximadamente el mismo tamaño, de lo contrario la vida se vuelve compleja, lenta o ambas ...

Un nodo Quadtree no necesita tener una capacidad fija. La capacidad se utiliza para

• Permita que cada nodo del árbol tenga un tamaño fijo en la memoria o en el disco , no es necesario si el nodo del árbol contiene un conjunto de elementos de tamaño variable y está utilizando un sistema de asignación de espacio que hace frente. (Por ejemplo, java / c # objetos en la memoria).
• Decide cuándo dividir un nodo.
  • Simplemente podría redefinir la regla, de modo que un nodo se divida si contiene más de "n" elementos de distrito, donde el distrito se define de acuerdo con la ubicación de los elementos.
  • O utilice un " elemento compuesto ", de modo que si hay elementos de multiplicación en la misma ubicación, introduce un nuevo elemento que contiene una lista de estos elementos de multiplicación.

Cuando se trata de problemas de indexación espacial, en realidad recomiendo comenzar con un hash espacial o mi favorito personal: la cuadrícula antigua simple.

... y entienda sus debilidades primero antes de pasar a estructuras de árbol que permitan representaciones dispersas.

Una de las debilidades obvias es que podría estar desperdiciando memoria en muchas celdas vacías (aunque una cuadrícula implementada decentemente no debería requerir más de 32 bits por celda a menos que tenga miles de millones de nodos para insertar). Otra es que si tiene elementos de tamaño moderado que son más grandes que el tamaño de una celda y a menudo abarcan, por ejemplo, docenas de celdas, puede desperdiciar mucha memoria insertando esos elementos de tamaño mediano en muchas más celdas de lo ideal. Del mismo modo, cuando realiza consultas espaciales, es posible que tenga que verificar más celdas, a veces mucho más, de lo ideal.

Pero lo único que es preciso con una cuadrícula para que sea lo más óptimo posible contra una determinada entrada es cell size, lo que no te deja con demasiado para pensar y jugar, y es por eso que es mi estructura de datos de acceso para problemas de indexación espacial hasta que encuentre razones para no usarlo. Es muy simple de implementar y no requiere que juegues con nada más que una sola entrada de tiempo de ejecución.

Puede sacar mucho provecho de una cuadrícula antigua simple y, de hecho, he superado muchas implementaciones de árbol cuádruple y árbol kd utilizadas en software comercial al reemplazarlas por una cuadrícula antigua simple (aunque no fueron necesariamente las mejores implementadas , pero los autores pasaron mucho más tiempo que los 20 minutos que pasé para crear una cuadrícula). Aquí hay una pequeña cosa rápida que preparé para responder una pregunta en otro lugar usando una cuadrícula para la detección de colisiones (ni siquiera realmente optimizada, solo unas pocas horas de trabajo, y tuve que pasar la mayor parte del tiempo aprendiendo cómo funciona la búsqueda de caminos para responder la pregunta y también fue la primera vez que implementé la detección de colisión de este tipo):

Otra debilidad de las cuadrículas (pero son debilidades generales para muchas estructuras de indexación espacial) es que si inserta muchos elementos coincidentes o superpuestos, como muchos puntos con la misma posición, se insertarán en las mismas celdas ) y degradar el rendimiento al atravesar esa celda. Del mismo modo, si inserta una gran cantidad de elementos masivos que son mucho, mucho más grandes que el tamaño de la celda, querrán insertarse en una gran cantidad de celdas y usar mucha memoria y degradar el tiempo requerido para consultas espaciales en todos los ámbitos. .

Sin embargo, estos dos problemas inmediatos anteriores con elementos coincidentes y masivos son realmente problemáticos para todas las estructuras de indexación espacial. La cuadrícula antigua simple en realidad maneja estos casos patológicos un poco mejor que muchos otros, ya que al menos no quiere subdividir recursivamente las células una y otra vez.

Cuando comienza con la cuadrícula y avanza hacia algo como un árbol cuádruple o árbol KD, entonces el problema principal que desea resolver es el problema con los elementos que se insertan en demasiadas celdas, que tienen demasiadas celdas, y / o tener que verificar demasiadas celdas con este tipo de representación densa.

Pero si piensas en un árbol cuádruple como una optimización sobre una cuadrículapara casos de uso específicos, entonces ayuda seguir pensando en la idea de un "tamaño mínimo de celda", para limitar la profundidad de la subdivisión recursiva de los nodos de cuatro árboles. Cuando haces eso, el peor de los casos del árbol cuádruple se degradará en la cuadrícula densa en las hojas, solo que será menos eficiente que la cuadrícula, ya que requerirá tiempo logarítmico para avanzar de la raíz a la celda de la cuadrícula en lugar de tiempo constante Sin embargo, pensar en ese tamaño de celda mínimo evitará el escenario de bucle infinito / recursividad. Para los elementos masivos también hay algunas variantes alternativas, como los quad-árboles sueltos, que no necesariamente se dividen de manera uniforme y podrían tener AABB para los nodos secundarios que se superponen. Los BVH también son interesantes como estructuras de indexación espacial que no subdividen uniformemente sus nodos. Para elementos coincidentes contra estructuras de árbol, lo principal es simplemente imponer un límite a la subdivisión (o como lo sugirieron otros, simplemente rechazarlos, o encontrar una manera de tratarlos como si no estuvieran contribuyendo al número único de elementos en una hoja al determinar cuándo la hoja debería subdividirse). Un árbol Kd también podría ser útil si anticipa entradas con muchos elementos coincidentes, ya que solo necesita considerar una dimensión al determinar si un nodo debe dividirse en la mediana.