Improved algorithm of inserting constrained edge into Delaunay triangulation

doi:10.3778/j.issn.1002-8331.2009.24.071

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (24): 235-237.DOI: 10.3778/j.issn.1002-8331.2009.24.071

• 工程与应用 • Previous Articles Next Articles

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

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

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

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

通讯作者: 陈学工

Abstract

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

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

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

CLC Number:

TP391.41

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.

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

[1]	WANG Yusi, LU Deyang, LI Haiyang. Sparse Subspace Clustering Method Based on Fractional Function Constraints [J]. Computer Engineering and Applications, 2020, 56(7): 39-47.
[2]	ZHAO Qing, YE Jimin, CHANG Fangli. Two Positive Definitive Matrices Based Joint Diagonalization Algorithm for Blind Source Separation [J]. Computer Engineering and Applications, 2019, 55(7): 214-219.
[3]	CHEN Zhe, WU Xiaojun. Robust Face Recognition Algorithm Based on Structured Low-Rank Recovery [J]. Computer Engineering and Applications, 2019, 55(6): 126-132.
[4]	LUO Dai, TAO Yang, YANG Gang. Face texture mapping and deformation with constrains of facial feature [J]. Computer Engineering and Applications, 2018, 54(6): 188-192.
[5]	XUE Qiufang, XIAO Yanting, WEI Feng. Multistage preconditioned AOR iterative methods for strictly diagonally dominant Z-matrices [J]. Computer Engineering and Applications, 2018, 54(22): 51-56.
[6]	ZHANG Chen, LI Hongjun, LUO Liuhong, HE Yinghao. Congruent permutation and computation of canonical form on matrix of equivalence relation [J]. Computer Engineering and Applications, 2017, 53(13): 42-48.
[7]	LI Zhengxin, LIU Jianli, ZHOU Jian, GAO Weidong. Improvements of fabric defect segmentation based on bidimensional empirical mode decomposition [J]. Computer Engineering and Applications, 2016, 52(24): 217-222.
[8]	DANG Xiaochao1，2, LI Fenfang1, HAO Zhanjun1，2. Method of node’s fuzzy information localization about Delaunay triangulation in three-dimensional space [J]. Computer Engineering and Applications, 2016, 52(23): 115-122.
[9]	SONG Xue, ZHOU Yihui, SHI Jun, WU Zhenqiang. Multi-level network coding scheme [J]. Computer Engineering and Applications, 2015, 51(18): 94-98.
[10]	ZHU Qingsheng, TANG Hui, FENG Ji. Outlier detection algorithm based on Delaunay triangulation [J]. Computer Engineering and Applications, 2015, 51(16): 166-170.
[11]	WANG Hanxin, WANG Fang, SU Kaiyou, ZHU Cuitao. QC-LDPC codes with slide rectangular window and quasi tri-diagonal structure [J]. Computer Engineering and Applications, 2014, 50(17): 186-190.
[12]	YE Jun, WANG Lei. Diagonal matrix method for fast computing positive region [J]. Computer Engineering and Applications, 2013, 49(8): 129-132.
[13]	ZHOU Xuemei1, LI Yingfei2. Algorithm research to generate triangulation network based on Bowyer-Watson [J]. Computer Engineering and Applications, 2013, 49(6): 198-200.
[14]	WU Jianbin1, LI Taiquan2, TIAN Mao3. Research of ADI-FDTD algorithm based on parallel diagonal dominant algorithm [J]. Computer Engineering and Applications, 2013, 49(23): 195-198.
[15]	ZHANG Xiaoqing, FAN Zhanting, LI Yanhong, LI Yajing. Tridiagonal decoupling control of a kind of special system [J]. Computer Engineering and Applications, 2012, 48(24): 212-215.

Improved algorithm of inserting constrained edge into Delaunay triangulation

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics