夏 俊，李映华

(昆明理工大学 理学院，昆明 650500)

球面凸类图形Delaunay三角剖分再分算法及其收敛性分析

夏 俊*，李映华

(昆明理工大学 理学院，昆明 650500)

在计算曲面Ricci Flow时，会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题，提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先,给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个：1)如果某条Delaunay劣弧被“侵占”, 通过添加Delaunay劣弧中点分割Delaunay劣弧;2)如果存在“瘦”球面三角形, 通过添加球面三角形外接球面小圆圆心分解球面三角形。然后，利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证，所提算法网格生成的球面三角形没有狭小的角，适合用来计算Ricci Flow。

球面；Delaunay三角剖分；劣弧；局部特征尺度；收敛

0 引言

Delaunay三角剖分在图形学、地理学以及有限元分析等领域是一项极为重要的预处理技术。随着计算机技术的发展以及分析对象的复杂性，Delaunay三角剖分在这些领域扮演着重要角色。例如，在有限元分析中，需要把研究的区域分解成三角形单位元。如果剖分的三角形角度过小，那么有限元算法的收敛性得不到保证。因为Delaunay三角剖分可以最大化最小角，所以Delaunay三角剖分是一种有效的剖分方法。

目前，平面上的Delaunay三角剖分的研究已经相当成熟。平面上的Delaunay三角剖分分为点集Delaunay三角剖分和约束Delaunay三角剖分。 对于平面点集Delaunay 三角剖分来说，Lee等[1]给出了点集Delaunay三角剖分的几何性质和算法。……