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

Bounding-volume hierarchies: prune box overlap searches

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

A bounding-volume hierarchy groups geometric objects under enclosing boxes. A query can reject a whole subtree when its enclosure does not intersect the requested box. This program stores axis-aligned rectangles and chooses a binary split by the wider axis of the current enclosure, sorting objects by center along that axis. Each internal node encloses both children; leaves store at most a configured number of original rectangles. Intersections include touching boundaries. The leaf check is necessary because overlapping a parent enclosure only makes its objects candidates. The hierarchy is built once from validated rectangles and is not updated in place. Duplicate IDs and inverted boxes are rejected before construction.

Operational case

Pump-47 and valve-19 have partly overlapping service boxes, sensor-61 touches a query near the right edge, and grid-83 lies well outside it. A query box from 40,40 to 75,55 returns the first three after leaf checks. The distant grid subtree may be pruned by its enclosure. If every object is a long rectangle overlapping the same central region, most enclosures overlap the query and the tree can do little pruning. Sorting by center is a deterministic split heuristic, not a guarantee of low overlap or the optimal tree for every workload.

Working Python program

python
class BoundingNode:
    def __init__(self, bounds, items=None, left=None, right=None):
        self.bounds = bounds
        self.items = items
        self.left = left
        self.right = right


def intersects(first, second):
    return (first[0] <= second[2] and second[0] <= first[2] and
            first[1] <= second[3] and second[1] <= first[3])


class DepotBoxHierarchy:
    def __init__(self, rectangles, leaf_capacity=2):
        if leaf_capacity < 1:
            raise ValueError("leaf capacity must be positive")
        if len({depot_id for depot_id, _ in rectangles}) != len(rectangles):
            raise ValueError("duplicate rectangle ID")
        if any(x0 > x1 or y0 > y1 for _, (x0, y0, x1, y1) in rectangles):
            raise ValueError("inverted rectangle")
        self.leaf_capacity = leaf_capacity
        self.root = self._build(list(rectangles)) if rectangles else None

    def _build(self, rectangles):
        boxes = [box for _, box in rectangles]
        bounds = (min(box[0] for box in boxes), min(box[1] for box in boxes),
                  max(box[2] for box in boxes), max(box[3] for box in boxes))
        if len(rectangles) <= self.leaf_capacity:
            return BoundingNode(bounds, items=rectangles)
        axis = 0 if bounds[2] - bounds[0] >= bounds[3] - bounds[1] else 1
        rectangles.sort(key=lambda item: (item[1][axis] + item[1][axis + 2], item[0]))
        middle = len(rectangles) // 2
        return BoundingNode(bounds, left=self._build(rectangles[:middle]),
                            right=self._build(rectangles[middle:]))

    def overlapping(self, query):
        x0, y0, x1, y1 = query
        if x0 > x1 or y0 > y1:
            raise ValueError("inverted query")
        matches = []
        pending = [self.root] if self.root else []
        while pending:
            node = pending.pop()
            if not intersects(node.bounds, query):
                continue
            if node.items is not None:
                matches.extend(depot_id for depot_id, box in node.items
                               if intersects(box, query))
            else:
                pending.extend((node.left, node.right))
        return sorted(matches)


index = DepotBoxHierarchy([
    ("pump-47", (12, 19, 47, 52)), ("valve-19", (45, 25, 61, 58)),
    ("sensor-61", (70, 15, 83, 47)), ("grid-83", (130, 80, 150, 97)),
])
print("overlap=", index.overlapping((40, 40, 75, 55)), sep="")

Output

Output
overlap=['pump-47', 'sensor-61', 'valve-19']

Time, space, and tradeoff

At each balanced build level, sorting a subset costs O(M log M), giving O(N log-squared N) time for this direct recursive implementation and O(N) stored nodes and records. Query work is O(V + K + R log R), where V visited nodes, K leaf rectangles tested, and R results sorted; worst-case traversal is O(N). Each intersection check uses constant work on four coordinates. This static index lacks deletion, incremental insertion, and box refitting after movement. For frequently moving objects, rebuild cost may dominate; compare with the moving-point grid and the existing packed R-tree before selecting a representation.

Common Mistakes

  • Do not report all objects merely because a parent enclosure overlaps.
  • Do not use point membership when the stored objects are rectangles.
  • Do not claim the center split guarantees small overlap.
  • Do not mutate an indexed rectangle without rebuilding or refitting ancestors.

Connected lessons

Compare its geometry and update costs with Spatial hash grids: move points between occupied cells, Point-region quadtrees: subdivide crowded cells, Morton ordering: decompose a grid window into code ranges, then run the spatial audit and contract quiz.

data structures
range-query-structures
Storage details