生成Delaunay三角网的合成算法

Delaunay三角网生成算法的研究与实现(1)摘要 Delaunay三角网作为一种主要的数字地形模型表示法，经过二十多年来的研究，它的生成算法已趋于成熟。

本文在简单回顾和评价了分割—归并法、逐点插入法、三角网生长法等三类主流算法的基础上，介绍并实现了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。

关键字数字地层模型；三棱柱； Delaunay；三角网；生成算法0 引言计算机图形学是利用计算机研究图形的表示、生成、处理、显示的学科。

经过30多年的发展，科学可视化已成为计算机图形学中最活跃的分支之一，并得到了广泛的应用。

在地质领域,由于大量珍贵的地层钻探数据需要用有效的方式进行直观地表达，因而致使可视化技术成为地质研究和工程勘查领域必不可少的手段。

在建模中，2.5维的分析处理由DTM(数字地形模型)模型进行。

DTM主要由栅格与TIN（不规则三角网）两种数据格式来表示[1，2]，而以后者更为重要。

TIN的生成算法中，最终有三种为普遍接受和采用，它们是分割—归并法、逐点插人法和逐步生长法。

本文在简要分析了上述算法所有缺点的基础上，实现了一种合成算法。

1 Delaunay三角网生成算法回顾Tsaj根据实现过程，把生成Delaunay三角网的各种算法分为三类：分治算法；逐点插入法；三角网生长法。

Tsai为比较算法性能，给出了一张各种算法的时间复杂度对照表，如表1所示。

表中，N为数据点数。

0(f(N))表示算法的时间复杂度，它以算法中频度最大的语句频度f(N)来度量。

上述三类算法中，三角网生长法在80年代中期以后就很少用到，较常见的是分治算法和逐点插入法，而这两类算法又各有其长处和短处。

逐点插入法虽然实现过程相对简单，所需内存较小，但它的时间复杂度高。

所以从时间复杂度方面看，分治算法最好。

但由于算法中存在递归，它需要较大内存空间。

在普通的计算机平台上，运行速度慢和占用较大内存都是应该尽量避免的。

本次设计中，我们引入并实现了一种合成算法，将逐点插入法植入到了分治算法中，互相取长补短，从而达到了较好的时空性能，也很好地体现了两者的优势。

Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形◆Delaunay 三角网的定义:由一系列相连的但不重叠的三角形的集合, 而且这些三角形的外接圆不包含这个面域的其他任何点。

◆Voronoi图的定义：Voronoi图把平面分成N 个区，每一个区包括一个点，该点所在的区域是距离该点最近的点的集合。

◆Delaunay三角网的特性：◆不存在四点共圆；◆每个三角形对应于一个Voronoi图顶点；◆每个三角形边对应于一个Voronoi图边；◆每个结点对应于一个Voronoi图区域；◆Delaunay图的边界是一个凸壳；◆三角网中三角形的最小角最大。

空外接圆准则最大最小角准则最短距离和准则在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角一点到基边的两端的距离和为最小Delaunay三角剖分的重要的准则张角最大准则面积比准则对角线准则一点到基边的张角为最大三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小两三角形组成的凸四边形的两条对角线之比。

这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化Delaunay三角剖分的重要的准则不规则三角网(TIN)的建立●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。

●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。

方法说明方法实例收缩生长算法先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网分割合并算法逐点插入算法扩张生长算法从一个三角形开始向外层层扩展，形成覆盖整个区域的三角网递归生长算法逐点插入算法分割合并算法12121212递归生长算法333TIN 建立过程中的几个问题:◆邵春丽.DELAUNAY 三角网的算法详述及其应用发展前景◆鲍蕊娜，等:基于凸壳技术的Delaunay 三角网生成算法研究◆于杰等：Delaunay 三角网构建方法比较研究周围点的提取 点在三角形中的查找 空外接圆判断准则 线段求交问题。

基于三角网生长法的Delaunay三角网生成算法***************【摘要】论文简要介绍了Delaunay三角网的性质以及基本生成算法，并重点介绍了三角网生长法的基本原理和算法步骤，并通过设计合理的数据结构，对算法进行实现。

