毕业论文三角网数据生成算法研究与实现.doc

《毕业论文三角网数据生成算法研究与实现.doc》由会员分享，可在线阅读，更多相关《毕业论文三角网数据生成算法研究与实现.doc（17页珍藏版）》请在三一办公上搜索。

1、中 南 大 学本科毕业设计调研报告学生姓名： 专业班级： 软件工程0702 学 号： 院 （系）： 软件学院指导老师： 研究课题： 三角网数据生成算法研究与实现毕业设计日期：2010年12月到2011年6月 摘 要 数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，Delaunay三角网在地形拟合方面表现最为出色，因此

2、常常用于TIN的生成。本文的主要内容便是研究Delaunay三角网生成算法。首先本文介绍了地理信息系统（GIS）的基本概念及相关信息；然后仔细介绍了数字地面模型的相关知识和国外内主要的三种Delaunay三角网生成算法分治算法、逐点插入法、三角网生长法；最后讲述了研究三角网生成算法的目的及意义，并描述了一种生成Delaunay三角网的合成算法，此算法在主流算法的基础上进行了优化。关键词：地理信息系统，数字地面模型，不规则三角网，Delaunay三角网 目 录摘要.2第一章 绪论.41.1 地理信息系统的基本概念及发展现状.41.1.1 地理信息系统的基本概念.41.1.2 地理信息系统的发展动

3、态.51.2 数字高程模型.6第二章 三角网数据生成方法.92.1 三角网数字模型.92.1.1 三角网数字模型的基本理论.92.1.2 三角网数字模型的研究现状.92.1.3 三角网数字模型的研究发展方向.102.2 Delaunay三角网.112.2.1 基本定义及相关概念.112.2.2 D-三角网生成算法回顾.12第三章 三角网数据生成算法的研究思路与方法.14 3.1 研究内容及其目的与意义.14 3.2 研究思路.14参考文献.15第一章 绪论 1.1 地理信息系统的基本概念及发展现状1.1.1 地理信息系统 地理信息系统（简称GIS）是跨越地球科学、信息科学和空间科学的应用基础学

4、科，它研究关于地理空间信息处理和分析过程中提出一系列基本问题，如空间对象表达与建模、空间关系及推理机制、空间信息的控制基准、空间信息的认知与分析、GIS系统设计与评价GIS应用模型与可视化、空间信息的政策与标准等1。关于它的全称，多数人认为时Geographical Information System，也有少数人认为时Geoinformation System。国际上现发行的两种杂志，就是各采用不同的全称。前者是英国出版的季刊全称，后者是德国出版的季刊全称。在加拿大和澳大利亚，则全称为Land Information System。在我国，通常称为Resourse and Enviromen

5、t Information。全称虽然有差异，但都简称为GIS。由于GIS是计算机科学、地理学、测量学、地图学等多门学科综合的技术。要给出GIS的准确定义是困难的，站在不同的角度，给出的定义就不同。通常可以从4种不同的途径来定义GIS：(1) 面向功能的定义，GIS是采集、存储、检查、操作、分析和显示地理数据的系统；(2) 面向应用的定义，这种方式根据GIS应用领域的不同，将GIS分为各类应用系统，例如土地信息系统、城市信息系统、规划信息系统、空间决策支持系统等；(3) 工具箱定义方式，GIS是一组用来采集、存储、查询、变换和显示空间数据的工具的集合，这种定义强调GIS提供的用于处理地理数据的工

6、具；(4) 基于数据库的定义，GIS是这样一类数据库系统，它的数据有空间次序，并且提供一个对数据进行操作的操作集合，用来回答对数据库中空间实体的查询2。 地理信息系统是一门多学科综合的边缘学科，但其核心是计算机科学，基本技术是数据库、地图可视化及空间分析(见图1一1)；GIS是处理地理据的输入、输出、管理、查询、分和辅助策的系统。 图1-1地理信息系统的组成1.1.2 地理信息系统的发展动态90年代以来，随着地理信息产业的建立和地球数字化产品的普及应用，GIS的发展进入用户时代。这个期间，社会对GIS的认识普遍提高，需求大幅度增加。GIS已成为许多机构（特别是政府决策部门）必备的工作系统。国家

