面向并行的动态增量式Delaunay三角剖分算法*

• 作者: 于灏 刘利 张诚 杨昊禹
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 增量 插入法 三角剖分
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 图形图像
• 页码范围: 140-148
• 页数: 9页
• 分类号: TP391.41
• 字数: 8056字
• 语种: 中文

摘要

三角剖分是计算机图形学中的重要话题.并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新.虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况.为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID.该算法能够支持任意次、任意数量、任意位置点的增量添加.TID算法能够对任意分布的点集均给出唯一三角剖分结果.对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小.此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘利	清华大学地球系统科学系地球系统数值模拟教育部重点实验室	13	49	4.0	7.0
2	张诚	清华大学地球系统科学系地球系统数值模拟教育部重点实验室	7	14	2.0	3.0
3	杨昊禹	清华大学地球系统科学系地球系统数值模拟教育部重点实验室	1	0	0.0	0.0
4	于灏	清华大学地球系统科学系地球系统数值模拟教育部重点实验室	1	0	0.0	0.0