怏怏不乐的意思三角网数据生成算法研究与实现调研报告

2021年1月5日发(作者：浦文睿)
中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波



中 南 大 学

本科毕业设计调研报告






学生姓名： 王静波
专业班级： 软件工程0702
学 号： 3901070219
院 （系）： 软件学院
指导老师： 陈学工
研究课题： 三角网数据生成算法研究与实现
毕业设计日期：2010年12月到2011年6月




1
中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波


摘 要


数字地形模型是针对地形地貌的一种数字建模,这种建 模的结
果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型
是DEM中存储 和表示非规则数据的理想模型，它既减少规则网格方
法造成的数据冗余，同时在计算效率方面又优于纯粹 基于等高线的方
法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌
三维信息。 在所有可能的三角网中，Delaunay三角网在地形拟合方面
表现最为出色，因此常常用于TIN的 生成。本文的主要内容便是研
究Delaunay三角网生成算法。首先本文介绍了地理信息系统（GI S）
的基本概念及相关信息；然后仔细介绍了数字地面模型的相关知识和
国外内主要的三种De launay三角网生成算法——
分治算法、逐点插入法、
三角网生长法
；最后讲述了 研究三角网生成算法的目的及意义，并描述
了一种生成Delaunay三角网的合成算法，此算法在主 流算法的基础
上进行了优化。

关键词：地理信息系统，数字地面模型，不规则三角网，Delaunay
三角网






2

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波

目 录

摘要…………………………………………………………………………….……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

















3

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
第一章 绪论

1.1 地理信息系统的基本概念及发展现状
1.1.1 地理信息系统

地理信息系统（简称GIS）是跨越地球科学、信息科学和空间科学的应用
基础学科，它研究关于地 理空间信息处理和分析过程中提出一系列基本问题，如
空间对象表达与建模、空间关系及推理机制、空间 信息的控制基准、空间信息的
认知与分析、GIS系统设计与评价GIS应用模型与可视化、空间信息的 政策与标
准等
［
1
］
。关于它的全称，多数人认为时Geograp hical Information System，也有少
数人认为时Geo－information System。国际上现发行的两 种杂志，就是各采用不
同的全称。前者是英国出版的季刊全称，后者是德国出版的季刊全称。在加拿大< br>和澳大利亚，则全称为Land Information System。 在我国，通常称为Resourse
and Enviroment Information。全称 虽然有差异，但都简称为GIS。由于GIS是计
算机科学、地理学、测量学、地图学等多门学科综合的 技术。要给出GIS的准
确定义是困难的，站在不同的角度，给出的定义就不同。通常可以从4种不同的
途径来定义GIS：(1) 面向功能的定义，GIS是采集、存储、检查、操作、分析
和显示地理数据的系统；(2) 面向应用的 定义，这种方式根据GIS应用领域的不
同，将GIS分为各类应用系统，例如土地信息系统、城市信息 系统、规划信息
系统、空间决策支持系统等；(3) 工具箱定义方式，GIS是一组用来采集、存储、
查询、变换和显示空间数据的工具的集合，这种定义强调GIS提供的用于处理
地理数据的工具 ；(4) 基于数据库的定义，GIS是这样一类数据库系统，它的数
据有空间次序，并且提供一个对数 据进行操作的操作集合，用来回答对数据库中
空间实体的查询
［
2
］
。
地理信息系统是一门多学科综合的边缘学科，但其核心是计算机科学，基
本技术 是数据库、地图可视化及空间分析(见图1一1)；GIS是处理地理据的输
入、输出、管理、查询、分 和辅助策的系统。


图1-1 地理信息系统的组成

1.1.2 地理信息系统的发展动态
4

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波

90年代以来，随着地理信息产业的建立和 地球数字化产品的普及应用，GIS
的发展进入用户时代。这个期间，社会对GIS的认识普遍提高，需 求大幅度增
加。GIS已成为许多机构（特别是政府决策部门）必备的工作系统。国家级乃至
全 球级的地理信息系统已成为公众关注的问题。地理信息系统已被列入“信息高
速公路”计划，也是美国前 总统戈尔提出的“数字地球”战略的重要组成部分。
90年代以来，GIS的开发和研究主题集中在下列 一些方向：空间信息分析的新
模式和新方法；空间信息的应用模型；GIS的效益评价；三维和四位空间 数据结
构和数据模型；人工智能和专家系统的引入，网络GIS；虚拟现实技术与GIS的
结合 等。尽管现存的地理信息系统软件很多，目前已成功地应用到了包括资源管
理、自动制图、设施管理、城 市和区域的规划、人口和商业管理、交通运输、石
油和天然气、教育、军事等九大类别的一百多个领域。 在美国及发达国家，地理
信息系统的应用遍及环境保护、资源保护、灾害预测、投资评价、城市规划建设 、
政府管理等众多领域。近年来，随我国经济建设的迅速发展，加速了地理信息系
统应用的进程 ，在城市规划管理、交通运输、测绘、环保、农业、制图等领域发
［］
挥了重要的作用，取得了 良好的经济效益和社会效益
3
。下面举例说明：

（1）地理信息系统在地理空间数据管理中的应用
以多种方式录入的地理数据，以有效的数据组织形式 进行数据库管理、更
新、维护、进行快速查询检索，以多种方式输出决策所需的地理空间信息。如
ARC／INFO在公路管理中的应用；ARC／INFO在对市政设施管理中的应用。
我国大城市数 量居全国前列,根据加快中心城市规划建设和加强城市建设决策科
学化的要求,利用地理信息系统作为城 市规划管理和分析的工具,具有十分重要的
意义。

（2）GIS在综合分析评价与模拟预测中的应用
GIS不仅可以对地理空间数据进行编码、存储和提 取，而且还是现实世界
模型，可以将对现实世界各个侧面的思维评价结果作用其上，得到综合分析评价< br>结果；也可以将自然过程、决策和倾向的发展结果以命令、函数和分析模拟程序
作用上这些数据上 ，摸拟这些过程的发生发展，对未来的结果作出定量的和趋势
预测，从而预知自然过程的结果，对比不同 决策方案的效果以及特殊倾向可能产
生的后果，以作出最优决策，避免和预防不良后果的发生。如GIS 在土地信息
和土壤保护中的应用。后者如美国资源部和威斯康星州合作建立了以治理土壤侵
蚀为 主要目的的多用途专用的土地GIS。

（3）GIS的空间查询和空间分析功能的应用
为了便于管理和开发地理信息(空间信息和属性信息)，在建库时是分层处
理的。也就是说，根 据数据的性质分类，性质相同或相近的归并一起，形成一个
数据层。这样GIS对单副或多副图件及其属 性数据进行分析和指标量算。这种
应用以原始图为输入，而查询和分析结果则是以原始图经过空间操作后 生成的新
图件来表示，在空间定位上仍与原始图一致。因此，也可将其称为空间函数变换。
这种 空间变换包括叠置分析、缓冲区分析、拓扑空间查询、空集合分析(逻辑交
运算、逻辑并运算、逻辑差运 算)。这方面应用例子有很多，例如在城市规划过
5

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
程中，对城市中救护车、救火车的分布位置以及行车路 线和控制的规划；在环境
保护方面，对水土流失导致土地资源的破坏进行评价；在区域环境质量现状评价
过程中，对整个区域的环境质量进行客观地、全面地评价，以反映出区域中受污
染的程度以及空 间分布状态；在地学方面，MAPGIS在油气勘探中和在成矿预测
中的应用，解决了肉眼所不能看见的 深部构造问题和指明矿产的远景区。在大都
市防震减灾系统中的应用，1994年的美国洛杉机大地震， 就是利用RAC／INFO
进行灾后应急响应决策支持，成为大都市利用GIS技术建立防震减灾系统的 成
功范例。在野生动植物保护中的应用，世界野生动物基金会(WWF)采用GIS软
件ARC INFO作为“老虎与人类”保护项目的主要技术工具。利用ARCINFO空
间分析功能，WWF已找 到新的方法来帮助世界最大的猫科动物改变它目前濒于
灭种的境地。

（4）GIS的输出功能在地图制图中的应用
地理信息系统的发展是从地图制图开始的，因而GIS的 主要功能之一用于
地图制图，建立地图数据库。与传统的、周期长、更新慢的手工制图方式相比，
利用GIS建立起地图数据库，可以达到一次投入、多次产出的效果。它不仅可
以为用户输出全要素地 形图，而且可以根据用户需要分层输出各种专题，如行政
区划图、土地利用图、道路交通图等等。更重要 的是由于GIS是一种空间信息
系统。它所制作的图也能够反映一种空间关系，可以制作多种立体图形， 而制作
立体图形的数据基础就是数字高程模型。在地图的输出中，MAPGIS达到世界先
进水 平。

（5）运用GIS系统，建立起专题信息系统和区域信息系统
专题信息 系统如水资源管理信息系统、矿产资源信息系统、草场资源信息
系统、水土流失信息系统和目前上海正在 建立长途电信局GIS系统等等。这类
信息系统具有有限目标和专业特点，系统数据项的选择和操作功能 是为特定的专
门目的服务。区域信息系统如加拿大国家信息系统、美国Oakridge地区模式信息系统等等。这类信息系统主要以区域综合研究和全面的信息服务为目标，可以
有不同的规模，其特 点是数据项多，功能齐全，通常具有较强的开放性。这两种
信息系统与上述四种GIS应用或多或少有重 叠处，但这里强调的是完整性、系
统性、故与它们分开讨论。

（6）地理信息系统与遥感图像处理系统的结合的应用
遥感数据是地理信息系统重要信息源。其实目前 大多数GIS系统已揉进图
像处理功能，并把它作为其一个子模块。这种应用如海湾战争期间，美国国防 制
图局GIS实时服务，为战争需要在工作站上建立了GIS与遥感的集成系统，它
能用自动影 像匹配和自动目标识别技术处理，处理卫星和高低侦察机实时获得战
场数字影像，及时地将反映战场现状 的正射影影像叠加到数字地图上，数据直接
传送到海湾前线指挥部和五角大楼，为军事决策提供24小时 的实时服务。

（7）应用GIS一些二次开发函数库开发出具有特定功能软件系统 < br>如国家九五攻关项目“紧缺金属资源快速勘察评价系统”，这个系统中，分
为地质变量信息提取模 块、数据挖掘模块、物探数据处理模块、图像处理模块、
综合预测模块等，其中地质变量信息提取模块使 用了MAPGIS中基本输入函数、
6

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
空间功能分析函数，目前这个系统已初具皱形。

（8）GIS中属性数据的综合及融合
在现有的GIS中，属性数据只是用于 检索和查询，或进行简单的统计，难
以深入的分析，难以发掘隐含在其中的模式和规律。在众多项的属性 数据中，有
时将几个属性项的属性数值加以综合，构成一个具有某领域特定意义的新属性项
新属 性值，这种综合不是综合前属性数据值的简单反映，也不是它们的孤立集合，
而是经过某领域研究人员深 思熟虑的综合分析，用数量表示某领域问题的综合概
念和结果特征。国家科委九五攻关项目“紧缺矿产资 源开发评价系统”中有体现。



1.2 数字高程模型
< br>数字地形模拟是针对地球表面实际地形地貌的一种数字建模过程，这种建模
的结果通常就是数字地 形模型，后来人们把基于高程或海拔分布的数字高程模型
称为 DEM(Digital Elevation Model，DEM)。

数字高程模型（DEM）自20世纪50年 代后期被采用以来，受到了极大的关
注。随着科学技术特别是计算技术的迅速发展，DEM的诸多基础理 论问题得到了
深入的研究，基于DEM数字地形分析的理论与技术方法体系在进一步完备
［4,5
］
。
DEM作为地形表面的一种数字表达形式具有如下特点:
(l)容易以多种形式显示地形信息。地形数据经过计算机软件处理后，产生
多种比例尺的地形 图、纵横断面图和立体图;
(2)精度不会损失。常规地图随着时间推移，图纸将会变形，失掉原有的 精
度，DEM采用数字媒介，因而能保持精度不变;
(3)容易实现自动化和实时化。DEM 由于是数字形式的，所以增加或改变地形
信息只需将修改信息直接输入到计算机;
(4)具有多比例尺特性。如lm分辨率的DEM自动涵盖了更小分辨率如 10m
和100m的DEM内容。
数字高程模型数据的来源主要有三种方式
［
6
］
：(1)数字摄影测量；(2)野外
数字测图；(3)地形图扫描矢量化。数字 摄影测量的基本思想是将模拟的影像变
成可以被计算机处理的数字影像，然后使用计算机实现摄影测量。 数字摄影测量
具有效率高、劳动强度低、精度高等优点，已经成为数字高程模型数据的重要来
源 。
数字高程模型数据是由一些离散点组成，要对离散点进行数字高程建模。
一个地区的地表高 程变化可以采用多种方法表达，用数学定义的表面或点、线都
可以用来表示数字高程模型。用数学方法来 表达，可以采用整体拟合方法，即根
据区域所有的高程点数据，用傅立叶级数和高次多项式拟合统一的地 面高程曲
面。也可用局部拟合方法，将地表复杂表面分成正方形规则区域或面积大致相等
7

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
的不规则区域，根据有限个点进行拟合形成高程曲面。
在地理信息系统中，DEM最主要的三种表示模型是规则格网模型、不规则
三角网模型和等高线 模型，三种模型都有各自的优点，而且相互之间可以基于一
种模型生成另一种模型。下面将简略介绍一下 这三种模型：

