生成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]。

一种改进的高效Delaunay三角网的生成算法
郭兆胜;张登荣
【期刊名称】《遥感信息》
【年(卷),期】2005(000)001
【摘要】Delaunay三角网在GIS/VR中具有很广泛的用途,而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法.本文在研究了基于这两种算法的合成算法后,对其进行了修改和优化,形成了高效合成算法.高效合成算法中提出了通过确定点线关系来解决点的定位问题,优化了其LOP的算法,提高了算法的稳定性,使其执行效率得到很明显地提高,本算法的设计思想还可推广到三维空间.【总页数】3页(P15-17)
【作者】郭兆胜;张登荣
【作者单位】浙江大学地球科学系,杭州,310027;浙江大学地球科学系,杭
州,310027
【正文语种】中文
【中图分类】TP391
【相关文献】
1.四叉树高效Delaunay三角网生成算法 [J], 石松;朱泉锋;唐丽玉
2.基于虚拟网格的高效Delaunay三角网生成算法研究 [J], 夏少芳;陈立潮;刘佳
3.一种改进的Delaunay三角网生成算法 [J], 王强;郑逢斌;乔保军;马庆华
4.一种高效的Delaunay三角网合并生成技术 [J], 向传杰;朱玉文
5.基于合成算法的Delaunay三角网生成改进算法 [J], 潘丽丽;孙玉秋
因版权原因，仅展示原文概要，查看原文内容请购买。

中南大学本科毕业设计调研报告学生姓名：王静波专业班级：软件工程0702学号： 3901070219院（系）：软件学院指导老师：陈学工研究课题：三角网数据生成算法研究与实现毕业设计日期：2010年12月到2011年6月摘要数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。

不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。

在所有可能的三角网中，Delaunay三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。

本文的主要内容便是研究Delaunay三角网生成算法。

首先本文介绍了地理信息系统（GIS）的基本概念及相关信息；然后仔细介绍了数字地面模型的相关知识和国外内主要的三种Delaunay三角网生成算法——分治算法、逐点插入法、三角网生长法；最后讲述了研究三角网生成算法的目的及意义，并描述了一种生成Delaunay三角网的合成算法，此算法在主流算法的基础上进行了优化。

关键词：地理信息系统，数字地面模型，不规则三角网，Delaunay 三角网目录摘要 (2)第一章绪论 (4)1.1 地理信息系统的基本概念及发展现状 (4)1.1.1 地理信息系统的基本概念 (4)1.1.2 地理信息系统的发展动态 (5)1.2 数字高程模型 (6)第二章三角网数据生成方法 (9)2.1 三角网数字模型 (9)2.1.1 三角网数字模型的基本理论 (9)2.1.2 三角网数字模型的研究现状 (9)2.1.3 三角网数字模型的研究发展方向 (10)2.2 Delaunay三角网 (11)2.2.1 基本定义及相关概念 (11)2.2.2 D-三角网生成算法回顾 (12)第三章三角网数据生成算法的研究思路与方法 (14)3.1 研究内容及其目的与意义 (14)3.2 研究思路 (14)参考文献 (15)第一章绪论1.1地理信息系统的基本概念及发展现状1.1.1 地理信息系统地理信息系统（简称GIS）是跨越地球科学、信息科学和空间科学的应用基础学科，它研究关于地理空间信息处理和分析过程中提出一系列基本问题，如空间对象表达与建模、空间关系及推理机制、空间信息的控制基准、空间信息的认知与分析、GIS系统设计与评价GIS应用模型与可视化、空间信息的政策与标准等［1］。

大量约束边条件下Delaunay 三角网的快速生成徐道柱,刘海砚(信息工程大学测绘学院,河南郑州450052)摘 要:讨论了建立约束Delaunay 三角网算法的研究现状,采用 逐点插入法 和 多对角线交换算法 构成 两步法 ,在此基础上,从建立高精度三角网模型的需求出发,研究以大数据量等高线为约束边进行Delaunay 三角剖分的改进算法。

针对 逐点插入法 ,采用网格分块的方法对构网点集和已生成的三角网建立索引,提高了点的查询速度和点在三角网中的定位速度,提高了三角网的生成效率;针对 多对角线交换算法 ,增加了一些特殊情况的处理,提高了算法的健壮性和交换速度。

关键词:约束Delaunay 三角网;逐点插入法;约束边嵌入;对角线交换;等高线中图分类号:P22 文献标识码:A 文章编号:1006-7949(2007)03-0006-05The of fast ge neration constraint delaunay triangulation with constraint linesXU Dao zhu,LIU Hai yan(Institute of Surveying and M apping ,I nformation Engineering U niversity,Zhengzhou 450052,China)Abstract :It presents the status of Delaunay triangulation m ethods,w hich consists of tw o steps,firstly,con structing Delaunay triangulation by incremental insertion algorithm,and them inserting constrained boundary by multiple diagonal exchanging algorithm to form constraint Delaunay Triangulation.In order to construct high resolution Triangulation,the algorithm uses contour line as constraint line.The tw o steps algorithm,w ill im prove the algorithm for fast inserting constrained line.In incremental insertion algorithm,it org anizes the point set and triangle by constructing grid index to enhance the query speed of point and the speed of searching for the triangle that contains the given point.With the improving measures,the efficiency of algorithm is greatly im proved.Key words :constraint delaunay triangulation;incremental insertion algorithm;inserting constrained boundary;diagonal ex chang ing;contour line收稿日期:2006-12-06基金项目:国家自然科学基金资助项目(40401052)作者简介:徐道柱(1982~),男,硕士研究生.一般的三维地形应用对三角网地形模型没有特殊要求,如三维地形浏览显示。