Question 1

¿Qué es un quadtree y para qué sirve?

Accepted Answer

Un quadtree es una estructura de datos en forma de árbol que divide una región del plano en cuatro cuadrantes iguales (noroeste, noreste, suroeste y sureste). Cada nodo almacena hasta un número fijo de puntos llamado capacidad; cuando se supera, el nodo se subdivide en cuatro hijos y reparte sus puntos entre ellos. Sirve para acelerar consultas espaciales: en lugar de comparar un punto con todos los demás, solo se examinan los nodos de la zona relevante. Es muy habitual en videojuegos para la detección de colisiones y en sistemas de información geográfica (SIG).

Question 2

¿Cómo acelera un quadtree la detección de colisiones?

Accepted Answer

Comprobar colisiones comparando cada objeto con todos los demás cuesta O(n²): con 1.000 objetos son cerca de un millón de comprobaciones por fotograma. Un quadtree agrupa los objetos por zonas del espacio, así que cada objeto solo se compara con los que comparten su cuadrante o los vecinos. Esta fase de descarte rápido se llama broad-phase: reduce muchísimo el número de parejas candidatas antes de hacer la comprobación precisa. En la mayoría de los casos el coste baja a aproximadamente O(n log n).

Question 3

¿Qué es la capacidad de un nodo y cómo elegirla?

Accepted Answer

La capacidad es el número máximo de puntos que un nodo guarda antes de subdividirse. Con una capacidad muy baja (por ejemplo 1) el árbol se vuelve muy profundo y crea muchos nodos casi vacíos, lo que gasta memoria y obliga a recorrer más niveles. Con una capacidad muy alta cada nodo guarda demasiados puntos y se pierde la ventaja de la partición. Suelen funcionar bien valores de 4 a 8. En este visualizador puedes mover el slider de capacidad y ver cómo cambian el número de nodos y la profundidad del árbol.

Question 4

¿Qué es una consulta de rango en un quadtree?

Accepted Answer

Una consulta de rango busca todos los puntos que caen dentro de una región rectangular. El quadtree la resuelve de forma eficiente: si un nodo no se solapa con el rectángulo de búsqueda, se descarta entero junto con todos sus descendientes sin examinar sus puntos. Solo se desciende por las ramas que intersecan la zona consultada. Por eso un quadtree visita muchos menos nodos que comprobar uno por uno todos los puntos (fuerza bruta), y la diferencia crece a medida que hay más puntos en el espacio.

Question 5

¿Cuál es la diferencia entre un quadtree y un octree?

Accepted Answer

Son la misma idea en distinta dimensión. El quadtree trabaja en 2D y divide cada región en 4 cuadrantes. El octree es su equivalente en 3D: divide cada caja en 8 octantes. Se usa un quadtree para juegos en 2D, mapas y tiles, y un octree para mundos 3D, motores de física, renderizado de voxels o nubes de puntos. También existen alternativas como la rejilla uniforme (grid) y el árbol k-d, cada uno con ventajas según la distribución de los objetos.

Visualizador de Quadtree

1. Elige qué hacer con el ratón

2. El quadtree

3. Ajusta y experimenta

4. Estado del árbol

📚Guía del Quadtree (Partición Espacial)

🔗Apps relacionadas