（地图制图学与地理信息工程专业论文）三维道路表面建模的tin算法.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 道路三维建模是实现道路三维可视化设计的前提和基础，也是道路三维可 视化研究的重要内容之一。对道路三维模型的建模研究，关键在于快速准确地 建模方法以及保证模型整体拓扑结构的统一，这也是本文研究的重点内容。本 文的主要工作和成果如下： 1 依据d e l a u n a y 三角剖分的理论和特性，一次性快速构建地形三维模型， 无需l o p ( l o c a lo p t i m i z a t i 如p r o c e d u r e ) 优化。 2 模型的拼合算法是道路整体三维模型实现的关键，也是保持整体模型内 部拓扑关系统一的保证。通过对国内外c d t 算法的研究，提出了基于 珐( x ，e ) 函数的约束d e l a u n a y 三角剖分算法，并从理论上对该算法与角度最 大法则和距离最近法则进行了比较，证明了该算法的优越性。 3 基于分割归并的思想，把道路整体三维模型分割为地形三维模型和三维 道路表面模型，进而将三维道路表面模型分割为设计线( 线路) 模型、构造物 模型( 桥、隧等) 和附属设施模型( 里程碑、路灯等) ，对各子模型分别建 模，提取各子模型边界依据约束d e l a u n a y 三角剖分( c o n s t r a i n e dd e l a u n a y t r i a n g u l a t i o n ，c d t ) 算法拼合为道路整体三维模型。在建模过程中，对于一些 关键问题进行了阐述并加以解决，比如逐点插入算法构建地形三维模型中点在 三角形中的判断方法，道路表面模型拼合交线的快速提取，删除拼合交线内地 形三角网等： 4 应用v c + + 6 0 设计了道路三维模型的实验系统，实验表明：基于 q 。( x 。，) 函数的约束d e l a u n a y 三角剖分算法，实现了三维道路表面模型和地 形三维模型的快速无缝拼合。 关键词：d e l 跚n a y 三角剖分；约束d e l a u n a y 三角剖分；分割一归并；q 函数； 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t t h e3 dr o a dm o d e l i n gw a st h ep r e m i s ea n df o u n d a t i o nf o rr e a l i z i n gt h ed e s i g n o f3 dr o a dv i s u a l i z a t i o n ，a l s ow a st h ei m p o r t a n tc o n t e n to fr e s e a r c hf o rt h ed e s i g no f 3 dr o a dv i s u a l i z a t i o n f a s ta n de x a c tm o d e l i n ga n dk e e p i n gt h eu n i t i v et o p o l o g i c a l s t r u c t u r ew e r et h ek e yt or e a l i z et h e3 dr o a dm o d e l i n g w h i c hm e t h o dw a ss e l e c t e d f o rm o d e l i n ga n dh o wt ok e 印t h eu n i f o r mt o p o l o g ys t r u c t u r e , w e r et h ec h i e f r e s e a r c hc o n t e n t si nt h i st h e s i s t h em a i nw o r ka n da c h i e v e m e n t sc a l lb es u m m a r i z e d a sf o l l o w s ： 1 )a c c o r d i n gt ot h et h e o r ya n dc h a r a c t e ro fd e l a u n a yt r i a n g u l a t i o n ，d i g i t s l e l e v a t i o nm o d e l ( d e m ) c a nb ee s t a b l i s h e df a s t , a n dt o p ( l o c a lo p t i m i z a t i o n p r o c e d u r e ) w a s n o tn e e d e d 2 1t h ep i e c ea l g o r i t h mw a st h ek e yf o rr e a l i z i n g3 dw h o l er o a dm o d e l ，a l s ow a s t h eg u a r a n t e ef o rk e e p i n gt h eu n i f o r mt o p o l o g i c a lr e l a t i o n s h i po ft h e3 dw h o l er o a d m o d e l t h ec o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o nb a s e do nf u n c t i o nq i ( x i ，y i ) w a s p r o p o s e db ys t u d y i n gi n t e r i o ra n do v e g s e a sc d ta l g o r i t h m ，a n dt h ea d v a n t a g eo f t h e a l g o r i t h mw a st e s t i f i e db yc o m p a r e dw i t hm a x - a n g i ep r i n c i p l ea n dm i n d i s t a n c e p r i n c i p l e 3 ) b a s e do nt h ei d e ao fd i v i s i o na n dc o n q u e r ，t h e3 dr o a dm o d e lw a sd i v i d e d i i l t o3 dt e r r a i nm o d e la n d3 dr o a ds u r f a c em o d e l t h e3 dr o a ds u r f a c em o d e lc a nb e d i v i d e di n t or o a dl i n em o d e l ，f a b r i c a t i o nm o d e l ( s u c ha sb d d g e ，t u n n e le t c ) a n d a t t a c h e df a c i l i t ym o d e l ( s u c ha sm i l e s t o n e ，s t r e e t l a m pe t c ) w eb u i l tm o d e l sf o re a c h s u b - m o d e l ，a n dd r e wt h eb o u n d a r yo fe a c hs u b - m o d e l ，f i n a l l y , w ep i e c et h ev a r i o u s m o d e l st o g e t h e rf o r3 dr o a dm o d e lb yc o n s t r a i n e dd d a u n a yt r i a n g u l a t i o n ( c d t ) i n t h ec o u l l 3 co fm o d e l i n g s o m ei m p o r t a n ta l g o r i t h m sw e r ee x p o s e da n ds o l v e d , s u c ha s j u d g e m c n to fp o i n td a t ai nt r i a n g u l a t i o n ，d r a w i n gt h eb o u n d a r y o fm o d e la n dd e l e t i n g t h et r i a n g l en e ti nb o u n d a r yp o l y g o na n ds oo n 舢t h ee x p e r i m e n t a ls y s t e mo f3 dr o a dm o d e lh a sb e e nd e v e l o p e db a s e do n v c + + 6 0 e x p e r i m e n t a lr e s u l th a ss h o w nt h a tu s i n gc d ta l g o r i t h mb a s e do nt h e f u n c t i o nq i ( x i ，y i ) ，3 dw h o l er o a dm o d e lc a nb eb u i l ts e a m l e s s l yb yu s i n ga l g o r i t h m s i nt h i st l l e s i s d e l a u n a yt r i a n g u l a t i o n ，c o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n ， d i v i s i o na n dc o n q u e r , f u n c t i o nq i 西南交通大学硕士研究生学位论文第v 页 图2 1 图2 2 图2 3 图2 - 4 图2 5 图2 6 图2 7 图2 8 图3 - 1 图3 2 图3 3 图3 - 4 图3 5 图3 - 6 图4 1 图4 2 图4 _ 3 图 图4 5 图4 6 图4 7 图4 - 8 图4 - 9 图5 1 图5 - 2 图5 3 图5 4 图5 5 图索引 空外接圆特性 “最大最小角”特性 逐点插入算法过程图 建立初始三角形。 逐点插入过程1 6 空外接圆特性测试 逐点插入算法构建d c l a u n a y 三角网。1 7 点与有向线段的位置关系判断 求鼹射线q i 长度2 3 定位和只相交的首三角形。 约束边只p i 的影响域 计算线段- , 4 ，f i b 的口值2 4 确定影响域三角形2 6 角度计算2 7 基于分割归并思想的道路三维表面模型的建立3 2 相邻横断面之间线路的三角剖分3 5 设计线三角网模型3 5 隧道模型图3 6 横断面设计线与t i n 求交3 8 构造拼合交线多边形的最小外接矩形3 9 点与多边形的位置判断4 0 拼合交线内地形点的删除4 l 道路整体三维模型4 1 实验系统工作流程图4 3 生成d e m ，4 4 道路设计线建模4 5 拼合交线内地形三角网的清除4 6 道路整俸三维模型的建立4 6 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 研究背景 在第四届海峡两岸g i s 发展研讨会暨中国g i s 协会第十届年 会上，“多维地理数据集成管理与可视化表达”为主要研讨内容之 一，可视化技术已成为目前国际上谈论的热门话题，也是国内外很 多相关学者研究的主要内容。而建模是可视化技术中非常重要的一 部分，是可视化技术实现的基础。建模是一个从现实世界到计算机 世界映射的过程，道路整体三维模型就是在计算机世界中对现实道 路进行模拟，制作出具有真实感的效果图和三维动画等多种视觉模 型，以便人们在工程建成之前即可在计算机上看到其“庐山真面 目”，从而可对设计方案进行分析和评价，如检验路线平、纵、横 三方面的组合是否得当，与周围环境、景观的配合是否协调等。随 着计算机软、硬件技术的发展，道路三维模型在道路设计中逐步得 到重视和应用。 改革开放以来，我国交通基础设施建设有了一个突飞猛进的发 展，但对于整个国民经济发展的需要来说，交通还处于滞后状态。 经济的进一步发展、改革开放的进一步深化，对铁路和公路交通建 设提出了更高、更新的要求。 道路三维建模是道路三维可视化研究的重点内容，也是道路三 维可视化实现的基础。道路三维建模的研究成果已经比较丰富，技 术也日趋成熟，但是道路三维建模的理论支持如三维数据模型等还 不够全面，此外，国内现有的一些道路设计软件功能还不够全面， 不能真正满足道路可视化设计的需要。本文基于以上背景，对道路 三维建模的方法以及相关的关键算法进行了深入研究。 1 2研究的目的和意义 道路三维模型的建立，主要是为道路规划、设计等服务。道路 的规划和设计是一项涉及面广、综合程度较高的工作，不但要考虑 时间效率和经济效益，而且还要顾及环境以及地形、地质等因素。 道路三维模型可逼真呈现道路建成后的效果和线路所经区域，让决 西南交通大学硕士研究生学位论文第2 页 策者和设计者们有比较直观的印象，从而为他们进行决策和设计带 来便利。因此对道路三维模型的建模及其应用进行研究，具有十分 重大的意义。主要表现为：1 ) 极大地提高了经济效益和社会效 益：2 ) 提高了道路三维可视化设计的质量和速度；3 ) 推动道路勘 测设计一体化、智能化的进程。 1 3 国内外研究现状及发展趋势 1 3 1国外研究现状 国外主要是研究开发自己的三维道路设计平台，目前大体可分 为两类： 1 ) 独立的道路c a d 系统在国外，c a d 技术早在6 0 年代就被 应用到道路设计领域，发展到9 0 年代，出现了几个比较优秀的道路 c a d 系统，如德国的c a r d 1 系统，该系统主要针对道路几何设计 和排水设计，实用性强，对硬件要求低，界面友好：以数据采集、 处理和图像输出为一体的芬兰r o a d c a d 道路系统；具有先进图像 处理、交互设计技术，体现计算机硬件与公路设计软件完美结合的 美国i n t e r g r a p h 公司的i n r o a d s 系统；英国的m x 系统( 原为m o s s 系统) 能用于铁路、公路、矿山、排水、机场等设计等【1 l 。国外这 些软件的共同特点是建立在功能强大的三维数字地面模型及结构物 模型基础之上，基础牢固；此外都注重可视化技术、用户界面技术 ( 交互技术1 ，并寻求一定的智能化功能以及系统的集成和设计的一 体化。但由于这些软件普遍存在着价格昂贵，并且不适应中国的设 计规范及设计习惯，加上出于商业目的，技术资料很少公开等问 题，要想使这些软件能真正用于我国的铁路和公路设计，还有大量 的二次开发工作，并且二次开发也仅仅限于系统的外围难以涉及内 核。 2 ) 模块式的道路设计模型。美国m u l t i g e n p a r a d i g m 公司的 软件产品m u l t i g e nc r e a t o r 推出的道路建模与漫游模块r o a d ，它 通过手工输入道路设计参数构建道路表面几何模型，具备灵活的纹 理映射工具，加上固有的地形构建工具，可以构建道路场景的整体 景观模型，并可在c r e a t o r 平台上对构建的道路场景及时进行简单 的驾驶模拟，因而在国外三维道路景观模型的建模和浏览方面有广 泛应用。但是，针对当前国内道路设计行业中的大量设计成果( 包括 西南交通大学硕士研究生学位论文第3 页 平、纵、横断面和矢量地形) ，c r e a t o r 并不能直接支持这些数据格 式，尤其是各个设计单位自：己定义的数据存储和组织的方式，也就 不能将道路设计的成果导入系统中进行自动化建模，要想达到动态 可视化的目的，必须在c r e a t o r 中按照已有的设计成果数据进行再 一次手工建模，显然耗时耗力，成本昂贵f 2 l 。 1 3 2国内研究现状 国内在这方面起步比国外稍晚，但是发展比较迅速。目前国内 的道路建模软件大体也可分为两类： 1 ) - - 次开发型的道路c a d 系统。从8 0 年代开始，国内部分高校 和生产单位已经开始自行研制开发道路c a d 软件并投入使用，取得 了明显的经济效益。9 0 年代以来，随着计算机软、硬件技术的提 高，更多功能强大的道路c a d 软件出现了，主要代表有中交二院开 发的路线与互通式立交集成c a d 系统b l d r o a d 系统、上海中交海 德科技的海德( h e a d ) 系统、西安立德公路工程咨询有限公司的 纬地道路辅助设计系统( h i n t c a d ) 、东南大学李方教授主持开发 的路线与互通式立交c a d 系统e i c a d 等t 3 l 。国产软件已经广泛投 入使用并占据绝大部分中国市场，技术水平与国外软件相比，差距 在不断缩小。 2 ) 独立自主型的道路c a d 系统。典型代表为中南大学土木建筑 工程学院，该院的研究者们设计新的三维数据结构和道路场景组织 方式，开发独立于c a d 系统的三维建模、浏览和分析应用平台一一 d i g i r o a d 系统。该系统具有支持多种数据源；具有较强的人机交 互能力，支持道路平、纵、横专项设计和一体化设计等特点。 1 3 3发展趋势 上述模型都在不断发展、不断完善之中，集成化、协同化、智 能化将会是今后道路c a d 发展的方向。网络技术的迅猛发展为 c a d 的集成与协同提供了强有力的支持，使得并行工程处理作业成 为可能。数字地球技术日趋成熟，数字地面模型、全球定位系统和 立体造型技术等计算机新技术会不断被引入道路c a d 软件之中。智 能技术把专家系统运用于c a d 系统，使系统的性能得到更大的改 善，可靠性进一步提高，灵活性更大。综合来说，这一领域内的每 一项新技术的应用，都会产生巨大的效益，迅速、有效地利用这些 最新的技术，必然会不断提高我们的技术水平，提高我们的工作效 西南交通大学硕士研究生学位论文第4 页 率、管理水平，带来巨大的经济效益和社会效益。 1 4 研究内容及拟解决的关键问题 1 4 1主要研究内容 本论文研究的主要内容包括以下几个方面： 1 数字高程模型( d e m ) 的构建算法及效率分析 d e m 是道路三维模型建立的基础，现已有很多相对成熟的算 法，也取得了较多的应用成果。结合道路模型的特点，针对海量数 据：选用合适的构t i n 算法，一次性构建地形三维模型，同时对影 响该算法时间效率的关键问题如点与三角形的定位等进行研究是本 文研究的主要内容之一。 2 基于c d t ( c o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n ) 理论 的拼合算法 c d t 算法是道路整体三维模型建立的关键。道路三维表面模型 的建立、数字高程模型和道路表面模型如何快速有效拼合，并且使 拼合后的模型不但外观而且内部拓扑关系都统一，c d t 算法将起 到决定性的作用。高效率的c d t 算法是本论文研究的一个重点。 3 基于拼合算法的道路三维表面建模 道路三维表面模型可分为道路设计线( 线路) 三维模型、构造 物三维模型( 如桥梁、隧道等) 和附属设施三维模型( 如路灯、里 程路标、公路的护栏等) 。道路三维表面模型的构建方法、道路模 型拼合交线的提取、拼合交线嵌入地形模型以及拼合交线内地形三 角网的清除是本文研究的另一重点内容。 1 4 2 拟解决的关键问题 道路三维整体模型的建立要涉及到较多的技术和理论，主要可 概括为以下两部分。 首先是建模。道路三维模型依据分割归并的思想可分为两部 分，一是地形三维模型，即数字高程模型；二为道路表面模型。而 道路表面模型又可划分为道路设计线模型、构造物模型和附属设施 模型。因此建模是本论文中工作量比较大的一部分。选择什么样的 方法建模，能够方便各种模型的拼合( 叠加) 是本论文需要解决的 关键问题之一。 西南交通大学硕士研究生学位论文第s 页 其次是算法。算法是解决问题实现的基本理论的关键技术之 一，在构t l n 过程中，点在三角形中的定位是影响构t i n 效率的主 要原因，因此快速判断点在三角形中是需要解决的关键算法之一： 对于道路三维整体模型的建立，地形三维模型与三维道路表面模型 的快速拼合算法是关键；其次，拼合交线的提取以及拼合交线内地 形三角网的删除算法等也急待解决的关键问题。 1 5论文的结构 本论文主要由以下几章构成： 第一章，主要介绍了论文研究的背景、意义、国内外研究现状 与发展趋势，阐述了本文的主要研究内容及要解决的关键问题，最 后给出论文的主体结构。 第二章，主要介绍数字高程模型的构建理论及其算法，对点在 三角形内的定位等关键问题进行了阐述，采用逐点插入算法及 d e l a u n a y 三角剖分的特性一次性构建地形三维模型，无需l o p 优 化。 第三章，主要介绍基于q ( 工i ，匕) 函数5 1 的约束d e l a u n a y 三 角剖分算法，将该算法与角度最大法则和距离最近法则理论上进行 比较，结果证明了该算法在时间效率上具有优越性。 第四章，详细阐述了三维道路表面模型的建立，讨论了三维道 路表面模型拼合交线的提取以及基于c d t 算法的模型拼合，最终实 现道路整体三维模型的构建。 第五章，本章主要介绍系统的结构体系及其功能，展示了实验 结果。 第六章，主要对本文的研究进行总结，阐述了论文的不足，对 道路三维整体模型的发展方向进行展望。 西南交通大学硕士研究生学位论文第6 页 第2 章地形三维模型的构建理论与算法 构建地形三维模型是道路整体三维模型建立中的一个重要内 容，是道路勘测设计中选线，平、纵、横设计等的主要依据。地形 三维模型其核心是数字地面模型的构建。数字地面模型英文全称为 d i g i t a l t e r r a i nm o d e l 。缩写为d t m ，d t m 术语起源于土木工程 界，在1 9 5 5 年到1 9 6 0 年其间，美国麻省理工学院摄影测量实验室 主任米勒教授( c h a i r e s l m 川e r ) 在美国麻省土木工程部门和美 国交通部门研究工作期间，首次将计算机与摄影测量技术结合在一 起，比较成功的解决了道路工程的设计问题，同时提出了一个一般 性的概念：数字地面模型。数字地面模型诞生至今，在测绘和遥 感、农林规划、土木与水利工程、军事领域、地学分析以及地理信 息系统等各个领域得到了广泛深入的研究和普遍应用，如铁路、公 路勘测设计中的选线，坡度计算，土方计算和三维可视化设计；水 利工程中的水库设计，运河和渠道的布线；对不同的地形作分析与 比较，生成坡度图、坡向图和地形图等；此外，选用其它特征还可 进行诸如人口、降水量等的分析。 2 1数字高程模型( d e m ) 的构建 数字地面模型是描述地球表面形态多种信息空间分布的有序数 值阵列，它是道路勘测设计和计算机辅助设计所要解决的首要问 题。当地形信息为高程时，数字地面模型即为通常所说的数字高程 模型( d i g i t a le l e v a t i o nm o d e l ，简称d e m ) 。数字高程模型是基 础测绘的重要产品之一，其用途十分广泛，它是地理信息系统中不 可缺少的数据源。 数字高程模型是表示区域d 上的三维向量有限序列，用函数的 形式描述为： k - ( x ，x ，z ，) ( i - 1 ，2 ，3 ，弹) 2 - 1 式中，( x f ，y f ) 是平面坐标，z f 是r x i ，y i j 对应的高程。 2 1 1 d e m 的数据来源和采集方式 为了建立d e m ，需要一定量的三维空间数据，这些数据主要从 以下几个方面得到： 西南交通大学硕士研究生学位论文第7 页 1 ) 影像。主要包括航空影像和航天遥感影像，航空摄影测量 一直是地形图测绘和更新最有效也是最主要的手段，而且可获得高 精度d e m 生成最有价值的数据源。航天遥感也是获取d e m 数据 的一种方式，主要通过一些空间摄影系统和卫星扫描系统获取影像 再提取d e m 数据，这种方式获取的高程数据相对精度较低，但随 着新技术比如干涉雷达和激光扫描仪等新型传感器的出现，已可获 得高精度、高分辨率的d e m 数据。 2 ) 地形图。我们可以对现有地形图进行数字化采集d e m 数 据，需要注意的是地图符号的数字化和数字化数据是否满足现势性 要求，另外一个很重要的方面是地形图的数据质量，特别是在精度 方面的数量指标。 3 ) 野外测量。我们通过全球定位系统g p s 、全站仪等野外测 量的数据经过适当处理后可作为d e m 的数据源。这种方法得到的 数据精度相当高，并且可满足现势性要求，但数据获取的方式工作 量比较大，效率相对较低。 d e m 数据的采集方式有摄影测量、地面测量、立体遥感、 g p s 、地形图数字化等，各种方法从性能、成本、时间、精度等方 面来说各有优缺点，主要比较见表2 1 i7 l 。 2 1 2 d e m 的表面建模方法 d e m 的建模方法大体分为四类【7 l ，包括基于点的建模方法、 基于三角形的建模方法、基于格网的建模方法和混合表面建模。在 实际应用中，由于基于点的建模不实用而混合表面也要转换为三角 形网络，因此基于三角形和格网的建模方法是最常用和最基本的建 模方法，而不规则三角网( t i n ) 和规则格网( g r i d ) 是两种最典 型的代表。 t i n ( t r i a n g u l a t e di r r e g u l a rn e t w o r k ) 地形模型是以不规 则的三角形作为基本的面元来构建地形模型；g r i d 是用规则的格网 作为构建地形模型的基本面元，常见的如矩形格网。两种模型都是 应用最广泛的连续表面数字表示的数据结构，它们各有优缺点： g r id 的优点比如数据结构简单、易于构网、数据存储量小、 各种分析计算方便有效等。它的缺点是存在大量数据冗余，特别是 在地形起伏不大的地方，另外不规则的地面特征与规则的数据表达 之间不协调。而t i n 能够很好的表达地形的结构特征，最主要的优 西南交通大学硕士研究生学位论文第8 页 点是可变的分辨率，即表面粗糙或变化剧烈时，t i n 能包含大量数 据点；而当表面相对单一时，在同样大小的区域t i n 只需最少的数 据点。另外，t i n 还具有考虑重要表面数据点的能力( 如特征点、 特征线等) 。当然，正是这些优点导致了t i n 的数据存储和操作的 复杂性。尽管如此，t i n 在g 1s 中还是得到了普遍的使用，特别是 在三维建模及其可视化方面。比如a r c i n f 0 和g e 0 s t a r 等g i s 软件都提供了分别从格网数据和等高线数据刨建t i n 的功能模块。 表2 1d e m 数据采集方法及各自特性比较 获取方式d e m 精度 速度 成本 更新应用范围 程度 地面测量 非常高( c m ) 耗时很高很困 区域较小，特别的 难 工程项目 摄影测量 比较高( c m - m ) 比较比较周期大的工程项目，屋 快高性 家范围内的数据采 集 立体遥感低很快低很容 国家范围内乃至全 易球范围的数据收集 g p s 比较高( c m i l l l ) 很快比较容易小范围，特别的项 高 目 地形图手扶比较低f 图上精比较低周期 国家范围内以及军 跟踪数字化度0 2 0 4 m m )耗时性事上的数据采集， 仪 中小比例尺地形图 地形图扫描比较低( 图上精非常比较的数据获取 数据化( 屏 度0 1 - 0 3 m m 、快低 幕数字化) 激光扫描， 非常高( c m ) 很快非常容易高分辨率、各种范 干涉雷达 高 围 道路勘测设计应用中的地形有如下几个特点，一是呈狭长的条 带状分布，二是跨越的地理范围较广，三是所经区域地形起伏可能 较大。地形的这些特征给地形构网带来了一定的限制。由于道路模 型边界的不规则，采用规则格网建立的地形模型和道路模型的接边 处会产生裂缝，而t i n 建立的地形模型由于其边界可表达任意不规 则形状，从而能与三维道路表面无缝拼合。不仅如此，t i n 能很好 的保持原始数据点的精度，并能顾及地形特征线。因此，综合考 虑，本论文选用t i n 来构建三维地形模型。 生成不规则三角网的关键是构网技术，目前已提出许多构网算 法，理论证明在所有的构网原则中d e l a l l n a y 三角网( 以下简称d 西南交通大学硕士研究生学位论文第9 页 三角网1 是最优的。 2 2d 三角网的定义及特性 1 9 0 8 年，v o r o n o ig 首先在数学上限定了每个离散点数据的 有效作用范围，即其有效反映区域信息的范围，并定义了二维平面 上的v o r o n o i 图 1 0 1 ( 以下简称v 图) 。v o r o n o i 图是由一组由连接 两邻点直线的垂直平分线组成的连续多边形组成。1 9 3 4 年， d e l a u n a yb 由v 图演化出了更易于分析应用的d 三角网1 1 1 1 。它 是v 图中相邻v 多边形内的中心点连接成三角形组成的。从此，v 图和d 三角网就成了被普遍接受和广泛采用的分析研究区域离散点 数据的有力工具。 d 三角网的定义是：相互邻接且互不重叠的三角形集合，每一 个三角形的外接圆内不包含其他的点，这样的三角网称为d 三角 网。d 三角网的外边界是一个凸多边形，通常称为凸壳。 d 三角网具有如下性质1 1 2 1 ： a ) 空外接圆性质：在由点集形成的d 三角网中，其每个三角形 的外接圆均不包含点集中的其他任意点，这样的三角形成为 d e l a u n a y 三角形，三角形上的边称为d e l a u n a y 边( 如图2 1 ) 。 b ) 最大最小角度性质：在d 三角网中，两相邻三角形构成的 凸四边形中，交换四边形的对角线，不会增加这两个三角形六个内 角和的最小值( 如图2 2 ) 。l a w s 0 1 1 据此提出了局部最优方法 ( l o p ，l o c a lo p t i m i z a t i 0 i ip r o c e d u r e ) 1 3 l ：交换凸四边形的 对角线，可获得等角性最好的三角网。 由于这两个性质，决定了d 三角网具有极大的应用价值。d 三 角网成为一种最主要的t l n 表示法。 图2 1空外接圆特性图2 - 2“最大最小角”特性 西南交通大学硕士研究生学位论文第l o 页 2 2 1 相关算法回顾 目前流行的构建d 三角网的算法主要有三类：逐点插入算 法、分治算法和三角网生长法。二十多年来，这三类算法有大量的 学者在研究，己经取得了丰硕的成果，但也存在各自的优缺点，下 面分别进行介绍1 7 l 。 1 ) 逐点插入算法 逐点插入算法最初由l a w s o n 提出，其核心是每插入一数据点 p ，在三角网中找到包含p 的三角形t ，把p 与t 的三个顶点相连， 形成三个新的三角形。再通过局部优化过程( l o p ) 进行边交换，将 插入p 点后所有非d e l a u n a y 边调整为d e l a u n a y 边。它利用了d 三角网的空圆特性，对有公共