Jason Davies → Maps

# Bounding Circle Tree

Similar to axis-aligned bounding box (AABB) trees, bounding circle trees can be used to speed up finding line segment intersections on the sphere.

Line segments are converted into a series of bounding circles, and then adjacent circles are repeatedly merged until a single bounding circle remains.

## Merging Circles

Given two circles *A* and *B* situated a distance *d* apart, assume *radius*_{A} ≤ radius_{B} and compute the bounding circle *C* as follows.

Firstly, observe that if *d + radius*_{A} ≤ radius_{B}, then *B* is the bounding circle.

Otherwise, the diameter of the bounding circle is *d + radius*_{A} + radius_{B}, which can be seen from the diagram below.
Hence *radius*_{C} = ½(d + radius_{A} ≤ radius_{B}).

The bounding circle centre, relative to the centre of *A*, can be found by interpolating along the path connecting *A* and *B*.
First move a distance *radius*_{A} away from *B* to reach the circumference of *C*.
Then move a distance *radius*_{C} towards *B*:
*centre*_{C} = interpolate(A, B)[(radius_{C} - radius_{A}) / d].

Note that the above calculations only rely on distances and interpolation, so they work in both Cartesian and spherical settings.
On a sphere, a bounding circle radius of 180° or greater is a special case as it covers the whole sphere.