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



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

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三角剖分, 凸壳