The Voronoi diagram, which is an important data structure in computational geometry, is employed in the field of GIS due to its natural proximity and dynamic stability 1–3. With the rapid development of earth observation technology, it is possible to acquire worldwide large-scale, multi-scale and multi-temporal data, and the research scope has been expanded from local to global. The spherical Voronoi diagram, which is the topic of much research in the GIS field, has been used in areas such as spherical modeling4,5, spatial interpolation6,7, ocean simulation8,9, and meteorological analysis10. Researchers have developed both vector- and raster-based algorithms to generate spherical Voronoi diagrams.

Vector-based algorithms include the insertion method11, scan line algorithm12, and projection algorithm13, most considering only Voronoi diagrams of spherical point sets. To generate spherical Voronoi diagrams of polyline and polygon sets, Christopher applied the point-line concept to the sphere by decomposing complicated solids into simple points and lines14. Although polylines and polygons can be well processed in this algorithm, the data structures and calculations are complex, which makes it impossible to handle large quantities of spherical data. Furthermore, vector-based algorithms are incapable of hierarchical expression of spherical data. Hence raster-based algorithms have been developed, including the attribution15,16, expansion17, hierarchy18, and raster scanning19,20 algorithms. Raster-based algorithms generate Voronoi diagrams by discretizing the spherical space into spherical polygons and calculating the nearest sites for each one. The differences among these algorithms lie in the methods of discretizing the spherical surface and obtaining the nearest sites. The spherical surface can be discretized into meshes like the quaternary triangular17, ortho-octahedral dissecting21, and spherical hexagonal mesh22. The nearest sites can be acquired by computing and comparing the distances between the polygon and all sites, or obtaining these from its neighbor polygons. Solutions have also been developed based on GPU parallelism or quadtree hierarchies to improve the efficiency of the Voronoi diagram generation algorithm. Tu (2015) 23developed a method for GPU parallel raster scanning on the CUDA platform that generated Voronoi diagrams in linear time. Wang (2015) 18developed a hierarchical algorithm that generates a spherical Voronoi diagram with a lower-level grid, and subdivides the boundary grids and performs attribution judgments on the sub-grids to produce a higher-level Voronoi diagram.

The attribution algorithm15, which ensures the Voronoi attribution of a blank grid by computing the distance to all the sites and obtaining the nearest, is one of the most accurate, and its time efficiency is less when working with huge amounts of data due to its higher temporal complexity. The raster scanning algorithm, which avoids computing and comparing the distance to all sites by transferring the nearest site information from neighbor grids to a central blank grid, has relatively good time complexity, but its accuracy is difficult to guarantee due to the incompleteness of the scanning. To make full use of the advantages of these two algorithms and make up for their shortcomings, we propose a spherical raster Voronoi diagram generating algorithm, which combines edge attribution with bidirectional scanning and is based on ortho-octahedral dissection. The algorithm establishes the transformation relationship from planar coordinates to spherical latitude and longitude, preferentially determines the attribution of edge grids through the attribution algorithm, and uses forward scanning and reverse error correction to obtain the right attribution of all other grids.

The remainder of this paper is organized as follows. Section 2 discusses the operational principles of the proposed algorithm. Section 3 experimentally validates the accuracy and temporal efficiency of the algorithm. Section 4 discusses the merits of the proposed algorithm, while section 5 presents our conclusions and suggests future research.