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

Situation

• Let's put 100 dots in the screen randomly, call them boids.
• We want to know which one of such boids are 50 pixels from the mouse, call this target area.

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.

Demo

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.

Configuration

• maxEntities: Divide a quadrant if it contains more than maxEntities boids. Default: 3
• maxDepth: Do not split a quadrant more than maxDepth times. Default: 5.
• entitiesCount: Number of boids to create. Default: 100.
• entitySize: Size of each boid in pixels. Default: 3.
• hoverSize: Width of the target area in pixels. Default: 120.
• maxSpeed: Limits how fast can boids move. Default: 10.

The demo is configured with query parameters in the URL:

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