计算机科学与探索 ›› 2020, Vol. 14 ›› Issue (1): 140-148.DOI: 10.3778/j.issn.1673-9418.1903014
杨昊禹，刘利，张诚，于灏
YANG Haoyu, LIU Li, ZHANG Cheng, YU Hao
摘要： 三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求，其中之一即是给定一个点数不断增大的点集，实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法，但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题，提出了三角剖分的外扩技术，基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明，TID算法比现有算法具有更高的计算效率，且增量功能引入的额外开销较小。此外，该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。
