Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (12): 3558-3562.DOI: 10.11772/j.issn.1001-9081.2017.12.3558

Previous Articles     Next Articles

Delaunay triangulation subdivision algorithm of spherical convex graph and its convergence analysis

XIA Jun, LI Yinghua   

  1. School of Science, Kunming University of Science and Technology, Kunming Yunnan 650500, China
  • Received:2017-06-29 Revised:2017-09-04 Online:2017-12-10 Published:2017-12-18
  • Supported by:
    This work is partially supported by the Natural Science Foundation of Kunming University of Science and Technology (KKSY201507066).

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

夏俊, 李映华   

  1. 昆明理工大学 理学院, 昆明 650500
  • 通讯作者: 夏俊
  • 作者简介:夏俊(1991-),男,安徽合肥人,硕士研究生,主要研究方向:计算几何;李映华(1978-),男,广东梅州人,讲师,博士,主要研究方向:计算几何。
  • 基金资助:
    昆明理工大学自然科学基金资助项目(KKSY201507066)。

Abstract: When calculating curved Ricci Flow, non-convergence emerges due to the existence of undersized angles in triangular meshes. Concerning the problem of non-convergence, a Delaunay triangulation subdivision algorithm of spherical convex graph of enhancing the minimum angle was proposed. First of all, the Delaunay triangulation subdivision algorithm of spherical convex graph was given. The proposed algorithm had two key operations:1) if a Delaunay minor arc was "encroached upon", a midpoint of the Delaunay minor arc was added to segment the Delaunay minor arc; 2) if there was a "skinny" spherical triangle, it was disassembled by adding the center of minor circle of its circumscribed sphere. Then, the convergence criteria of the proposed algorithm was explored on local feature scale and an upper-bound formula of the output vertex was given. The grids based on the output of experiment show that the spherical triangle generated by the grids of the proposed algorithm has no narrow angle, so it is suitable for calculating Ricci Flow.

Key words: sphere, Delaunay triangulation, minor arc, local feature scale, convergence

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

关键词: 球面, Delaunay三角剖分, 劣弧, 局部特征尺度, 收敛

CLC Number: