# Octree Search

# Octree Search

Octree search extends quadtree ideas to three dimensional space. It recursively partitions space into eight octants, enabling efficient spatial queries over 3D points or volumes.

It is commonly used in graphics, physics simulation, and spatial indexing.

## Problem

Given a set of 3D points and a query axis aligned bounding box (AABB), find all points inside the box:

$$
x_1 \le x \le x_2,\quad y_1 \le y \le y_2,\quad z_1 \le z \le z_2
$$

## Structure

Each node represents a cubic region and has up to eight children:

| octant | region                 |
| ------ | ---------------------- |
| 000    | x low, y low, z low    |
| 001    | x low, y low, z high   |
| 010    | x low, y high, z low   |
| 011    | x low, y high, z high  |
| 100    | x high, y low, z low   |
| 101    | x high, y low, z high  |
| 110    | x high, y high, z low  |
| 111    | x high, y high, z high |

Each node stores:

| field    | meaning        |
| -------- | -------------- |
| boundary | 3D box region  |
| points   | points in leaf |
| children | eight octants  |

## Algorithm

Search prunes nodes whose bounding boxes do not intersect the query box.

```text id="ot0k7q"
octree_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:
        octree_search(child, Q, result)
```

## Example

Points:

| point   |
| ------- |
| (1,1,1) |
| (2,3,4) |
| (5,5,5) |
| (7,8,9) |

Query box:

$$
[1,1,1] \to [4,4,4]
$$

Matches:

| point   | inside |
| ------- | ------ |
| (1,1,1) | yes    |
| (2,3,4) | yes    |
| (5,5,5) | no     |
| (7,8,9) | no     |

## Correctness

Each node covers a disjoint axis aligned region of 3D space. If a node’s region does not intersect the query box, none of its children can intersect it, so pruning is safe.

Leaf nodes contain explicit point lists, and every point belongs to exactly one leaf region at the deepest level. Therefore all candidate points are checked, and only those inside the query box are returned.

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

Octrees are useful when:

* working in 3D space (graphics, physics, simulations)
* spatial partitioning is needed for collision detection
* volumetric queries or visibility tests are required
* data is static or moderately dynamic

Compared to k-d trees, octrees partition space uniformly rather than by median splits. Compared to R trees, octrees are simpler but less flexible for arbitrary volumes.

## Implementation

```python id="ot1m8v"
class Node:
    def __init__(self, boundary):
        self.boundary = boundary
        self.points = []
        self.children = []

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

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

def octree_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:
        octree_search(child, Q, result)
```

```go id="ot2n7x"
type Point3 struct {
	X, Y, Z float64
}

type Box struct {
	X1, Y1, Z1 float64
	X2, Y2, Z2 float64
}

type Node struct {
	Boundary Box
	Points   []Point3
	Children []*Node
}

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

func inside(p Point3, Q Box) bool {
	return p.X >= Q.X1 && p.X <= Q.X2 &&
		p.Y >= Q.Y1 && p.Y <= Q.Y2 &&
		p.Z >= Q.Z1 && p.Z <= Q.Z2
}

func OctreeSearch(node *Node, Q Box, res *[]Point3) {
	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 {
		OctreeSearch(child, Q, res)
	}
}
```