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

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (6): 198-200.

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

周雪梅1，黎应飞2

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

出版日期:2013-03-15 发布日期:2013-03-14

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

摘要/Abstract

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

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

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

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

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]	党小超1，2，李芬芳1，郝占军1，2. Delaunay三角剖分的节点模糊信息三维定位方法[J]. 计算机工程与应用, 2016, 52(23): 115-122.
[2]	刘鹏程1，2，揭毅1，2，杨文博1，2. 临近特征点类型匹配的多边形渐变表达模型[J]. 计算机工程与应用, 2015, 51(22): 42-47.
[3]	朱庆生，唐汇，冯骥. Delaunay三角剖分在离群点检测中的应用[J]. 计算机工程与应用, 2015, 51(16): 166-170.
[4]	赵建芳1，钱雪忠1，贾志伟2. 基于凸壳的约束信息扩展方法[J]. 计算机工程与应用, 2014, 50(4): 173-176.
[5]	赵景昌1，白润才1，刘光伟1，刘威2. 一种基于TIN的等值线快速生成算法[J]. 计算机工程与应用, 2014, 50(24): 10-15.
[6]	邹永贵，张涛. 改进的平面域Delaunay三角网生成算法[J]. 计算机工程与应用, 2013, 49(20): 171-174.
[7]	宋敦江1，毕诚2，岳天祥3. 由等高线重构曲面的HASMOC方法应用研究[J]. 计算机工程与应用, 2013, 49(18): 171-175.
[8]	马彩虹1，2，戴芹1，王建民3，刘士彬1. 基于分块优化的不规则三角网的快速构成方法[J]. 计算机工程与应用, 2012, 48(3): 169-172.
[9]	赵军¹，高满屯²，王三民². 求平面多边形集凸壳的方法[J]. 计算机工程与应用, 2011, 47(1): 205-207.
[10]	徐鹏飞^1，2，陈志刚². 增量构造Voronoi区域的改进算法[J]. 计算机工程与应用, 2010, 46(8): 8-10.
[11]	孙小军^1，2，魏炳乾¹，周孝德¹，燕荔¹. 考虑泥沙水下休止角的淤积量测报模型及优化[J]. 计算机工程与应用, 2010, 46(7): 200-202.
[12]	王三¹，刘润涛²，王洪艳¹. 求两个相交凸多边形并的凸包及交的算法[J]. 计算机工程与应用, 2010, 46(5): 154-156.
[13]	王占刚，左建平. 多体模型的三角形网格可控边折叠方法研究[J]. 计算机工程与应用, 2010, 46(32): 13-16.
[14]	孙继忠¹，马永强¹，胡艳²，孔旭¹. 分布式Delaunay三角剖分在栅栏覆盖中的应用[J]. 计算机工程与应用, 2010, 46(26): 76-79.
[15]	安维华，付永刚，张习文. 基于图像的点云建模及其真实感绘制[J]. 计算机工程与应用, 2010, 46(20): 4-8.