Quadtree

Quadtrees can be found all around our digital life: in computer games, digital art, and maps, in other words - everywhere information is connected with the location on the plane. Anytime you search for “closest cafe” or calling a taxi using map services, all these are examples of quadtrees in action. Depending on data other common use cases for quadtrees include image processing, effective collision detection, and many others.

In this post we will take a closer look into quadtrees: what they are, where and why should we use them, and most importantly we will create basic implementation of the quadtree using TypeScript.

Definition#

Quadtree is a tree data structure in which each internal node has exactly four children. It is commonly used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a “leaf” cell varies by application, but the “leaf” node represents a “unit of interesting spatial information”. Interesting means that the node is not empty and there is something worth noting.

Usually the nodes are rectangular or square, but they can have an arbitrary shape.

All forms of quadtrees share some common features:

• They decompose space into adaptable “cells”;
• Each “cell” has a maximum capacity; when it’s reached, the node splits;
• The tree directory follows the spacial decomposition of the quadtree.

Quadtrees may be classified according to the data they represent, including areas, points, lines, and curves; or by whether the tree shape is dependant or not of the order in which data is processed.

A problem to solve#

Let’s consider the collision detection problem. Let there be n randomly placed moving objects in some planar boundary. The task is to determine the collision of objects at some point in time. Bruteforcing the problem means to calculate the distance between each pair of objects. The algorithmic complexity in this case is quadratic: O(n^2), as there are n * n checks for n objects we have.

In fact, most of the calculations could be avoided if we were somehow able to delimit objects that are definitely too far away, the intersection with which is extremely unlikely. In other words, we need to get the information about the relative distance between the objects in some part of space.

That is where the Quadtree steps into the game. Having a tree with registered the position of each object, we can get the information about the objects located in an arbitrary area; as a result, it will only be necessary to check for a subset of objects. This approach will reduce the algorithmic complexity to logarithmic O (n log n). Let’s compare the difference for one thousand objects. The number of required operations drops from one million to three thousand. A significant increase in performance as the number of operations drops dramatically, even taking into account the resources needed to build the tree itself.

With the help of a quadtree storing the coordinates we can solve a number of other similar problems where the spacial location plays a significant role.

Quadtree in action#

Using rectangular “cells” a quadtree splits the plane into quadrants that look familiar to the quadrants of the Cartesian coordinate system. As the tree depth increases, the quadrants are split recursively and the plane is covered by smaller and smaller “cells”:

The demonstration above visually resembles a table and gives little idea about a quadtree. Let’s have a look at a more illustrative example. Now we can add an object to the plane by touching the area - just a point. As we remember, quadrant have a fixed capacity. Adding more and more points to the same part of the plane makes the quadtree split in such a way that no quadrant will have more points it can store.

Now as we can see the quadtree spacial decomposition, it is time to use it for it’s intended purpose. The quadtree resembles a “spacial database”. We can query it by specifying an area, and the quadtree will provide the information about the objects located in this area. The area can have an arbitrary shape and size, of course.

In the interactive demonstration below a quadtree is built from one hundred randomly placed points. Beside the points there are the query area of a circular (rectangular) shape. Dragging this area over the plane a query is performed over the quadtree to get information about the points located within it. This information is used to provide visual feedback.

Usage Example#

A quadtree in action can be seen on this website in flocking visualization; it is used as an optimization by default. The flocking simulation consists of groups of objects - boids, that moves around by forces formed on the basis on neighbors, primarily depending on the distance. More distant neighbors contribute noticeable low influence which can be safely neglected for optimization purposes.

Thus, each boid has a “perception” parameter - the distance beyond which other boids won’t have influence. Based on coordinates of the boid and “perception” area, the quadtree gives us information only about significant neighbors for each boid in the flock.

Using quadtree boosts animation performance significantly. To feel the difference, turn of the quadtree optimization and increase the number of boids.

Implementing the Quadtree#

Pseudocode#

The following pseudocode shows one means of implementing a rectangular shape quadtree which handles only points.

As prerequisites the Point and Rect structures are used:

// Coordinate object to represent points and vectors.
struct Point {
	float x;
	float y;

	function construct(float x, float y): Point;
}

// Axis-aligned rectangle defined by top-left vertex coordinate and it's dimensions.
struct Rect {
	Point center;
	float width;
	float height;

	function construct(Point center, float width, float height): Rect;
	function contains(Point coordinate): boolean;
	function intersects(Rect otherRect): boolean;
}

The QuadTree class represents both quadtree itself and the node it is rooted.

//
class QuadTree {
	constant int CAPACITY = 4;

	Rect boundary;

	points: Array of Point [ size = CAPACITY ];

	children: Array of QuadTree [ size = 4 ];

	function construct(Rect boundary): QuadTree;
	function insert(Point p): boolean;
	function query(Rect range): Array of Point;
	private function split(): void;
}

The insert method registers a point into the appropriate quad of a quadtree, splitting if necessary.

class QuadTree {
	...

	function insert(Point p): boolean {
		if (!boundary.contains(p)) {
			return false
		}

		if (points.size < CAPACITY) {
			points.append(p);
			return true;
		}

		if (children[0] == null) {
			split();
		}

		each children as child {
			if (child.insert(p)) {
				return true;
			}
		}

		// the point cannot be inserted for some unknown reason, this should never happen
		return false;
	}
}

The query method finds all points contained within a range:

class QuadTree {
	...

	query(Rect range): Array of Point {
		items: Array of Point;

		if (!boundary.intersects(range)) {
			return items;
		}

		each points as point {
			if (range.contains(point)) {
				items.append(point);
			}
		}

		if (children[0] == null) {
			return items;
		}

		each children as child {
			child.query(range);
		}

		return items;
	}
}

The split method should be private and the splitting performed automatically based on quadtree nodes capacity and other options. The method implementation depends on boundary shape and it’s representation. For example, a rectangle boundary can be represented by it’s center and half dimensions, but it’s not the only options. This is important to consider as the split method should break the boundary into four similar boundaries using the same representation.

Implementing a QuadTree using TypeScript#

TypeScript implementation uses the same rectangular shape quadtree which handles points. Important to note that only “leaf” nodes will store the data.

Following the pseudocode, the implementation starts with helper data structures: Point and Rect. The only difference is the data key, as the Point is just wrapper over the user data to register in a quadtree:

/**
 * Coordinate object to represent points and vectors.
 */
class Point<Data = unknown> {
	readonly x: number;
	readonly y: number;
	readonly data?: Data;

	constructor(x: number, y: number, data?: Data) {
		this.x = x;
		this.y = y;
		this.data = data;
	}
}

Rectangular boundary is represented by it’s top-left vertex coordinate and it’s dimensions, which is often used with graphical data on the screen.

/**
 * Axis-aligned rectangle defined by top-left vertex coordinate and it's dimensions.
 */
export class Rectangle {
	readonly x: number;
	readonly y: number;
	readonly w: number;
	readonly h: number;

	constructor(x: number, y: number, w: number, h: number) {
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
	}

	/**
	 * Performs a check if the given point contained within the boundary.
	 */
	contains(item: Point): boolean {
		return (
			item.x >= this.x &&
			item.x <= this.x + this.w &&
			item.y >= this.y &&
			item.y <= this.y + this.h
		);
	}

	/**
	 * Performs a check if the given range intersects the boundary.
	 */
	intersects(range: Rectangle): boolean {
		return !(
			this.x >= range.x + range.w ||
			this.x + this.w <= range.x ||
			this.y >= range.y + range.h ||
			this.y + this.h <= range.y
		);
	}
}

The QuadTree class implementation will have additional state: depth and depthLimit to denote the current node depth and the maximum depth the tree can have respectively. Since recursion will be used, too deep trees can hit performance quite a bit.

The children nodes will be stored in an array. Since the rectangular quadrants represent [the Cartesian Coordinate System quadrants] it will be convenient to refer to quadrant by index (with the only difference that count starts from zero).

class QuadTree<Item extends Point> {
	readonly boundary: Rectangle;
	readonly capacity: number;
	readonly depth: number;
	private readonly depthLimit: number;
	items: Item[];
	quadrants: QuadTree<Item>[];

	constructor(capacity: number, boundary: Rectangle, depthLimit = 12, depth = 1) {
		this.boundary = boundary;
		this.capacity = capacity;
		this.depth = depth;
		this.depthLimit = depthLimit;
		this.items = [];
		this.quadrants = [];
	}

	...
}

As the next step, let’s implement hasChildren getter:

class QuadTree<Item extends Point> {
	...

	/**
	 * Performs a check whether the node has children.
	 */
	get hasChildren(): boolean {
		return this.quadrants.length > 0;
	}
}

Now it is time to implement the private split method. Using the Rect representation model, it splits the boundary into four similar boundaries to hold the data:

class QuadTree<Item extends Point> {
	...

	/**
	 * Creates children nodes, expanding the `QuadTree` instance.
	 */
	private split(): void {
		const hw = this.boundary.w / 2;
		const hh = this.boundary.h / 2;

		// boundaries position shifts
		const delta = [
			[ hw, 0 ],
			[ 0, 0 ],
			[ 0, hh ],
			[ hw, hh ]
		];

		for (const [ dx, dy ] of delta) {
			this.quadrants.push(new QuadTree<Item>(
				this.capacity,
				new Rectangle(this.boundary.x + dx, this.boundary.y + dy, hw, hh),
				this.depthLimit,
				this.depth + 1
			));
		}
	}
}

Next in line is the insert method. It is used to register a point in a quadtree. As the data is stored in “leaf” nodes, the registration process have some additional logic: if the tree splits all previously registered points should be re-registered in new children before the registration resume.

Method returns boolean to indicate the success of operation.

class QuadTree<Item extends Point> {
	...

	/**
	 * Inserts a given point in the `QuadTree` instance.
	 */
	insert(item: Item): boolean {
		if (!this.boundary.contains(item)) {
			return false;
		}

		if (!this.hasChildren && this.items.length < this.capacity) {
			this.items.push(item);
			return true;
		}

		if (!this.hasChildren && this.depth < this.depthLimit) {
			this.split();

			// Re-registering previously stored points
			for (const thisItem of this.items) {
				for (const quadrant of this.quadrants) {
					if (quadrant.insert(thisItem)) {
						break;
					}
				}
			}

			// clean-up
			this.items = [];
		}

		for (const quadrant of this.quadrants) {
			if (quadrant.insert(item)) {
				return true;
			}
		}

		return false;
	}
}

At last, the query method is left to implement. The data will be selected from the nodes recursively. An array of items with the selected data is passed down till the final function call returns the result:

class QuadTree<Item extends Point> {
	...

	/**
	 * Queries the data within the given range.
	 */
	query(range: Rect, items: Item[] = []): Item[] {
		// Нет пересечения, соответственно, нет и результатов
		if (!range.intersects(this.boundary)) {
			return items;
		}

		for (const item of this.items) {
			if (range.contains(item)) {
				items.push(item);
			}
		}

		if (this.hasChildren) {
			for (const quadrant of this.quadrants) {
				quadrant.query(range, items);
			}
		}

		return items;
	}
}

Putting all together:

/**
 * Coordinate object to represent points and vectors.
 */
class Point<Data = unknown> {
	readonly x: number;
	readonly y: number;
	readonly data?: Data;

	constructor(x: number, y: number, data?: Data) {
		this.x = x;
		this.y = y;
		this.data = data;
	}
}

/**
 * Axis-aligned rectangle defined by top-left vertex coordinate and it's dimensions.
 */
export class Rectangle {
	readonly x: number;
	readonly y: number;
	readonly w: number;
	readonly h: number;

	constructor(x: number, y: number, w: number, h: number) {
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
	}

	/**
	 * Performs a check if the given point contained within the boundary.
	 */
	contains(item: Point): boolean {
		return (
			item.x >= this.x &&
			item.x <= this.x + this.w &&
			item.y >= this.y &&
			item.y <= this.y + this.h
		);
	}

	/**
	 * Performs a check if the given range intersects the boundary.
	 */
	intersects(range: Rectangle): boolean {
		return !(
			this.x >= range.x + range.w ||
			this.x + this.w <= range.x ||
			this.y >= range.y + range.h ||
			this.y + this.h <= range.y
		);
	}
}

export class QuadTree<Item extends Point> {
	readonly boundary: Rectangle;
	readonly capacity: number;
	readonly depth: number;
	private readonly depthLimit: number;
	items: Item[];
	quadrants: QuadTree<Item>[];

	constructor(capacity: number, boundary: Rectangle, depthLimit = 12, depth = 1) {
		this.boundary = boundary;
		this.capacity = capacity;
		this.depth = depth;
		this.depthLimit = depthLimit;
		this.items = [];
		this.quadrants = [];
	}

	/**
	 * Performs a check whether the node has children.
	 */
	get hasChildren(): boolean {
		return this.quadrants.length > 0;
	}

	/**
	 * Inserts a given point in the `QuadTree` instance.
	 */
	insert(item: Item): boolean {
		if (!this.boundary.contains(item)) {
			return false;
		}

		if (!this.hasChildren && this.items.length < this.capacity) {
			this.items.push(item);
			return true;
		}

		if (!this.hasChildren && this.depth < this.depthLimit) {
			this.split();

			for (const thisItem of this.items) {
				for (const quadrant of this.quadrants) {
					if (quadrant.insert(thisItem)) {
						break;
					}
				}
			}

			this.items = [];
		}

		for (const quadrant of this.quadrants) {
			if (quadrant.insert(item)) {
				return true;
			}
		}

		return false;
	}

	/**
	 * Creates children nodes, expanding the `QuadTree` instance.
	 */
	private split(): void {
		const hw = this.boundary.w / 2;
		const hh = this.boundary.h / 2;

		const delta = [
			[ hw, 0 ],
			[ 0, 0 ],
			[ 0, hh ],
			[ hw, hh ]
		];

		for (const [ dx, dy ] of delta) {
			this.quadrants.push(new QuadTree<Item>(
				this.capacity,
				new Rectangle(this.boundary.x + dx, this.boundary.y + dy, hw, hh),
				this.depthLimit,
				this.depth + 1
			));
		}
	}

	/**
	 * Queries the data within the given range.
	 */
	query(range: Rectangle | Circle, items: Item[] = []): Item[] {
		// boundary.intersects(range) or vice versa?
		if (!range.intersects(this.boundary)) {
			return items;
		}

		for (const item of this.items) {
			if (range.contains(item)) {
				items.push(item);
			}
		}

		if (this.hasChildren) {
			for (const quadrant of this.quadrants) {
				quadrant.query(range, items);
			}
		}

		return items;
	}
}

Conclusion#

In this post we took a closer look look into quadtrees, learned how they work, why and how should we use them and even wrote our own implementation. Nevertheless there are more to learn about this amazing data structure as we used trees that process only points. If you are eager to continue, the next step is the region quadtrees. They are heavily used in image processing, more example of it can be found here.

Resources#

• Quadtree
• An interactive explanation of quadtrees
• Partitioning 2D Spaces: An Introduction to Quadtrees
• Coding Challenge 98: QuadTree, Part 1