基于VS平台的D—TIN生长算法优化

黄煌

【摘 要】本文对传统不规则三角网生长算法实现的研究，并对其进行优化，利用了Visual Studio 2012平台强大的可视化用户界面及其编程语言的灵活性及简单易懂特点，基于各行业对于DEM的需要，从而开发出一种构网速度快，运行效率高的一种三角网构建算法。

【关键词】不规则三角网；Delaunay三角网；VS环境；算法优化

0 引言

地球表面高低起伏，呈现为一种连续变化的曲面，这种曲面无法用平面地图来确切表示，于是我们就利用数字高程模型来表达，这种方法已经被广泛使用。数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。

由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[1]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。

基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。C#语言简洁易学并且开发效率高，易于移植，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学生对C#语言熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在Visual Studio 2012环境下的实现。

1 TIN的算法种类及各算法特点

在介绍构成TIN各种算法之前我们要来了解认识一下一个重要法则——Delaunay三角网法则。通常构建三角网并不考虑地性线（山脊线，山谷线）的骨架作用，但是，由于用等高线数据构建三角网时，由于地形的复杂多样，有的地区存在因地形突变而形成的断裂线等特殊地貌。另外一些地区存在大面积水域等内部不需要构网的区域，因此，在精度要求较高的TIN中，必须考虑以上问题。因此此时应顾及地性线，断裂线，水域线等特殊情况，也就是应构建约束—Delaunay三角网。约束法是基于约束图计算约束D—三角剖分[2，4]（简称CDT，即Constrained Delaunay Triangulation）构造算法，这种Delaunay三角网满足这样的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的Voronoi多边形有一个公共的顶点，此顶点是Delaunay三角形外接圆的圆心。

1.1 三角网生成算法的分类

根据构建三角网的步骤，可将三角网生成算法分为三类：（1）分而治之算法（由Shmaos和Hoey提出），其基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用局部优化（LOP，即Local Optimization Procedure）算法保证其成为Delaunay三角网[3]，它的优点是时间效率高，但需要大量递归运算，因此占用内存空间较多，如果计算机没有足够的内存，这一方法就无法使用；（2）数据点渐次插入算法（由Lawson提出），其思路很简单，先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法保证其成为Delaunay三角网[3]。此算法虽然容易实现，但效率极低；（3）三角网生长算法，在这三种算法中，三角网生长算法在20世纪80年代以后的文献中已很少见，较多的是前两种算法[3]，三角网生长算法目前较少人研究，笔者在这里讨论的就是这一算法，该算法是由Michael J.McCullagh，Charles G.Ross提出的，本文对原有的三角网生长算法作了进一步优化。

1.2 三角网生长算法的优化

传统的三角网生长算法需要对新生成的两条边都进行扩展，这样就导致已经扩展一次的边再次扩展，加大了运算量。本文将在传统三角网生长算法的基础上加以改进，主要是在边的数据结构中加入了使用次数这一属性，这样就没有必要对每个新生成的三角形的两条边都进行扩展，从而有效的减少了扩展边的条数，提高了三角网生成速度。详细算法如下：

（1）在离散数据点集V 中任取一点A，以点A为基点寻找与它最近的一点B。连接AB，就得到了三角形的一条基边，把该边作为扩展基边，转（2）。

（2）在扩展基边（是有向的）的右边点集中去找与该边两端点连成直线组成的夹角为最大的P点，就组成了第一个三角形，将所有新生成的边与三角形信息用相应的链表进行存储起来，边每使用一次，其数据结构中的使用次数就加1，转（3）。

（3）在边链表中取出头位置的边，以该边为扩展基边向外进行扩展。如果该边的使用次数为2或是右边没有点，该边不进行扩展；否则，转（2）进行扩展，同时存储新生成的边和三角形。转（4）。

（4）对边链表中下一位置的边进行扩展，实现过程同步骤（3），转（5）。

（5）重复步骤（4），直至边链表中的所有边都进行了扩展，就结束构网。

为了对算法的稳定性及可行性进行检验，笔者用C#语言实现了上述算法，并用一些实验数据点验证了上述算法。应用以上算法原理，基于Visual Studio 编译环境，高效地实现了大量量数据的Delaunay 三角网构建，实验表明，此算法的执行效率较高，对计算机硬件配置的要求较低。

2 总结

实现上述算法具有很强的现实意义，为DEM的生成在许多领域中打下基础。在土木工程中，如工程项目的填挖方计算，线路勘测设计，水利建设工程等的应用；TIN在GIS中得到了普遍使用，特别是在三维可视化方面受到格外关注，基于DEM的水文分析与GIS结合，DEM库，矢量库，影像库的三维一体化，DEM与数字地球等的应用。还有在摄影测量与遥感方面，气候分析和环境研究中的应用以及在地质和采矿工程，林业，地形学方面都有很强的应用。

本文对不规则三角网生长算法实现的研究，将传统的三角网生长算法进行了改进，使三角网构建速度大大提高，相信这一研究会有一定的价值和现实意义。

【参考文献】

[1]李志林，朱庆.数字高程模型[M].武汉大学出版社，2001.

[2]刘锦中，马辉.基于等高线的DEM生成算法研究和实现[J].现代测绘，2004：27（3）.

[3]武哓波，王世新，肖春生.Delaunay三角网的生成算法研究[J].测绘学报，1999：28（1）.

[4]刘学军，龚健雅.约束数据域的Delaunay 三角剖分与修改算法[J].测绘学报，2001：30（1）.

[责任编辑：杨玉洁]