Understanding QuadTrees: organizing space to reduce unnecessary work
Talking about Javascript.
A QuadTree is a spatial data structure designed to organize objects in a two-dimensional space. Its main purpose is not data storage, but performance optimization: it helps answer spatial questions efficiently, such as: which objects are near this point? Which entities might collide? What lies inside this area?
The need for a QuadTree arises whenever you have many objects distributed in space, but each operation only concerns a small portion of that space. This situation is extremely common in games, physics simulations, editors, and interactive DOM-based interfaces.
The core problem
Consider a world containing hundreds or thousands of objects. If all objects are stored in a simple list, every spatial query requires checking each object individually.
This approach has a clear drawback: the cost of a query grows linearly with the number of objects, even when only a few of them are actually relevant.
For example, checking which objects are close to the mouse should not require inspecting objects on the opposite side of the world. Yet, without spatial organization, that is exactly what happens.
From objects to space
A QuadTree solves this problem by organizing space first, objects second.
The world is represented as a square region. This region can be subdivided into four equally sized quadrants. Each quadrant represents a smaller area of space, and can itself be subdivided again if needed.
Objects are inserted into the smallest region that fully contains them. Areas with many objects become more detailed, while empty or sparse areas remain large.
This produces a hierarchical structure where space is divided only where it provides a benefit.
How subdivision works
Each node of the QuadTree represents a rectangular region of space. A node can store a limited number of objects. When that limit is exceeded, the node is subdivided into four children, each covering a quarter of the original area.
At that point:
- The node becomes an internal node.
- Its children handle object storage at a finer spatial resolution.
- Subdivision continues recursively, but only where object density requires it.
The result is a tree structure whose shape reflects the actual distribution of objects.
Querying the QuadTree
The real advantage of a QuadTree appears during queries.
Instead of checking every object, the algorithm proceeds top-down:
- Check whether a node’s region intersects the query area.
- If it does not, discard the entire node and all objects it contains.
- If it does, inspect the objects in that region and recurse into its children.
A single rectangle intersection test can eliminate dozens or hundreds of objects from consideration. This is the fundamental optimization provided by a QuadTree.
An intuitive analogy
A useful way to think about a QuadTree is as a filing cabinet.
At first, you have one large drawer. As documents accumulate, you split the drawer into smaller drawers, each responsible for a portion of the content. You continue splitting only where documents pile up.
When searching for a specific document, you do not open every drawer. You read the labels first and ignore entire sections that cannot possibly contain what you are looking for.
The drawer labels correspond to QuadTree nodes.
The documents correspond to objects in space.
Why QuadTrees are fast
QuadTrees do not make individual checks faster. Instead, they reduce the number of checks required.
Object-level checks are often expensive: they may involve collision math, game logic, or DOM updates. Node-level checks are cheap: simple numeric comparisons between rectangles.
By replacing many expensive checks with a few cheap ones, a QuadTree dramatically improves performance in scenarios with localized queries.
Advantages
QuadTrees offer several important benefits:
- Efficient spatial queries.
- Reduced computational cost for collision detection and proximity checks.
- Adaptive subdivision based on actual data distribution.
- Suitability for real-time systems such as games and editors.
They are especially effective when objects are unevenly distributed across space.
Limitations and trade-offs
QuadTrees are not a universal solution.
They introduce:
- Additional memory usage.
- Insertion and maintenance overhead.
- More complex logic than a flat list.
They are less effective when:
- The number of objects is very small.
- All objects are tightly clustered.
- The structure must be rebuilt entirely every frame
Like any spatial index, a QuadTree represents a trade-off between precision, memory usage, and update cost.
When to use a QuadTree
A QuadTree is a good choice when:
- The world is two-dimensional.
- Object count is moderate to high.
- Queries are local in nature.
- Objects move infrequently or moderately.
In these conditions, the performance gains usually far outweigh the overhead.
A practical example
To make these concepts concrete, the following example implements a QuadTree using only HTML, CSS, and JavaScript. Objects are represented as DOM elements, and the tree structure is visualized directly on screen.
As you move the mouse, a query region highlights only the objects contained within it. Despite hundreds of objects being present, only a small subset is actually tested at each step.
This visual demonstration makes it clear how spatial subdivision allows us to ignore large portions of the world efficiently.
Move the green area with the mouse to highlight points.
This is the source code, where you can find QuadTreeNode class, the core of the script:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Quad Tree</title>
<style>
body {
margin: 0;
background: #111;
height: 100vh;
display: flex;
justify-content: center;
align-items: center;
font-family: sans-serif;
}
#world {
position: relative;
width: 600px;
height: 600px;
background: #000;
overflow: hidden;
}
.node {
position: absolute;
border: 1px solid #333;
box-sizing: border-box;
pointer-events: none;
}
.point {
position: absolute;
width: 4px;
height: 4px;
background: #fff;
transform: translate(-50%, -50%);
pointer-events: none;
}
.point.found {
background: #0f0;
}
.query-range {
position: absolute;
border: 1px solid #0f0;
background: rgba(0, 255, 0, 0.08);
pointer-events: none;
}
</style>
</head>
<body>
<div id="world"></div>
<script>
/*
Represents a spatial entity inside the QuadTree.
This class stores only positional data (x, y) and a reference
to a DOM element used for visualization purposes.
In a real game or engine, this object could also include
velocity, size, collision data, or other gameplay-related state.
*/
class SpatialPoint {
constructor(x, y, domElement) {
this.x = x;
this.y = y;
this.domElement = domElement;
}
}
/*
Axis-Aligned Bounding Box (AABB).
This class represents a rectangular region of space whose edges
are aligned with the X and Y axes. AABBs are widely used in spatial
data structures and collision detection because they are fast
to test and simple to reason about.
In this QuadTree implementation, BoundingBox is used both for:
- defining the spatial region covered by each QuadTree node
- defining query areas (for example, the area around the mouse)
*/
class BoundingBox {
constructor(centerX, centerY, halfWidth, halfHeight) {
this.centerX = centerX;
this.centerY = centerY;
this.halfWidth = halfWidth;
this.halfHeight = halfHeight;
}
/*
Checks whether a point lies inside this bounding box.
The test is inclusive on all sides, meaning that points lying
exactly on the border are considered inside.
*/
contains(point) {
return (
point.x >= this.centerX - this.halfWidth &&
point.x <= this.centerX + this.halfWidth &&
point.y >= this.centerY - this.halfHeight &&
point.y <= this.centerY + this.halfHeight
);
}
/*
Checks whether this bounding box intersects another bounding box.
The 'boundingBox' parameter represents a second AABB.
If the two boxes do NOT overlap on at least one axis,
then they cannot intersect.
This method is the foundation of QuadTree spatial pruning:
if a node's bounding box does not intersect the query area,
the entire subtree can be skipped.
*/
intersects(boundingBox) {
return !(
boundingBox.centerX - boundingBox.halfWidth > this.centerX + this.halfWidth ||
boundingBox.centerX + boundingBox.halfWidth < this.centerX - this.halfWidth ||
boundingBox.centerY - boundingBox.halfHeight > this.centerY + this.halfHeight ||
boundingBox.centerY + boundingBox.halfHeight < this.centerY - this.halfHeight
);
}
}
/*
QuadTree node.
Each node represents a rectangular region of space and can either:
- store a limited number of points (leaf node)
- or be subdivided into four child nodes (internal node)
The combination of maxPoints and maxDepth controls how the space
is partitioned and prevents infinite subdivision.
*/
class QuadTreeNode {
constructor(boundary, maxPoints, maxDepth, depth, containerElement) {
this.boundary = boundary;
this.maxPoints = maxPoints;
this.maxDepth = maxDepth;
this.depth = depth;
this.containerElement = containerElement;
this.points = [];
this.isSubdivided = false;
this.domElement = document.createElement('div');
this.domElement.className = 'node';
this.updateDomElement();
containerElement.appendChild(this.domElement);
}
/*
Updates the DOM element so that it matches
the spatial boundaries of this node.
This is purely for visualization/debug purposes.
*/
updateDomElement() {
const b = this.boundary;
this.domElement.style.left = (b.centerX - b.halfWidth) + 'px';
this.domElement.style.top = (b.centerY - b.halfHeight) + 'px';
this.domElement.style.width = (b.halfWidth * 2) + 'px';
this.domElement.style.height = (b.halfHeight * 2) + 'px';
}
/*
Subdivides this node into four children:
- north-west
- north-east
- south-west
- south-east
All existing points are redistributed into the children.
After subdivision, this node no longer stores points directly.
*/
subdivide() {
const { centerX, centerY, halfWidth, halfHeight } = this.boundary;
const hw = halfWidth / 2;
const hh = halfHeight / 2;
const nextDepth = this.depth + 1;
this.northWest = new QuadTreeNode(
new BoundingBox(centerX - hw, centerY - hh, hw, hh),
this.maxPoints,
this.maxDepth,
nextDepth,
this.containerElement
);
this.northEast = new QuadTreeNode(
new BoundingBox(centerX + hw, centerY - hh, hw, hh),
this.maxPoints,
this.maxDepth,
nextDepth,
this.containerElement
);
this.southWest = new QuadTreeNode(
new BoundingBox(centerX - hw, centerY + hh, hw, hh),
this.maxPoints,
this.maxDepth,
nextDepth,
this.containerElement
);
this.southEast = new QuadTreeNode(
new BoundingBox(centerX + hw, centerY + hh, hw, hh),
this.maxPoints,
this.maxDepth,
nextDepth,
this.containerElement
);
for (let point of this.points) {
this.northWest.insert(point) ||
this.northEast.insert(point) ||
this.southWest.insert(point) ||
this.southEast.insert(point);
}
this.points.length = 0;
this.isSubdivided = true;
}
/*
Inserts a point into the QuadTree.
The algorithm follows these steps:
- ignore the point if it lies outside this node's boundary
- if this is a leaf node and there is room, store the point
- if the node is full and not at max depth, subdivide
- delegate insertion to the appropriate child
*/
insert(point) {
if (!this.boundary.contains(point)) {
return false;
}
if (!this.isSubdivided) {
if (this.points.length < this.maxPoints || this.depth === this.maxDepth) {
this.points.push(point);
return true;
}
this.subdivide();
}
return (
this.northWest.insert(point) ||
this.northEast.insert(point) ||
this.southWest.insert(point) ||
this.southEast.insert(point)
);
}
/*
Retrieves all points that lie inside the given query area.
The method uses spatial pruning:
if the query area does not intersect this node,
the entire subtree can be skipped.
*/
query(queryArea, result = []) {
if (!this.boundary.intersects(queryArea)) {
return result;
}
for (let point of this.points) {
if (queryArea.contains(point)) {
result.push(point);
}
}
if (this.isSubdivided) {
this.northWest.query(queryArea, result);
this.northEast.query(queryArea, result);
this.southWest.query(queryArea, result);
this.southEast.query(queryArea, result);
}
return result;
}
}
const world = document.getElementById('world');
const quadTreeRoot = new QuadTreeNode(
new BoundingBox(300, 300, 300, 300),
4, // maximum number of points per square
6, // maximum depth
0, // starting depth
world
);
const allPoints = [];
// insert 400 random points
for (let i = 0; i < 400; i++) {
const x = Math.random() * 600;
const y = Math.random() * 600;
const el = document.createElement('div');
el.className = 'point';
el.style.left = x + 'px';
el.style.top = y + 'px';
world.appendChild(el);
const p = new SpatialPoint(x, y, el);
allPoints.push(p);
quadTreeRoot.insert(p);
}
const queryEl = document.createElement('div');
queryEl.className = 'query-range';
world.appendChild(queryEl);
// on mouse move, query the quad tree
world.addEventListener('mousemove', e => {
const r = world.getBoundingClientRect();
const x = e.clientX - r.left;
const y = e.clientY - r.top;
const queryArea = new BoundingBox(x, y, 50, 50);
queryEl.style.left = (x - 50) + 'px';
queryEl.style.top = (y - 50) + 'px';
queryEl.style.width = '100px';
queryEl.style.height = '100px';
allPoints.forEach(p => p.domElement.classList.remove('found'));
quadTreeRoot.query(queryArea).forEach(p => p.domElement.classList.add('found'));
});
</script>
</body>
</html>At a high level, the script builds a spatial index over a 2D world and then uses it to answer proximity queries efficiently. It combines three ideas: a visual world, a spatial data structure (the QuadTree), and a live query driven by user input.
The script starts by defining a world area, represented by a fixed-size container (#world). This is the coordinate space in which all objects live. Every point generated later uses the same coordinate system, so spatial relationships are consistent and easy to reason about.
Next, a QuadTree is created to cover the entire world. This root node represents the whole space and is configured with two important limits: how many points a region can hold before it subdivides, and how deep the tree is allowed to grow. As points are inserted, the tree automatically subdivides only in areas where point density requires it. Sparse regions remain large, while dense regions become more detailed.
Each point is represented by a small DOM element and a lightweight data object that stores its position. When a point is inserted into the QuadTree, it is placed into the smallest region that can contain it. If a region becomes too crowded, it is subdivided and its points are redistributed into child regions. This process happens once during setup and produces a spatial hierarchy that mirrors the actual distribution of points.
Once the structure is built, the script listens for mouse movement inside the world. On every mouse move, a rectangular query area is created around the cursor. This rectangle represents the spatial question: “which points are inside this area?”
To answer that question, the script queries the QuadTree instead of scanning all points. The query starts at the root and recursively descends into child nodes only if their spatial region intersects the query area. Entire branches of the tree are skipped with a single bounding-box check, which avoids unnecessary point-level tests.
All points found inside the query area are then visually highlighted by updating their DOM elements. Before each query, previous highlights are cleared, so the user sees only the points that are currently relevant.
The result is a live, visual demonstration of spatial pruning in action. Even though hundreds of points exist in the world, only a small subset is actually tested and highlighted on each mouse movement. This clearly shows how organizing space instead of iterating over objects leads to more efficient queries, which is the core motivation behind using a QuadTree.
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.