Las simulaciones espaciales a menudo plantean una pregunta engañosamente simple: ¿qué cuerpos están lo suficientemente cerca de la materia? La respuesta costosa es medir cada cuerpo. Un quadtree ofrece una primera respuesta más económica: pregunte sólo los cuadrantes que intersectan el área de búsqueda y luego realice comprobaciones exactas de lo que devuelven.
Mueve el puntero por el modelo. El círculo rojo de prueba es el vecindario solicitado; Los puntos chartreuse son coincidencias exactas. La cuadrícula recursiva cambia con la población y la presión dividida, haciendo visible la fase amplia en lugar de ocultarla detrás de una afirmación de desempeño.
Una consulta móvil sobre un índice espacial recursivo
INTERACTIVO- Empezar por separarse ✓
- Un grupo todavía puede discrepar ✓
- La alineación crea una bandada ✓
- Limitar quién puede importar +
Mueve la consulta por el índice y arrastra el borde verde. Los conteos de candidatos e impactos exactos deben cambiar por separado.
Transcripción accesible del experimento
Los puntos subdividen el plano; un radio móvil resalta solo los candidatos de las celdas intersectadas. Gesto en el lienzo: mueve para consultar; arrastra el anillo para ajustarlo.
Un árbol hecho de rectángulos.
El nodo raíz comienza con todo el lienzo. Almacena cadáveres hasta superar su capacidad. Si no se ha alcanzado la profundidad máxima, crea cuatro rectángulos secundarios (arriba a la izquierda, arriba a la derecha, abajo a la izquierda y abajo a la derecha) y luego reinserta sus hijos actuales.
La implementación archivada acepta tanto puntos como cuerpos con ancho y alto. Un cuerpo puede cruzar a más de un niño, por lo que al insertarlo se puede colocar el mismo objeto en varias ramas. Eso hace necesario un paso posterior de deduplicación.
La capacidad crea estructura sólo cuando es necesaria.
SIGUE LAS FLECHASA point or body enters the smallest current node that contains its corners.
Transcripción accesible del diagrama
Insertion tests node capacity. A full node below maximum depth splits into four and recursively redistributes its children.
La consulta es deliberadamente incompleta
La consulta comienza con una región. Cada nodo pregunta qué cuadrantes secundarios toca esa región y visita solo esas ramas. El resultado es una matriz candidata de fase amplia, no una garantía geométrica.
Esta distinción es fácil de pasar por alto en las demostraciones visuales. Un punto puede compartir un cuadrante de intersección mientras aún se encuentra fuera de un radio de percepción circular. Un cuerpo rectangular puede abarcar varias celdas y aparecer más de una vez. Por tanto, el llamante necesita dos operaciones de seguimiento:
- eliminar referencias a objetos duplicados;
- Aplicar la prueba exacta de forma o distancia requerida por el dominio.
El árbol devuelve candidatos; la geometría devuelve la verdad
SIGUE LAS FLECHASA square or radius defines the requested neighborhood.
Transcripción accesible del diagrama
A query shape selects intersecting cells, deduplicates candidates, then applies exact geometry before returning verified results.
Lo que enseña la grilla
Una cuadrícula uniforme presta la misma atención en todas partes. Un árbol cuádruple asigna detalles donde se agrupan los cuerpos. Las regiones dispersas siguen siendo amplias; las regiones densas se dividen hasta que la capacidad o la profundidad máxima detiene la recursividad.
Eso lo hace adecuado para el experimento de boids, fases amplias de colisión, herramientas de selección y otros campos 2D desiguales. Es menos mágico de lo que sugieren sus diagramas. Una capacidad deficiente, poca profundidad o un conjunto de grandes organismos muy superpuestos aún pueden producir listas de candidatos grandes. Reconstruir el árbol de cada cuadro de animación también tiene un costo.
El original repository expone la capacidad máxima, la profundidad, la forma de la consulta, los esquemas de depuración y las estadísticas de los candidatos. Su decisión de diseño más importante es que el quadtree sigue siendo una utilidad reutilizable en lugar de absorber el comportamiento específico del boid.
El siguiente experimento
Yo agregaría un contador en paralelo: cuerpos totales, células visitadas, candidatos de fase amplia, duplicados eliminados y coincidencias exactas. Luego dejaría que el lector cambie entre todos los pares, una cuadrícula uniforme y el árbol cuádruple en la misma distribución de puntos.
El desempeño se vuelve comprensible cuando el lector puede ver dónde desapareció el trabajo. La contribución del quadtree no es que sepa lo que está cerca. Sabe dónde no mirar.