【作者】 周元峰； 孙峰； 王文平； 汪嘉业； 张彩明；

【Author】 Zhou Yuanfeng~(1,4),Sun Feng~4,Wang Wenping~4,Wang Jiaye~(2,3),Zhang Caiming~(1,2,3) 1(School of Computer Science and Technology,Shandong University,Jinan,250101) 2(School of Computer Science and Technology,Shandong University of Finance and Economics,Jinan,250014) 3(Shandong Prov.Key Lab of Digital Media Technology,Jinan,250014) 4(Department of Computer Science,University of Hong Kong,Hong Kong,China)

【机构】 山东大学计算机科学与技术学院； 香港大学计算机科学系； 山东财经大学计算机科学与技术学院； 山东省数字媒体重点实验室； 山东财经大学,计算机科学与技术学院；

【摘要】 在移动数据点Delaunay三角化更新问题中,采用双三角单元过滤算法能够检测出大部分连接关系未发生改变的双三角单元结构,当在算法中出现反转三角单元时,需要重新计算所有数据点的Delaunay三角化。基于以上问题,本文提出了一个具有局部修复的双三角单元过滤新算法,在局部区域检查三角单元反转并进行修复,避免对所有数据点进行重新Delaunay三角化。实验表明,对于三角单元反转出现较多的情况下,新算法能够节省约20%～30%的运行时间,提高了原有算法的效率。更多还原

【Abstract】 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 reversed bi-cell occurs,rebuilding method for all points will be triggered.Based on this problem,we present a new algorithm by adding the reverse fixing strategy.The new algorithm improves the performance of the original bi-cell filtering algorithm via checking and fixing reversed bi-cell locally.Experimental results show that the new algorithm runs 20%to 30%faster than the original algorithm when rebuilding method is triggered frequently.更多还原