多阶三角形数据结构的高阶Voronoi图算法研究  

High order Voronoi algorithm based on korder triangle-based data structure

作　　者：邓曙光 郑智华[3] 敖四芽 黄树新 DENG Shuguang;ZHENG Zhihua;AO Siya;HUANG Shuxin(Guilin University of Technologyat Nanning,Nanning 530029,China;School of Urban Design,Wuhan University,Wuhan 430072,China;Land and Resources Information Center of Guangxi Province,Nanning 530028,China)

机构地区：[1]桂林理工大学南宁分校,南宁530029 [2]武汉大学城市设计学院,武汉430072 [3]广西壮族自治区国土资源信息中心,南宁530028

出　　处：《测绘科学》2019年第7期35-39,共5页Science of Surveying and Mapping

基　　金：桂林理工大学南宁分校科研启动项目(GUTNNQDJJ01)

摘　　要：针对大多数传统高阶Voronoi算法复杂且运行效率低下,缺乏拓扑关系与多种邻近查询以及地理空间可视化交互与分析上的问题,该文借助Delaunay三角形天然优势,首先建立了一种k阶Delaunay三角形数据结构,利用k阶Delaunay三角剖分与k阶的Voronoi图存在的间接性对偶关系,提出了一种k阶Delaunay三角形数据结构的高阶Voronoi图的算法,并通过数据实验分析与对比,结果表明:该算法易于理解,程序设计简单易行,提高了运行效率,有效支持地理空间应用与几何学与拓扑邻近查询,满足实际应用的需要。Aiming at the problem that the most popular traditional Higher-order Voronoi algorithms are complex and inefficient and lack topological relationship and multiple adjacent queries.In addition to addition,spatial visual interaction and analysis.This paper presents a new algorithm for High-order Voronoi.It is based on Delaunay k order triangle natural advantages for constructing High-order Voronoi.This algorithm has been introduced to established a k-order Delaunay triangle data structure and indirect dual relationship with High-order Voronoi.An experimental comparison is made of the proposed algorithm with the other popular high order algorithms,and examples of application.We show that this algorithm is easy to understand and program design.It can also be easily suitable for improvement of the running efficiency,as such effective support for geospatial applications and eometry and topology queries with the need of actual applications.

关 键 词：k阶Delaunay三角形 高阶Voronoi 拓扑结构 算法 

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