Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Packed R-tree: search intersecting depot rectangles

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A packed R-tree groups spatial records into bounded-size nodes and stores a minimum bounding rectangle over each group. This example sorts rectangle centers into x-oriented strips, then groups each strip by y position. It repeats that packing process over child nodes until one root remains. A query descends only into nodes whose bounding rectangles intersect the query, then checks each candidate record's own rectangle. Bounding boxes can overlap; finding one matching child does not license skipping another. The index is static after bulk loading and caps node size without enforcing a minimum fill rule. It does not implement R-tree insertion, split repair, deletion, or geographic distance. Rectangle boundaries count as intersections here, and reversed input bounds are rejected.

Operational case

Five depot service zones include D-19 at [4, 5] to [11, 12], D-26 at [18, 7] to [26, 14], D-47 at [9, 10] to [16, 19], D-61 far away, and D-83 at [12, 2] to [20, 8]. A query from [10, 8] to [19, 15] intersects D-19, D-26, D-47, and D-83, including a boundary touch at y=8. A distant query returns an empty list. Internal bounds can admit a false candidate because they enclose a group, so the leaf-level check is necessary. Results are sorted by ID for repeatable output; the sort is a presentation cost, not part of pruning.

Working Python program

python
"""Static, packed rectangle index with exact intersection filtering."""

import math
from dataclasses import dataclass


@dataclass(frozen=True)
class Rectangle:
    west: int
    south: int
    east: int
    north: int

    def __post_init__(self):
        if self.west > self.east or self.south > self.north:
            raise ValueError("rectangle bounds are reversed")

    def intersects(self, other: "Rectangle") -> bool:
        return not (self.east < other.west or other.east < self.west or
                    self.north < other.south or other.north < self.south)


def enclosing(rectangles: list[Rectangle]) -> Rectangle:
    return Rectangle(min(box.west for box in rectangles), min(box.south for box in rectangles),
                     max(box.east for box in rectangles), max(box.north for box in rectangles))


@dataclass
class SpatialNode:
    bounds: Rectangle
    children: list
    leaf: bool


class PackedDepotIndex:
    def __init__(self, depots: list[tuple[str, Rectangle]], fanout: int = 4):
        if fanout < 2:
            raise ValueError("fanout must be at least two")
        if len({depot_id for depot_id, _ in depots}) != len(depots):
            raise ValueError("depot IDs must be distinct")
        self.fanout = fanout
        if not depots:
            self.root = None
            return
        level = [SpatialNode(enclosing([box for _, box in group]), group, True)
                 for group in self._groups(depots, lambda depot: depot[1])]
        while len(level) > 1:
            level = [SpatialNode(enclosing([child.bounds for child in group]), group, False)
                     for group in self._groups(level, lambda node: node.bounds)]
        self.root = level[0]

    def _groups(self, items: list, bounds_of):
        group_count = math.ceil(len(items) / self.fanout)
        slices = math.ceil(math.sqrt(group_count))
        slice_size = math.ceil(len(items) / slices)
        by_x = sorted(items, key=lambda item: (bounds_of(item).west + bounds_of(item).east,
                                               bounds_of(item).south + bounds_of(item).north))
        for start in range(0, len(by_x), slice_size):
            strip = sorted(by_x[start:start + slice_size],
                           key=lambda item: (bounds_of(item).south + bounds_of(item).north,
                                             bounds_of(item).west + bounds_of(item).east))
            for group_start in range(0, len(strip), self.fanout):
                yield strip[group_start:group_start + self.fanout]

    def search(self, query: Rectangle) -> list[str]:
        if self.root is None:
            return []
        matches = []
        pending = [self.root]
        while pending:
            node = pending.pop()
            if not node.bounds.intersects(query):
                continue
            if node.leaf:
                matches.extend(depot_id for depot_id, box in node.children if box.intersects(query))
            else:
                pending.extend(node.children)
        return sorted(matches)


depots = [
    ("D-19", Rectangle(4, 5, 11, 12)),
    ("D-26", Rectangle(18, 7, 26, 14)),
    ("D-47", Rectangle(9, 10, 16, 19)),
    ("D-61", Rectangle(42, 40, 48, 49)),
    ("D-83", Rectangle(12, 2, 20, 8)),
]
depot_index = PackedDepotIndex(depots, fanout=2)
print(depot_index.search(Rectangle(10, 8, 19, 15)))
print(depot_index.search(Rectangle(30, 30, 35, 35)))

Output

Output
['D-19', 'D-26', 'D-47', 'D-83']
[]

Time, space, and tradeoff

For N records and fixed fanout M at least two, repeated sorting during bulk loading takes O(N log N) time and O(N) stored nodes and records. The search visits only intersecting bounding rectangles when the groups separate well, but heavy overlap can force O(N) traversal. If K records match, sorting the returned IDs adds O(K log K) time and O(K) result space. The explicit traversal stack can grow with the number of visited nodes. No worst-case logarithmic query promise follows from the tree shape alone. A static k-d tree is suited to a different point-nearest-neighbor contract; this index answers axis-aligned rectangle intersection. Geographic coordinates require a separately defined projection and wrap policy.

Common Mistakes

  • Do not stop after the first intersecting child when bounding rectangles overlap.
  • Do not return every record inside an intersecting parent box without a leaf check.
  • Do not treat touching edges as disjoint under this inclusive rectangle contract.
  • Do not call this immutable packed index a live insertion and deletion API.

Connected lessons

Apply the invariant in the asset and depot audit project, then check the operations quiz.

Bounding-volume hierarchies: prune box overlap searches adds another spatial query contract.

data structures
range-query-structures
Storage details