Bounding-Box Hierarchies and R-Trees

Introduces minimum bounding rectangles (MBRs) as cheap pre-filters for polygon queries, the four-inequality MBR intersection test, and how R-trees organize MBRs hierarchically to answer spatial queries efficiently. Applies to air routing where flights must be tested against thousands of airspace polygons.

Step 1 of 157%

Tutorial

Minimum Bounding Rectangles

Aircraft routing systems must repeatedly check whether a flight path interacts with thousands of polygonal regions: restricted airspaces, weather cells, controlled sectors. Testing each polygon directly is expensive, so we use a cheap pre-filter built on minimum bounding rectangles.

The minimum bounding rectangle (MBR) of a polygon $P$ with vertices $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ is the smallest axis-aligned rectangle containing every vertex:

\text{MBR}(P) = [x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}],

where $x_{\min} = \min_i x_i$ , $x_{\max} = \max_i x_i$ , $y_{\min} = \min_i y_i$ , and $y_{\max} = \max_i y_i$ .

For example, the triangle with vertices $(1, 2)$ , $(4, 5)$ , $(3, 1)$ has

x_{\min} = 1, \quad x_{\max} = 4, \quad y_{\min} = 1, \quad y_{\max} = 5,

so its MBR is $[1, 4] \times [1, 5]$ .

Because the MBR contains the polygon, any query region that fails to touch the MBR cannot touch the polygon. We have replaced an expensive polygon test with four scalar comparisons.