对算法进行分析并提出通过构建格网索引，进一步提高三角网生成效率。

【关键词】三角网生长法扩展TIN 格网索引1.引言数字地形模型DTM（Digital Terrain Model）是指对地形表面形态属性信息的数字表达，是带有空间位置特征和地形属性特征的数字描述[1]。

DTM是GIS的基础数据来源，可用于土地利用现状的分析、合理规划及洪水险情预报等。

DTM地形属性为高程时称为数字高程模型(DEM)。

DEM主要的三种表示模型为规则格网模型、等高线模型、不规则三角网模型（Triangular Irregular Network 简称TIN）。

数字化等高线模型不适合计算坡度或制作地貌渲染图等地形分析，规则格网数据结构简单，计算方便；但存在数据冗余，数据采集较麻烦，难以表达复杂地形等缺陷。

TIN即能够避免平坦地形时数据冗余，也能表达复杂地形，可以根据任意地形特征点表示DEM，因此被广泛应用。

Delaunay三角剖分能最大程度的接近等边三角形，避免狭长三角形，并且能保持三角网的唯一性，使其成为生成TIN的最佳选择。

本论文将简要介绍和比较几种常用的Delaunay三角网生成算法（逐点插入法，三角网生长法，分割合并算法等），并且对三角网生长法算法原理进行研究分析和程序实现。

2.Delaunay三角网的性质Delaunay三角网中的三角形必须满足以下几个性质：（1）空圆特性每一个Delaunay三角形的外接圆不包括Delaunay三角网中的任何其他点。

（2）最大最小角特性在三角剖分中，Delaunay三角网的所有三角形的最小角之和最大。

即使得Delaunay三角形最大程度接近等边三角形。

收稿日期:2004ν04ν20DE LAUNAY 三角网的算法详述及其应用发展前景邵春丽①,胡　鹏①,黄承义②,彭　琪①(①武汉大学资源与环境科学学院,武汉　430079;②青岛环海海洋工程勘察研究院,山东青岛　266033)【摘　要】在GIS 应用领域中,Delaunay 三角网通常被用于生成不规则三角网(TI N )模型,并用于描述地表形态。

本文详细叙述改进了的现有国内外Delaunay 三角网的生成算法,并发现Delaunay 三角网不但在描述地表形态上有很大的优势,而且在图像处理、模式识别领域也将有很大的优势。

而且国内外已经有部分学者专家作出一定的尝试,并且取得了较好的效果。

所以作者进一步提出将Delaunay 三角网用于地图符号信息识别,将是一个很有发展前景的应用方向。

【关键词】Delaunay 改进算法;TI N ;地图模式识别【中图分类号】P208 【文献标识码】A 【文章编号】1009ν2307(2004)06ν0068ν041　引　言虽然目前关于Delaunay 三角网的文章有很多,但是大多都只介绍了算法的主要思想,并没有介绍其详细生成算法,给参看这类文章的读者带来了很大的不便。

所以笔者针对该不足,详细介绍了改进的分割ν归并法、逐点插入法和三角网生长法。

可以根据不同的实际情况选用不同的算法。

并在此基础上发现了如果能把Delaunay 三角网应用于地图信息识别,将是一个很有发展前景的方向。

2　相关概念211　TI N (T riangulated Irregular Net )即不规则三角网,Delaunay 三角网是其中的一种表现形式,也是一种主要的DT M 表示法[1]。

212　Delaunay 三角网的定义:它是一系列相连的但不重叠的三角形的集合,而且这些三角形的外接圆不包含这个面域的其他任何点。

它具有两个特有的性质:1)每个Delaunay 三角形的外接圆不包含面内的其他任何点,称之为Delaunay 三角网的空外接圆性质,这个特征已经作为创建Delaunay 三角网的一项判别标准;2)它的另一个性质最大最小角性质:在由点集V 中所能形成的三角网中,Delaunay 三角网中三角形的最小角度是最大的[1]。