¿Qué método se prefiere para almacenar objetos geométricos grandes en un árbol cuádruple?

15

Al colocar objetos geométricos en un quadtree (u octree), puede colocar objetos que son más grandes que un solo nodo de varias maneras:

  1. Colocando la referencia del objeto en cada hoja para la que está contenido
  2. Colocar la referencia del objeto en el nodo más profundo para el que está completamente contenido
  3. Ambos # 1 y # 2

Por ejemplo:

ingrese la descripción de la imagen aquí

En esta imagen, puede colocar el círculo en los cuatro nodos hoja (método # 1) o solo en el nodo raíz (método # 2) o en ambos (método # 3).

A los efectos de consultar el quadtree, ¿qué método es más común y por qué?

graphics data-structures computational-geometry nsantorello
fuente
1
Ciertamente debería ser una referencia. Tengo la intención de preguntar si, a los efectos de consultar el árbol cuádruple, debería haber referencias en las hojas, no hojas, o ambas.
nsantorello
PD Editado para, con suerte, aclarar las intenciones de la pregunta.
nsantorello
¿Cuál es la consulta que intentas admitir?
Joe
@Joe Estoy particularmente interesado en la detección de colisiones, la indexación espacial y el sacrificio de región / tronco.
nsantorello
1
@nsantorello La regla puede ser diferente dependiendo de cuáles de esas consultas desea admitir, pero esto parece muy relevante para la detección de colisiones: stackoverflow.com/questions/4434335/…
Joe

Respuestas:

8

Suponiendo que está almacenando una referencia, no el objeto en sí, puede tener sentido hacerlo de manera diferente dependiendo de su aplicación.

Por ejemplo, si estuviera calculando colisiones con este círculo (sólido) y la colisión ocurriera en la esquina inferior izquierda, sería más fácil si tuviera acceso a toda la geometría en esa hoja directamente desde esa hoja (método # 3) (sin tener que atravesar el árbol hacia arriba y determinar la geometría heredada). Pero, digamos que solo estaba usando cuadrúteros para dibujar geometría, querría usar el método n. ° 1, porque solo tiene sentido dibujar algo en el nodo para el que está completamente contenido (sería más difícil averiguar qué porción dibujar para cada nodo de hoja y dónde).

En cuanto a lo que es más común, mi única experiencia con los quadtrees es escribir una simulación de n cuerpos donde los objetos geométricos eran realmente puntos que no tenían área, por lo que definitivamente no puedo responder eso.

Rafe Kettler
fuente
Gracias Rafe, creo que tienes razón en que depende de la aplicación.
nsantorello
6

Una de las ventajas de un Quadtree es que no tiene que dividir un nodo en sus nodos secundarios si todos los nodos secundarios contendrían la misma información. Esto puede ahorrarle mucha memoria y acelerar el procesamiento.

Siguiendo este principio, creo que tiene más sentido almacenarlo solo en el nodo raíz (método # 2). Podría ahorrarle mucha memoria y creo que también facilitaría el procesamiento. Por ejemplo, si trató de encontrar intersecciones del círculo con una línea que pasa por tres de los nodos hoja, necesitaría calcular la intersección por separado para cada nodo hoja o recordar que ya se cruzó con este círculo.

Por otro lado, si tiene objetos en los nodos hoja, podría ayudarlo a eliminar los falsos positivos (objetos que debe verificar para la intersección, porque están en el nodo correcto, pero que en realidad no se cruzan).

Entonces, creo que ambos enfoques tienen sus usos y no estoy seguro de cómo elegir cuál usar.

Probablemente no usaría el enfoque # 3, porque no veo ningún aspecto positivo al respecto.

svick
fuente