增/删点后的Voronoi图构造法研究  

The Method of Adding or Deleting Point for Voronoi Diagram

作　　者：史霄[1] 闫浩文[1] 方爱玲[1] 王超超[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《测绘与空间地理信息》2011年第3期44-46,共3页Geomatics & Spatial Information Technology

基　　金：国家自然科学基金项目(40871208)资助

摘　　要：论述了在原Voronoi图的基础上增加点和删去点后生成新Voronoi图的算法。在增点过程中,针对新增加点后不满足Delaunay三角网特性的情况,利用最大最小角规则进行局部优化,根据优化后的三角网生成新Voronoi图;在删点过程中,针对删点的不同位置情况,修改相应Voronoi域,生成新Voronoi图。This paper discussed a method of building a new Voronoi diagram after adding a point to the old Voronoi diagram or deleting point from the old one.In allusion to the new point which is not conform to the characteristic of Delaunay triangle,the method uses the max-min angle principle to make the part triangle optimization,and build the new Voronoi diagram based on the optimized triangle.In the process of deleting point,in allusion to different position of deleted point,the method modifies the corresponding region and builds the new Voronoi diagram.

关 键 词：VORONOI图 增点构造算法 删点构造算法 

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