7、级乃至全球级的地理信息系统已成为公众关注的问题。地理信息系统已被列入“信息高速公路”计划，也是美国前总统戈尔提出的“数字地球”战略的重要组成部分。90年代以来，GIS的开发和研究主题集中在下列一些方向：空间信息分析的新模式和新方法；空间信息的应用模型；GIS的效益评价；三维和四位空间数据结构和数据模型；人工智能和专家系统的引入，网络GIS；虚拟现实技术与GIS的结合等。尽管现存的地理信息系统软件很多，目前已成功地应用到了包括资源管理、自动制图、设施管理、城市和区域的规划、人口和商业管理、交通运输、石油和天然气、教育、军事等九大类别的一百多个领域。在美国及发达国家，地理信息系统的应用遍及环境保护

8、、资源保护、灾害预测、投资评价、城市规划建设、政府管理等众多领域。近年来，随我国经济建设的迅速发展，加速了地理信息系统应用的进程，在城市规划管理、交通运输、测绘、环保、农业、制图等领域发挥了重要的作用，取得了良好的经济效益和社会效益3。下面举例说明：（1）地理信息系统在地理空间数据管理中的应用以多种方式录入的地理数据，以有效的数据组织形式进行数据库管理、更新、维护、进行快速查询检索，以多种方式输出决策所需的地理空间信息。如ARCINFO在公路管理中的应用；ARCINFO在对市政设施管理中的应用。我国大城市数量居全国前列,根据加快中心城市规划建设和加强城市建设决策科学化的要求,利用地理信息系统作

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

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

11、制的规划；在环境保护方面，对水土流失导致土地资源的破坏进行评价；在区域环境质量现状评价过程中，对整个区域的环境质量进行客观地、全面地评价，以反映出区域中受污染的程度以及空间分布状态；在地学方面，MAPGIS在油气勘探中和在成矿预测中的应用，解决了肉眼所不能看见的深部构造问题和指明矿产的远景区。在大都市防震减灾系统中的应用，1994年的美国洛杉机大地震，就是利用RACINFO进行灾后应急响应决策支持，成为大都市利用GIS技术建立防震减灾系统的成功范例。在野生动植物保护中的应用，世界野生动物基金会(WWF)采用GIS软件ARC/INFO作为“老虎与人类”保护项目的主要技术工具。利用ARC/INFO

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

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

14、信息系统与遥感图像处理系统的结合的应用遥感数据是地理信息系统重要信息源。其实目前大多数GIS系统已揉进图像处理功能，并把它作为其一个子模块。这种应用如海湾战争期间，美国国防制图局GIS实时服务，为战争需要在工作站上建立了GIS与遥感的集成系统，它能用自动影像匹配和自动目标识别技术处理，处理卫星和高低侦察机实时获得战场数字影像，及时地将反映战场现状的正射影影像叠加到数字地图上，数据直接传送到海湾前线指挥部和五角大楼，为军事决策提供24小时的实时服务。（7）应用GIS一些二次开发函数库开发出具有特定功能软件系统如国家九五攻关项目“紧缺金属资源快速勘察评价系统”，这个系统中，分为地质变量信息提取模块

15、、数据挖掘模块、物探数据处理模块、图像处理模块、综合预测模块等，其中地质变量信息提取模块使用了MAPGIS中基本输入函数、空间功能分析函数，目前这个系统已初具皱形。（8）GIS中属性数据的综合及融合在现有的GIS中，属性数据只是用于检索和查询，或进行简单的统计，难以深入的分析，难以发掘隐含在其中的模式和规律。在众多项的属性数据中，有时将几个属性项的属性数值加以综合，构成一个具有某领域特定意义的新属性项新属性值，这种综合不是综合前属性数据值的简单反映，也不是它们的孤立集合，而是经过某领域研究人员深思熟虑的综合分析，用数量表示某领域问题的综合概念和结果特征。国家科委九五攻关项目“紧缺矿产资源开发评

16、价系统”中有体现。1.2 数字高程模型数字地形模拟是针对地球表面实际地形地貌的一种数字建模过程，这种建模的结果通常就是数字地形模型，后来人们把基于高程或海拔分布的数字高程模型称为 DEM(Digital Elevation Model，DEM)。数字高程模型（DEM）自20世纪50年代后期被采用以来，受到了极大的关注。随着科学技术特别是计算技术的迅速发展，DEM的诸多基础理论问题得到了深入的研究，基于DEM数字地形分析的理论与技术方法体系在进一步完备4,5。DEM作为地形表面的一种数字表达形式具有如下特点: (l)容易以多种形式显示地形信息。地形数据经过计算机软件处理后，产生多种比例尺的地形图

17、、纵横断面图和立体图;(2)精度不会损失。常规地图随着时间推移，图纸将会变形，失掉原有的精度，DEM采用数字媒介，因而能保持精度不变;(3)容易实现自动化和实时化。DEM由于是数字形式的，所以增加或改变地形信息只需将修改信息直接输入到计算机;(4)具有多比例尺特性。如lm分辨率的DEM自动涵盖了更小分辨率如 10m和100m的DEM内容。数字高程模型数据的来源主要有三种方式6：(1)数字摄影测量；(2)野外数字测图；(3)地形图扫描矢量化。数字摄影测量的基本思想是将模拟的影像变成可以被计算机处理的数字影像，然后使用计算机实现摄影测量。数字摄影测量具有效率高、劳动强度低、精度高等优点，已经成为数

18、字高程模型数据的重要来源。数字高程模型数据是由一些离散点组成，要对离散点进行数字高程建模。一个地区的地表高程变化可以采用多种方法表达，用数学定义的表面或点、线都可以用来表示数字高程模型。用数学方法来表达，可以采用整体拟合方法，即根据区域所有的高程点数据，用傅立叶级数和高次多项式拟合统一的地面高程曲面。也可用局部拟合方法，将地表复杂表面分成正方形规则区域或面积大致相等的不规则区域，根据有限个点进行拟合形成高程曲面。在地理信息系统中，DEM最主要的三种表示模型是规则格网模型、不规则三角网模型和等高线模型，三种模型都有各自的优点，而且相互之间可以基于一种模型生成另一种模型。下面将简略介绍一下这三种模

19、型：(1)规则格网模型规则格网通常是由矩形组成，它将区域空间切分为规则的格网单元。规则格网在数学上可以表示为一个矩阵，在计算机实现中则是一个二维数组，每个格网单元的顶点都对应一个高程值。规则格网的高程矩阵，可以很容易地用计算机进行处理，而且它还可以很容易地计算等高线、坡度坡向、山坡阴影和自动提取流域地形，使得它成为DEM最广泛使用的格式，目前许多国家提供的DEM数据都是以规则格网的数据矩阵形式提供的。格网DEM的缺点是不能准确表示地形的结构和细部，为避免这些问题，可采用附加地形特征数据，如地形特征点、山脊线、谷底线、断裂线，以描述地形结构。格网DEM的另一个缺点是数据量过大，给数据管理带来了不

20、方便，通常要进行压缩存储。DEM数据的无损压缩可以采用普通的栅格数据压缩方式，如游程编码、块码等，但是由于DEM数据反映了地形的连续起伏变化，普通压缩方式难以达到很好的效果;因此对于格网DEM数据，可以采用哈夫曼编码进行无损压缩;有时，在牺牲细节信息的前提下，可以对格网DEM进行有损压缩，通常的有损压缩大都是基于离散余弦变换或小波变换，由于小波变换具有较好的保持细节的特性，近年来将小波变换应用于DEM数据处理的研究较多。(2)不规则三角网模型不规则三角网 (Triangulated Irregular Network,TIN)是一种表示数字高程模型的方法，它既减少规则格网方法带来的数据冗余，同

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

22、一个记录，三角形的记录包括三个指向它三个边的记录的指针，边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针，也可以直接对每个三角形记录其顶点和相邻三角形。每个节点包括三个坐标值的字段，分别存储X.Y，Z坐标。这种拓扑网络结构的特点是对于给定一个三角形查询三个顶点高程和相邻三角形所用的时间是定长的，在沿直线计算地形剖面线时具有较高的效率。当然可以在此结构的基础上增加其它变化，以提高某些特殊运算的效率，例如在顶点的记录里增加指向其关联的边的指针。不规则三角网数字高程由连续的三角面组成，三角面的形状和大小取决于不规则分布节点的位置和密度。不规则三角网可以随地形起伏的变

23、化而改变采样点的密度和决定采样点的位置，因而它能够避免地形平坦时的数据冗余，又能按地形特征点表示数字高程特征。(3) 等高线模型等高线模型表示高程, 高程值的集合是己知的，每一条等高线对应一个已知的高程值，这样一系列等高线集合和它们的高程值就一起构成了一种数字高程模型。等高线通常被存成一个有序的坐标点对序列，可以认为是一条带有高程值属性的简单多边形或多边形弧段。由于等高线模型只表达了区域的部分高程值，往往需要一种插值方法来计算落在等高线外的其它点的高程，又因为这些点是落在两条等高线包围的区域内，所以，通常只使用外包的两条等高线的高程进行插值。等高线通常可以用二维的链表来存储。还可以用树结构来表

24、示等高线的拓扑关系，将等高线之间的区域表示成树的节点，用边表示等高线本身。此方法满足等高线闭合或与边界闭合、等高线互不相交两条拓扑约束。 第二章 三角网数字模型2.1 三角网数字模型2.1.1 三角网数字模型基本理论三角网数字模型(Triangulated Irregular Network，简写为TIN)是用一系列的互不交又、互不重复的三角形逼近地形表面，与Grid相比，TIN在拟合地表上更灵活、更精确。但由于结构的不同，Grid许多成熟的技术并不能完全移植到TIN中。从结构上讲，TIN是一典型的矢量数据结构。它主要通过节点(地表采样点)、三角形边和三角形面之间的关系来显式或隐式的表达底细功

25、能散点的拓扑关系，因此设计一个高效的、结构紧凑的、维护方便的TIN的存储与组织结构对TIN的应用与维护是至关重要的。TIN的基本单元三角形的几何形状直接决定着TIN的应用质量。由于地形的自相关性，相互越接近的地形采样点，其之间的关联程度越大;同时，理论与实践均证明，狭长的三角形其插值精度比规则的三角形插值精度可信度要低。因此，在TIN中对三角形的几何形状有着严格的要求。一般有三条原则:l)尽量接近正三角形;2)保证最近的点成三角形;3)三角形网络唯一。2.1.2 三角网数字模型的研究现状按地形数据采样的分布情况，对TIN的三角化可分为三大类，不规则分布数据三角剖分、规则分布数据三角剖分、基于等

26、高线采样数据三角剖分。其中不规则分布数据三角剖分的算法最多，主要有Delaunay三角化算法为代表的基于数学形态学的三角化算法。Delaunay三角化算法的本质是对凸域进行三角剖分，然而实际中的数据域很难为凸域，这就要求三角剖分一方面满足Delaunay Trangulation算法，另一方面数据边界为三角形的一边，此所谓约束Delaunay Trangulation三角网算法。Delaunay Trangulation的两个显著特性一最大最小角特性和空外接圆特性是构成各种Delaunay Trangulation算法的基础。Delaunay Trangulation算法可分为间接Delaun

27、ay三角网算法和直接Delaunay三角网算法。间接Delaunay算法复杂、内存开销大切效率低下，现今很少使用。直接Delaunay三角网生成算法包括分割-归并法、逐点插入法、三角网生长算法。所有的Delaunay Trangulation算法都是对矢量结构的三角剖分。实际上也可对栅格影象数据进行三角剖分，这就是基于数学形态的学的三角剖分。在目前所有的三角化算法中，以Delaunay Trangulation的应用最为广泛，这是由于Detlaunay Trangulation能自动的避免狭长三角形单元。2.1.3 三角网数字模型的研究发展方向 三角网数字模型的研究发展方向主要有：（1）三维空

28、间数据域的三角剖分目前的TIN模型，是一种面向曲面(三角形面元)的表面重构技术。在本质上，这种方法产生的数字模型是2.5维。虽然Delannay三角网在二维数据域上，最为成功，但其理论与方法不能直接推广到三维情形。目前对三维数据域的三角剖分是一研究热点，主要集中在三角剖分原则、数据结构和算法设计上。（2）地表的动态仿真与可视化技术基于三角网数字模型的三维动态仿真与可视化有助于用户对地表的直观理解。（3）TIN的元数据结构对于TIN，由于结构灵活，使用方式多样，建立费用较高，故需建立统一标准，实现数据共享。2.2 Delaunay三角网2.2.1 基本定义及相关概念 Delaunay三角网是V-