(1)规则格网模型
规则格网通常是由矩形组成，它将区域空间切 分为规则的格网单元。规则格
网在数学上可以表示为一个矩阵，在计算机实现中则是一个二维数组，每个 格网
单元的顶点都对应一个高程值。
规则格网的高程矩阵，可以很容易地用计算机进行处理， 而且它还可以很容
易地计算等高线、坡度坡向、山坡阴影和自动提取流域地形，使得它成为DEM
最广泛使用的格式，目前许多国家提供的DEM数据都是以规则格网的数据矩阵形
式提供的。
格网DEM的缺点是不能准确表示地形的结构和细部，为避免这些问题，可采
用附加地形特征数据，如 地形特征点、山脊线、谷底线、断裂线，以描述地形结
构。格网DEM的另一个缺点是数据量过大，给数 据管理带来了不方便，通常要进
行压缩存储。DEM数据的无损压缩可以采用普通的栅格数据压缩方式， 如游程编
码、块码等，但是由于DEM数据反映了地形的连续起伏变化，普通压缩方式难以
达到 很好的效果;因此对于格网DEM数据，可以采用哈夫曼编码进行无损压缩;
有时，在牺牲细节信息的前 提下，可以对格网DEM进行有损压缩，通常的有损压
缩大都是基于离散余弦变换或小波变换，由于小波 变换具有较好的保持细节的特
性，近年来将小波变换应用于DEM数据处理的研究较多。
(2)不规则三角网模型
不规则三角网 (Triangulated Irregular Network,TIN)是一种表示数字高
程模型的方法，它既减少规则格网方 法带来的数据冗余，同时在计算效率方面又
优于纯粹基于等高线的方法。

TIN模 型根据区域内有限个点集将区域划分为相连的三角面网络。区域中任
意点落在三角面的顶点、边上或三角 形内，如果该点不在顶点上，那么点的高程
值通常通过线性插值的方法得到(在边上用边的两个顶点的高 程，在三角形内则
用三个顶点的高程)。所以TIN是一个三维空间的分段线性模型，在整个区域内连续但不可微。
TIN的数据存储方式比较复杂，它不仅要存储每个点的高程，还要存储平面坐标、节点连接的拓扑关系、三角形与邻接三角形的关系。TIN模型在概念上类
似于多边形网络的 矢量拓扑结构。

有许多种表达TIN拓扑结构的存储方式，一种简单的记录方式是:对于每 一
个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边的记
录的指针，边 的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它
的两个顶点的记录的指针，也可以直接 对每个三角形记录其顶点和相邻三角形。
8

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
每个节点包括三个坐标值的字段，分别存储X.Y，Z 坐标。这种拓扑网络结构的
特点是对于给定一个三角形查询三个顶点高程和相邻三角形所用的时间是定长
的，在沿直线计算地形剖面线时具有较高的效率。当然可以在此结构的基础上增
加其它变化，以 提高某些特殊运算的效率，例如在顶点的记录里增加指向其关联
的边的指针。

不规 则三角网数字高程由连续的三角面组成，三角面的形状和大小取决于不
规则分布节点的位置和密度。不规 则三角网可以随地形起伏的变化而改变采样点
的密度和决定采样点的位置，因而它能够避免地形平坦时的 数据冗余，又能按地
形特征点表示数字高程特征。

(3) 等高线模型
等高线模型表示高程,

