{ Adrian.Matías Quezada }

MonorepoQuadtreeSpatialLernaParcelData structure

Quadtree

Un Quadtree es una forma de organizar datos espaciales para ubicarlos de forma eficiente.

Situación

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

La demostarción es configurada con parámetros de URL:

https://amatiasq.github.io/npm-libraries/quadtree/?maxEntities=2&maxDepth=10&entitiesCount=10&entitySize=10&hoverSize=200&maxSpeed=3