Geodesic Intersections

Abstract

A complete treatment of the intersections of two geodesics on the surface of an ellipsoid of revolution is given. With a suitable metric for the distances between intersections, bounds are placed on their spacing. This leads to fast and reliable algorithms for finding the closest intersection, determining whether and where two geodesic segments intersect, finding the next closest intersection to a given intersection, and listing all nearby intersections. The cases where the two geodesics overlap are also treated. The intersection of lines plays a central role when performing geometric operations on geographical objects. Often, this is performed on a map projection; but this has the disadvantage that the projection introduces an inevitable distortion. It is, therefore, preferable to compute the intersections directly on the surface of the Earth (or, more precisely, on some ellipsoidal approximation to the Earth); in this case, the lines in question are best taken to be geodesics, the generalization of straight lines to a curved surface. This paper describes a fast, reliable, and accurate method of computing the intersections of geodesics.