高程值的集合是己知的，每一条等高线对应一个已知
的高程值，这样一系列等高线集合和它们的高程值就一起构成了一种数字高程模
型。
等高线通 常被存成一个有序的坐标点对序列，可以认为是一条带有高程值属
性的简单多边形或多边形弧段。由于等 高线模型只表达了区域的部分高程值，往
往需要一种插值方法来计算落在等高线外的其它点的高程，又因 为这些点是落在
两条等高线包围的区域内，所以，通常只使用外包的两条等高线的高程进行插值。 等高线通常可以用二维的链表来存储。还可以用树结构来表示等高线的拓扑
关系，将等高线之间的区 域表示成树的节点，用边表示等高线本身。此方法满足
等高线闭合或与边界闭合、等高线互不相交两条拓 扑约束。













9

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
第二章 三角网数字模型

2.1 三角网数字模型
2.1.1 三角网数字模型基本理论

三角网数字模型(Triangulated Irregular Network，简写为TIN) 是用一
系列的互不交又、互不重复的三角形逼近地形表面，与Grid相比，TIN在拟合
地表 上更灵活、更精确。但由于结构的不同，Grid许多成熟的技术并不能完全
移植到TIN中。

从结构上讲，TIN是一典型的矢量数据结构。它主要通过节点(地表采样
点)、三 角形边和三角形面之间的关系来显式或隐式的表达底细功能散点的拓扑
关系，因此设计一个高效的、结构 紧凑的、维护方便的TIN的存储与组织结构对
TIN的应用与维护是至关重要的。

TIN的基本单元三角形的几何形状直接决定着TIN的应用质量。由于地形
的自相关性，相互越接近 的地形采样点，其之间的关联程度越大;同时，理论与
实践均证明，狭长的三角形其插值精度比规则的三 角形插值精度可信度要低。因
此，在TIN中对三角形的几何形状有着严格的要求。一般有三条原则:l )尽量接
近正三角形;2)保证最近的点成三角形;3)三角形网络唯一。


2.1.2 三角网数字模型的研究现状

按地形数据采样的分布情况，对TIN的 三角化可分为三大类，不规则分布数
据三角剖分、规则分布数据三角剖分、基于等高线采样数据三角剖分 。

其中不规则分布数据三角剖分的算法最多，主要有Delaunay三角化算法为
代表的基于数学形态学的三角化算法。Delaunay三角化算法的本质是对凸域进
行三角剖分，然 而实际中的数据域很难为凸域，这就要求三角剖分一方面满足
Delaunay Trangulation算法，另一方面数据边界为三角形的一边，此所谓约束
Delaunay Trangulation三角网算法。Delaunay Trangulation的两个显著特性
一最大最小角特性和空外接圆特性是构成各种Delaunay Trangulation算法的基
础。Delaunay Trangulation算法可分为间接 Delaunay三角网算法和直接
Delaunay三角网算法。间接Delaunay算法复杂、内 存开销大切效率低下，现今
很少使用。直接Delaunay三角网生成算法包括分割- 归并法、逐点插入法、三角
网生长算法。所有的Delaunay Trangulation算法都是 对矢量结构的三角剖分。
实际上也可对栅格影象数据进行三角剖分，这就是基于数学形态的学的三角剖< br>分。
10

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波

在目前所有的三角化算法中，以Delaunay Trangulation的应用最为广泛，
这是由于Detlaunay Trangulation能自动的避免狭长三角形单元。


2.1.3 三角网数字模型的研究发展方向
三角网数字模型的研究发展方向主要有：
（1）三维空间数据域的三角剖分
目前的TIN模型，是一种面向曲面(三角形面元)的表面 重构技术。在本质
上，这种方法产生的数字模型是2.5维。虽然Delannay三角网在二维数据域 上，
最为成功，但其理论与方法不能直接推广到三维情形。目前对三维数据域的三角
剖分是一研 究热点，主要集中在三角剖分原则、数据结构和算法设计上。

（2）地表的动态仿真与可视化技术
基于三角网数字模型的三维动态仿真与可视化有助于用户对地表的直观理
解。

（3）TIN的元数据结构
对于TIN，由于结构灵活，使用方式多样，建立费用较高，故需 建立统一
标准，实现数据共享。


2.2 Delaunay三角网


2.2.1

基本定义及相关概念

Delaunay三角网是V-图（也称为Thiessen图，Dirichle t图，
Vigner-Seithz图）的伴生图形。对它的研究是从对V-图的研究开始的。

