#Choosing Quadtree Depth for Uneven Point Density

Stop choosing a depth. Choose a leaf capacity, cap the depth as a safety valve, and let the tree be as deep as each region’s density requires. Geographic data is never uniform, so any fixed depth is simultaneously too coarse over cities and absurdly too fine over water — and the whole point of a quadtree is that it does not have to be. This page extends spatial partitioning with quadtree indexes.

#Quick Reference

#Capacity Instead of Depth

A quadtree subdivides a cell into four children. With a fixed depth d, every cell is subdivided exactly d times regardless of what is in it, so cell area is uniform and cell population is whatever the world happens to put there. On a national address dataset that means a cell over a city centre holds hundreds of thousands of points while a cell over open sea holds none — and every consumer of the partitioning inherits that imbalance.

Capacity-driven subdivision inverts the rule: subdivide a cell only while it holds more than capacity points. Dense regions recurse deeply and sparse regions stop early, so leaf population becomes roughly uniform and leaf area varies by orders of magnitude. That is precisely the right way round, because everything downstream — a row group, a task, a tile — has a budget in items or bytes, not in square kilometres.

The one hazard is unbounded recursion. Points at identical coordinates cannot be separated by subdivision, so a naive capacity rule recurses until floating-point resolution runs out. A depth cap turns that into a bounded, explicit outcome.

#Implementation

# Requires: numpy>=1.26, shapely>=2.0  (Python 3.10+)
from __future__ import annotations

from dataclasses import dataclass, field

import numpy as np


@dataclass
class Cell:
    xmin: float
    ymin: float
    xmax: float
    ymax: float
    depth: int
    indices: np.ndarray
    children: list["Cell"] = field(default_factory=list)

    @property
    def is_leaf(self) -> bool:
        return not self.children

    @property
    def count(self) -> int:
        return int(self.indices.size)


def build_quadtree(
    xs: np.ndarray,
    ys: np.ndarray,
    *,
    capacity: int = 200_000,
    max_depth: int = 16,
    bounds: tuple[float, float, float, float] | None = None,
) -> Cell:
    """Subdivide on population, not on area, with depth as a safety valve.

    Returns the root cell; leaves are the partitions to hand downstream.
    """
    if xs.shape != ys.shape:
        raise ValueError("xs and ys must have the same shape")
    if xs.size == 0:
        raise ValueError("no points to partition")
    if capacity < 1:
        raise ValueError("capacity must be at least 1")

    if bounds is None:
        bounds = (float(xs.min()), float(ys.min()), float(xs.max()), float(ys.max()))
    root = Cell(*bounds, depth=0, indices=np.arange(xs.size))

    stack = [root]
    while stack:
        cell = stack.pop()
        if cell.count <= capacity or cell.depth >= max_depth:
            # At the cap, an over-capacity leaf is a legitimate outcome: those
            # points are coincident and geometry cannot separate them further.
            continue

        mid_x = 0.5 * (cell.xmin + cell.xmax)
        mid_y = 0.5 * (cell.ymin + cell.ymax)
        px, py = xs[cell.indices], ys[cell.indices]
        left, lower = px < mid_x, py < mid_y

        quadrants = (
            (cell.xmin, cell.ymin, mid_x, mid_y, left & lower),
            (mid_x, cell.ymin, cell.xmax, mid_y, ~left & lower),
            (cell.xmin, mid_y, mid_x, cell.ymax, left & ~lower),
            (mid_x, mid_y, cell.xmax, cell.ymax, ~left & ~lower),
        )
        for x0, y0, x1, y1, mask in quadrants:
            selected = cell.indices[mask]
            if selected.size == 0:
                continue                      # empty quadrants cost nothing
            child = Cell(x0, y0, x1, y1, cell.depth + 1, selected)
            cell.children.append(child)
            stack.append(child)

    return root


def leaves(root: Cell) -> list[Cell]:
    out, stack = [], [root]
    while stack:
        cell = stack.pop()
        if cell.is_leaf:
            out.append(cell)
        else:
            stack.extend(cell.children)
    return out

#Validation

The diagnostic is the distribution of leaf populations. A healthy capacity-driven tree has a narrow spread bounded above by the capacity; a long right tail means the depth cap is binding somewhere it should not be.

# Requires: numpy>=1.26 — is the partitioning actually balanced?
import numpy as np

sizes = np.array([leaf.count for leaf in leaves(root)])
depths = np.array([leaf.depth for leaf in leaves(root)])

print(f"{sizes.size} leaves · median {np.median(sizes):.0f} · "
      f"p95 {np.percentile(sizes, 95):.0f} · max {sizes.max()}")
print(f"depth range {depths.min()}–{depths.max()} · "
      f"{(sizes > CAPACITY).sum()} leaf/leaves over capacity (coincident points)")
print(f"empty leaves: {(sizes == 0).sum()}  (should be zero)")

Expected ranges on a national address dataset at capacity 200,000: median leaf around 120,000, p95 near the capacity, depth spanning roughly 3 to 12, zero empty leaves, and at most a handful of over-capacity leaves corresponding to genuinely coincident points such as flats sharing a building centroid.

#Edge Cases and Caveats

Coincident points at the depth cap. Flats in one building often share a centroid, so a leaf can sit above capacity at the cap no matter how deep you allow it to go. That is not a failure of the tree; it is the data saying geometry cannot separate these. Handle it downstream with a secondary key — unit number, feature identifier — rather than by raising the cap.

Bounds derived from the data. Building the root from the data’s own extent means two runs over different inputs produce incompatible trees, which breaks any join that assumes a shared partitioner. Fix the root bounds to the CRS extent or to a documented constant so partition identifiers are stable between runs — the same requirement that Sedona’s shared partitioner imposes.

Choosing capacity from tree aesthetics. A capacity that produces a pleasingly balanced tree is not the goal; a capacity that produces the right downstream unit is. If leaves become Parquet row groups, work backwards from the target row group size and the average bytes per feature.

#Frequently Asked Questions

Why is a fixed quadtree depth wrong for geographic data?

Because population, infrastructure, and observation are all wildly uneven, so a depth that gives sensible cell sizes over a city gives millions of empty cells over ocean and farmland, while a depth that suits the countryside leaves urban cells holding a thousand times more points than rural ones. Depth is a property of area; what you actually want to control is a property of content. Subdividing on a leaf capacity does that directly and lets depth vary as the data requires.

What leaf capacity should I choose?

Whatever makes a leaf a sensible unit of the thing it becomes downstream. If each leaf will be written as a Parquet row group, choose a capacity that produces a row group in the hundred-megabyte range. If each leaf becomes one task in a distributed join, choose a capacity that gives a task of a few seconds. The number is set by the consumer of the partitioning, not by the tree.

What happens when many points share exactly the same coordinates?

Subdivision cannot separate them, because every child cell that contains one contains all of them, so a capacity-driven tree recurses until it hits a depth limit or exhausts floating-point resolution. Always cap the depth, and treat a leaf that is over capacity at the cap as a legitimate outcome rather than a bug — it means those points are genuinely coincident and must be handled by a rule other than geometry.

#Related

• Spatial Partitioning with Quadtree Indexes — parent guide: the structure and how queries use it
• Quadtree vs R-Tree Index Build Time — the other structure, and what each costs to build
• Apache Sedona for Distributed Spatial Joins — where an unbalanced partitioner turns into a straggler task
• Row Group Sizing Strategies for Parquet — the downstream unit that usually sets the capacity

← Back to Spatial Partitioning with Quadtree Indexes