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

中南大学本科生毕业设计调研报告 软件学院 中 南 大 学本科毕业设计调研报告学生姓名： 专业班级： 软件工程0702 学 号： 院 （系）： 软件学院指导老师： 研究课题： 三角网数据生成算法研究与实现毕业设计日期：2010年12月到2011年6月 摘 要 数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息在所有可能的三角网中，Delaunay三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成本文的主要内容便是研究Delaunay三角网生成算法首先本文介绍了地理信息系统（GIS）的基本概念及相关信息；然后仔细介绍了数字地面模型的相关知识和国外内主要的三种Delaunay三角网生成算法——分治算法、逐点插入法、三角网生长法；最后讲述了研究三角网生成算法的目的及意义，并描述了一种生成Delaunay三角网的合成算法，此算法在主流算法的基础上进行了优化。

关键词：地理信息系统，数字地面模型，不规则三角网，Delaunay三角网 目 录摘要…………………………………………………………………………….……2第一章 绪论………….………………………………………………………..…..41.1 地理信息系统的基本概念及发展现状……….…………………………....41.1.1 地理信息系统的基本概念………………………………………..……41.1.2 地理信息系统的发展动态……………………………...…………..….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）是跨越地球科学、信息科学和空间科学的应用基础学科，它研究关于地理空间信息处理和分析过程中提出一系列基本问题，如空间对象表达与建模、空间关系及推理机制、空间信息的控制基准、空间信息的认知与分析、GIS系统设计与评价GIS应用模型与可视化、空间信息的政策与标准等［1］。

关于它的全称，多数人认为时Geographical Information System，也有少数人认为时Geo－information System国际上现发行的两种杂志，就是各采用不同的全称前者是英国出版的季刊全称，后者是德国出版的季刊全称在加拿大和澳大利亚，则全称为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 地理信息系统的发展动态90年代以来，随着地理信息产业的建立和地球数字化产品的普及应用，GIS的发展进入用户时代这个期间，社会对GIS的认识普遍提高，需求大幅度增加GIS已成为许多机构（特别是政府决策部门）必备的工作系统国家级乃至全球级的地理信息系统已成为公众关注的问题地理信息系统已被列入“信息高速公路”计划，也是美国前总统戈尔提出的“数字地球”战略的重要组成部分90年代以来，GIS的开发和研究主题集中在下列一些方向：空间信息分析的新模式和新方法；空间信息的应用模型；GIS的效益评价；三维和四位空间数据结构和数据模型；人工智能和专家系统的引入，网络GIS；虚拟现实技术与GIS的结合等尽管现存的地理信息系统软件很多，目前已成功地应用到了包括资源管理、自动制图、设施管理、城市和区域的规划、人口和商业管理、交通运输、石油和天然气、教育、军事等九大类别的一百多个领域。

在美国及发达国家，地理信息系统的应用遍及环境保护、资源保护、灾害预测、投资评价、城市规划建设、政府管理等众多领域近年来，随我国经济建设的迅速发展，加速了地理信息系统应用的进程，在城市规划管理、交通运输、测绘、环保、农业、制图等领域发挥了重要的作用，取得了良好的经济效益和社会效益［3］下面举例说明：　　（1）地理信息系统在地理空间数据管理中的应用以多种方式录入的地理数据，以有效的数据组织形式进行数据库管理、更新、维护、进行快速查询检索，以多种方式输出决策所需的地理空间信息如ARC／INFO在公路管理中的应用；ARC／INFO在对市政设施管理中的应用我国大城市数量居全国前列,根据加快中心城市规划建设和加强城市建设决策科学化的要求,利用地理信息系统作为城市规划管理和分析的工具,具有十分重要的意义　　（2）GIS在综合分析评价与模拟预测中的应用GIS不仅可以对地理空间数据进行编码、存储和提取，而且还是现实世界模型，可以将对现实世界各个侧面的思维评价结果作用其上，得到综合分析评价结果；也可以将自然过程、决策和倾向的发展结果以命令、函数和分析模拟程序作用上这些数据上，摸拟这些过程的发生发展，对未来的结果作出定量的和趋势预测，从而预知自然过程的结果，对比不同决策方案的效果以及特殊倾向可能产生的后果，以作出最优决策，避免和预防不良后果的发生。

