Suppose you need to check whether two drawn edges cross, or find points near a location. Testing every object directly can be expensive. A bounding box provides a cheap first question: could this object or group of points possibly matter? It is an axis-aligned rectangle in two dimensions, or a hyper-rectangle in higher dimensions, that contains what it represents. section 15.4.1 section 10.2.2
For a line segment, compare the boxes formed by its projections onto the x and y axes. If the projections are disjoint on either axis, the segments cannot cross. If the boxes overlap, the segments still might not cross: a more precise intersection test is necessary. The box rejects impossible cases; it does not establish a hit. section 15.4.1
Figure 15.16 Examples of non-intersecting segments: the bounding-box check can only rule out an intersection, but cannot confirm it.
Contrasts separated boxes with overlapping boxes around segments that nevertheless do not intersect. section 15.4.1
An R-tree applies the same containment idea to a collection of points. Each leaf has the smallest axis-aligned rectangle containing its points. Each internal node has the smallest such rectangle containing its children’s rectangles. The root therefore bounds the whole collection. Unlike a partition into disjoint regions, sibling rectangles can overlap, so a search may need to follow multiple branches. section 8.3 section 10.2.2
Figure 10.3 Cartesian plane representation of a (possible) R-tree for our city maps as presented in the example of figure 9.4 (the names of the cities are omitted to avoid confusion). This R-tree contains 12 bounding rectangles, from R1 to R12, organized in a hierarchical structure. Notice that rectangles can and do overlap, as shown in the bottom half.
Shows hierarchical R-tree rectangles in a plane, including overlapping regions. section 10.2.2
The box must stay consistent as the collection changes:
- On insertion, choose a leaf, add the point, and split nodes that exceed their entry limit; choices among overlapping rectangles and split heuristics affect the resulting tree. section 10.2.3
- On deletion, restore the tree’s occupancy requirements and update affected bounding regions. section 10.2.2 section 10.3.5
Bounding boxes also help with curves. For two symmetric quadratic Bézier curves, start with coarse boxes and discard the pair if they do not overlap. Otherwise, split at horizontal and vertical tangents into monotone sections, compare the sections’ boxes, and subdivide overlapping sections further. This narrows the work before approximating small sections with segments. section 15.4.4
Figure 15.26 The interval subdivision method used to check intersections between two symmetric, quadratic Bézier curves (A). (B) Compute the bounding boxes using what we know about the curve’s tangents at apex. Here, they overlap. (C) We thus need to move forward, computing the tangents to the curve parallel to the axes, and use them as pivot points at which we can split the curves. Each section is now monotonic and can be interpolated with a segment. Each pair of sections from the two curves will at most cross in one point. (D) For each section in curve C1, compute the intersections using only the overlapping sections in curve C2 (then sum the results for each of the three cases). (E) We can split each section further by halving it. Only some sub-sections will still overlap, and we can iterate steps (D-E) until they become small enough that the error in approximating a curve with a segment is within a given threshold.
Traces the progression from coarse curve boxes to boxes around successively smaller sections. section 15.4.4
The envelope’s shape is a trade-off. R-trees use axis-aligned boxes; SS-trees use spheres. Rectangles can grow differently along each axis and fit some point distributions more tightly, while spheres offer cheaper storage and distance calculations and may lead searches through fewer leaves. Neither shape eliminates overlapping branches: the reported worst-case costs for R-tree search and nearest-neighbor queries remain O(n). section 10.3 section 10.5.1
