Computational Spherical Geometry

Robert Raskin
Geography-NCGIA, University of California, Santa Barbara, CA 93106 USA

There is a growing interest in processes and environmental changes occurring at the global scale. This challenge represents a "final frontier" for geographers more accustomed to local and regional studies. Global scale databases are proliferating rapidly, and planned remote sensing missions in the coming years will provide terabytes of data on an ongoing basis.

A characteristic feature of large-scale spatial analysis is that the spherical (or ellipsoidal) geometry of the earth cannot be ignored. This issue typically is handled by applying a planar projection and then performing planar analysis on the projection surface. This approach is undesirable because of the distortions in distance, area, and/or orientations introduced by the projection. If geography is to embrace global scale analysis, future geographic information systems (GIS) must account for the sphericity of the earth in a more explicit manner.

Computational geometry is concerned with spatial algorithms (and their computational complexity) that are a consequence of the geometry of the underlying topological space. Subareas include search, triangulation, convex hulls, intersections of geometric elements, quadtrees, etc. Such algorithms are central to the analysis capabilities of a modern GIS. However, work in computational geometry has been limited almost exclusively to the Euclidean spaces R2 and R3. The primary objectives of this study are to describe the computational aspects of spherical analysis, compare the computational efficiencies to analogous analyses in Euclidean spaces, identify efficient methods that might underly a future GIS designed for spherical geometry, and identify the extensions needed for the case of the ellipsoid.

Classical spherical trigonometry provides some of the mathematical foundation for this study, but does not address computational issues. A modern treatment of computational efficiency branches off in two directions depending on whether the sphere surface is indexed using spherical coordinates or whether it is considered a constrained subset of the Euclidean space R3. In the first approach, trigonometric calculations are ubiquitous. Such calculations are at least an order of magnitude more time-consuming than a simple arithmetic operation. In the second approach, points are represented as direction cosines, or dimensionless Cartesian coordinates. This approach requires increased storage overhead to represent the third dimension, but the number of trigonometric calculations is greatly reduced. The constrained subset approach also generalizes easily to the case of the ellipsoid. This approach is particularly useful for proving that the theoretical complexity of most spherical operations is the same as that in R3. However, there are other cases in which the complexity is that of the R2 or is not related to either Euclidean case. An example of the latter is finding the coordinates of a point lying a specified geodesic distance from a second point in a specified direction. Such an operation is trivial in Euclidean spaces.

Several formulas relevant to standard GIS operations are derived, such as the area of a spherical polygon area in terms of its vertices. Also considered are definitions of ellipses and other conic sections on the sphere. Issues related to tessellations of the sphere are also explored.