meskeIA

Visualizador de Quadtree

Partición espacial paso a paso: cómo un quadtree divide el espacio en cuadrantes para acelerar las colisiones y las consultas de rango en videojuegos

© 2026 meskeIA© 2026

1. Elige qué hacer con el ratón

2. El quadtree

Haz clic o arrastra sobre el lienzo para añadir puntos. Cuando un nodo supera la capacidad, se subdivide en 4 cuadrantes (NO, NE, SO, SE) y reparte sus puntos.
Punto Dentro del rango Subdivisión Rango de consulta

3. Ajusta y experimenta

Capacidad baja → árbol más profundo y más nodos. Capacidad alta → menos subdivisión.

4. Estado del árbol

Puntos0
Nodos del árbol1
Profundidad máxima0
Cambia al modo Consultar rango y arrastra un rectángulo sobre el lienzo para comparar el quadtree con la fuerza bruta.

Guía del Quadtree (Partición Espacial)

Cómo dividir el espacio en cuadrantes acelera las colisiones y las consultas espaciales

Quadtree frente a otras formas de buscar en el espacio

EnfoqueCoste de consultar colisionesSe adapta a puntos agrupadosCuándo conviene
Fuerza brutaO(n²): cada objeto contra todosNoMuy pocos objetos o pruebas rápidas
Rejilla uniformeRápida si los objetos están repartidosMal: celdas vacías o saturadas si se agrupanObjetos de tamaño parecido y bien distribuidos
Quadtree≈ O(n log n) en la mayoría de casosSí: subdivide solo donde hay densidadEscenas 2D con zonas más pobladas que otras
Árbol k-d≈ O(log n) por consultaSí, divide por mediana en cada ejeConjuntos estáticos y vecino más cercano

Dónde se usa la partición espacial

Colisiones en videojuegos (broad-phase)

En un juego con cientos de balas, enemigos y obstáculos, comparar todos contra todos es inviable. El quadtree agrupa por zonas y solo compara objetos que comparten cuadrante: es el primer filtro rápido antes de la comprobación precisa.

Si los objetos se mueven cada fotograma, el árbol se reconstruye o se actualiza en cada frame.

Consultas espaciales en mapas y SIG

«¿Qué tiendas hay en esta zona del mapa?» o «¿qué marcadores caben en la vista actual?» son consultas de rango. Un quadtree descarta de golpe las regiones que no se solapan con el área visible.

Es la misma idea que usan los mapas web para mostrar solo los puntos del recuadro visible.

Compresión de imágenes

Un quadtree puede dividir una imagen en cuadrantes y dejar de subdividir donde el color es uniforme. Las zonas lisas quedan como un solo nodo grande y solo se detalla donde hay bordes, ahorrando datos.

Aquí el criterio para subdividir no es la cantidad de puntos, sino la variación de color.

Simulación de N cuerpos (Barnes-Hut)

Para simular la gravedad entre miles de estrellas, el algoritmo de Barnes-Hut usa un quadtree (u octree en 3D) para tratar grupos lejanos de cuerpos como una sola masa, bajando el coste de O(n²) a O(n log n).

Es uno de los usos más elegantes del quadtree fuera de los videojuegos.

Preguntas frecuentes

¿Por qué un quadtree es más rápido que comparar todos los puntos?

Porque agrupa los puntos por zonas del espacio. En una consulta de rango, si un nodo no se solapa con la región buscada, se descarta entero junto con todos sus descendientes, sin mirar ni uno de sus puntos. Así solo se examinan las ramas que tocan la zona, en lugar de recorrer la lista completa.

En esta app puedes ver «nodos visitados» frente a «comprobaciones por fuerza bruta»: cuantos más puntos haya, mayor es la diferencia.

¿En cuántas partes divide cada nodo?

Un quadtree divide siempre cada región en exactamente cuatro cuadrantes iguales: noroeste, noreste, suroeste y sureste. De ahí el «quad» del nombre. Su equivalente en tres dimensiones es el octree, que divide cada caja en ocho octantes.

Un quadtree sirve para juegos y mapas 2D; un octree, para mundos y físicas 3D.

¿Qué capacidad por nodo debo usar?

Depende de cuántos puntos manejes y de cómo estén repartidos. Una capacidad muy baja genera un árbol muy profundo con muchos nodos casi vacíos; una muy alta apenas subdivide y pierde la ventaja. Valores entre 4 y 8 suelen ir bien. Prueba el slider de esta app y observa cómo cambian los nodos y la profundidad.

