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

刘文昊沈炜秦志霞

浙江理工大学;

摘要：

针对Voronoi图与Delaunay三角网具有的对偶特性,提出一种二维Voronoi图任意点删除网络更新算法.利用具有拓扑关系的双向链表三角网搜索影响多边形区域,以凸耳消元法为工具重新剖分影响域多边形,通过连接剖分后的三角网中相邻Delaunay三角形外接圆圆心,实现二维Voronoi图的重构.与其它方法相比,该方法具有操作简单、容易理解、计算效率高的优点.

关键词：Voronoi图、Delaunay三角网、凸耳、影响多边形、网络更新

所属期刊栏目：27

分类号：TP311.12(计算技术、计算机技术)

在线出版日期：2010-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：421-425