29、图（也称为Thiessen图，Dirichlet图，Vigner-Seithz图）的伴生图形。对它的研究是从对V-图的研究开始的。V-图定义是：假设V=v1,v2,.,vN , N3是欧几里德平面上的一个点集，并且这些点不共线，四点不共圆，用d(vi , vj)表示点vi , vj间的欧几里德距离，设x为平面上的点，则区域V(i)=xE2|d(x,vi)d(x,vj), j=1,2,.,N, jI称为Voronoi多边形（V-多边形）。各点的V-多边形共同组成V-图。平面上的V-图可以看作是点集V中的每个点作为生长核，以相同的速率向外扩张，直到彼此相遇为止而在平面上形成的图形。除最外层的点形成

30、开放的区域外，其余每个点都形成一个凸多边形。D-三角网的定义是：有公共边的V-多边形称为相邻的V-多边形。连接所有相邻的V-多边形的生长中心所形成的三角网称为D-三角网。D-三角网的外边界是一个凸多边形，它由连接V中的凸集形成，通常称为凸壳。D-三角网具有两个非常重要的性质：1）空外接圆性质：在由点集V所形成的D-三角网中，其每个三角形的外接圆均不包含点集V中的其他任意点；2）最大的最小角度性质：在由点集V所能形成的三角网中，D-三角网中三角形的最小角度是最大的。由于这两个性质，决定了D-三角网具有极大的应用价值。同时，它也是二维平面三角网中唯一的、最好的。Miles证明D-三角网是“最好的三

31、角网” 7；Sibson认定“在一个有限点集中，只存在一个局部等角的三角网，这就是D-三角网” 8；Lingas进一步论证了“在一般情况下，D-三角网是最优的” 9；Tsai认为，“在不多于3个相邻点共圆的欧几里德平面中，D-三角网是唯一的” 10。2.2.2 D-三角网生成算法回顾Tsai根据实现过程，把生成D-三角网的各种算法分为三类：分治算法、逐点插入法、三角网生长法9。（1）分治算法1975年，Shamos和Hoey提出了分治算法思想11，并给出了一个生成V-图的分治算法。Lewis和Robinson将分治算法思想应用于生成D-三角网12。他们给出了一个“问题简化”算法，递归地分割点集

32、，直至子集中只包含三个点而形成三角形，然后自下而上地逐级合并生成最终的三角网。以后Lee和Schachter又改进和完善了Lewis和Robinson的算法13。Lee和Schachter算法的基本步骤是：将点集V以横坐标为主，纵坐标为辅按升序排序，然后递归地执行以下步骤；把点集V分为近似相等的两个子集VL和VR；在VL和VR中生成三角网；用Lawson提出的局部优化算法优化所生成的三角网，使之成为D-三角网；找出连接VL和VR中两个凸壳的底线和顶线；由底线至顶线合并VL和VR中两个三角网。 以上步骤显示，分治算法的基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三

33、角网合并生成最终的三角网，用LOP算法保证其成为D-三角网。不同的实现方法可有不同的点集划分法、子三角网生成法及合并法。（2） 逐点插入法 1978年，Lawson提出了用逐点插入法建立D-三角网的算法思想12。Lee和Schachter，Bowyer，Watson，Sloan，Macedonio和Pareschi，Floriani和Puppo，Tsai先后进行了发展和完善10,12-19。逐点插入算法的基本步骤是：定义一个包含所有数据点的初始多边形；在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点都被处理；插入一个数据点P，在三角网中找出包含P的三角形t，把P与t的三个顶点相连

34、，生成三个新的三角形；用LOP算法优化三角网。从上述步骤可以看出，逐点插入算法的思路非常简单，先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为D-三角网。各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法不同。（3） 三角网生成法 1978年，Green和Sibson首次实现了一个生成Dirichlet多边形图的生长算法20。Brassel和Reif稍后也发表了类似的算法21。McCullagh和Ross通过把点集分块和排序改进了点搜索方法，减少了搜索时间22。Maus也给出了一个非常相似的算法23。三角网生长算法的基本步骤是：以任一

