A Small Introduction to R-Trees

Jerry Huang

February 7, 2023

Introduction

Imagine we have a bunch of overlapping rectangles, and we want to query a point $p$ or a rectangle $r$ to see which rectangles encompass this point or overlap with this rectangle. How do we solve this problem?

One could think of a naive algorithm, iterate through all the rectangles, or sort the rectangles and binary search for the point [1]. A binary search could eliminate all points with a bottom left $x$ larger than $p_x$. Binary searching sounds interesting, and R-Trees is a natural progression on this idea of eliminating rectangles by cleverly storing close rectangles next to each other. Unlike a sorted list idea, R-Trees allows us to insert new rectangles efficiently, and potentially eliminate more rectangles than a simple binary search. To do this, think of an R-Tree node as a rectangle, specifically a "minimum bounding rectangle" of all of its children. If the R-Tree node is a child, then that is one of our original rectangles. To query, we can see which of the children the point/rectangle intersects, and go down this tree path. To insert into an R-Tree, we can check which path increases the minimum bounding rectangle the least, and recurse down until we can insert as one of the children. If there are too many children, then we call a split function, splitting the children into two new parent nodes.

from typing_extensions import Self
from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def calc_area(p1: Point, p2: Point) -> int:
  return (p2.y - p1.y) * (p2.x - p1.x)

def get_bottom_left(p1: Point, p2: Point) -> Point:
  return Point(x=min(p1.x, p2.x), y=min(p1.y, p2.y))

def get_top_right(p1: Point, p2: Point) -> Point:
  return Point(x=max(p1.x, p2.x), y=max(p1.y, p2.y))

class RTree:
  def __init__(self: Self, p1: Point, p2: Point, split_ratio: int) -> None:
    self.bottom_left = get_bottom_left(p1, p2)
    self.top_right = get_top_right(p1, p2)
    self.split_ratio = split_ratio
    self.children = []

  def insert_rect(self: Self, p1: Point, p2: Point) -> None:
    bottom_left = get_bottom_left(p1, p2)
    top_right = get_top_right(p1, p2)
    
    def insert_rect_helper(rtree: Self) -> None:
      if len(rtree.children) == 0:
        rtree.children.append(RTree(rtree.bottom_left, rtree.top_right, self.split_ratio))
      
      rtree.bottom_left = get_bottom_left(rtree.bottom_left, bottom_left)
      rtree.top_right = get_top_right(rtree.top_right, top_right)

      if len(rtree.children) < self.split_ratio:    
        rtree.children.append(RTree(p1, p2, self.split_ratio))
        return

      smallest_added_area = None
      best_child = None

      for child in rtree.children:
        child_area = calc_area(child.bottom_left, child.top_right)
        new_bottom_left = get_bottom_left(child.bottom_left, bottom_left)
        new_top_right = get_top_right(child.top_right, top_right)
        new_child_area = calc_area(new_top_right, new_bottom_left)

        if smallest_added_area is None or smallest_added_area > new_child_area - child_area:
          smallest_added_area = new_child_area - child_area
          best_child = child
      
      insert_rect_helper(best_child)

    insert_rect_helper(self)

To test this implementation, let's graph the R-Tree and randomly insert points:

from random import randint
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

def display_rtree(rtree: RTree) -> None:
  fig, ax = plt.subplots()
  ax.plot([-5, 105], [-5, 105], linestyle='None')

  def draw_dfs(rtree: RTree, depth: int) -> None:
    width = rtree.top_right.x - rtree.bottom_left.x
    height = rtree.top_right.y - rtree.bottom_left.y
    if len(rtree.children) == 0:
      ax.add_patch(Rectangle(rtree.bottom_left, width, height, fc=(1, 0, 0, 0.03 * depth), ec=(0, 0, 0, 1)))
    else:
      ax.add_patch(Rectangle((rtree.bottom_left.x - 5, rtree.bottom_left.y - 5), width + 10, height + 10, fill=None, linestyle='dotted'))
      for child in rtree.children:
        draw_dfs(child, depth + 1)
  
  draw_dfs(rtree, 1)
  plt.show()

def rand_point():
  return Point(randint(0, 100), randint(0, 100))

rtree = RTree(rand_point(), rand_point(), 2)
for _ in range(7):
  rtree.insert_rect(rand_point(), rand_point())

display_rtree(rtree)

That looks good! Note how the order of insertion matters, compare these two graphs:

rtree = RTree(Point(0, 50), Point(45, 75), 2)
rtree.insert_rect(Point(55, 50), Point(100, 75))
rtree.insert_rect(Point(25, 0), Point(45, 100))
rtree.insert_rect(Point(55, 0), Point(75, 100))

display_rtree(rtree)

rtree = RTree(Point(0, 50), Point(45, 75), 2)
rtree.insert_rect(Point(25, 0), Point(45, 100))
rtree.insert_rect(Point(55, 0), Point(75, 100))
rtree.insert_rect(Point(55, 50), Point(100, 75))

display_rtree(rtree)

Which one is better? Well, our goal is to eliminate as many possibilities as we can while traversing down the tree. We have two different heuristics which we can evaluate an R-Tree on:

• Minimize the total overlapping area of the R-Tree nodes
• Minimize the total area the R-Tree nodes encompasses

In the example above maxmizing one does not maximize the other. I think the first one is more initutive, but both are fine.

Notes on Implementation

Usually, we don't mix R-Tree non-leaf nodes and leaf nodes to be the children of the same node. We usually pack a bunch of rectangles into one leaf node and add to that leaf node until we call some split function, with the split_ratio being different for leaf and nonleaf nodes. I wrote the code this way for the sake of simplicity. In the future, I'll implement the conventional way and compare various ways of splitting, since those split algorithms only make sense when coding up R-Trees the conventional way.

[1] One could also think of a quadtree, but that could require preprocessing time bounded by $O(\sum_i w_ih_i)$, where $w_i, h_i$ is the width and height of a rectangle. Additionally, a quadtree structure doesn't extend well to querying rectangles, which also can take up to $O(wh)$ time.