如GIS在土地信息和土壤保护中的应用后者如美国资源部和威斯康星州合作建立了以治理土壤侵蚀为主要目的的多用途专用的土地GIS　　（3）GIS的空间查询和空间分析功能的应用为了便于管理和开发地理信息(空间信息和属性信息)，在建库时是分层处理的也就是说，根据数据的性质分类，性质相同或相近的归并一起，形成一个数据层这样GIS对单副或多副图件及其属性数据进行分析和指标量算这种应用以原始图为输入，而查询和分析结果则是以原始图经过空间操作后生成的新图件来表示，在空间定位上仍与原始图一致因此，也可将其称为空间函数变换这种空间变换包括叠置分析、缓冲区分析、拓扑空间查询、空集合分析(逻辑交运算、逻辑并运算、逻辑差运算)这方面应用例子有很多，例如在城市规划过程中，对城市中救护车、救火车的分布位置以及行车路线和控制的规划；在环境保护方面，对水土流失导致土地资源的破坏进行评价；在区域环境质量现状评价过程中，对整个区域的环境质量进行客观地、全面地评价，以反映出区域中受污染的程度以及空间分布状态；在地学方面，MAPGIS在油气勘探中和在成矿预测中的应用，解决了肉眼所不能看见的深部构造问题和指明矿产的远景区在大都市防震减灾系统中的应用，1994年的美国洛杉机大地震，就是利用RAC／INFO进行灾后应急响应决策支持，成为大都市利用GIS技术建立防震减灾系统的成功范例。

在野生动植物保护中的应用，世界野生动物基金会(WWF)采用GIS软件ARC/INFO作为“老虎与人类”保护项目的主要技术工具利用ARC/INFO空间分析功能，WWF已找到新的方法来帮助世界最大的猫科动物改变它目前濒于灭种的境地　　（4）GIS的输出功能在地图制图中的应用地理信息系统的发展是从地图制图开始的，因而GIS的主要功能之一用于地图制图，建立地图数据库与传统的、周期长、更新慢的手工制图方式相比，利用GIS建立起地图数据库，可以达到一次投入、多次产出的效果它不仅可以为用户输出全要素地形图，而且可以根据用户需要分层输出各种专题，如行政区划图、土地利用图、道路交通图等等更重要的是由于GIS是一种空间信息系统它所制作的图也能够反映一种空间关系，可以制作多种立体图形，而制作立体图形的数据基础就是数字高程模型在地图的输出中，MAPGIS达到世界先进水平　　（5）运用GIS系统，建立起专题信息系统和区域信息系统专题信息系统如水资源管理信息系统、矿产资源信息系统、草场资源信息系统、水土流失信息系统和目前上海正在建立长途电信局GIS系统等等这类信息系统具有有限目标和专业特点，系统数据项的选择和操作功能是为特定的专门目的服务。

区域信息系统如加拿大国家信息系统、美国Oakridge地区模式信息系统等等这类信息系统主要以区域综合研究和全面的信息服务为目标，可以有不同的规模，其特点是数据项多，功能齐全，通常具有较强的开放性这两种信息系统与上述四种GIS应用或多或少有重叠处，但这里强调的是完整性、系统性、故与它们分开讨论　　（6）地理信息系统与遥感图像处理系统的结合的应用遥感数据是地理信息系统重要信息源其实目前大多数GIS系统已揉进图像处理功能，并把它作为其一个子模块这种应用如海湾战争期间，美国国防制图局GIS实时服务，为战争需要在工作站上建立了GIS与遥感的集成系统，它能用自动影像匹配和自动目标识别技术处理，处理卫星和高低侦察机实时获得战场数字影像，及时地将反映战场现状的正射影影像叠加到数字地图上，数据直接传送到海湾前线指挥部和五角大楼，为军事决策提供24小时的实时服务　　（7）应用GIS一些二次开发函数库开。