Delaunay三角网的生成算法研究.doc

Delaunay三角网的生成算法研究*武晓波　王世新　肖春生摘　要　Delaunay三角网作为一种主要的DTM表示法，具有极其广泛的用途经过二十多年来的研究，它的生成算法已趋于成熟本文简要介绍了Delaunay三角网的定义及其特性，在简单回顾和评价了分割-归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法经测试，一般情况下它的运算速度远快于逐点插入法，与分割-归并法相当，较好的情况下快于分割-归并法关键词　DTM　Delaunay三角网　生成算法　合成算法分类号　TP309A new study of Delaunay triangulation creationWu Xiaobo, Wang Shixing, Xiao Chunsheng(Institute of Remote Sensing Applications, Chinese Academy of Sciences,Beijing,100101)Abstract　As one of the most important DTM model, Delaunay triangulation is widely applied in manifold fields. This paper introduces briefly its definition and significant properties. After reviewed and assessed simply to its prevalent generation algorithms—divide-conquer, incremental insertion, triangulation growth, this article provides a new upgrade algorithm—compound algorithm. The new algorithm takes advantages of divide-conquer and incremental insertion algorithm. It uses computer resources of time and space more reasonably. Through test with real DEM data, its running speed proves far faster than that of incremental insertion and matches to divide-conquer in average case. In better case, faster than divide-conquer.Keywords　DTM, Delaunay triangulation, Generation algorithm, Compound algorithm 1　前言　　在地学领域，经常需要处理大量分布于地域内的离散数据。

由于这些数据分布的不均匀性，就产生了一个如何合理有效地使用这些宝贵数据的问题1908年，G.Voronoi首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的Voronoi图［1］（以下称为V-图）1911年，A.H.Thiessen应用V-图进行了大区域内的平均降水量研究［2］1934年，B.Delaunay由V-图演化出了更易于分析应用的Delaunay三角网［3］（以下称为D-三角网）从此，V-图和D-三角网就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具当然，它的应用不仅适用于地学，而且活跃于所有与2.5维分析有关的领域　　在GIS中，2.5维的分析处理由DTM（数字地形模型）模型进行DTM主要由栅格与TIN（不规则三角网）两种数据格式来表示［4，5］，而以后者更为重要前者的优点是，充分表现了高程的细节变化，拓扑关系简单，算法实现容易，某些空间操纵及存储方便；它的不足之处是，占用巨大的存储空间，不规则的地面特征与规则的数据表示之间的不协调后者的优点是，高效率的存储，数据结构简单，与不规则的地面特征和谐一致，可以表示线性特征和迭加任意形状的区域边界，易于更新，可适应各种分布密度的数据等；它的局限性是，算法实现比较复杂和困难。

在现今的GIS系统中，基本上均支持以上两种数据格式，以TIN为主，栅格为辅，并提供相互转换功能　　历经二十余年的不懈努力，TIN的许多算法难关已被攻克TIN的生成算法中，最终有三种为普遍接受和采用，它们是分割-归并法、逐点插入法和逐步生长法，而又以前二者更为流行分割-归并法时间效率高，但占用内存空间较多逐点插入法时间效率较差，占用内存空间较少本文在此二者基础上，提出了一种综合性能的算法——合成算法它的时性能优于以上两种算法2　Delaunay三角网的定义及其特性　　Delaunay三角网是V-图（也称为Thiessen图，Dirichlet图，Vigner-Seithz图）的伴生图形对它的研究是从对V-图的研究开始的V-图定义是：　　假设V={v1,v2,...,vN }, N≥3是欧几里德平面上的一个点集，并且这些点不共线，四点不共圆用d(vi , vj)表示点vi , vj间的欧几里德距离设x为平面上的点，则区域V(i)={x∈E2|d(x,vi)≤d(x,vj), j=1,2,...,N, j≠I}称为Voronoi多边形（V-多边形）各点的V-多边形共同组成V-图　　平面上的V-图可以看作是点集V中的每个点作为生长核，以相同的速率向外扩张，直到彼此相遇为止而在平面上形成的图形。

