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

doi:10.11772/j.issn.1001-9081.2017.12.3558

计算机应用 ›› 2017, Vol. 37 ›› Issue (12): 3558-3562.DOI: 10.11772/j.issn.1001-9081.2017.12.3558

• 计算机视觉与虚拟现实 • 上一篇下一篇

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

夏俊, 李映华

昆明理工大学理学院, 昆明 650500

收稿日期:2017-06-29 修回日期:2017-09-04 出版日期:2017-12-10 发布日期:2017-12-18
通讯作者: 夏俊
作者简介:夏俊(1991-),男,安徽合肥人,硕士研究生,主要研究方向:计算几何;李映华(1978-),男,广东梅州人,讲师,博士,主要研究方向:计算几何。
基金资助:
昆明理工大学自然科学基金资助项目（KKSY201507066）。

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

XIA Jun, LI Yinghua

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).

摘要/Abstract

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

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

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

中图分类号:

TP301.6

夏俊, 李映华. 球面凸类图形Delaunay三角剖分再分算法及其收敛性分析[J]. 计算机应用, 2017, 37(12): 3558-3562.

XIA Jun, LI Yinghua. Delaunay triangulation subdivision algorithm of spherical convex graph and its convergence analysis[J]. Journal of Computer Applications, 2017, 37(12): 3558-3562.

参考文献

[1] LEE D T, SCHACHTER B J. Two algorithms for constructing Delaunay triangulations[J]. International Journal of Computer and Information Sciences, 1980, 9(3):219-242.
[2] DWYER R A. A faster divide-and-conquer algorithm for constructing Delaunay triangulations[J]. Algorithmica, 1987, 2(1/2/3/4):137-151.
[3] 高莉.改进的Deluanay三角剖分算法研究[D].兰州:兰州交通大学,2015:30-33.(GAO L. An improved Deluanay triangulation algorithm[D]. Lanzhou:Lanzhou Jiaotong University, 2015:30-33.)
[4] CHEW L P. Constrained Delaunay triangulation[J]. Algorithmica, 1989, 4(1/2/3/4):97-108.
[5] LEE D T, LIN A K. Generalized Delaunay triangulation for planar graphs[J]. Discrete & Computational Geometry, 1986, 1(3):201-217.
[6] 张群会,解子毅.带断层约束的Delaunay三角剖分混合算法[J].西安科技大学学报,2014,34(1):52-56.(ZHANG Q H, XIE Z Y. Mixed algorithm of Delaunay triangular subdivision with fault constraint[J]. Journal of Xi'an University of Science and Technology, 2014, 34(1):52-56.)
[7] RUPPERT J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation[J]. Journal of Algorithms, 1995, 18(3):548-585.
[8] SHEWCHUK J R. Delaunay refinement algorithms for triangular mesh generation[J]. Computational Geometry, 2002, 22(1/2/3):21-74.
[9] BARBIC J, MILLER G. A quadratic running time example for ruppert's refinement algorithm[EB/OL].[2017-04-16]. http://www-bcf.usc.edu/~jbarbic/BarbicMiller-RupperQuadraticExampleTechReport.pdf.
[10] RAND A. Where and how Chew's second Delaunay refinement algorithm works[C/OL]//Proceedings of the 201323rd Annual Canadian Conference on Computational Geometry,[2017-04-16]. http://www.w.cccg.ca/proceedings/2011/papers/paper91.pdf.
[11] CAROLI M, DE CASTRO P M M, LORIOT S, et al. Robust and efficient Delaunay triangulations of points on or close to a sphere[C]//Proceedings of the 20109th International Conference on Experimental Algorithms. Berlin:Springer, 2010:462-473.
[12] ZENG W, SHI R, GU X F. Global surface remeshing using symmetric Delaunay triangulation in uniformization spaces[C]//Proceedings of the 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering. Piscataway, NJ:IEEE, 2011:160-169.
[13] GU X F, GUO R, LUO F, et al. A discrete uniformization theorem for polyhedral surfaces Ⅱ[EB/OL].[2017-04-16]. http://math.oregonstate.edu/~guoren/docs/u10-10.pdf.
[14] GU X F, GUO R, LUO F, et al. A discrete uniformization theorem for polyhedral surfaces I[EB/OL].[2017-04-16]. https://arxiv.org/pdf/1401.4594.pdf.
[15] PREPARATA F P, SHAMOS M I. Computational Geometry-an Introduction[M]. New York:Springer, 1985:241-276.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[2]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[3]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[4]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[5]	张豪, 张强, 邵思羽, 丁海斌. 深度学习在单图像三维模型重建的应用[J]. 计算机应用, 2020, 40(8): 2351-2357.
[6]	刘静姝, 王莉, 刘惊雷. 无需特征分解的快速谱聚类算法[J]. 计算机应用, 2020, 40(12): 3413-3422.
[7]	陈维兴, 刘清涛, 孙习习, 陈斌. 机坪感知网络的快速收敛平均一致性时间同步算法[J]. 计算机应用, 2020, 40(11): 3407-3412.
[8]	韦姗姗, 胡圣波, 鄢婷婷, 莫金容. 基于分步小波变换的对流层电波传播特性和分析软件[J]. 计算机应用, 2019, 39(6): 1792-1798.
[9]	陈林烽, 齐学梅, 陈俊文, 黄琤, 陈付龙. 批量流水调度问题的量子候鸟协同优化算法[J]. 计算机应用, 2019, 39(11): 3250-3256.
[10]	李人敏, 黄劲松, 陈琛, 吴君钦. 基于改进粒子群算法的毫米波大规模MIMO混合预编码方案[J]. 计算机应用, 2018, 38(8): 2365-2369.
[11]	王岩, 罗倩, 邓辉. 基于Gibbs抽样的轴承故障诊断方法[J]. 计算机应用, 2018, 38(7): 2136-2140.
[12]	徐光宪, 赵越, 赖俊宁. 基于网络编码的确定性逐层构造算法[J]. 计算机应用, 2018, 38(3): 769-775.
[13]	林畅, 李国平, 赵海武, 王国中, 顾晓. 全景视频双环带映射算法[J]. 计算机应用, 2017, 37(9): 2631-2635.
[14]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.
[15]	吕立国, 季伟东. 结合质心思想和柯西变异策略的粒子群优化算法[J]. 计算机应用, 2017, 37(5): 1369-1375.