摘要
针对现有基于发生元离散化思想的Voronoi算法在计算效率与边界位置精度之间难以平衡控制的问题,提出了一种基于邻居对分类插值策略的面向多尺度面状居民地匹配的Voronoi图自适应构建算法(adaptive Voronoi diagrams algorithm for matching multi-scale areal residential areas, AVARA)。首先,利用居民地多边形的质心构成的Delaunay三角网计算出居民地邻居对;其次,根据邻居对之间的最小距离及其最小面积外包矩形的边长最小值的大小关系将邻居对分类;然后,根据邻居对类别采用相应的方法在居民地边界上自适应地内插点;最后,基于内插点集及居民地的顶点集构建居民地的Voronoi图。利用1∶10 000和1∶50 000居民地数据进行了Voronoi图实验,结果表明,在1∶10 000数据中,AVARA在局部位置精度与时间性能方面均优于通视点法、3 m及6 m等间隔内插点法;在1∶50 000数据中,与30 m等间隔内插点法相比,AVARA取得了较高的局部位置精度;与15 m等间隔内插点法相比,AVARA的位置精度稍微偏低,但时间性能提升了40%。可见,AVARA有效缓解了Voronoi图计算效率与边界位置精度的平衡控制问题。
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 of1∶ 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.
作者
吴建华
戴鹏
胡烈云
WU Jianhua;DAI Peng;HU Lieyun(School of Geography and Environment,Jiangxi Normal University,Nanchang 330022,China)
出处
《武汉大学学报（信息科学版）》
EI
CAS
CSCD
北大核心
2022年第2期304-312,共9页
Geomatics and Information Science of Wuhan University
基金
国家自然科学基金(41561084,41201409)
江西省教育厅研究生创新基金(YC2019-S154)。
