Exact Voronoi diagram for topographic spatial analysis

ABSTRACT

The Voronoi diagram (VD) is a fundamental geo-computing structure that has crucial applications. Computing this structure on a topographic surface requires having every point clustered on the geodesic distances, and thus the same challenging task as the geodesic distance mapping. This article proposes a new algorithm for the geodesic VD (GVD) by breaking up the highly complicated task into regular routines on the exact computation. The exact approach is due to the irregular rough nature of the Earth surface, where the discrete computation is more appropriate. The key operation involves a direct window growth devised to avoid the overloaded facet splitting and realized in a conic arrangement. Conventional clustering and GVD structure post-extraction are built on top of the window growth. The fundamental role of GVD in geo-computing is then demonstrated. The experimental results showed that the dual structure of GVD is useful in justifying the potential wrong triangulations from the popularly used 2D Delaunay, and the geometric exactness of GVD is more reliable in guaranteeing the surface process model efficiency and convergence, under the harsh checking of centroidal Voronoi tessellation optimization.

KEYWORDS:

• Geodesic distance mapping
• Geodesic voronoi diagram
• window growth
• conic arrangement
• Delaunay triangulation
• Centroidal voronoi tessellation

Acknowledgement

We thank the Editor and the anonymous reviewers for their valuable comments which help greatly to improve the article. This work was supported by a grant from State Key Laboratory of Resources and Environmental Information System and the National Natural Science Foundation (No.42230110).

Disclosure statement

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Data availability statement

The data that support the findings of this study are available in GitHub at: https://github.com/sanchopanza72/gvd_topographic

Notes

1. https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html.