基于局部修复的移动数据点Delaunay三角化快速更新方法  

A New Algorithm for Fast Updating Delaunay Triangulation of Moving Points Based on Local Fixing

作　　者：周元峰[1,4] 孙峰[4] 王文平[4] 汪嘉业[2,3] 张彩明[1,2,3] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101 [2]山东财经大学计算机科学与技术学院,济南250014 [3]山东省数字媒体技术重点实验室,济南250014 [4]香港大学计算机科学系,香港

出　　处：《计算机辅助设计与图形学学报》2011年第12期2006-2012,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金重点项目(60933008);国家自然科学基金国际合作项目(61020106001)

摘　　要：在移动数据点Delaunay三角化更新问题中,采用双三角单元过滤算法能够检测出大部分连接关系未发生改变的双三角单元结构,当在算法中出现反转三角单元时,需要重新计算所有数据点的Delaunay三角化.基于以上问题,提出一种具有局部修复的双三角单元过滤算法,通过在局部区域检查三角单元反转并进行修复,避免对所有数据点进行重新Delaunay三角化.实验结果表明,对于三角单元反转出现较多的情况,该算法能够节省约20%～30%的运行时间,提高了原有算法的效率.For updating a Delaunay triangulation of moving points,bi-cell filtering method can find the most bi-cells whose Delaunay connectivities remain unchanged after the points are slightly perturbed.When flipped bi-cells occur,rebuilding method for all points has to be applied.In this paper,we present a new algorithm that improves the performance of the original bi-cell filtering algorithm via checking and fixing flipped bi-cells locally.Experimental results show that the new algorithm runs 20% to 30% faster than the original algorithm when rebuilding method is applied frequently.

关 键 词：DELAUNAY三角化 双三角单元 反转修复 过滤 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]