离散地形曲面上的精确Voronoi图直接生成算法  

Direct Algorithm for the Exact Voronoi Diagram on Discrete Topographic Space

作　　者：段新桥 葛咏 张彤[5] 李霖[6,7] 谭永滨 DUAN Xinqiao;GE Yong;ZHANG Tong;LI Lin;TAN Yongbin(School of Surveying and Geoinformation Engineering,East China University of Technology,Nanchang 330013,China;State Key Laboratory of Resources and Environmental Information System,Beijing 100101,China;Key Laboratory of Mine Environmental Monitoring and Improving Around Poyang Lake,Ministry of Natural Resources,Nanchang,330013,China;University of Chinese Academy of Sciences,Beijing 100049,China;State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China;School of Resources and Environmental Sciences,Wuhan University,Wuhan 430079,China;Geospatial Information Technology Collaborative Innovation Center,Wuhan University,Wuhan 430072,China)

机构地区：[1]东华理工大学测绘与空间信息工程学院,江西南昌330013 [2]资源与环境信息系统国家重点实验室,北京100101 [3]自然资源部环鄱阳湖区域矿山环境监测与治理重点实验室,江西南昌330013 [4]中国科学院大学,北京100049 [5]武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079 [6]武汉大学资源与环境科学学院,湖北武汉430079 [7]武汉大学地球空间信息技术协同创新中心,湖北武汉430072

出　　处：《武汉大学学报（信息科学版）》2023年第5期799-806,共8页Geomatics and Information Science of Wuhan University

基　　金：资源与环境信息系统国家重点实验室2020年度开放基金。

摘　　要：Voronoi图是地学计算中的一个基本结构,但是在地形曲面上,它还缺乏能与平面Voronoi图媲美的精度和成熟的算法。在离散地形曲面的不规则三角网格网上引入计算几何的测地距离场,从格网边上的距离场奇点逐步生长代表平分线的双曲线,由双曲线的排列得到离散曲面的精确划分,再将划分的面片聚类,生成精确的测地Voronoi图(geodesic Voronoi diagram,GVD)。然后,从定量与定性两方面对精确Voronoi图进行了检验,证明GVD可以给地形曲面空间分析带来基础性改进。基于奇点生长和双曲线排列的直接算法避免了现有算法对格网面片的过度细分与预处理,整体上直观易行,为数字地形分析发展严密的Voronoi图分析提供了有益探索。Objectives:Voronoi diagram is a fundamental structure in geo-computing,but it still encounters the problem of exactness and the challenge of an exact algorithm comparable to planar Voronoi diagrams in the topographic space.Methods:The geodesic distance field of computational geometry is introduced into the triangulated irregular network in the discrete topographic surface.The hyperbolic curves representing the bisector are gradually grown from the singularity of the distance field on the edge of the grid.The precise division of the discrete surface is obtained by the arrangement of the hyperbolic curves,and the exact geodesic Voronoi diagram(GVD)is obtained by clustering the divided patches.Then,the exact Voronoi diagrams are tested quantitatively and qualitatively.Results and Conclusions:It is found that the exact GVD can bring a basic improvement for the spatial analysis of topographic surface.The direct algorithm based on singular growth and hyperbolic arrangement is intuitive and easy to implement,which avoids the excessive subdivision and preprocessing of grid patches by the existing algorithms,and provides a useful exploration for the development of Voronoi diagram analysis in digital topographic analysis.

关 键 词：地形曲面空间 测地距离场 测地Voronoi图 奇异生长 双曲线排列 

分 类 号：P208[天文地球—地图制图学与地理信息工程]