{ Adrian.Matías Quezada }

MonorepoQuadtreeSpatialLernaParcelData structure


A Quadtree is a way to organise spatial data to efficiently locate them.


The problem

A simple way of doing this is going boid by boid and check if their X and Y coordinates are inside the target area. This is computationally intensive because we have to do one check per boid in the screen, even if they are far away from the target area.

The solution

Give we have more than 5 boids in the screen the total area is divided in four rectangles of equal size. The same process is repeated on each of the smaller rectangles, creating a tree of quadrants (see what I did there?) until each quadrant has 5 boids or less.


In this example the screen is filled with 100 boids and the algorithm is started.

Once we have the Quadtree structure we can quickly check which boids are inside a given area by walking the structure and ignoring all the branches that don't collide with the target area, effectively ignoring most of the boids in the screen.

In this demo the boids are also moving, that means the Quadtree is updated more or less 60 times per second with the new position of the boids.

A blue rectangle is drawn around the mouse, every boid found inside that area is painted red.


The demo is configured with query parameters in the URL: