Algorithm research to generate triangulation network based on Bowyer-Watson

Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (6): 198-200.

Previous Articles Next Articles

Algorithm research to generate triangulation network based on Bowyer-Watson

ZHOU Xuemei1, LI Yingfei2

1.Institute of Computer Science and Technology, Guizhou University, Guiyang 550025, China
2.Office of Academic Affairs, Guizhou University, Guiyang 550025, China

Online:2013-03-15 Published:2013-03-14

基于Bowyer-Watson三角网生成算法的研究

周雪梅1，黎应飞2

1.贵州大学计算机科学与信息学院，贵阳 550025
2.贵州大学教务处，贵阳 550025

Abstract

Abstract: TIN（Triangulated Irregular Network） has better performance on shaping terrain. The generation algorithm has been great concerned. This paper has discussed the data structure design of triangulation, and designed and implemented the algorithm based on Bowyer-Watson idea that is an incremental insertion algorithm. This paper analyzes why the algorithms may arise the phenomenon of cross during the experiment, and gives the improved idea. The improved algorithm has been used to visualize the terrain modeling, to obtain good results, for the research triangulation has some value.

Key words: Triangulated Irregular Network（TIN）, Delaunay triangulation, convex hull

摘要： 不规则三角网（Triangulated Irregular Network，TIN）在表示地形的形态方面具有较好的表现，其生成算法一直备受关注。讨论了三角网的数据结构的设计，采用逐点插入算法中的Bowyer-Watson算法思想为研究重点，设计并实现了该算法，对算法实验过程中可能出现的交叉现象进行分析，给出算法的改进。该改进算法已用于地形的可视化建模中，获得了较好的效果，对于三角剖分的相关研究具有一定的价值。

关键词: 不规则三角网, Delaunay三角剖分, 凸壳

ZHOU Xuemei1, LI Yingfei2. Algorithm research to generate triangulation network based on Bowyer-Watson[J]. Computer Engineering and Applications, 2013, 49(6): 198-200.

周雪梅1，黎应飞2. 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200.

[1]	WANG Jiarun, SUN Yunan, YIN Hui, YANG Zhilong. Terrain Fitting and Double Convex Preserving for Visual Modeling of Military Target Relations [J]. Computer Engineering and Applications, 2020, 56(5): 270-278.
[2]	DONG Benzhi, YU Shangshu, JING Weipeng. Salient Object Detection Algorithm via Multiple Prior Fusion [J]. Computer Engineering and Applications, 2019, 55(2): 179-186.
[3]	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.
[4]	LI Gefei1, MA Weiyin2, LI Li3. Convex hull problem based on Spark platform [J]. Computer Engineering and Applications, 2018, 54(22): 67-73.
[5]	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.
[6]	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.
[7]	YANG Xiujuan1, DONG Jun1, LI Huihui2. Research of reverse furthest neighbors query in euclidean space [J]. Computer Engineering and Applications, 2015, 51(4): 142-147.
[8]	ZHU Qingsheng, TANG Hui, FENG Ji. Outlier detection algorithm based on Delaunay triangulation [J]. Computer Engineering and Applications, 2015, 51(16): 166-170.
[9]	ZHAO Jianfang1, QIAN Xuezhong1, JIA Zhiwei2. Constraints extending method based on convex hull [J]. Computer Engineering and Applications, 2014, 50(4): 173-176.
[10]	ZHAO Jingchang1, BAI Runcai1, LIU Guangwei1, LIU Wei2. Fast isolines generation algorithm based on TIN [J]. Computer Engineering and Applications, 2014, 50(24): 10-15.
[11]	HUANG Ke, XUE Yueju, CHEN Yao, CHEN Hanming, LI Hongsheng. Research on QR code images geometric rectification algorithm [J]. Computer Engineering and Applications, 2014, 50(20): 192-196.
[12]	WANG Zhihua, DAI Linsong, CHEN Sugen, SU Benyue. Timmer-like curve [J]. Computer Engineering and Applications, 2014, 50(10): 161-164.
[13]	Cairangzhuoma1, ZHANG Mingcheng2. Aircraft recognition via structural features [J]. Computer Engineering and Applications, 2013, 49(4): 174-177.
[14]	SONG Dunjiang1, BI Cheng2, YUE Tianxiang3. Application of HASMOC method in terrain surface reconstruction from contours [J]. Computer Engineering and Applications, 2013, 49(18): 171-175.
[15]	CHANG Zhenhua1，CHEN Bocheng1，LI Yingjie2，LIU Wenhuang1，YAN Xuewei3. Study on geometric approach of SVM algorithm——SK algorithm analysis and study [J]. Computer Engineering and Applications, 2011, 47(8): 149-153.

Algorithm research to generate triangulation network based on Bowyer-Watson

基于Bowyer-Watson三角网生成算法的研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics