Quadtree Search

Quadtree search partitions 2D space recursively into four quadrants. Each node represents a rectangular region and stores points or subregions within that area.

It is used for spatial indexing, collision detection, and range queries in two dimensions.

Problem

Given a set of 2D points and a query rectangle $Q$ , find all points inside $Q$ :

x_1 \le x \le x_2, \quad y_1 \le y \le y_2

Structure

Each node represents a bounding rectangle and has up to four children:

quadrant	region
NW	top left
NE	top right
SW	bottom left
SE	bottom right

Each node stores:

field	meaning
boundary	rectangle region
points	points in leaf node
children	subdivided quadrants

Algorithm

Search prunes regions that do not intersect the query rectangle.

quadtree_search(node, Q, result):
    if node is null:
        return

    if not intersects(node.boundary, Q):
        return

    if node is leaf:
        for p in node.points:
            if p inside Q:
                add p to result
        return

    for child in node.children:
        quadtree_search(child, Q, result)

Example

Points:

point
(1,1)
(2,5)
(6,7)
(8,3)

Query:

[1,1] \to [5,6]

Matches:

point	inside
(1,1)	yes
(2,5)	yes
(6,7)	no
(8,3)	no

Correctness

Each node represents a disjoint spatial region. If a node’s region does not intersect the query rectangle, none of its descendants can contain valid points, so pruning is safe.

If a node is a leaf, all points inside it are checked individually. Since all points are stored in exactly one leaf node at the deepest level, all valid points are eventually examined.

Therefore the algorithm returns exactly the set of points inside the query region.

Complexity

Let $n$ be number of points and $k$ number of results.

case	time
average query	$O(\log n + k)$
worst case	$O(n)$

Space complexity:

O(n)

When to Use

Quadtrees are useful when:

data is 2D spatial (maps, games, graphics)
range queries are frequent
dynamic insertion is needed
spatial partitioning is natural

Compared to k-d trees, quadtrees use axis aligned recursive subdivision instead of alternating split planes.

Compared to R trees, quadtrees are simpler but less flexible for arbitrary rectangles.

Implementation

class Node:
    def __init__(self, boundary):
        self.boundary = boundary
        self.points = []
        self.children = []

def intersects(a, b):
    return not (a[2] < b[0] or a[0] > b[2] or a[3] < b[1] or a[1] > b[3])

def inside(p, Q):
    return Q[0] <= p[0] <= Q[2] and Q[1] <= p[1] <= Q[3]

def quadtree_search(node, Q, result):
    if node is None:
        return

    if not intersects(node.boundary, Q):
        return

    if len(node.children) == 0:
        for p in node.points:
            if inside(p, Q):
                result.append(p)
        return

    for child in node.children:
        quadtree_search(child, Q, result)

type Point struct {
	X, Y float64
}

type Rect struct {
	X1, Y1, X2, Y2 float64
}

type Node struct {
	Boundary Rect
	Points   []Point
	Children []*Node
}

func intersects(a, b Rect) bool {
	return !(a.X2 < b.X1 || a.X1 > b.X2 || a.Y2 < b.Y1 || a.Y1 > b.Y2)
}

func inside(p Point, Q Rect) bool {
	return p.X >= Q.X1 && p.X <= Q.X2 && p.Y >= Q.Y1 && p.Y <= Q.Y2
}

func QuadtreeSearch(node *Node, Q Rect, res *[]Point) {
	if node == nil {
		return
	}

	if !intersects(node.Boundary, Q) {
		return
	}

	if len(node.Children) == 0 {
		for _, p := range node.Points {
			if inside(p, Q) {
				*res = append(*res, p)
			}
		}
		return
	}

	for _, child := range node.Children {
		QuadtreeSearch(child, Q, res)
	}
}