2D-Delaunay三角网格的数据结构与遍历

Data structure and traverse of 2D-Delaunay triangulation

本文总结了二维Delaunay三角网格的Bowyer-W atson自动生成算法及其实现步骤,提出了一种类的结构、函数范例(采用V isual C++6.0编写程序),并讨论了遍历三角网格各种方法的优劣性,给出实验数据对比;最后得出结论,用广度优先的遍历方法创建网格是生成三角网格一种相对便利有效率的方法;另外,讨论了初始点加入顺序对程序运行时间的影响.

The article summarized the realization of2D-Delaunay triangulation, the steps of creating Bowyer-Watson automatic mesh generator, and then constructed a kind of Class structure as well as functions of this algorithm （using V C ＋＋6.0）, and discussed different methods to traverse the triangle mesh, using data examination as contrast. Finallg, the author got the conclusion that Width First Traversal method is more effective and convenient, Besides, we discussed the effect between the order of original point set and running time of the program.