No existe un valor universal: ajústalo midiendo el rendimiento con tus propios datos.

¿Qué pasa con los objetos que se mueven?

Cuando los objetos cambian de posición, el árbol deja de reflejar la realidad. Lo más sencillo es reconstruirlo entero cada fotograma; con muchos objetos es preferible actualizar solo los que han cambiado de cuadrante. Esa es una de las decisiones de diseño más importantes al usar quadtrees en un juego.

Reconstruir todo cada frame es válido si el número de objetos no es enorme.

¿Y los objetos que ocupan más de un cuadrante?

Un punto cae siempre en un único cuadrante, pero una caja o un círculo grande puede cruzar la frontera entre varios. Hay dos enfoques: guardar el objeto en el nodo padre que lo contiene por completo, o insertarlo en todos los hijos que toca (con cuidado de no contarlo dos veces). Esta app trabaja con puntos para centrarse en la idea base.

En motores reales se suele usar el rectángulo envolvente del objeto, no un punto.

¿Cuándo NO conviene un quadtree?

Si tienes muy pocos objetos, la fuerza bruta es más simple y rápida. Si los objetos están repartidos de forma uniforme y son de tamaño parecido, una rejilla fija suele rendir mejor y es más fácil de actualizar. El quadtree brilla cuando hay zonas mucho más pobladas que otras, porque subdivide solo donde hace falta.

Mide siempre: la estructura «teóricamente mejor» no siempre gana en tu caso concreto.

Cómo se inserta un punto y cuándo subdivide

1
¿El punto cae dentro del nodo?

Se comprueba si el punto está dentro del rectángulo que cubre el nodo. Si no lo está, ese nodo lo rechaza y la inserción continúa por otra rama.

2
¿Queda hueco en el nodo?

Si el nodo aún no se ha dividido y le caben más puntos (no llega a su capacidad), el punto se guarda ahí y termina la inserción.

3
Subdividir al llenarse

Si el nodo está lleno y todavía no tiene hijos, se subdivide en cuatro cuadrantes (NO, NE, SO, SE) y reparte entre ellos los puntos que ya tenía.

4
Bajar al cuadrante correcto

El nuevo punto se inserta en el hijo que lo contiene. Es una llamada recursiva: en ese hijo se repite todo el proceso desde el paso 1.

5
Repetir hasta encontrar sitio

La recursión continúa hacia abajo hasta que un nodo con hueco acepta el punto. Si hay muchos puntos muy juntos, el árbol crece en profundidad solo en esa zona.

Buenas prácticas al implementarlo

Reinserta al subdividir

Cuando un nodo se divide, mueve sus puntos a los hijos. Si los dejas también en el padre, los contarás dos veces y las consultas devolverán duplicados.

Define bien el borde

Decide un criterio claro de pertenencia (por ejemplo, borde izquierdo y superior incluidos, derecho e inferior excluidos) y úsalo igual en todos los cuadrantes para que ningún punto se pierda ni se duplique.

Acota la profundidad

Pon un límite máximo de niveles. Si muchos puntos coinciden casi en la misma posición, un árbol sin tope intentaría subdividir sin fin y se quedaría colgado.

Poda en las consultas

En una consulta de rango, descarta de inmediato cualquier nodo cuyo rectángulo no se solape con la región buscada. Ahí está casi toda la ganancia de velocidad.

Elige la capacidad midiendo

No fijes la capacidad por intuición. Prueba varios valores con tus datos reales y quédate con el que dé mejor rendimiento; suele estar entre 4 y 8.

Piensa en los objetos en movimiento

Si tu escena cambia cada fotograma, decide pronto si reconstruyes el árbol entero o lo actualizas de forma incremental. Es lo que más afecta al rendimiento real.

Errores frecuentes al programar un quadtree
  • No reinsertar los puntos del nodo en los hijos al subdividir → puntos duplicados o perdidos.
  • Criterio de borde ambiguo → un punto justo en la línea entre cuadrantes cae en dos hijos o en ninguno.
  • Elegir mal la capacidad → demasiado baja crea miles de nodos casi vacíos; demasiado alta no aprovecha la partición.
  • No acotar la profundidad → con puntos casi coincidentes el árbol subdivide sin fin y se cuelga.
  • Olvidar la poda en las consultas → recorrer todo el árbol anula la ventaja frente a la fuerza bruta.
  • No actualizar el árbol con objetos que se mueven → las colisiones se calculan sobre posiciones antiguas.

Apps relacionadas