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 radiusA ≤ radiusB and compute the bounding circle C as follows.

Firstly, observe that if d + radiusA ≤ radiusB, then B is the bounding circle.

Otherwise, the diameter of the bounding circle is d + radiusA + radiusB, which can be seen from the diagram below. Hence radiusC = ½(d + radiusA ≤ radiusB).

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 radiusA away from B to reach the circumference of C. Then move a distance radiusC towards B: centreC = interpolate(A, B)[(radiusC - radiusA) / 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.