基于逐点插入法生成Voronoi图的算法研究及实现  

Research and implementation of Voronoi diagram generation algorithm based on point by point insertion method

作　　者：张艳[1] 李强[1] 

机构地区：[1]中国矿业大学(北京)地球科学与测绘工程学院,北京100083

出　　处：《黑龙江工程学院学报》2016年第5期22-24,共3页Journal of Heilongjiang Institute of Technology

摘　　要：基于逐点插入法生成Voronoi图需要首先生成Voronoi对应的Delaunay三角剖分,为满足大量离散点数据快速构建Voronoi图的效率需求,研究利用Lawson算法在形成三角网过程中进行LOP优化,快速生成可靠的Delaunay三角网,并应用Delaunay三角网与Voronoi图互为对偶的关系,构建所需的Voronoi图。在对大量的随机离散数据进行试验,并与标准的结果进行对比后发现,除部分异常情况,利用该算法可以快速准确地构建出目标Voronoi图。Based on point by point insertion method ,the Voronoi diagram needs to generate the Delaunay triangulation first in order to meet the efficiency requirement of constructing Voronoi diagram quickly with a number of discrete point data .In the paper Lawson algorithm is used to carry on the LOP optimization in the process of forming a triangulation network to generate a reliable Delaunay triangulation .The relation of mutual duality between Delaunay triangulation and Voronoi diagram is used to construct the desired Voronoi map . After testing a number of random discrete data and comparing with the results of the standard result ,this paper obtains a result that in addition to some abnormal conditions ,this algorithm can quickly and accurately frame the targetted Voronoi map .

关 键 词：DELAUNAY三角剖分 LOP优化 VORONOI图 逐点插入法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]