Delaunay三角网剖分的约束边嵌入改进算法

doi:10.3778/j.issn.1002-8331.2009.24.071

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (24): 235-237.DOI: 10.3778/j.issn.1002-8331.2009.24.071

Delaunay三角网剖分的约束边嵌入改进算法

陈学工¹，李源¹，曹建¹，肖克炎²

1.中南大学信息科学与工程学院，长沙 410083
2.中国地质科学院矿产资源研究所，北京 100037

收稿日期:2008-05-08 修回日期:2008-07-31 出版日期:2009-08-21 发布日期:2009-08-21
通讯作者: 陈学工

Improved algorithm of inserting constrained edge into Delaunay triangulation

CHEN Xue-gong¹，LI Yuan¹，CAO Jian¹，XIAO Ke-yan²

1.School of Information Science and Engineering，Central South University，Changsha 410083，China
2.Institute of Resources，Chinese Academy of Geological Science，Beijing 100037，China

Received:2008-05-08 Revised:2008-07-31 Online:2009-08-21 Published:2009-08-21
Contact: CHEN Xue-gong

摘要/Abstract

摘要： 重点研究约束边强行嵌入D-三角网的问题。约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法，而CD-三角网才能真实地虚拟地形地貌。针对基于凸凹判定的对角线交换算法存在的缺陷，提出“分裂约束边”的思想完善算法的健壮性，并引入快速点定位算法以提高算法的执行效率。

关键词: 约束边, Delaunay三角剖分, 对角线, 凸凹性

Abstract: This paper focuses on researching the problem of inserting constrained edge into D-Triangulation.It is a very effective method of changing D-Triangulation into CD-Triangulation that constrained edge is inserted into D-Triangulation，and only CD-Triangulation can present real terrain and relief.According to the shortcoming of the diagonal line exchange algorithm which is based on convexo-concave，this paper proposes an idea of “split -restraint” to improve the robustness of the algorithm and introduces the rapid point positioning algorithm to enhance the efficiency of the algorithm.

Key words: constrained edge, Delaunay triangulation, diagonal, convexo-concave

中图分类号:

TP391.41

陈学工¹，李源¹，曹建¹，肖克炎². Delaunay三角网剖分的约束边嵌入改进算法[J]. 计算机工程与应用, 2009, 45(24): 235-237.

CHEN Xue-gong¹，LI Yuan¹，CAO Jian¹，XIAO Ke-yan²
. Improved algorithm of inserting constrained edge into Delaunay triangulation[J]. Computer Engineering and Applications, 2009, 45(24): 235-237.

[1]	党小超1，2，李芬芳1，郝占军1，2. Delaunay三角剖分的节点模糊信息三维定位方法[J]. 计算机工程与应用, 2016, 52(23): 115-122.
[2]	朱庆生，唐汇，冯骥. Delaunay三角剖分在离群点检测中的应用[J]. 计算机工程与应用, 2015, 51(16): 166-170.
[3]	周雪梅1，黎应飞2. 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200.
[4]	戴宽平，吕全义. 改进的并行Arnoldi方法[J]. 计算机工程与应用, 2011, 47(34): 72-73.
[5]	段治健1，杨永1，吕全义2，马欣荣3. 求解块三对角方程组的一种并行策略[J]. 计算机工程与应用, 2011, 47(13): 46-49.
[6]	郭华磊^1，2，马苗¹. 改进的模糊C均值聚类的图像分割算法[J]. 计算机工程与应用, 2011, 47(1): 176-178.
[7]	徐鹏飞^1，2，陈志刚². 增量构造Voronoi区域的改进算法[J]. 计算机工程与应用, 2010, 46(8): 8-10.
[8]	隋玲玲，陈雄. 机器人在线路径规划改进算法[J]. 计算机工程与应用, 2010, 46(28): 36-39.
[9]	孙继忠¹，马永强¹，胡艳²，孔旭¹. 分布式Delaunay三角剖分在栅栏覆盖中的应用[J]. 计算机工程与应用, 2010, 46(26): 76-79.
[10]	钟家民，郭新志，李源. 三维不规则三角网格的精确裁剪算法[J]. 计算机工程与应用, 2010, 46(16): 204-206.
[11]	樊艳红,吕全义,聂玉峰. 块三对角线性方程组的并行直接解法[J]. 计算机工程与应用, 2009, 45(3): 60-63.
[12]	相鹏,刘展,孙记红,宋学锋. 三维可视化建模方法在位场模拟中的应用[J]. 计算机工程与应用, 2009, 45(3): 239-241.
[13]	汪保^1，2，吕全义¹，樊艳红¹，聂玉峰¹. 改进的求解线性方程组的并行Arnoldi方法 [J]. 计算机工程与应用, 2009, 45(22): 41-43.
[14]	陈学工¹,李小勇¹,曾俊钢¹,肖克炎². 三维物体表面重建的分支处理算法研究[J]. 计算机工程与应用, 2008, 44(32): 155-157.
[15]	王占刚,潘懋,屈红刚,王斌. 三维折剖面的Delaunay三角剖分算法[J]. 计算机工程与应用, 2008, 44(1): 94-96.

Delaunay三角网剖分的约束边嵌入改进算法

Improved algorithm of inserting constrained edge into Delaunay triangulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics