# Quadtree Search

# 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.

```text id="qt0k7q"
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

```python id="qt1m8v"
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)
```

```go id="qt2n7x"
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)
	}
}
```