Un Quadtree es una forma de organizar datos espaciales para ubicarlos de forma eficiente.
Situación
- Pongamos 100 puntos en la pantalla de forma aleatoria, llamémosles boid.
- Queremos saber cuáles boids están a 50 píxeles del mouse, llamaremos a esto área objetivo.
El problema
Una forma simple de hacerlo es ir boid por boid y comprobar si sus coordenadas X
e Y
est'an dentro del área objetivo. Esto es computacionalmente intenso porque tenemos que hacer tantas comprobaciones como boids hayan en el escenario, incluso con los que están muy lejos del área objetivo.
La solución
Dado que hay más de 5 boids en la pantalla el área total se divide en cuatro rectángulos de igual tamaño. El mismo proceso se repite con cada uno de los nuevos rectángulos creando un árbol de cuadrantes (Quad-tree) hasta que cada cuadrante tiene 5 boids o menos.
Demostración
En este ejemplo la pantalla se llena con 100 boids y el algoritmo empieza.
Una vez tenemos la estructura Quadtree podemos rápidamente comprobar qué boids están dentro de un área en concreto recorriendo la estructura Quadtree e ignorando todas las ramificaciones que no coincidan con el área objetivo, efectivamente ignorando la mayoría de los boids en pantalla.
En esta demostración los boids además se mueven, eso significa que el Quadtree se actualiza más o menos 60 veces por segundo con las nuevas posiciones de los boids.
Un rectángulo azul se dubuja alrededor del mouse, cada boid encontrado dentro de esa área se pinta de rojo.
Configuración
maxEntities
: Divide un cuadrante si contiene más demaxEntities
boids. Por defecto:3
maxDepth
: No dividir un cuadrante más demaxDepth
veces. Por defecto:5
.entitiesCount
: Cantidad de boids a crear. Por defecto:100
.entitySize
: Tamaño de cada boid en píxeles. Por defecto:3
.hoverSize
: Ancho del área objetivo en píxeles. Por defecto:120
.maxSpeed
: Limita qué tan rápido pueden moverse los boids. Por defecto:10
.
La demostarción es configurada con parámetros de URL: