An algorithm using edge attribution and bilateral scanning to generate spherical raster Voronoi diagrams

doi:10.21203/rs.3.rs-3332783/v1

Download PDF

Article

An algorithm using edge attribution and bilateral scanning to generate spherical raster Voronoi diagrams

https://doi.org/10.21203/rs.3.rs-3332783/v1

This work is licensed under a CC BY 4.0 License

Version 1

posted

You are reading this latest preprint version

The spherical Voronoi diagram is an important research field in computational geometry, and the method that generates it is a key technology. Most spherical raster algorithms are extensions of planar algorithms. The attribution determination algorithm is one of the most accurate spherical raster Voronoi algorithms. However, it deals inefficiently with large amounts of data. To overcome this issue, a spherical Voronoi diagram generation algorithm that combines edge attribution with bidirectional scanning based on octahedral subdivision is proposed. A coordinate conversion method is built to perform coordinate transformation between latitude–longitude and Cartesian coordinates. The Voronoi attributions of edge grids are determined by computing and comparing the distances to all the sites. A 3×3 template is designed for forward scanning, where grids obtain attributions from their neighbors. Reverse error correction scanning is conducted based on the forward scanning result to guarantee that all grids are correctly assigned. Experiments were conducted to compare the proposed algorithm with the attribution determination algorithm, showing that it has the same accuracy while saving more than 40% of computations. The efficiency advantage of the proposed algorithm becomes more obvious at higher resolutions.

Earth and environmental sciences/Space physics

Physical sciences/Mathematics and computing

spherical Voronoi diagram

bilateral scanning

attribution determination

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 modeling^4,5, spatial interpolation^6,7, ocean simulation^8,9, and meteorological analysis¹⁰. Researchers have developed both vector- and raster-based algorithms to generate spherical Voronoi diagrams.

Vector-based algorithms include the insertion method¹¹, scan line algorithm¹², and projection algorithm¹³, 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 lines¹⁴. 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 attribution^15,16, expansion¹⁷, hierarchy¹⁸, and raster scanning^19,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 triangular¹⁷, ortho-octahedral dissecting²¹, and spherical hexagonal mesh²². 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) ²³developed a method for GPU parallel raster scanning on the CUDA platform that generated Voronoi diagrams in linear time. Wang (2015) ¹⁸developed 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 algorithm¹⁵, 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.

2.1 Ortho-octahedral dissection method

Latitude–longitude grids divide the earth’s surface into a series of regions by using equal longitude and latitude intervals. However, the shapes and areas of regions are quite different. As shown in Fig. 1, the higher the latitude, the smaller the real area of the grid and the greater the deformation when using the equatorial grid as a reference. Hence the accuracy of Voronoi diagrams generated based on latitude–longitude grids will be uneven.

To obtain spherical Voronoi diagrams of higher and more uniform precision, a spherical grid, combining the octahedron and the spherical surface and folding the square over the sphere, is used to divide the earth’s surface into a series of nearly uniform regions²¹. The square is divided into eight triangles, where the inner four are mapped to the northern hemisphere, and the outer four to the southern hemisphere, as shown in Fig. 2. According to this mapping rule, spherical Voronoi diagrams can be obtained by gridding the square as in Fig. 2, computing the planar Voronoi diagram on the gridded square, and mapping the computed grids in the square to the spherical surface. We next discuss the transformation from planar coordinates to spherical latitude and longitude, which is the key to mapping the grids to the spherical surface.

2.2 Coordinate transformation

Latitude–longitude coordinates can be acquired in longitude and latitude steps. In the longitude step, as described above, the north pole is located at the plane’s center, as shown in Fig. 3, and the line leading upward from the plane’s center is zero degrees longitude. With this line as a reference, east and west longitudes can be obtained along the clockwise and counterclockwise directions, respectively. If a point P is located in the northern hemisphere (regions 1–4 in Fig. 3(a)), its longitude is the angle between vectors $\overrightarrow{OP}$ and $\overrightarrow{OA}$, which can be calculated as

$$\lambda =arccos\frac{\overrightarrow{OP}*\overrightarrow{OA}}{\left|\overrightarrow{OP}\right|*\left|\overrightarrow{OA}\right|}$$

and when point P is in the southern hemisphere (regions 5–8 in Fig. 3(b)), the symmetry of this point about the equator (P¹ in Fig. 3(b)), which has the same longitude as point P, is first found, and then the longitude can be similarly calculated.

The latitude can be obtained as follows. A line from the pole to the equator will span 90 degrees of latitude. Taking the northern hemisphere as an example, the latitude of point P in Fig. 4 can be represented by the length ratio of OP and OM,

$$\phi = \frac{OP}{OM}*90^\circ ,$$

and the latitude of points in the southern hemisphere can be represented and calculated by the length ratio of $\overrightarrow{{O}^{1}{P}^{1}}$ and $\overrightarrow{{O}^{1}{M}^{1}}$, where ${O}^{1}$ is the square corner in Fig. 4, i.e. the south pole of the earth.

2.3 Improved Voronoi diagram generation algorithm

As described in section 1, the attribution algorithm obtains the Voronoi attribution by computing and comparing distances to all the sites, while the raster scanning algorithm obtains the Voronoi attribution by transferring the nearest site information from neighbor grids. To make full use of the precision advantage of the attribution algorithm and the efficiency advantage of the raster scanning algorithm, an improved Voronoi diagram generation algorithm, combining attribution calculation with raster scanning, is proposed. The Voronoi attribution of the grids located on the boundary of the square are computed using the attribution algorithm to set up an initial area for scanning, as shown in Fig. 5. To improve computing efficiency, a forward scanning step and reverse error correction step for the other grids are designed based on the raster scanning algorithm to reduce attribution calculations.

2.3.1 Forward Scanning

As shown in Fig. 6, a 3×3 neighborhood template, which is used for top-down forward scanning and bottom-up reverse error correction, is first created.

In the forward scanning process, if Q₁–Q₄ in the 3×3 neighborhood of a blank grid belong to the same Voronoi region, i.e., they have the same Voronoi attribution, the blank grid will be assigned the same Voronoi attribution (as shown in Fig. 7(a)). If the four neighbors of the blank grid belong to different Voronoi regions(as shown in Fig. 7(b)), the blank grid will be determined to be a boundary grid by the algorithm, and the Voronoi attribution should be obtained by using the attribution algorithm, i.e., computing the distances from the blank grid to all the sites, and choosing the nearest by comparing the distances.

All the grids on the square obtain their Voronoi attribution after forward scanning. However, some grids obtain the wrong attribution, which results in the appearance of non-convex Voronoi polygons, as illustrated in Figs. 8(a) and (b). To more explicitly determine the reason for a wrong attribution, the spherical surface obtained from the square octahedron should be folded back to a square, as shown in Figs. 8(c)–(e). Figure 8(c) shows the result of the forward scan, the red pixels in Fig. 8(d) show the grids with wrong Voronoi attribution, and Fig. 8(e) shows the correct Voronoi attribution, as obtained by the attribution algorithm. Comparing Figs. 8(d) and (e), it can be seen that the grids with Voronoi attribution errors are distributed near the correct Voronoi region boundaries, and exhibit the characteristic of extending toward the lower-right.

2.3.2 Reverse Error Correction

When a blank grid is located on the correct Voronoi boundary and its four neighbors Q₁–Q₄ belong to the same Voronoi region, the forward scan will misclassify the blank grid as a non-Voronoi boundary grid and set the Voronoi attribution, which is the same as its four neighbors but may be incorrect, to the blank grid. In Fig. 9(a), grid P₁ is located on the boundary of Voronoi regions A and C, and the actual distance from P₁ to seed point A is greater than that to seed point C. However, the forward scan will set Voronoi attribution A rather than C to P₁, because its four neighbors Q₁–Q₄ all belong to Voronoi region A. Furthermore, the same mistake will occur during the scanning of the next grid, P₂, as shown in Fig. 9(b), and this will continue until the four neighbors of a blank grid have different Voronoi attributions. As shown in Fig. 9(c), the four neighbors of P₃ belong to different Voronoi regions, and the attribution will be obtained by using the attribution algorithm.

According to the scanning rules and the spatial characteristics of the four neighbors, the Voronoi attributions of all grids on the upper-left boundary of each Voronoi region after the forward scan, which may be real or incorrect, are calculated by determining attribution, whose correctness can be guaranteed. In Fig. 10(a), grids C₁–C₅ are located on the upper-left boundary of Voronoi region C after the forward scan, and their attribution can be assured to be correct. Grid C₁ is located on the boundary of the study area, and its attribution is obtained while setting up the starting area. The attributions of grids C₂–C₅ are obtained by using the attribution algorithm because their four neighbors belong to different Voronoi regions. Although the Voronoi boundaries formed by these five grids are not the real boundaries, i.e., those in Fig. 10(b), their own attribution can be ensured to be correct. Therefore, the Voronoi attributions of the grids located on the bottom-right direction of the boundary, which may be real or incorrect, can be ensured to be correct after the forward scan.

According to the above analysis, if a Voronoi boundary is incorrect, or the grids on the incorrect boundary obtain the wrong attribution in the forward scan, this can be corrected by using the right attributed grids located on their bottom-right direction based on a reverse error correction step, which scans the grids from right to left and bottom to top. If the eight neighbors in the 3×3 neighborhood template of a grid belong to different Voronoi regions, such as grid P in Fig. 11(a), an attribution determination calculation will be conducted for the grid during reverse error correction. If the eight neighbors belong to the same Voronoi region, as shown in Fig. 11(b), the grid will be skipped. Reverse scanning ensures that the incorrectly attributed grids located on incorrect boundaries can be touched and corrected. As reverse error correction proceeds, incorrectly attributed grids and incorrect Voronoi boundaries will be corrected gradually, so as to obtain the correct Voronoi diagram.

Comparative experiments were set up to assess the accuracy and efficiency of the proposed algorithm, using the Python 3.8 programming language, Cesium open-source framework, and AMD Ryzen 7 5800H hardware environment. Figure 12 shows the spherical Voronoi diagrams generated by the proposed algorithm with 10, 100, and 500 random seed points.

3.1 Accuracy

As demonstrated in section 1, the accuracy of the attribution determination algorithm is outstanding, and Voronoi errors can be limited to one grid compared to the spherical vector Voronoi diagram. Hence this algorithm was used as a benchmark against which to assess the accuracy of the proposed algorithm. To test the accuracy, the spherical surface was divided into 218 grids using the ortho-octahedral dissection method described in section 2.1, and spherical Voronoi diagrams were generated by the attribution determination algorithm and the proposed algorithm. The experiment was carried out 10,000 times with 50–100 randomly selected seed points, and the Voronoi diagrams generated by the two algorithms were the same. Hence the accuracy rate of the proposed algorithm was 100%.

To verify the uniformity of accuracy of the proposed algorithm, absolute Voronoi errors, which are relative to vector-based Voronoi diagrams and can be expressed by the difference of the distance from Voronoi boundary grids and corresponding seed points, were calculated at different latitudes. Figure 13 illustrates the absolute errors of Voronoi diagrams generated by the proposed algorithm based on ortho-octahedral dissection and the attribution determination algorithm based on the latitude–longitude grids. It is evident that the error based on the longitude and latitude grid decreased gradually with the increase of latitude because of the non-uniform grid size, as illustrated in Fig. 1, while the accuracy of the proposed algorithm was more uniform and did not change with latitude because of the uniform ortho-octahedral dissection. The distortion of the spherical grid divided in the proposed algorithm was reduced, resulting in more uniform accuracy of the generated spherical Voronoi diagram.

Table 1

Time Taken by Two Algorithms to Generate Voronoi Diagrams
Number of grids	Number of seeds	Attribution Algorithm/s	Proposed Algorithm/s	Attribution Calculation Ratio	Time Ratio
	50	1.69	1.108	0.323	0.655
2¹⁴	100	2.849	1.837	0.431	0.644
	200	5.271	3.658	0.563	0.694
	50	6.698	3.405	0.188	0.508
2¹⁶	100	11.564	5.148	0.249	0.445
	200	22.273	9.783	0.331	0.439
	50	28.091	11.676	0.116	0.415
2¹⁸	100	49.471	16.233	0.142	0.328
	200	86.533	25.785	0.187	0.298
	50	111.796	42.551	0.072	0.380
2²⁰	100	191.995	51.775	0.081	0.269
	200	343.551	78.057	0.115	0.227

3.2 Efficiency Analysis

To test the efficiency of the proposed algorithm, experiments were carried out with different numbers of seed points and different grid levels, which determined the number of spherical grids and the grid resolution. Table 1 shows the time taken by the proposed algorithm and the attribution determination algorithm to generate spherical Voronoi diagrams, as well as the attribution determination calculation ratio of the proposed algorithm, which was 100% in the attribution determination algorithm, and the time ratio relative to the attribution determination algorithm, from which it can be seen that the proposed algorithm took less time than the attribution determination algorithm in all experimental conditions with different numbers of seed points and different grid levels. Furthermore, for the same number of seed points, as the number of divided grids increased, the attribution determination calculation ratio and the time ratio of the proposed algorithm decreased significantly. Figure 14 shows the percentage of attribution determination calculations of the proposed algorithm at different grid levels with 500 seed points. Only a small number of grids needed attribution determination steps in the proposed algorithm, and a huge number of calculations, including most of the time needed to generate the Voronoi diagram, were saved compared to the attribution determination algorithm, which led to the higher efficiency of the proposed algorithm.

We proposed a spherical Voronoi diagram generation algorithm that divides a spherical surface based on an ortho-octahedron [22] and ensures the uniformity of the divided spherical grids, thereby guaranteeing the uniform accuracy of the generated Voronoi diagram. Experimental results showed that the errors of Voronoi diagrams generated using this dissection method exhibit a more uniform distribution than those based on latitude–longitude grids. The algorithm combines edge attribution with bidirectional scanning to obtain the Voronoi attribution of each grid. The forward scan and reverse error-correction steps guarantee the correctness of the generated Voronoi diagram, consistent with the accuracy of the attribution determination algorithm. The algorithm calculates the Voronoi attribution of a small portion of the grids in advance, and transmits attribution information through neighbor grids, which substantially decreases attribution determination calculations, and the higher the resolution the more calculations are saved. Experimental results validated the accuracy and efficiency of the proposed algorithm.

A spherical Voronoi diagram generation algorithm that combines edge attribution with bidirectional scanning based on octahedral subdivision was proposed. The algorithm calculates the Voronoi attribution of boundary grids, and combines a forward scan and reverse error correction to ensure the accuracy of the generated Voronoi diagram with improved algorithmic efficiency. Our analysis focused on the grid division method, the cause of Voronoi attribution errors in forward scans, and the reverse scan method to correct Voronoi attributions. In experiments, the attribution determination algorithm reduced the number of grids required to calculate Voronoi attribution, thus improving efficiency. The algorithm generated Voronoi diagrams based on ortho-octahedral dissection, with more uniform accuracy than latitude–longitude grids. Although the studied algorithm cannot utilize GPU parallel computing, its underlying principles can be applied to the generation of spherical Voronoi diagrams encompassing all elements. Subsequent research will further investigate the application of this algorithm within spheroidal gridded spatial domains.

Data availability

The authors confirm that the data supporting the findings of this study are available within the article and its supplementary materials.

Acknowledgments

The authors would like to thank the anonymous reviewers for their constructive comments on improving this paper.

Author’s Contributions

Z.S. designed the experiments and wrote the main manuscript. L.W. and N.Y. reviewed the manuscript. The experimental work is being established and maintained by H.Z. , P.Z. and Z.S. All components of this research were carried out under Z.S. All authors reviewed the manuscript.

Competing interests

The authors declare no competing interests.

Additional information

Correspondence and requests for materials should be addressed to L.W.

