Quadtrees, Spatial Decomposition, and Mesh Generation

Quadtrees, Spatial Decomposition, and Mesh Generation

Part 13 organized geometric objects so that a query could ignore most of them. Quadtrees apply the same principle to space itself: recursively divide a square into four children, then stop wherever the local geometry is simple enough. The result is simultaneously an index, a multiresolution picture, and—after a little repair—the skeleton of a mesh.

That combination is unusually powerful. A dense city block can receive thousands of tiny cells while an empty lake remains one large cell. A collision detector can focus on crowded regions; a GIS can store detail only near boundaries; a mesher can spend elements where a solution changes quickly.

One tree, three interpretations

Begin with an axis-aligned root square containing the domain. Splitting a cell at its horizontal and vertical midlines creates four equal children. A node is either a leaf, representing one current cell, or an internal node with four children.

The stopping test determines what the tree means:

A uniform depth-\(d\) quadtree has \(4^d\) leaves even if almost all are empty. An adaptive tree pays for detail locally. Its storage is \(O(m)\), where \(m\) is the number of materialized nodes, not the number of cells in the imaginary finest grid.

Point insertion and the split rule

For point data, each leaf holds at most \(b\) points. Inserting point \(p\) descends through the unique child containing \(p\). If the bucket overflows, split the leaf and redistribute its points. A small capacity produces finer spatial discrimination but more nodes; a large capacity reduces tree overhead but makes leaf scans longer.

This simple rule needs two safety valves. Coincident points can never be separated by subdivision, and finite-precision coordinates may stop making progress. Therefore use a maximum depth or minimum cell width, and allow an overfull terminal bucket. Choose one convention for midlines—for example, west and south intervals closed, east and north intervals half-open—so a point never belongs to two children.

child(cell, p):
    east  = p.x >= cell.mid_x
    north = p.y >= cell.mid_y
    return index(north, east)   # one deterministic owner

For a well-spread point set, insertion and lookup are often \(O(\log n)\). There is no unconditional logarithmic guarantee: adversarially clustered points can create depth \(n\) unless depth, precision, or compression is controlled. Building a depth-limited tree takes \(O(nD)\) by repeated insertion, where \(D\) is maximum depth; bulk construction by sorting Morton codes can approach \(O(n\log n)\).

Queries prune by geometry

An orthogonal range query visits a node only when its square intersects the query rectangle. If a leaf is reached, test its points exactly. The cost is naturally output-sensitive: \(O(v+k)\), where \(v\) is the number of visited nodes and \(k\) the reported points. Under regular distributions and a balanced spatial hierarchy, this behaves like \(O(\sqrt n+k)\) in two dimensions, but a thin query crossing many tiny cells can do worse.

Nearest-neighbor search uses cell distance instead of overlap. Maintain the best point found so far and visit children in increasing lower-bound distance from the query. Prune any cell whose minimum possible distance exceeds the current best. For radius search, the circle's bounding box gives a cheap first rejection, followed by exact distance tests.

Neighbor finding is subtler because adjacent leaves may have different sizes. One method ascends until it can cross the requested side, crosses to a sibling subtree, then descends along the opposite boundary. Another stores temporary leaf-to-leaf links. Links accelerate repeated stencil or mesh operations, but updates must maintain them.

from dataclasses import dataclass, field

@dataclass
class Cell:
    x0: float; y0: float; x1: float; y1: float
    points: list = field(default_factory=list)
    children: list | None = None

    def intersects(self, q):
        a, b, c, d = q
        return not (self.x1 < a or c < self.x0 or
                    self.y1 < b or d < self.y0)

def range_query(cell, rect, out):
    if not cell.intersects(rect):
        return                      # reject a whole subtree
    if cell.children is not None:
        for child in cell.children:
            range_query(child, rect, out)
        return
    x0, y0, x1, y1 = rect
    out.extend(p for p in cell.points
               if x0 <= p[0] <= x1 and y0 <= p[1] <= y1)

# Try changing the rectangle and count visited cells as well as output points.

Compression and looseness

