R-trees: group objects inside enclosing rectangles

After this page, you should be able to:

• Explain the enclosing-bound invariant and why sibling rectangles can overlap.

• Distinguish a bounding-box candidate from an exact geometry match.

Builds on: A PR tree partitions cells; an R-tree groups object bounds instead.

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¶

A parent bound encloses every descendant object¶

A line or polygon can cross many fixed partition cells. An R-tree instead groups objects and stores a minimum bounding rectangle (MBR) for each object or child group. Every parent entry must enclose all bounds below that entry. Internal entries refer to child nodes; leaf entries associate object bounds with record identifiers.

An ordinary R-tree is a balanced multiway structure with all leaves at the same depth and configured node-occupancy limits. Its construction and splitting policy tries to keep bounds useful. This reading starts with a given small tree; it does not implement general insertion, balancing or node splitting.

Sibling rectangles may overlap¶

R-tree sibling bounds are enclosures, not a disjoint partition of the plane. A query can intersect several siblings, requiring more than one branch. Tree balance limits path length but does not guarantee that a query follows only one path.

The following original example stores five line segments. It uses a different object/query example from the shared point comparison so that filtering and exact geometry can be distinguished.

Build the bounds of a given two-leaf tree¶

segments = {
    "L1": ((0, 0), (10, 10)),
    "L2": ((0, 7), (6, 7)),
    "L3": ((8, 0), (10, 2)),
    "L4": ((3, 5), (3, 9)),
    "L5": ((5, 6), (9, 8)),
}
line_query = (2, 6, 4, 8)

def segment_bounds(segment):
    a, b = segment
    return (min(a[0], b[0]), min(a[1], b[1]),
            max(a[0], b[0]), max(a[1], b[1]))

def enclosing_bounds(boxes):
    boxes = list(boxes)  # requires a nonempty collection
    return (min(b[0] for b in boxes), min(b[1] for b in boxes),
            max(b[2] for b in boxes), max(b[3] for b in boxes))

class RNode:
    def __init__(self, entries, leaf):
        self.entries = list(entries)  # (enclosing_box, child_or_id)
        self.leaf = leaf

line_boxes = {key: segment_bounds(value) for key, value in segments.items()}
group_u = RNode([(line_boxes[key], key) for key in ["L1", "L2"]], True)
group_v = RNode([(line_boxes[key], key) for key in ["L3", "L4", "L5"]], True)
r_root = RNode([
    (enclosing_bounds(box for box, _ in group_u.entries), group_u),
    (enclosing_bounds(box for box, _ in group_v.entries), group_v),
], False)

var segments=new Map([["L1",[[0,0],[10,10]]],["L2",[[0,7],[6,7]]],["L3",[[8,0],[10,2]]],
    ["L4",[[3,5],[3,9]]],["L5",[[5,6],[9,8]]]]), line_query=[2,6,4,8];
function segment_bounds([a,b]) { return [Math.min(a[0],b[0]),Math.min(a[1],b[1]),Math.max(a[0],b[0]),Math.max(a[1],b[1])]; }
function enclosing_bounds(boxes) {
    boxes=[...boxes]; if(!boxes.length)throw new RangeError("nonempty boxes required");
    return boxes.reduce((a,b)=>[Math.min(a[0],b[0]),Math.min(a[1],b[1]),Math.max(a[2],b[2]),Math.max(a[3],b[3])]);
}
class RNode { constructor(entries,leaf) { this.entries=[...entries]; this.leaf=leaf; } }
var line_boxes=new Map([...segments].map(([key,value])=>[key,segment_bounds(value)]));
var group_u=new RNode(["L1","L2"].map(k=>[line_boxes.get(k),k]),true);
var group_v=new RNode(["L3","L4","L5"].map(k=>[line_boxes.get(k),k]),true);
var r_root=new RNode([[enclosing_bounds(group_u.entries.map(e=>e[0])),group_u],
    [enclosing_bounds(group_v.entries.map(e=>e[0])),group_v]],false);

segments=Dict("L1"=>((0,0),(10,10)),"L2"=>((0,7),(6,7)),"L3"=>((8,0),(10,2)),
    "L4"=>((3,5),(3,9)),"L5"=>((5,6),(9,8)))
line_query=(2,6,4,8)
function segment_bounds(segment)
    a,b=segment; return (min(a[1],b[1]),min(a[2],b[2]),max(a[1],b[1]),max(a[2],b[2]))
end
function enclosing_bounds(boxes)
    boxes=collect(boxes)
    return (minimum(b[1] for b in boxes),minimum(b[2] for b in boxes),
        maximum(b[3] for b in boxes),maximum(b[4] for b in boxes))
end
struct RNode
    entries::Vector{Any}
    leaf::Bool
end
RNode(entries,leaf)=RNode(Any[entries...],leaf)
line_boxes=Dict(k=>segment_bounds(v) for (k,v) in segments)
group_u=RNode([(line_boxes[k],k) for k in ["L1","L2"]],true)
group_v=RNode([(line_boxes[k],k) for k in ["L3","L4","L5"]],true)
r_root=RNode([(enclosing_bounds(b for (b,_) in group_u.entries),group_u),
    (enclosing_bounds(b for (b,_) in group_v.entries),group_v)],false)

Group U encloses (0,0,10,10); group V encloses (3,0,10,9). Both intersect query (2,6,4,8), so neither can be skipped. This deliberately overlapping grouping illustrates query behaviour, not an optimal packing claim. Both leaves are at depth one; their occupancies two and three fit an example maximum of three and minimum of two.

A bounding-box hit can be a false positive¶

L1’s diagonal has box (0,0,10,10), which overlaps the query, but the line itself does not cross the query rectangle: at x between 2 and 4 its y is between 2 and 4, below the query. L2 and L4 do intersect the query.

The index produces candidates, followed by a predicate on the actual geometry. For axis-aligned rectangular objects and a rectangle-intersection question, box overlap can itself be exact. For general geometry, enclosure is sufficient to reject a disjoint box but insufficient to confirm intersection.

Reference: Guttman’s original R-tree paper. The PostGIS spatial-index workshop explains the same filter/refine principle in an application setting.

Check your understanding¶

Predict the answer before opening the explanation.

1. Does diagonal L1 intersect the query (2,6,4,8) just because its box does?

2. The example’s leaves are at the same depth. Can the query choose only one of groups U and V?

Next: Range candidates and exact refinement. The following operation reading reuses that traversal for exact lookup and develops construction, nearest search and deletion.