Hao, Z., Dang, J., Yan, Y. & Wang, X. A node localization algorithm based on Voronoi diagram and support vector machine for wireless sensor networks. International Journal of Distributed Sensor Networks 17, 155014772199341 (2021).
Kim, J. & Son, H. I. A Voronoi Diagram-Based Workspace Partition for Weak Cooperation of Multi-Robot System in Orchard. IEEE Access 8, 20676–20686 (2020).
Lifeng Liu & Shuqing Zhang. Voronoi diagram and GIS-based 3D path planning. in 2009 17th International Conference on Geoinformatics 1–5 (IEEE, 2009). doi:10.1109/GEOINFORMATICS.2009.5293350.
Du, Q., Gunzburger, M. D. & Ju, L. Voronoi-based finite volume methods, optimal Voronoi meshes, and PDEs on the sphere. Computer Methods in Applied Mechanics and Engineering 192, 3933–3957 (2003).
Kolar, J. Representation of the geographic terrain surface using global indexing. in Proceeding of 12th International Conference on Geoinformatics 321–328 (Citeseer, 2004).
Hashemi Beni, L., Mostafavi, M. A., Pouliot, J. & Gavrilova, M. Toward 3D spatial dynamic field simulation within GIS using kinetic Voronoi diagram and Delaunay tetrahedralization. International Journal of Geographical Information Science 25, 25–50 (2011).
Pang, M. Y. C. & Shi, W. Development of a process-based model for dynamic interaction in spatio-temporal GIS. GeoInformatica 6, 323–344 (2002).
Abolfazl Mostafavi, M. & Gold, C. A global kinetic spatial data structure for a marine simulation. International Journal of Geographical Information Science 18, 211–227 (2004).
Herzfeld, M., Engwirda, D. & Rizwi, F. A coastal unstructured model using Voronoi meshes and C-grid staggering. Ocean Modelling 148, 101599 (2020).
Ringler, T. et al. A multi-resolution approach to global ocean modeling. Ocean Modelling 69, 211–232 (2013).
Y. Ma & Q. Chen. Fast Delaunay Triangulation and Voronoi Diagram Generation on the Sphere. in 2010 Second World Congress on Software Engineering vol. 1 187–190 (2010).
Fortune, S. A sweepline algorithm for Voronoi diagrams. in Proceedings of the second annual symposium on Computational geometry - SCG ’86 313–322 (ACM Press, 1986). doi:10.1145/10515.10549.
Na, H.-S., Lee, C.-N. & Cheong, O. Voronoi diagrams on the sphere. Computational Geometry 23, 183–194 (2002).
Gold, C. & Mostafavi, M. A. Towards the global GIS. ISPRS Journal of Photogrammetry and Remote Sensing 55, 150–163 (2000).
Wang, L., Zhao, X. S., Cao, W. M. & Guo, J. F. A GPU-based algorithm for the generation of spherical Voronoi diagram in QTM mode. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 40, 45–50 (2013).
Wang, L. & Zhao, X. A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space. Geomatics and Information Science of Wuhan University vol. 42 691–696 (2017).
Chen, J., Zhao, X. & Li, Z. An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM. photogramm eng remote sensing 69, 79–89 (2003).
Wang, L. & Zhao, X. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram. Geomatics and Information Science of Wuhan University vol. 40 1111-1115+1122 (2015).
Hu, H., Liu, X. & Hu, P. Voronoi diagram generation on the ellipsoidal earth. Computers & Geosciences 73, 81–87 (2014).
Liu, Q., Zhao, X., Wang, L. & Sun, W. A raster Voronoi diagram generation algorithm based on horizontal-longitudinal scanning. Acta Geodaetica et Cartographica Sinica 48, 393–399 (2019).
Clarberg, P. Fast Equal-Area Mapping of the (Hemi)Sphere using SIMD. Journal of Graphics Tools 13, 53–68 (2008).
Zhou, J., Ben, J., Wang, R., Zheng, M. & Du, L. Lattice Quad-Tree Indexing Algorithm for a Hexagonal Discrete Global Grid System. IJGI 9, 83 (2020).
TU, W. & WANG, J. Raster-based method for Voronoi diagram using GPU parallel technologyVoronoi. Modern Electronics Technique vol. 38 66-68+72 (2015).

No competing interests reported.

Supplementarymaterial.zip

Download PDF

Version 1

posted

You are reading this latest preprint version

An algorithm using edge attribution and bilateral scanning to generate spherical raster Voronoi diagrams

Status:

Version 1

Abstract

Figures

1. Introduction

2. Methods

2.1 Ortho-octahedral dissection method

2.2 Coordinate transformation

2.3 Improved Voronoi diagram generation algorithm

2.3.1 Forward Scanning

2.3.2 Reverse Error Correction

3. Results

3.1 Accuracy

3.2 Efficiency Analysis

4. Discussion

5. Conclusion

Declarations

References

Additional Declarations

Supplementary Files

Status:

Version 1