An algorithm for the generation of Voronoi diagrams on the sphere based on QTM

摘要

In order to efficiently store and analyze spatial data on a global scale, the digital expression of Earth data in a data model must be global, continuous, and conjugate, i.e., a spherical dynamic data model is needed. The Voronoi data structure is the only published attempt (Wright and Goodchild, 1997) and the only possible solution currently available (Li et al., 1999) for a dynamic GIS. However, the complexity of the Voronoi algorithm for line sets and area sets in vector mode limits its application in a dynamic GIS. So far, there is no raster-based Voronoi algorithm for objects (including points, arcs, and regions) on a spherical surface. To overcome this serious deficiency, an algorithm for generating a spherical Voronoi diagram is presented, based on the O-QTM (Octahedral Quaternary Triangular Mesh). The principle of the dilation operation in mathematical morphology is extended to the spherical surface. A method is developed for a spherical distance transformation based on the QTM. A detailed algorithm is also presented. This algorithm can handle points, arcs, and area features on a spherical surface. Tests have shown that the computational time consumption of this algorithm with points, arcs, and areas is equal and proportionate to the levels of the spherical surface tessellation; and the difference (distortion) between the great circle distance and the QTM cells distance is slightly related to spherical distance (not as the raster dilation on a planar surface), and is mainly related to the locations of the generating points.