An Adaptive Voronoi Diagrams Algorithm for Matching Multi-scale Areal Residential Areas

  Objectives  There is a difficult problem of controlling the balance between computation efficiency and boundary position accuracy in existing Voronoi algorithms.

  Methods  Based on occurrence element discretization, we proposed an adaptive Voronoi diagram algorithm for matching multi-scale areal residential areas (AVARA) utilizing interpolation strategies according to the classification of neighbor pairs. Firstly, it uses the Delaunay triangle network composed of the centroids of residential areas to calculate the neighbor pairs. Secondly, it classifies the neighbor pairs according to the size relationship between the minimum distance of the neighbor pairs and the minimum side length of their minimum area bounding rectangles. Thirdly, it adaptively interpolates points on the boundary of residential area according to the type of neighbor pair. Finally, it constructs the Voronoi diagram for residential areas based on the interpolated point set and the vertex set. AVARA, the Voronoi diagram algorithm based on intervisible points and the Voronoi diagram algorithm based on equal-interval dense point method (VBEDP) are applied to create Voronoi diagrams for two residential area datasets with the scale of 1∶10 000 and 1∶50 000.

  Results  The experiment results show that compared with VBEDP of 3 m interval and 6 m interval, AVARA outperformes the local position accuracy and time performance in the datasets with the scale of 1∶10 000. And in the datasets with the scale of 1∶50 000, AVARA achieves higher local position accuracy than VBEDP of 30 m interval, and has a time performance improvement of 40% than VBEDP of 15 m interval.

  Conclusions  AVARA can effectively alleviate the problem of controlling the balance between computation efficiency and boundary position accuracy of Voronoi diagram.