35、点为起始点；找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线，按D-三角网的判别法则（即它的两个基本性质），找出与基线构成D-三角形的第三点；基线的两个端点与第三点相连，成为新的基线；迭代以上两步直至所有基线都被处理。上述过程表明，三角网生长算法的思路是，先找出点集中相距最短的两点连接成为一条Delaunay边，然后按D-三角网的判别法则找出包含此边的D-三角形的另一端点，依次处理所有新生成的边，直至最终完成。各种不同的实现方法多在搜寻“第三点”上做文章。第三章 三角网数据生成算法的研究思路与方法3.1 研究内容及其目的及意义近年来，随着科技的发展，地理信息系统在军事、自然资源管

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

37、三角网不仅在描述地表形态上有很大的优势，而且在图像处理、模式识别领域也将有很大的优势。Delaunay三角网生成算法经过多年的发展已经相当成熟，它在生活、军事、工业等领域都得到了广泛地应用，如：在印鉴方面的应用，易于识别；军事上构建地面数字模型，易于部队指挥员对地貌的识别和对地形的分析；工业上适用于应用层组播叠加网的构建；在现在的数字城市建设以及线路CAD软件开发中的应用等。由此可见，Delaunay三角网生成算法具有非常重要的意义。本课题便是基于Delaunay三角网进行不规则三角网数据生成算法的研究，主要内容便是研究Delaunay三角网生成的算法。 3.2 研究思路在三类主流Delaun

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

39、思路便是基于此种合成算法，其Delaunay三角网生成算法主要步骤如下：（1）数据预处理，即将初始点集按升序以x 坐标为主, y 坐标为辅进行排列, 确保子三角网不相互叠置；（2）计算凸壳,即使用格雷厄姆算法29求出点集凸壳；（3）初始三角网的建立，即以凸壳上y 值最小的点为出发点,按序与凸壳上其余的点相连，构成初始三角网；（4）插点入网，首先定位待插入点, 即确定点在哪个三角形中，然后根据点在三角形的位置, 修改三角网；（5）局部优化过程，即一旦三角网被修改, 必须进行LOP优化；（6）查找上下切线，即块找出连接相邻两个子三角网的凸壳的上切线和下切线；（7）子网合并，即以两凸壳的下切线为起始

40、基线, 分别沿一个凸壳的逆时针方向、 沿另一个凸壳的顺时针方向找出与基线构成Delaunay三角形的第三个顶点，LOP优化新生成的三角形, 将新生成的边作为新的基线继续上述过程, 当基线成为两个凸壳的上切线时终止。 参考文献1黄杏源，地理信息系统概论，20022吴信才，地理信息系统的基本技术与发展动态J，地理科学，1998,23(4)3CHEN Shupeng, ZHONG Ershun. Perspectives on GIS Development in China .and Annual GIS Infrastructure Planning and Management Confere

41、nce, Beijing, China 26-28 May, 1998.4 李志林，朱庆数字高程模型武汉：武汉大学出版社，2003 5 吴立新，史文中地理信息系统原理与算法北京：科学出版社，20036 Shaoming WangA smooth surface interpolation to 3D triangulationsJournal ofComputational and Applied Mathematics，2004，163：2872937 Miles R E. Solution to Problem 67-15(Probability Distribution of a Net

42、work of Triangles). SIAM, 1969(11)：3994028Sibson R. Locally Equiangular Triangulations. Computer Journal, 1978,21(3)：2432459 Lingas A. The Greedy and Delaunay Triangulations are not Bad in the Average Case. Information Processing Letters, 1986(22)： 253110 Tsai V J D. Delaunay Triangulations in TIN C

43、reation: an Overview and a Linear-time Algorithm. Int. J. of GIS, 1993,7(6):50152411 Shamos M I. and Hoey D. Closest-point Problems, In: Proceedings of the 16th Annual Symposium on the Foundations of Computer Science, 1975.15116212 Lewis B A. and Robinson J S. Triangulation of Planar Regions with Ap

44、plications, The Computer Journal, 1978,21(4)：32433213 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： Ac

45、ademic Press, 197715 Bowyer A. Computing Dirichlet Tesselations, Computer Journal, 1981(24)：16216616 Watson D F. Computing the n-dimension Delaunay Tesselation with Application to Voronoi Polytopes. Computer Journal, 1981(24):16717217 Sloan S W. A fast Algorithm for Constructing Delaunay Triangulations in the Plane. Andvanced Engineering Software, 1987(9):345518 Macedonia G and Pareschi M T. An Algorithm for the Triangulat