V-图定义是：假设V={v
1
,v
2
,...,vN
}, N≥3是欧几里德平面上的一个点集，
并且这些点不共线，四点不共圆，用d(v
i
, v
j
)表示点v
i
, v
j
间的欧几里德距
离，设x为平面上的点，则区域V
(i)
={x∈E
2
|d(x,v
i
)≤d(x,v
j
), j=1,2,...,N, j≠I}
称为Voronoi多边形（V-多边形）。各点的V-多边形共同组成V-图。

平面上的V-图可以看作是点集V中的每个点作为生长核，以相同的速率向
外扩张，直到彼 此相遇为止而在平面上形成的图形。除最外层的点形成开放的区
域外，其余每个点都形成一个凸多边形。

D-三角网的定义是：有公共边的V-多边形称为相邻的V- 多边形。连接所有
相邻的V-多边形的生长中心所形成的三角网称为D-三角网。

11

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
D-三角网的外边界是一个凸多边形，它由连接V 中的凸集形成，通常称为凸
壳。D-三角网具有两个非常重要的性质：
1）空外接圆性质：在由点集V所形成的D- 三角网中，其每个三角形的外接
圆均不包含点集V中的其他任意点；
2）最大的最小角度性质：在由点集V所能形成的三角网中，D-三角网中三
角形的最小角度是最大的。

由于这两个性质，决定了D- 三角网具有极大的应用价值。同时，它也是二
维平面三角网中唯一的、最好的。Miles证明D- 三角网是“最好的三角网”

［
7
］
；
Sibson
认定“在一个有限点集中，只存在一个局部等角的三角网，这就是D-三角
网”

［
8
］
；Lingas进一步论证了“在一般情况下，D-三角网是最优的”

［
9
］
；Tsai

［
10
］
认 为，“在不多于3个相邻点共圆的欧几里德平面中，D-三角网是唯一的”。


2.2.2

D-三角网生成算法回顾

Tsai根据实现过程，把生成D-三角网的各种算法分为三类：分治算法、逐
点插入法、三角 网生长法
［
9
］
。

（1）分治算法

1975年，Shamos和Hoey提出了分治算法思想
［
11
］
，并给 出了一个生成V-
图的分治算法。Lewis和Robinson将分治算法思想应用于生成D-三角网
［
12
］
。他
们给出了一个“问题简化”算法，递归地分割点集，直 至子集中只包含三个点而
形成三角形，然后自下而上地逐级合并生成最终的三角网。以后Lee和Sch achter
又改进和完善了Lewis和Robinson的算法
［
13
］
。

Lee和Schachter算法的基本步骤是：将点集V以横坐标为主，纵坐标为
辅按升序 排序，然后递归地执行以下步骤；把点集V分为近似相等的两个子集
VL和VR；在VL和VR中生成三 角网；用Lawson提出的局部优化算法优化所生成
的三角网，使之成为D- 三角网；找出连接VL和VR中两个凸壳的底线和顶线；
由底线至顶线合并VL和VR中两个三角网。

以上步骤显示，分治算法的基本思路是使问题简化，把点集划分到足够小，
使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用LOP
算法保证其成为D- 三角网。不同的实现方法可有不同的点集划分法、子三角网
生成法及合并法。

（2） 逐点插入法


1978年，Lawson提出了用逐点插入法建立D- 三角网的算法思想
［
12
］
。Lee和
12

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
Schachter，Bowyer，Watson， Sloan，Macedonio和Pareschi，Floriani和Puppo，
Tsai先后 进行了发展和完善
［
10,12-19
］
。

逐点插入算 法的基本步骤是：定义一个包含所有数据点的初始多边形；在初
始多边形中建立初始三角网，然后迭代以 下步骤，直至所有数据点都被处理；插
入一个数据点P，在三角网中找出包含P的三角形t，把P与t的 三个顶点相连，
生成三个新的三角形；用LOP算法优化三角网。

从上述步骤 可以看出，逐点插入算法的思路非常简单，先在包含所有数据点
的一个多边形中建立初始三角网，然后将 余下的点逐一插入，用LOP算法确保其
成为D- 三角网。各种实现方法的差别在于其初始多边形的不同以及建立初始三
角网的方法不同。


（3） 三角网生成法

1978年，Green和Sibson首次 实现了一个生成Dirichlet多边形图的生长
［
20
］
算法。Bras sel和Reif稍后也发表了类似的算法
［
21
］
。McCullagh和 Ross通
过把点集分块和排序改进了点搜索方法，减少了搜索时间
［
22
］
。。Maus也给出了
一个非常相似的算法
［
23
］
。