除最外层的点形成开放的区域外，其余每个点都形成一个凸多边形　　D-三角网的定义是：　　有公共边的V-多边形称为相邻的V-多边形连接所有相邻的V-多边形的生长中心所形成的三角网称为D-三角网　　D-三角网的外边界是一个凸多边形，它由连接V中的凸集形成，通常称为凸壳D-三角网具有两个非常重要的性质　　. 空外接圆性质：在由点集V所形成的D-三角网中，其每个三角形的外接圆均不包含点集V中的其他任意点；　　. 最大的最小角度性质：在由点集V所能形成的三角网中，D-三角网中三角形的最小角度是最大的　　由于这两个性质，决定了D-三角网具有极大的应用价值同时，它也是二维平面三角网中唯一的、最好的Miles证明D-三角网是“好的”三角网［6］；Sibson认定“在一个有限点集中，只存在一个局部等角的三角网，这就是D-三角网”［7］；Lingas进一步论证了“在一般情况下，D-三角网是最优的”［8］； Tsai认为，“在不多于3个相邻点共圆的欧几里德平面中，D-三角网是唯一的”［9］3　D-三角网生成算法回顾　　Tsai根据实现过程，把生成D-三角网的各种算法分为三类：分治算法；逐点插入法；三角网生长法［7］。

3.1　分治算法　　Shamos和Hoey提出了分治算法思想［10］，并给出了一个生成V-图的分治算法Lewis和Robinson将分治算法思想应用于生成D-三角网［11］他们给出了一个“问题简化”算法，递归地分割点集，直至子集中只包含三个点而形成三角形，然后自下而上地逐级合并生成最终的三角网以后Lee和Schachter又改进和完善了Lewis和Robinson的算法［12］　　Lee和Schachter算法的基本步骤是：　　把点集V以横坐标为主，纵坐标为辅按升序排序，然后递归地执行以下步骤：　　把点集V分为近似相等的两个子集VL和VR；　　在VL和VR中生成三角网；　　用Lawson提出的局部优化算法LOP［12］优化所生成的三角网，使之成为D-三角网；　　找出连接VL和VR中两个凸壳的底线和顶线；　　由底线至顶线合并VL和VR中两个三角网　　以上步骤显示，分治算法的基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用LOP算法保证其成为D-三角网不同的实现方法可有不同的点集划分法、子三角网生成法及合并法3.2　逐点插入法　　Lawson提出了用逐点插入法建立D-三角网的算法思想［11］。

Lee和Schachter，Bowyer，Watson，Sloan，Macedonio和Pareschi，Floriani和Puppo，Tsai先后进行了发展和完善［9，13～18］　　逐点插入算法的基本步骤是：　　定义一个包含所有数据点的初始多边形；　　在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点都被处理；　　插入一个数据点P，在三角网中找出包含P的三角形t，把P与t的三个顶点相连，生成三个新的三角形；　　用LOP算法优化三角网　　从上述步骤可以看出，逐点插入算法的思路非常简单，先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为D-三角网各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法不同3.3　三角网生长法　　Green和Sibson首次实现了一个生成Dirichlet多边形图的生长算法［19］Brassel和Reif稍后也发表了类似的算法［20］McCullagh和Ross通过把点集分块和排序改进了点搜索方法，减少了搜索时间［21］Maus也给出了一个非常相似的算法［22］ 　　三角网生长算法的基本步骤是：　　以任一点为起始点；　　找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线，按D-三角网的判别法则（即它的两个基本性质），找出与基线构成D-三角形的第三点；　　基线的两个端点与第三点相连，成为新的基线；　　迭代以上两步直至所有基线都被处理。

　　上述过程表明，三角网生长算法的思路是，先找出点集中相距最短的两点连接成为一条Delaunay边，然后按D-三角网的判别法则找出包含此边的D-三角形的另一端点，依次处理所有新生成的边，直至最终完成各种不同的实现方法多在搜寻“第三点”上做文章 　　Tsai为比较算法性能，给出了一张各种算法的时间复杂度对照表［9］如表1所示表1　几种Delaunay三角网生成算法的时间复杂度Tab.1　Run-time complexities for several Delaunay triangulation algorithms算法一般情况最坏情况Lawson(1977)2O(N4/3)O(N2)Green和Sibson(1978)3O(N3/2)O(N2)Lewis和and Robinson(1978)1O(NlogN)O(N2)Brassel和Reif(1979)3O(N3/2)O(N2)MaCullagh和Ross(1980)3O(N3/2)O(N2)Lee和Schachlter(1980)1O(NlogN)O(NlogN)Lee和Schachlter(1980)2O(N3/2)O(N2)Bowyer(1981)2O(N3/2)O(N2)Watson(1981)2O(N3/2)O(N2)Mirante和Weigarten (1982)3O(N3/2)O(N2)Sloan(1987)2O(N5/4)O(N2)Dwyer(1987)1O(NloglogN)O(NlogN) Chew(1989)1O(NlogN)O(NlogN)Macedonio和Pareschi(1991)2O(N3/。