Point quadtrees: split through a stored point

After this page, you should be able to:

• Extend a point-based split from one active axis to four two-axis quadrants.

• Trace insertion and range pruning with explicit east/north tie ownership.

Builds on: K-d construction splits through a stored point; here both axes are used at each node.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

JavaScript points are arrays compared by same_point; Julia points are value tuples. Julia coordinate/child indices are one-based (x=1, y=2; SW/SE/NW/NE=1/2/3/4), while depth still starts at zero. R-tree orientation uses exact big-integer arithmetic for the supplied integer-coordinate geometry; nearest distances remain floating calculations. General R-tree update code is still conceptual in every language.

Follow the five operations¶

Extend the familiar point-based split to both axes¶

Our two-dimensional k-d tree splits through the current point along one active axis. A point quadtree splits through the current point along both x and y, producing four possible children. Each node stores one point; the split is restricted to its inherited region.

This is a change in the branching rule, not a midpoint subdivision. Inserting another first point can move the initial boundaries, just as it can change the insertion-order k-d tree. No balancing guarantee follows from having four children.

Assign every coordinate tie to exactly one quadrant¶

Use Cartesian axes, with y increasing northwards. West means x < sx; east means x >= sx. South means y < sy; north means y >= sy. Detect an identical point before branching. This gives child order SW, SE, NW, NE.

def point_quadrant(point, pivot):
    return int(point[0] >= pivot[0]) + 2 * int(point[1] >= pivot[1])

class PointQuadNode:
    def __init__(self, point):
        self.point = point
        self.children = [None] * 4

def point_quad_insert(root, point):
    if root is None:
        return PointQuadNode(point)
    node = root
    while True:
        if point == node.point:
            return root
        quadrant = point_quadrant(point, node.point)
        child = node.children[quadrant]
        if child is None:
            node.children[quadrant] = PointQuadNode(point)
            return root
        node = child

def point_quad_contains(root, point):
    node = root
    while node is not None:
        if point == node.point:
            return True
        node = node.children[point_quadrant(point, node.point)]
    return False

point_root = None
for point in shared_points:
    point_root = point_quad_insert(point_root, point)

function point_quadrant(point,pivot) { return Number(point[0]>=pivot[0])+2*Number(point[1]>=pivot[1]); }
class PointQuadNode {
    constructor(point) { this.point=point; this.children=Array(4).fill(null); }
}
function point_quad_insert(root,point) {
    if (root===null) return new PointQuadNode(point);
    let node=root;
    while (true) {
        if (same_point(point,node.point)) return root;
        const q=point_quadrant(point,node.point), child=node.children[q];
        if (child===null) { node.children[q]=new PointQuadNode(point); return root; }
        node=child;
    }
}
function point_quad_contains(root,point) {
    let node=root;
    while (node!==null) {
        if (same_point(point,node.point)) return true;
        node=node.children[point_quadrant(point,node.point)];
    }
    return false;
}
var point_root=null;
for (const point of shared_points) point_root=point_quad_insert(point_root,point);

point_quadrant(point,pivot)=1+Int(point[1]>=pivot[1])+2Int(point[2]>=pivot[2])
mutable struct PointQuadNode
    point
    children::Vector{Any}
end
PointQuadNode(point)=PointQuadNode(point,Any[nothing for _ in 1:4])
function point_quad_insert(root,point)
    root===nothing && return PointQuadNode(point)
    node=root
    while true
        point==node.point && return root
        q=point_quadrant(point,node.point); child=node.children[q]
        if child===nothing; node.children[q]=PointQuadNode(point); return root; end
        node=child
    end
end
function point_quad_contains(root,point)
    node=root
    while node!==nothing
        point==node.point && return true
        node=node.children[point_quadrant(point,node.point)]
    end
    return false
end
point_root=let tree=nothing
    for point in shared_points; tree=point_quad_insert(tree,point); end
    tree
end

The code assumes finite numeric two-element tuples, as on the k-d-tree pages. It returns the resulting root and ignores repeated identical points. These iterative operations use constant working space. Insert/search follow one path, costing $O(h+1)$ for nonempty tree height h, with linear worst-case paths; an empty tree takes constant time. Persistent storage is $O(n)$ for n distinct points.

Reuse the seven-point insertion order¶

At A=(5,4), D goes SW, C goes SE, B goes NW and F goes NE. E=(3,6) first goes NW to B=(2,7), then SE because 3≥2 and 6<7. G=(9,2) first goes SE to C=(8,1), then NE.

A split line drawn on the plot is a decision boundary, not a stored object or a road. Deeper cross-shaped cuts stop at inherited boundaries. Labels on the tree identify stored points rather than rectangular cells.

Visit every quadrant the closed query can reach¶

def point_quad_range(root, rect):
    rect = checked_rect(rect)
    xmin, ymin, xmax, ymax = rect
    out, stack = [], []
    if root is not None:
        stack.append(root)
    while stack:
        node = stack.pop()
        x, y = node.point
        if in_closed_rect(node.point, rect):
            out.append(node.point)
        west, east = xmin < x, xmax >= x
        south, north = ymin < y, ymax >= y
        possible = (west and south, east and south,
                    west and north, east and north)
        for i in range(3, -1, -1):
            if possible[i] and node.children[i] is not None:
                stack.append(node.children[i])
    return out

function point_quad_range(root,rect) {
    rect=checked_rect(rect); const [xmin,ymin,xmax,ymax]=rect, out=[], stack=root===null ? [] : [root];
    while (stack.length) {
        const node=stack.pop(), [x,y]=node.point;
        if (in_closed_rect(node.point,rect)) out.push(node.point);
        const west=xmin<x, east=xmax>=x, south=ymin<y, north=ymax>=y;
        const possible=[west&&south,east&&south,west&&north,east&&north];
        for (let i=3;i>=0;i--) if (possible[i] && node.children[i]!==null) stack.push(node.children[i]);
    }
    return out;
}

function point_quad_range(root,rect)
    rect=checked_rect(rect); xmin,ymin,xmax,ymax=rect
    out=Any[]; stack=root===nothing ? Any[] : Any[root]
    while !isempty(stack)
        node=pop!(stack); x,y=node.point
        in_closed_rect(node.point,rect) && push!(out,node.point)
        west,east=xmin<x,xmax>=x; south,north=ymin<y,ymax>=y
        possible=(west&&south,east&&south,west&&north,east&&north)
        for i in 4:-1:1
            possible[i] && node.children[i]!==nothing && push!(stack,node.children[i])
        end
    end
    return out
end

The shared rectangle visits A, D, B and E, reporting D, B, E in this traversal order. It skips A’s entire east side, but must search both north and south on the west side. Equal upper query bounds can include north/east ties; equal lower bounds cannot reach strictly west/south points.

Each visited nonempty node performs a constant amount of work, so time is $O(v+1)$ for v visits, up to $O(n)$. A depth-first stack has $O(h+1)$ pending nodes because branching is bounded by four, plus $O(r)$ result storage. The split tests may explore more than an exact inherited-cell intersection test, but never exclude a valid answer.

The point-quadtree idea is also described in OpenDSA’s spatial-structure comparison.

Check your understanding¶

Predict the answer before opening the explanation.

1. At A=(5,4), which first branch owns a new point (5,3)? Explain both coordinate decisions.

2. If B becomes the first inserted point, must the point-quadtree partition stay the same? Must the final shared range-answer set stay the same?

Next: Point-quadtree nearest search, deletion and costs.