三角网生长算法的基本步骤是：以任一点为起始点；找出与起始点最近的数
据点相互 连接形成D-三角形的一条边作为基线，按D- 三角网的判别法则（即它
的两个基本性质），找出与基线构成D- 三角形的第三点；基线的两个端点与第
三点相连，成为新的基线；迭代以上两步直至所有基线都被处理。

上述过程表明，三角网生长算法的思路是，先找出点集中相距最短的两点连
接成 为一条Delaunay边，然后按D-三角网的判别法则找出包含此边的D-三角形
的另一端点，依次 处理所有新生成的边，直至最终完成。各种不同的实现方法多
在搜寻“第三点”上做文章。














13

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
第三章 三角网数据生成算法的研究思路与方法

3.1 研究内容及其目的及意义

近年来，随着科技的发展，地理信息 系统在军事、自然资源管理、土地和城
市管理、电力、电信、石油和天然气、城市规划、交通运输、环境 监测和保护、
110和120快速反应系统等国防、经济建设、日常生活中得到了越来越广泛地应
用。与地理信息系统相关的问题也逐渐成为人们研究的对象，而Delaunay三角
网更是人们研究 的热点。因为Delaunay三角网被认为是三角剖分中最优的，并
且它使用原始数据建模，更能准确 地客观地反应真实信息。由于它的良好性质，
决定了它有极大的应用价值，常常被用于构建TIN。在所 有的TIN中，Delaunay
三角网尽可能地避免了病态三角形的出现，以不规则三角网为表现形式 的数字地
面模型与以网格表现的形式相比，更能反应原始地形的细节。Delaunay三角网不
仅在描述地表形态上有很大的优势，而且在图像处理、模式识别领域也将有很大
的优势。

Delaunay三角网生成算法经过多年的发展已经相当成熟，它在生活、军事、
工业等领域 都得到了广泛地应用，如：在印鉴方面的应用，易于识别；军事上构
建地面数字模型，易于部队指挥员对 地貌的识别和对地形的分析；工业上适用于
应用层组播叠加网的构建；在现在的数字城市建设以及线路C AD软件开发中的
应用等。由此可见，Delaunay三角网生成算法具有非常重要的意义。

本课题便是基于Delaunay三角网进行不规则三角网数据生成算法的研究，
主 要内容便是研究Delaunay三角网生成的算法。



3.2 研究思路

在三类主流Delaunay三角网生成算法中，三角网生长法 在80年代中期以后
的文献中已很少见，较多的是分治算法和逐点插入法，而后两类算法又各有其长处及短处。逐点插入法虽然实现比较简单，占用内存较小，但它的时间复杂度差，
即运行速度慢，S hamos和Hoey已证明在N个数据点中建立任何三角网至少需要
Ω(NlogN)时间
［ 11］
，所以从时间复杂度方面看，分治算法最好。但由于递归执行，
它需要较大内存空间。在 较低档的计算机平台上，速度慢和占用大空间都是令人
［28］
难以接受的。基于两种算法的优 缺点，武晓波等研究人员提出了一种合成算法，
它把逐点插入法植入到了分治算法中，互相取长补短，体 现了它们的综合优势，
从而达到了较好的时空性能。本人的研究思路便是基于此种合成算法，其
Delaunay三角网生成算法主要步骤如下：
14

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
（1）数据预处理，即将初始点集按升序以x 坐标为主, y 坐标为辅进行排
列, 确保子三角网不相互叠置；
（2）计算凸壳,即使用格雷厄姆算法
［29］
求出点集凸壳；
（3）初始三角网的建立，即以凸壳上y 值最小的点为出发点,按序与凸壳
上其余的点相连，构成初始三角网；
（4）插点入网，首先定位待插入点,

即确定点在哪个三角形中，然后根据
点在三角形的位置, 修改三角网；
（5）局部优化过程，即一旦三角网被修改, 必须进行LOP优化；
（6）查找上下切线，即块找出连接相邻两个子三角网的凸壳的上切线和下
切线；
（7）子网合并，即以两凸壳的下切线为起始基线, 分别沿一个凸壳的逆时
针方向、 沿另一 个凸壳的顺时针方向找出与基线构成Delaunay三角形的第三个
顶点，LOP优化新生成的三角形 , 将新生成的边作为新的基线继续上述过程, 当
基线成为两个凸壳的上切线时终止。



























