二维Voronoi图删除任意生成点算法研究  

Research on the Algorithm for Two-Dimensional Random Point Deletion in Voronoi Diagram

作　　者：秦志霞[1] 沈炜[1] 刘文昊[1] 

机构地区：[1]浙江理工大学信息电子学院,杭州310018

出　　处：《浙江理工大学学报（自然科学版）》2010年第3期421-425,共5页Journal of Zhejiang Sci-Tech University(Natural Sciences)

摘　　要：针对Voronoi图与Delaunay三角网具有的对偶特性,提出一种二维Voronoi图任意点删除网络更新算法。利用具有拓扑关系的双向链表三角网搜索影响多边形区域,以凸耳消元法为工具重新剖分影响域多边形,通过连接剖分后的三角网中相邻Delaunay三角形外接圆圆心,实现二维Voronoi图的重构。与其它方法相比,该方法具有操作简单、容易理解、计算效率高的优点。Based on the relationship between Voronoi diagram and Delaunay triangulation,a new algorithm is proposed to cope with Two-Dimensional Random Point Deletion in Voronoi diagram.First,a two-way linked list with a topological character triangulations is used to search the influence polygon area H,then H is divided making use of ear elimination method.Lastly,connect the circumcircle center of the adjacent Delaunay triangles to achieve the reconstruction of two-dimensional Voronoi diagram.Compared with other methods,this method is simple,easy to understand,and has high calculation efficiency.

关 键 词：VORONOI图 DELAUNAY三角网 凸耳 影响多边形 网络更新 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]