A compressed quadtree contracts every maximal one-child path into one edge, storing only branching nodes and occupied leaves together with their cell levels. This turns enormous empty depth—common with tightly clustered coordinates—into constant structural overhead. Search must account for skipped levels, but the tree has \(O(n)\) relevant nodes under standard bucket assumptions.

A loose quadtree enlarges each node's effective region by a fixed factor while retaining the same subdivision centers. Extended objects are stored in the smallest node whose loose region contains them. An object moving slightly is less likely to cross a storage boundary, making loose trees valuable in games and collision broad phases. The price is overlap: a query may visit more candidate nodes, and an object can be geometrically outside the strict cell that indexes it.

Region quadtrees face a different boundary issue. A polygon edge may intersect a cell even when none of its vertices lies inside. Classification must therefore test cell-edge crossings (and containment), not merely vertex membership. Holes, rings, and domain boundaries also need explicit inside/outside semantics. Exact predicates or a documented tolerance prevent almost-on-boundary features from flickering between refinements.

Balance before meshing

Unrestricted adaptation permits a huge leaf beside many tiny leaves. That is fine for some indexes but awkward for neighbor stencils and meshes. A 2:1 balanced quadtree requires edge-adjacent leaves to differ by at most one level. Whenever refinement violates the rule, recursively split the coarse neighbor. Balance adds cells around a refined region, forming a graded transition rather than a cliff.

Turning leaves into a mesh is not as simple as drawing one diagonal per square. Where a refined edge meets a coarse edge, the intermediate endpoint is a hanging node. A conforming mesh requires every element intersection to be a whole shared vertex or edge. Common remedies split the coarse cell according to templates, connect its center to boundary vertices, or triangulate a balanced cell complex with consistent diagonal rules.

Balance controls size grading, not triangle quality by itself. Skinny triangles still harm interpolation and numerical conditioning. Practical pipelines combine quadtree refinement with feature-size tests, boundary recovery, template selection, smoothing, or Delaunay refinement. Cells cut by a curved boundary require special care: snap vertices only when doing so preserves topology, keep inside/outside labels, and refine when a cut creates a tiny angle or sliver.

The workload usually looks like this:

1. Enclose the domain in a root square and fix boundary conventions.
2. Refine cells intersecting features or failing an error/size criterion.
3. Enforce 2:1 balance to grade neighboring scales.
4. Clip, classify, or fit cells along the domain boundary.
5. Introduce edges and vertices using conforming templates.
6. Check orientation, topology, minimum angle, and element-size targets.

For a tree with \(m\) nodes, traversal and storage are \(O(m)\). Under common balancing schemes, enforcing 2:1 balance adds only a constant-factor number of cells, so it remains \(O(m)\); implementation time may be \(O(m\log m)\) with tree lookups or near-linear with Morton-order hashing and neighbor tables. Output mesh construction must additionally pay for its vertices and elements.

Where quadtrees earn their keep

In collision systems, leaves generate candidate pairs locally; loose bounds reduce reinsertion for moving objects. In GIS, region trees compress large uniform land-cover areas and refine coastlines or parcel boundaries. In image processing, each leaf represents a nearly constant block. In adaptive PDE solvers, estimated error drives refinement and balance supplies graded neighborhoods. The common theme is local work proportional to local complexity.

But quadtrees are axis-aligned and scale-sensitive. Rotated, needle-like features may intersect many cells. A poor root square wastes levels; unbounded coordinates require expansion or normalization. Deletion may merge four leaf siblings when their combined content meets the stopping rule, but repeated split/merge oscillation calls for hysteresis. Always distinguish mathematical degeneracy from implementation limits: coincident points, zero-area bounds, points on midlines, features on the domain border, and coordinates at maximum depth all need declared behavior.

The spatial indexes of Part 13 told us where to look. This chapter added a second idea: the index can also become a discretization of the domain, provided balance and conformity repair the adaptive boundaries. Part 15 will build on that hierarchy, using multilevel geometric structure to accelerate navigation across several related search catalogs rather than searching each one from scratch.