R-Trees

1 min read•1 page

An R-Tree is a dynamic height-balanced tree structure designed to index multi-dimensional spatial objects. Unlike KD-trees or Octrees, the bounding regions in an R-Tree can overlap.

RTreeNode:

1. MBR (Minimum Bounding Rectangle): The smallest bounding box enclosing all child elements. 2. Overlapping Bounds: Subtrees are allowed to overlap, avoiding rigid coordinate subdivision. 3. B-Tree Derivative: Nodes have variable capacity limits, splitting when full.

python

1class RTreeNode:
2    def __init__(self, is_leaf=False):
3        self.is_leaf = is_leaf
4        self.mbr = MinimumBoundingRectangle() # MBR enclosing all children
5        self.children = [] # List of RTreeNodes or spatial objects
6        
7    def get_enclosing_mbr(self) -> 'MinimumBoundingRectangle':
8        # Union of all child MBRs
9        ...

2 min read•1 page

R-Trees insert elements dynamically. To insert a new object, the algorithm recursively traverses down by picking the child bounding box that requires the least area enlargement.

ChooseLeaf(node, new_object):

1. Enlargement Cost: Calculate area difference after enclosing the new object. 2. Least Area Enlargement: Route the object to the node with minimal enlargement cost. 3. Tie Breaking: Choose child node with smaller overall area on tie.

python

1def choose_leaf(node, new_object) -> RTreeNode:
2    if node.is_leaf:
3        return node
4        
5    best_child = None
6    min_enlargement = float('inf')
7    
8    for child in node.children:
9        # Calculate area expansion if child MBR expands to enclose new_object
10        area_before = child.mbr.area()
11        area_after = child.mbr.union(new_object.mbr).area()
12        enlargement = area_after - area_before
13        
14        if enlargement < min_enlargement:
15            min_enlargement = enlargement
16            best_child = child
17            
18    return choose_leaf(best_child, new_object)

New Object Position X

-1.50

1 min read•1 page

R-Tree search processes overlaps recursively. If the query region intersects a node's Minimum Bounding Rectangle, we descend; otherwise, the entire branch is pruned.

SearchRTree(node, query_rect):

1. MBR Intersection: Check if query boundaries overlap the node's bounds. 2. Branch Pruning: Skip searching child branches whose bounding boxes do not overlap. 3. Multiple Branches: Because child bounds can overlap, we may need to traverse multiple branches.

python

1def search_rtree(node, query_rect, results):
2    # Base Case: check if node's MBR intersects the query rectangle
3    if not node.mbr.intersects(query_rect):
4        return # Prune this branch immediately
5        
6    if node.is_leaf:
7        for obj in node.children:
8            if obj.mbr.intersects(query_rect):
9                results.append(obj)
10    else:
11        for child in node.children:
12            search_rtree(child, query_rect, results)

Query Box Position X

-1.00