15

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波


参考文献

[1]黄杏源，地理信息系统概论，2002

[2]吴信才
，
地理 信息系统的基本技术与发展动态[J]，地理科学，1998,23(4)
[3]CHEN Shupeng, ZHONG Ershun. Perspectives on GIS Development in
China .and Annual GIS Infrastructure Planning and Management Conference, Beijing,
China 26-28 May, 1998.
[4] 李志林，朱庆．数字高程模型．武汉：武汉大学出版社，2003
[5] 吴立新，史文中．地理信息系统原理与算法．北京：科学出版社，2003
[6] Shaoming Wang．A smooth surface interpolation to 3D triangulations．Journal of
Computational and Applied Mathematics，2004，163：287~293
[7] Miles R E. Solution to Problem 67-15(Probability Distribution of a
Network of Triangles). SIAM, 1969(11)：399～402
[8]Sibson R. Locally Equiangular Triangulations. Computer Journal,
1978,21(3)：243～245
[9] Lingas A. The Greedy and Delaunay Triangulations are not Bad in the
Average Case. Information Processing Letters, 1986(22)： 25～31
[10] Tsai V J D. Delaunay Triangulations in TIN Creation: an Overview and
a Linear-time Algorithm. Int. J. of GIS, 1993,7(6):501～524
[11] Shamos M I. and Hoey D. Closest-point Problems, In: Proceedings of
the 16th Annual Symposium on the Foundations of Computer Science,
1975.151～162
[12] Lewis B A. and Robinson J S. Triangulation of Planar Regions with
Applications, The Computer Journal, 1978,21(4)：324～332
[13] Lee D T. and Schachter B J. Two Algorithms for Constructing a Delaunay
Triangulation, Int. J. of Computer and Information Sciences, 1980,9(3)
[14] Lawson C L. Software for C' Surface Interpolation. Mathematical
Software III. J. Rice, Ed. New York： Academic Press, 1977
[15] Bowyer A. Computing Dirichlet Tesselations, Computer Journal,
1981(24)：162～166
[16] Watson D F. Computing the n-dimension Delaunay Tesselation with
Application to Voronoi Polytopes. Computer Journal, 1981(24):167～172
[17] Sloan S W. A fast Algorithm for Constructing Delaunay Triangulations
in the Plane. Andvanced Engineering Software, 1987(9):34～55
[18] Macedonia G and Pareschi M T. An Algorithm for the Triangulation of
Arbitrarily Distributed Points: Applications to Volume Estimate and
Terrain Fitting, Computers & Geosciences, 1991(17):859～874
[19]De Floriani L and Puppo E. An on-line Algorithm for Constrained
Delaunay Triangulation, CVGIP: Graphical Models and Image Processing,
16

中南大学本科生毕业设计调研报告 软件学院 3901070219 王静波
1992,54(3):290～300
[20] Green P J. and Sibson R. Computing Dirichlet Tesselations in the Plane.
The Computer Journal, 1978,21(2):168～173
[21] Brassel K E. and Reif D. Procedure to Generate Thiessen Polygons.
Geophysical Analysis, 1979(11):289～303
[22] McCaullagh M T. and Ross C G. Delaunay Triangulation of a Random Data
Set For Iirarithmic Mapping. The Cartographic Journal, 1980(17):93～99
[23] Maus A. Delaunay Triangulation and the Convex Hull of n Points in
Expected Linear Time. BIT, 1984(24):151～163
[24]Voronoi G. Nouvelles Applications des Parameters Continus, a la-
theorie des Formes Quadratiques, Deuxieme Memorie: Recherches sur les
Parrallelloedres Primitifs, Jounal fur die Reine und Angewandte
Mathematik, 1908(134)： 198～287

[25]Thiessen A H. Precipitation Averages for Large Areas, Monthly Weather
Review, 1911(39):1082～1084
[26]Delaunay B. Sur la Sphere Vide. Bulletin of the Academy of Sciences of the USSR, Classe
des Sciences Mathematiques et Naturelles, 1934(8):793～800
[27]姜宇涛，计算几何的不规则三角网算法研究及在GIS中应用，2003
[28]武晓波，王世新，肖春生，Delaunay三角网的生成算法研究法[J ]. 遥感学
报, 2000, 4 (1) : 32- 35
[29]周培德,计算几何——算法分析与设计[M ],北京: 清华大学出版社, 2000
17