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

摘要

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