（计算机应用技术专业论文）带约束条件的离散点不规则三角网生成.pdf

摘要 规则格网模型、不规则三角网模型和等高线模型是数字高程模型( d e m ) 的三种表示方法。其中不规则三角网( t i n ) 能以不同层次的分辨率来描述地形 表面，被视为d e m 中最基本和最重要的一种模型。因此本文主要研究了带约束 条件的空间离散点的不规则三角网生成算法。 首先，本文对现有的不规则三角网各种生成算法进行对比。在所有可能的三 角网中，d e l a u n a y 三角网是一种相互邻接且互不重叠的三角形集合，其中任一三 角形的外接圆内不包含其他的点。在地形拟合方面表现最为出色，因此本文采用 d e l a u n a y _ 三角网进行建模。 其次，本文结合了分割合并算法和凸壳算法的优点，提出了一种生成 d e l a u n a y - - 角网的合成算法。该算法首先对离散点进行排序然后根据离散点密度 使用四叉树进行分块。对每个叶节点内的数据点集，使用凸壳算法进行三角剖分， 再通过凸壳合并算法将所有叶节点按层次遍历算法进行合并得至t d e l a u n a y - - 角 网。经分析，整个算法的时间复杂度为o ( n l o g n ) 。 最后对空间约束条件的处理采用了嵌入约束边的方法。两步法是目前采用较 多，效率较高的一种约束边嵌入的方法。本文使用边交换迭代算法进行了实现， 达到了较好效果。 关键词d e l a u n a y 三角网，t i n ，四叉树，分割- 合并算法 a b s t r a c t d e mc a nb ee x p r e s s e di nt h r e ek i n d so fm e t h o d sw h i c ha r e 酣d ，t r i a n g u l a t e d i r r e g u l a rn e t t i n g ( t i n ) a n dc o n t o u r b e c a u s et i nc a np r e s e n tt h es u r f a c eo ft e r r a i n b yd i f f e r e n tr e s o l u t i o n s ，i ti st h em o s ti m p o r t a n ta n db a s i cm o d e li ng i s s ot h e a l g o r i t h mo fd e l a u n a yt r i a n g u l t i o nb a s e do ns c a t t e r e dp o i n t si ns o m ec o n s t r i c t e d c o n d i t i o ni ss t u d i e di nt h i sa r t i c l e f i r s to fa l l ，t h ea r t i c l ec o n t r a s t sw i t hr e s e a r c ho na l lk i n d so f a l g o r i t h m so f t r i a n g u l a t e di r r e g u l a rn e t t i n g ( t i n ) a m o n gt h ep o s s i b l et r i a n g u l a rn e t ，t h e d e l a u n a yt r i a n g u l a rn e ti sc o n s i d e da st h eb e s tt r i a n g u l a t i o nt r i a n g u l a rn e ti nt h e t e r r a i nf i t t i n ga s p e c t i ti so n ek i n do fn e x tm u t u a l l ya n dm u t u a l l yn o to v e r l a p t r i a n g l es e t ，i nw h i c ha n yt r i a n g l e sc i r c u m c i r c l ed o e sn o tc o n t a i no t h e rt r i a n g l e s s p o t s ot h ea r t i c l eu s e st i nt om o d e ld e m s e c o n d l y , ac o m p o s i t i o na l g o r i t h mt oc r e a t ed e l a u n a yt r i a n g u l a rn e t w o r ki s r a i s e d ，w h i c hc o m b i n i n ga d v a n t a g eo f t h ed i v i d e - c o n q u e ra l g o r i t h ma n d a d v a n t a g e o fc o n v e xh u l la l g o r i t h m i nt h ea l g o r i t h m ，w em a k et h ed i s c r e t e p o i n t ss o r ti ns c a nm a n n e r , i ne a c hl e a fn o d e sd a t as e to fp o i n t s ，u s e sc o n v e xh u l l a l g o r i t h mt oc r e a t et h et r i a n g u l a t e di r r e g u l a rn e t t i n g ，a n dt h e n ，m e r g e sa l ln o d e r e g i o na c c o r d i n gt ot h eo r d e ro fh i e r a r c h yt r a v e r s a b ya n a l y s i s ，n et i m es c o m p l e x i t yo ft h i sa l g o r i t h mi so ( r d o g n ) f i n a l l y , i n s e r t i n gc o n s t r a i n e de d g ei su s e dt oe x p r e s s e sd e l a u n a yt r i a n g u l a t i o n i nt h ec o n s t r a i n e dd a t af i e l d t w os t e p sa r ew i d e l yu s e da tp r e s e n t ；i t sa o n ek i n do f e f f i c i e n c ym e t h o di ni n s e r t i n gc o n s t r a i n e de d g e k e yw o r d s d e l a u n a yt r i a n g u l a rn e t w o r k ，t i n ，f o u rf o r k st r e e ，d i v i d e c o n q u e ra l g o r i t h m 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：幺必魄趔年互月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：啦嫦师签名眨日期：逊年土月l 日 硕士学位论文 第一章绪论 第一章绪论 不规则三角网( t r i a n g u l a t e di r r e g u l a r n e t w o r k ，t i n ) 由p e u l ( e r 和他的同事于 1 9 7 8 年设计的一个系鲥1 1 ，它由不规则分布的数据点连成的三角网组成，三角面 的形状和大小取决于不规则分布的观测点或称节点的密度和位置【2 1 。不规则三角 网模型是地理信息系统中数字高程模型的最重要的表现形式。 1 1 研究内容与意义 地理信息系统( g i s ) 作为获取、处理、管理和分析地理空间数据的重要工 具、技术和学科，近年来得到了广泛关注和迅猛发展。而在地理信息系统中，数 字高程模型( d e m ) 作为地球空间框架数据的基本内容和其它各种地理信息的 载体，d e m 是各种地学分析的最基础的数据，也是g i s 的基本内容l l j 。 d e m 有多种表现形式，不规则三角网( 简称t i n ) 是其中最重要的一种形 式。t i n 数字高程模型是通过从不规则分布的采样数据点生成的连续三角面来逼 近地形表面。就地形信息的表示角度来看，t i n 模型的优点是它能以不同层次的 分辨率来描述地形表面，即根据地形变化，来进行采样，当采样点集密集时生成 的三角形小而密，稀疏时生成的三角形大而疏。这与实际地形特征恰好一致，因 此由于其能够较好地反映实际地形信息而被广泛使用。特别当地形包含大量特 征，t i n 模型能更好顾及这些特征从而能更精确合理地表达地表形态【3 卅。 从地形表现来说，面对地形海量数据的处理，如何更合理的表示和存储地形 数据，如何得到更高效，更健壮的三角网的算法研究显得尤为重要。并且由于特 殊地形的需要，如何使建立的三角网格更真实的反映特征地形，反映实际地形有 效区域，仍然是人们研究的热点。从计算效率来说，虽然计算机处理数据能力在 不断提高，但是所处理的数据量也越来越大，越来越复杂。优化算法，提高算法 效率一直是许多研究者努力的方向，并出现了很多成熟的算法。提高算法效率的 途径很多，例如把数据分块，建立栅格索引，采用较好的数据结构等等。三角网 生成算法的选择会影响t i n 建模的精度和使用效率此外，从结构上讲，t i n 的 数据结构是矢量数据结构它主要通过节点( 地形采样) 、三角形边和三角形面之间 的关系来显式或隐式地表达地形离散点的拓扑关系，因此设计一个高效的、结构 紧凑的、维护方便的数据存储与组织结构也是至关重要的1 5 l 。 同时，d e m 的好坏个重要标志就是对地形的还原程度，所以如何改进模型 硕士学位论文第一章绪论 表示地形的逼真度与精度是进行t i n 建模的重要内容。d e l a u n a y 三角网可以自 动避免狭长三角形的产生，三角形插值可信度高，成为最为广泛采用的三角剖分算 法【6 】。 实际地形表面有连续变化的，也有断裂的，要使得t i n 能更加逼近地形， 在构建一t i n 时就要充分考虑到地形特征。因此，一般都会考虑到以地形特征 为约束条件，建立带约束条件的限制性d e l a u n a y 三角网。 因此将在三角网生成方面进行以下几个方面的研究： ( 1 ) 找到一种高效基于离散点的d e l a u n a y 三角剖分算法； ( 2 ) 寻找一种高效带约束条件的离散点的d e l a u n a y 三角剖分算法。 1 2 研究现状 由于地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 的普及，在美国、 中国、德国、英国等国家，d e m 作为数字地形模拟的重要成果已经成为国家空 间数据基础设施( n a t i o n a ls p a t i a ld a t ai n f r a s t r u c t u r e ，n s d i ) 的基本内容之一， 并被纳入数字化空间数据框架( d i g i t a ls p a t i md a t af r a m e w o r k ，d s d f ) 进行规 模化生产。目前，d e m 己成为各勘测部门的基本任务和日常工作之一。d e m 作 为地球空间框架数据的基本内容，是各种地理信息的载体，在国家空间数据基础 设施的建设和数字地球战略的实施进程中都具有十分重要的作用【卜】。 g i s 工作者在充分考虑地形特征( 如地性线、陡坎、地物等) 的情况下，发展 了带约束条件的d e l a u n a y 三角网建网理论和算法，该理论兼顾了地形和d e l a u n a y 网特征建模，被证明是对数字地面最佳和唯一的表达，关于该算法的研究正处于 蓬勃的发展中。有的学者还将d e l a u n a y 网理论扩展到三维，用于d t m 建模【1 2 1 。 d e l a u n a y 三角形的两个显著特性最大最小角特性和空外接圆特性是构 成各种d e l a u n a y 三角剖分算法的基础【l3 】十几年来，人们丰富和发展了多种 d e l a u n a y 三角网算法，根据生成三角网之前是否先需要建立其对偶图v o r o n o i 图， 可分为间接d e l a u n a y 三角剖分算法和直接d e l a u n a y 三角剖分算法。间接 d e l a u n a y 算法复杂效率低下而且内存开销大，现在很少使用。因此大部分地方 d e l a u n a y 三角剖分算法即指直接d e l a u n a y 三角剖分算法。直接d e l a u n a y 三角剖 分经典算法，根据其实现过程可分为分割一合并算法、逐点插入算法和三角网生 长法三种类型1 1 3 1 。国内外近年来也出现了一些改进的算法，较之传统算法具有 更高的时间效率，如快速插入算法【1 17 l 和合成算法1 6 1 引，而且还出现了大量的不 2 硕士学位论文第一章绪论 同于经典算法基本思想的d e l a u n a y 三角剖分算法，如贪心算澍1 9 1 、扫描线算法 2 0 l 和凸壳算法【2 1 1 。 在目前的研究中，因为需要满足实际应用中的要求，d e l a u n a y 三角剖分算法 研究中以研究约束d e l a u n a y 三角剖分算法最为广泛。d e l a u n a y 三角剖分算法的 本质是对凸域进行三角剖分，然而实际中的数据域很难为凸域，这就要求三角剖 分一方面满足d e l a u n a y 三角剖分算法，另一方面数据边界为三角形的一边，此 所谓约束d e l a u n a y 三角剖分算法。其中许多算法是将经典d e l a u n a y 三角剖分经 典算法进行扩展使其成为约束d e l a u n a y 三角剖分算、法1 2 2 - 2 4 】，但也产生了一些新 的算法，如分割算法f 2 5 1 、动态算、法【2 6 1 、通用算法【2 7 1 等。 1 3 论文组织 本文共分5 章，具体论文组织如下： 第一章为绪论，主要介绍了本文的研究内容和研究意义，以及国内外的研 究现状，并给出了论文的大体结构。 第二章为研究的背景知识，主要介绍了地理信息系统，数字高程模型的相 关概念与特点。 第三章对不规则三角网生成算法进行介绍，主要内容包括建立不规则三角 网的基本概念，特性和现有生成算法，重点介绍d e l a u n a y 三角网的剖分算法。 首先介绍了d e l a u n a y 角网的概念和性质，以及约束性d e l a u n a y 三角网的概念和 性质；然后介绍了d e l a u n a y 三角网的常见的生成算法，最后介绍了t i n 建模中数 据的组织形式，并阐述了论文中使用的数据组织形式。 第四章详细阐述了空间离散点的不规则三角网建立的算法思想和具体实现 的过程。这种算法结合分而治之法和凸壳算法的优点，使用四叉树保存离散点信 息，对数据域按点密度进行划分，然后使用凸壳算法生成叶结点内点集的三角剖 分。然后用四叉树层次遍历顺序对节点进行合并，形成这个区域的三角剖分。 第五章带约束条件不规则三角网生成算法研究。 第六章对论文所做的工作进行了总结，并说明有待进一步研究的方向。 3 硕士学位论文 第二章地理信息系统建模 2 1 地理信息系统 第二章地理信息系统建模 现实世界中，人们的生产和生活中8 0 以上的信息和地理空间位置有关。随 着信息社会发展，为能更好的处理这些信息，人们综合了地理学、测量学、地图 制图学、摄影测量与遥感学、计算机科学、数学、统计学以及一切与处理和分析 空间数据有关的学科知识，发展出一种能采集、存储、检索、变换、处理和显示 输出从自然界和人类社会获取的各式各样数据、信息的强有力工具理信息系 统。 2 1 1 地理信息系统的概念 地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m 或g e o - - i n f o r m a t i o ns y s t e m ， g i s ) 有时又称为“地学信息系统或“资源与环境信息系统”。它是一种特定 的十分重要的空间信息系统。它是在计算机硬、软件系统支持下，对整个或部分 地球表层( 包括大气层) 空间中的有关地理分布数据进行采集、储存、管理、运 算、分析、显示和描述的技术系统。地理信息系统处理、管理的对象是多种地理 空间实体数据及其关系，包括空间定位数据、图形数据、遥感图像数据、属性数 据等，用于分析和处理在一定地理区域内分布的各种现象和过程，解决复杂的规 划、决策和管理问题1 2 j 。 2 2 2 地理信息系统的组成 完整的g i s 主要由四个部分构成，即计算机硬件系统、计算机软件系统、 地理空间数据和系统管理操作人员，其核心部分是计算机软硬系统，空间数据库 反映了g i s 的地理内容，而管理人员和用户则决定系统的工作方式和信息表示 方式【2 8 - 2 9 1 。地理信息系统的组成可综合表示为图2 1 。 4 硕士学位论文第二章地理信息系统建模 图2 - 1 地理信息系统的组成 其中计算机硬件系统是计算机系统中的实际物理装置的总称，g i s 硬件配置 一般包括四个部分：计算机，输入设备，输出设备，存储设备【3 0 1 。 计算机软件系统包括：指g i s 运行所必需的各种程序，通常包括( 见图2 2 ) ： 1 、计算机系统软件 图2 - 2 计算机歇件系统的层次 5 硕士学位论文第二章地理信息系统建模 2 、地理信息系统软件和其他支撑软件 g i s 软件按功能可分为以下几类： ( 1 ) 数据输入 ( 2 ) 数据存贮与管理 ( 3 ) 数据分析与处理 ( 4 ) 数据输出与表示模块 ( 5 ) 用户接口模块 3 、应用分析程序 地理空间数据是指以地球表面空间位置为参照的自然、社会和人文景观数 据，可以是图形、图像、文字、表格和数字等，由系统的建立者通过数字化仪、 扫描仪、键盘、磁带机或其他通讯系统输入g i s ，是系统程序作用的对象，是 g i s 所表达的现实世界经过模型抽象的实质性内容。不同用途的g i s 其地理空间 数据的种类、精度都是不同的，但基本上都包括三种互相联系的数据类型： ( 1 ) 某个已知坐标系中的位置 ( 2 ) 实体间的空间相关性 即拓扑关系，表示点、线、面实体之间的空间联系，如网络结点与网络线之 间的枢纽关系，边界线与面实体间的构成关系，面实体与岛或内部点的包含关系 等。 ( 3 ) 与几何位置无关的属性 即常说的非几何属性或简称属性( a t t r i b u t e ) ，是与地理实体相联系的地理 变量或地理意义。 2 1 3 地理信息系统的发展 1 9 6 3 年，加拿大测量学家r f t o m l i n s o n 首先提出了地理信息系统这一术语， 并建立了世界上第一个实用的地理信息系统加拿大地理信息系统( c g i s ) ， 用于自然资源的管理和规划1 3 1 。3 2 1 。诞生至今，g i s 发展分为四阶段： l 、地理信息系统的开拓期( 6 0 年代) 当5 0 年代末和6 0 年代初，计算机应用于空间数据的存储和处理，出现了地 6 硕士学位论文 第二章地理信息系统建模 理信息系统的早期雏形。这时地理信息系统的特征是和计算机技术的发展水平联 系在一起的，表现在计算机存储能力小，磁带存取速度慢。机助制图能力较强， 地学分析功能比较简单，实现了手扶跟踪的数字化方法，可以完成地图数据的拓 扑编辑，分幅数据的自动拼接，开创了格网单元的操作方法，发展了许多面向格 网的系统。 2 、地理信息系统的巩固发展期( 7 0 年代) 在7 0 年代，由于计算机技术及其在自然资源和环境环境数据处理中的应用， 促使地理信息系统迅速发展。例如从1 9 7 0 年至1 9 7 6 年，美国地质调查所就建成 5 0 多个信息系统，分别作为处理地理、地质和水资源等领域空闻信息的工具。 其它如加拿大、联邦德国、瑞典和日本等国也先后发展了自己的地理信息系统。 这一时期，利用了新的计算机技术，但系统的数据分析能力仍然很弱；在地理信 息系统技术方面未有新的突破；系统的应用与开发多限于某个机构；专家个人的 影响削弱，而政府影响增强。 3 、地理信息系统技术大发展时期( 8 0 年代) 这个时期大规模和超大规模集成电路问世、计算机网络建立起来，同时系统 软件工具和应用软件工具的研制，使得数据处理开始和数学模型、模拟等决策工 具结合，地理信息系统的应用领域迅速扩大，并与卫星遥感技术相结合，开始用 于解决全球性的问题。 4 、地理信息系统的应用普及时代( 9 0 年代) 由于计算机的软硬件均得到飞速的发展，网络已进入千家万户，地理信息系 统己成为许多机构必备的工作系统，国家级乃至全球性的地理信息系统已成为公 众关注的问题，例如地理信息系统已列入美国政府制定的“信息高速公路 计划， 美国副总统戈尔提出的“数字地球”战略也包括地理信息系统3 3 捌1 。毫无疑问， 地理信息系统将发展成为现代社会最基本的服务系统。 2 , 1 4 地理信息系统的特征 g i s 具有以下三个方面的特征： ( 1 ) 具有采集、管理、分析和输出多种地理信息的能力，具有空间性和动 态性： ( 2 ) 由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规 的或专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成 7 硕士学位论文第二章地理信息系统建模 的任务； ( 3 ) 计算机系统的支持是地理信息系统的重要特征，因而使得地理信息系 统能以快速、精确、综合地对复杂的地理系统进行空间定位和过程动态分析。 上世纪9 0 年代以来，随着地理信息产业的建立和地球数字化产品的普及应 用，g i s 的发展进入用户时代。这个期间，社会对g i s 的认识普遍提高，需求大 幅度增加。g i s 已成为许多机构( 特别是政府决策部门) 必备的工作系统，国家 级乃至全球级的g i s 已成为公众关注的问题。g i s 已被列入“信息高速公路”计划， 也是美国前总统戈尔提出的“数字地球”战略的重要组成部分。近年来g i s 的开发 和研究主题集中在下列一些方向：空间信息分析的新模式和新方法；空间信息的 应用模型；g i s 的效益评价；三维和四维空间数据结构和数据模型；人工智能和 专家系统的引入，网络g i s ；虚拟现实技术与g i s 的结合等。现存的g i s 软件很 多，目前已成功地应用到了包括资源管理、自动制图、设施管理、城市和区域的 规划、人口和商业管理、交通运输、石油和天然气、教育、军事等九大类别的一 百多个领域。在美国及发达国家，g i s 的应用遍及环境保护、资源保护、灾害预 测、投资评价、城市规划建设、政府管理等众多领域。近年来，随我国经济建设 的迅速发展，加速了g i s 应用的进程，在城市规划管理、交通运输、测绘、环 保、农业、制图等领域发挥了重要的作用，取得了良好的经济效益和社会效益。 2 2 数字高程模型 地理信息系统不仅要完成管理大量复杂的地理数据的任务，更为重要的是要 完成地理分析、评价、预测和辅助决策的任务，必须发展广泛的适用于地理信息 系统的地理分析模型，这是地理信息系统走向实用的关键。 所谓模型，就是将系统的各个要素，通过适当的筛选，用一定的表现规则所 描写出来的简明映像【3 5 】。模型通常表达了某个系统的发展过程或发展结果。地 学模型是用来描述地理系统各地学要素之间的相互关系和客观规律信息的语言 的或数学的或其他表达形式，通常反映了地学过程及其发展趋势或结果。 数字地面模型是地理信息系统地理数据库中最为重要的空间信息资料和赖 以进行地形分析的核心数据系统【3 6 】。数字地面模型已经在测绘、资源与环境、 灾害防治、国防等与地形分析有关的科研及国民经济各领域发挥着越来越巨大的 作用。 8 硕士学位论文第二章地理信息系统建模 2 2 1 数字地面模型与数字高程模型的概念 数字地面模型d t m ( d i g i t a lt e r r a i nm o d e l ) 是地形表面形态等多种信息的一 个数字表示 3 7 1 。严格地说，d t m 是定义在某一区域d 上的m 维向量有限序列： k ，i = 1 ，2 ，1 1 ) 其向量形= ( ，形：，口，) 的分量为地形x ，z ，互( ( x ，r ) d ) ，资源、环境、 土地利用、人口分布等多种信息的定量或定性描述。d t m 是一个地理信息数据 库的基本内核【3 8 】。 数字高程模型( d i g i t a le l e v a t i o nm o d e l ，d e m ) 是d t m 最基本的组成部分， 是通过地形高程数据实现对地形曲面的数字化模拟或者说是地形表面形态的数 字化表示。对比d t m 的定义，即d e m 为在某一区域d 上的地形的3 维向量序 列 形2 ( x ，z ，互) i ( x ，) d ，互2 f ( 置，z ) ，i = 1 ，2 ，n 其中( 置，z ) 为数据点k 的平面坐标，互为数据点杉对应的高程值。 由于d t m ( d e m ) 的数字表达形式，运用计算机进行辅助设计、存储、运 算，便于修改、更新和管理，方便转换。有传统地形表示方式无可比拟的优越性， 从2 0 世纪6 0 年代起，数字高程模型成为测绘学科重要的一个分支，主要研 究如何在地形采样数据基础上对地形表面进行重构。主要包括：( 1 ) 地形数据 采样；( 2 ) 地形建模与内插；( 3 ) 数据组织与管理；( 4 ) 地形分析与地学应 用。( 5 ) d e m 可视化；( 6 ) 不定性分析和表达。 对于一个通用的d t m 系统，一般要经过数据采集、d t m 建立和应用模型建 立3 个步骤【5 1 。 2 2 2d e m 的数据源与采集方法 1 、以航空或航天遥感图像为数据源 这种方法是由航空或航天遥感立体像对，用摄影测量的方法建立空间地形立体 模型，量取密集数字高程数据，建立d e m ( 见图2 1 ) 。 9 硕士学位论文第二章地理信息系统建模 豳凰 图2 1 利用航片建立d e m 采集数据的摄影测量仪器包括各种解析的和数字的摄影测量与遥感仪器。 2 、以地形图为数据源 主要以比例尺不大于l ：1 万的国家近期地形图为数据源，从中量取中等密 度地面点集的高程数据，建立d e m 。其方法有下列几种： ( 1 ) 扫描数字化仪采集手工方法，见图2 2 ( a ) ； ( 2 ) 手扶跟踪数字化仪采集采集，见图2 2 ( b ) ； ( 3 ) 手工方法，见图2 - 2 ( e ) ； ( a ) 图2 - 2 以地形图为数据源建立o e i d 3 、以地面实测记录为数据源 用电子速测仪( 全站仪) 和电子手簿或测距经纬仪配合p c i 5 0 0 等袖珍计算机， 在已知点位的测站上，观测到目标点的方向、距离和高差三个要素。计算出目标 点的x 、y 、z 三维坐标，存储于电子手簿或袖珍计算机中，成为建立d e m 的原 始数据。这种方法一般用于建立小范围大比例尺( 比例尺大于l ：5 0 0 0 ) 区域的 d e m ，对高程的精度要求较高。另外气压测高法获取地面稀疏点集的高程数据， 也可用来建立对高程精度要求不高的d e m 。 l o 黼 硕士学位论文 第二章地理信息系统建模 4 、其它数据源 采用近景摄影测量在地面摄取立体像对，构造解析模型，可获得小区域 的d e m 。此时，数据的采集方法与航空摄影测量基本相同。这种方法在山区 峡谷、线路工程和露天矿山中有较大的应用价值。 另外，航空测高仪可获得精度要求不太高的高程数据，也可以依此来构造 d e m 。 2 2 3d e m 的表示方法 1 、数学分块曲面表示法 这种方法把地面分成若干个块，每块用一种数学函数，如傅立叶级数高次多 项式、随机布朗运动函数等，以连续的三维函数高平滑度地表示复杂曲面，并使 函数曲面通过离散采样点。这种近似数学函数表示的d e m 不太适合于制图，但 广泛用于复杂表面模拟的机助设计系统。 2 、规则格网表示法 规则格网表示方法是把d t m 表示成高程矩阵，在m 行n 列规则格网中，设 h i j 为第i 行，第j 列网格对应高程值，d e m 搞成矩阵表示如下。 d e m = ( h 0 ) ( 滓l ，2 ，m - l ，m ；j = l ，2 ，n - l ，n ) 图2 - 3 显示了几种规则格网的d t m 。 ( a ) 按正方形交点布网( b ) 按圆锥网交点帮同 ( c ) 安等边三角形交点布同 图2 - 3 几种规则格网的d e m 此时，d e m 来源于直接规则矩形格网采样点或由规则或不规则离散数据点 内插产生。由于计算机对矩阵的处理比较方便，特别是以栅格为基础的g i s 系 统中高程矩阵已成为d e m 最通用的形式。高程矩阵特别有利于各种应用，但规 则的格网系统也有下列缺点： 硕士学位论文 第二章地理信息系统建模 ( 1 ) 地形简单的地区存在大量冗余数据； ( 2 ) 如不改变格网大小，则无法适用于起伏程度不同的地区； ( 3 ) 对于某些特殊计算如视线计算时，格网的轴线方向被夸大； ( 4 ) 由于栅格过于粗略，不能精确表示地形的关键特征，如山峰、洼坑、山 脊、山谷等。为了压缩栅格d e m 的冗余数据，可采用游程编码或四叉树编码方 法。 3 、 不规则三角网( t i n ) 表示法 不规则三角网( t r i a l l g u l a t e di r r e g u l a rn e t w u i k ，li n ) 是专为产生d e m 数据而 设计的一种采样表示系统。它克服了高程矩阵中冗余数据的问题，而且能更加有 效地用于各类以d t m 为基础的计算。因为t i n 可根据地形的复杂程度来确定采 样点的密度和位置，能充分表示地形特征点和线，从而减少了地形较平坦地区的 数据冗余。t m 表示法利用所有采样点取得的离散数据，按照优化组合的原则， 把这些离散点( 各三角形的顶点) 连接成相互连续的三角面( 在连接时，尽可能地确 保每个三角形都是锐角三角形或是三边的长度近似相等) ，如图2 4 所示。 与g r i d 结构相比，t i n 能以更加灵活的方式在不同层次和空间上表达更复 杂的地形表面，当地形数据中含有特征线如山脊线、山谷线、断裂线等时，t i n 比 g r i d 更能方便地表示之。d t m 的发展早期，由于计算机硬件的限制，主要研究 g r i d 的存储、内插与应用，近几年来，借助于飞速发展的计算机软硬件技术，在耵n 的快速建立、压缩存储、数据组织等方面均取得了突破性的进展1 5 1 。 1 2 硕士学位论文 第三章不规则三角网生成算法对比研究 第三章不规则三角网生成算法对比研究 三角网数字地面模型是用一系列的互不交叉、互不重复的三角形逼近地形表 面建立一个三角网地面模型需要从t i n 的数据组织、三角划分准则、算法 和程序三个方面进行考虑。 3 1t i n 的数据组织 用来描述t 斟的基本元素有三个：节点( n o d e ) 、边( e d g e ) 和面( f a c e ) 。节点是 相邻三角形的公共顶点，是构建t i n 的采样数据。边是两个三角形的公共边界， 它还包含特征线、断裂线和区域边界，t i n 是否光滑由它决定。面是由最近的三 个节点组成的三角形面，是t i n 描述地形表面的基本单元，不能交叉和重叠。 节点、边和面之间存在着关联、邻接等拓扑关系1 4 0 1 。 3 2t i n 的三角化准则 t 附的三角剖分准则是指t i n 中三角形形成的法则，它决定着三角形的几何 形状和形成t i n 的质量。理论与实践均证明，狭长的三角形其插值精度比规则的 三角形插值精度可信度要 ，则递归执行p a r t1 ； ( 4 ) 直到所有结点均满足刀，n q ； ( 5 ) 结束。 这里的算法是递归的，而在数据量过大的时候，用到大量递归调用的程序运行 效率是较低的。为了提高算法效率在具体实现时，使用迭代替换递归。 为了更好的跟踪数据区域的分块，对每个数据区域设立块标志，具体左上块 标志为o o ，右上块标志为0 l ，右下块标志为l o ，左下块标志为l l ，每增加一层 标志位后加两位，图4 3 ( a ) 中区域即可标志为如图4 3 ( b