（计算机应用技术专业论文）三维地形建模实现方法研究.pdf

贵弛大学硕士学位论文 三维地形建模实现方法研究 摘要 随着社会的进步、科技的发展和经济的腾飞，信息时代正阔步向我们走来。人 们生活在地球上，并与这个地球表面处处发生联系：工程师对地表进行设计、构筑 楼房；地质学家研究地表结构；地质生态学家了解地表形态和地物形成的过程；而 测绘工作者则对地形起伏进行各种测量，并用各种方式描述地形。尽管专业领域不 同，研究的侧重点各异，但所有的工作都希望能用一种既方便又准确的方法来表达 实际地表现象。 数字高程模型d e m ( o i g i t a le l e v a t i o nm o d e l ) 在地理信息系统中有着广泛的应 用。它是进行地形分析的重要数据模型，也是巡航飞行器地形相关匹配的基本数据。 在巡航飞行器的地形相关匹配过程中，飞行器的高度测量表不断颖4 得飞行器相对地 面的高度值，此数据作为卡尔漫滤波中的观察方程数据而输入的，与事先装在飞行 器中的基准数字高程模型和飞行器的状态方程一起估计出飞行器的当前空间位置。 选择什么样的地形进行匹配，使致飞行器获得的信息最多，匹配的歧义性最小这 就是所谓的匹配地形的选择问题。d e m 用途广泛，数字地球、数字城市、数字区域等 工作以及虚拟现实三维可视化都需要高精度的d e m 支撑。当前，真三维地理信息系 统的实现仍然存在诸多尚未解决的技术难点。首先，空间三维数据的采集，其成本 昂贵；空间数据量大，种类多，结构复杂；三维空间的点、线、面和体之间的拓扑 关系复杂，技术尚不成熟，空问分析困难。所以，采用一种实用性强、精度较高、 牛成速度快，使用方便的d e m 的生成算法十分必要的。总体来说，三维地形模型的 生成与显示算法研究目前还处在理论原型设计和技术试验阶段，一个不断完善和发 展的工程。通过对地球三维模型生成技术的研究，进一步探索数字地球的基本思想、 概念和理论，并为建立贵阳市三维地形建模系统提供理论方法和技术探索。 本课题的主要研究重点放在算法实现方面： ( 1 ) 读入等高线的数量 ( 2 ) 读入每条等高线的坐标数量 责翻大学硕士学位论文 ( 3 ) 进行插值算法的生成 ( 4 ) 生成不规则三角网 关键词：地理理信息系统、数字地形模型、数字高程模型、不规则三角网、d e l a u n a y 、 三角网、内插 贵炳大学硕士学位论文 r e s e a r c ho fi m p l e m e n t a lm e t h o d so nt h r e e d i m e n s i o n a lt e r r a i nm o d e l i n g a b s t r a c t w i t hs o c i a ip r o c e s s ，s c i e n t i f i cd e v e l o p m e n ta n de s l a t i o no fe c o n o m y e p o c h o fi n f o r m a t i o nh a s b e et a k i n gi t ss t r i d et ou s t h eh u m a n b e i n gh a s b e e nl i v i n go n g l o b a la n dr e a c t i n gw i t hs u r f a c eg l o b a le v e r y w h e r e f o re x a m p l e ，e n g i n e e r s e x p l o r ea n dd e s i g ns u r f a c eo ft e r r a i na n d r u c t b u i l d i n g ，g e o l o g i s t sr e s e a r c h r u c t i o no ft e r r a i na n de c o g e o l o g i s t sa r ee a g e rt or e s e a r c hg l o b a ls t a t ea n dt h e p r o c e s so ft h ee a r t hm a t e r i a l sg e n e r a t i o n i n g 。w h i l et h ew o r k e r sm e a s u r i n g e x p l o r ev a d e t yo ft e r r a i np r o f i l ea n dd e s c r i b es h a p eo ft h ee a r t hw i t ham a s so f m e a n s a l t h o u g hf i e l d so fr e s e a r c ha r ed i f f e r e n t ，a s p e c t so fr e s e a r c ha r ev a r i o u s ， a l lw o r ki st ob eh o p et od i s p l a yr e a lt e r r a i n si m a g ew i t hc o n v e n i e n ta n da c c u r a t e m e a n s d i g i t a le l e v a t i o nm o d e li sa p p l i e dw i d e l yi ng e o l o g i c a li n f o r m a t i o ns y s y t e m i t i s ，f o re x a m p l e 。i m p o r t a n td a t am o d e l ；a n di ti sa l s ob a s i cd a t am a t c h i n gw i t h c r u i s ef l i g h tv e h i c l e 。s i nt h em a t c h i n gp r o c e s so fc r u i s ef l i n gv e h i c l e 。st e r r a i n ，t h e h e i g h to ff l i g h tv e h i c l ec o n t i n u e l ym e a s u r e sv a l u eo fr e l a t i v eh e i g h to ft h ef l i g h t v e h i c l ew i t ht h eg r o u n d ，t h ed a t ai si n p u t e da sc u l ii h eo b s e r v a t i o ni nt h ef i l t e r ， a n di ti sc o m p a r e ds t a n d a r dd i g i t i a le l e v a t i o nm o d e l i n gi n s t a l l e db e f o r e h a n di nt h e f l i g h tv e h i c l em o d e lw i t hs t a t ee q u a t i o no ft h ef l i g h tv e h i c l ee q u a t i o nt oe s t i m a t e c u r r e n ts p a c ep o s i t i o no ft h ef l i g h tv e h i c l e w h a tt y p ei sc h o o s e dt om a t c hw i t h i t ，s ol h a tt h ef l i g h to b t a i n sm o r ei n f o r m a t i o na n dc a u s e ss m a l l e s td i f f e r e n t m e a n i n gb yf a r ；a n di ti st h es o c a l l e dc h o i c eq u e s t i o no fm a t c ht e r r a i n t h ed e m e m p l o y e db r o a d l y ；a n dn u m e r a lt h ee a r t h 、t h ed i g i t a lc i t ya n dt h ed i g i t a la r e aa n d s oo n ，t h ew o r ka sw e l ia st h ev i r t u a ir e a l i t yo nl h r e ed i m e n s i o n a iv i s i b l ea l in e e d s t h eh i g ha c c u r a c ys t u c t u r eo ft h ed e m p r e s e n t l y ，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 b a s i n go nt h er e a l l yt h r e ed i m e n s i o nr e a l i z a t i o ns t i l lh a st h et e c h n i c a id i 衔c u l t i e s w h i c ha r en o ty e ts o l v e d i nt h ef i r s tp l a c e ，g a t h e r i n go ns p a t i a lt h r e ed i m e n s i o n a l d a t a ，w h i c hi se x p e n s i v eo nc o s t ，i sb i ga n do ns p a c ed a t aq u a n t i t y ，i sv a r i o u s t y p e ，i sc o m p l e xo ns t u r c t u r e ；a m o n gs i t u sr e l a t i o n so fs p o t ，i i n e ，s u r f a c ea n d 贵确大学硕士学位论文 b o d yo nt h et h r e e - d i m e n s i o n a ts p a c ea r ec o m p l e x ：t h et e c h n o l o g ys t i l l w a s i m m a t u r e ；a n di ti sd i f f i c u l to ns p a t i a la n a l y s i s t h e r e f o r e ，a d o p t i n gau t i l i t y s t o n g l yt h ep r e c i s i o nh i g h l y ，s p e e dq u i c ko ng e n e r a t i o n ，p r o d u c t i n ga l g o r i t h mo f c o n v e n i e n td e mu s e da r ee x t r e m e l ye s s e n t i a l g e n e r a l l y - r e s e a r c ha l g o r i t h mo fg e n e r a t i o na n dd e m o s t r a t i o na b o u tt h e t h r e ed i m e n s i o n a lt e r r a i nm o d e la tp r e s e n ts t i l lh a sb e e nt h et h e o r yp r o t o t y p e d e s i g na n dt h ee n g i n e e r i n gs t a g ea tp r e s e n t ；i ti su n c e a s i n g l yc o n s u m m a t e sa n d t h ed e v e l o p m e n tp r o j e c t t h r o u g hr e s e a r c h i n gt e c h n o l o g yo ft h r e e - d i m e n s i o n a l m o d e id e m o n s t r a t i o no nt h ee a r t h ，f u r t h e ri ti se x p l o r e da b o u tt h ed i g i t a le a r t h b a s i n gt h o u g h t ，c o n c e p ta n dt h e o r y ； t e r r a i n m o d e l l i n gs y s t e mt op r o v i d e e x p l o r a t i o nm o d e la b o u tt h eg u i y a n g a n df o re s t a b l i s h i n gt h r e ed i m e n s i o n a t h et h e o r ym e t h o da n dt h et e c h n i c a t h i sp a p e rm a i l yr e s e a r c ha n a l y s i so fa l g o r i t h m ： f 倦i 。 r e a dn u m b e ro fc o n t o u r s e c o n d ，r e a dn u m b e ro fc o o r d i n a t eo ne v e r yc o n t o u r t h j r d 。d e s i g na l g o r i t h mo fi n t e r p o l a t i o n l a s t ，g e n e r a t i o nt r i a n g l u a t e di r r e g u l a rn e t w o r k s k e yw o r d ：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 ，d i g i t a lt e r r a i nm o d e l ，d i g i t a le l e v a t i o n m o d e l ，t r i a n g l u a t e di r r e g u l a rn e t w o r k ，d e l a u n a yt i n ，i n t e r p o l a t i o n 6 贵抽大学硕士学位论文 第一章绪论 1 1 课题研究的背景及意义 1 1 1 数字高程模型的发展现状 目前，地形生成技术大致可归纳为三个阶段： 第一类是基于真实数据的地形生成技术，它用d e m 数据构造多边形面，用多边 形网格逼近，h o p p 提出的渐进网格( p r o g r e s s i v em e s h e s ，p m ) 法【i j 。这种算法通 过一系列边的折迭，将原始数据网格简化为一个简单的基网格，这样就可以根据其 逆操作边进行分裂，将细节逐渐增加到基网格上，这对于需要通过网络传输的数据 绘制来说是很重要的。m a r kd u c h a i n e a u 等人提出了“实时优化自适应网格”算法， 这种算法的基础是三角形二叉树的动态网格表示法，因此可通过定义三角形二叉树 和分裂、合并操作，来保证增加或删除顶点时网格的连续性，通过对矩阵进行优化， 产生一个误差约束，就可以直接获取指定的三角形数目。 第二类是基于分形技术的地形生成。分形几何学的思想是m a n d e l b r o t 于1 9 7 3 年提出的【2 l 。分形几何关注的是物体的随机性、奇异性和复杂性。分形几何具有细 节无限性以及统计相似性的典型特性，它用递归算法使复杂的景物可用简单的规则 来生成，在现代的计算机图形学中，分形几何在对自然现象的真实绘制和建模方面 起着重要作用。 第三类是基于数据拟合的地形生成。国内已有许多优秀的半自动扫描矢量化软 件。从等高线数据可以直接生成t i n ，也可以直接生成格网d e m ，格网d e m 也可由 等高线先生成t i n 再内插而获得，经过实践证明，由等高线先生成t i n 再内插格网 d e m 的精度和效率都是最好的。 地形是人类社会赖以生存并从事一切实践活动的根基。在人们的日常生活中， 地图一直是人们表达和传递地表信息的土要手段。然而，从本质上讲，地图是对客 观存在的特征和变化规则的一种科学的概括( 综合) 和抽象。其客观世界是丰富多彩、 千姿百态的三维空间实体。这种用二维介质平面图与所表示的三维现实世界的复杂 9 责确大学硕士学位论文 物体之间有着不可逾越的鸿沟。以及空间要素，对于大多数不具备专用地图学知识 的使用者来说，是难以理解和接受的。因此，根据测绘学等学科理论，借助先进的 计算机技术。生成具有高度真实感的和可量测性的地形三维模型，实现三维地形表 面的逼真还原，无疑是一项富有建设性和开创性的工作。近几年，“数字地球( d i g i t a l e a r t h ) ”一词风靡全球，它被列为中国2 l 世纪的战略目标之一。数字地球试图在全 球范围内建立一个基于地理位置，并将各领域的信息进行组织，融合起来的复杂虚 拟现实系统，它使人们沉浸式，交互式，灵活式地浏览所需的信息，这其中包括地 形，河流，森林，建筑，乃至经济，科学，文化，教育等信息，数字地球涉及到大 规模计算、海量存贮、卫星遥感、宽带网络、互操作、元数据等支撑技术，并需要 以虚拟现实、地理信息系统和互联网为基础，通过地理信息系统组织海量的地理相 关信息；同时基于互联网构架一个全球信息网络，实现资源共享。 课题来源是教育部“春晖计划”项目一“贵阳市三维地形虚拟漫游系统的研究”。 这个项目的目的是数字化贵阳，使得人们可以通过计算机平台来看到实时的、具有 高逼真度的地形地貌，也使得人们可以了解到贵阳的在线风光：不仅可以用于防止 自然灾害而且还用于贵阳市地质的勘探和考察。 1 2 本文主要的研究工作和章节安排 1 2 1 主要的研究工作： 探讨基于规则格网( g r i d ) 和不规则三角网( t i n ) 模型的结构和生成算法； 规则格网和不规则三角网的相互转换问题； 不规则三角网中的d e l a u n e y 三角网的建立； 在已生成的模型基础上探讨内插值的问题； 对d e l a u n e y 三角网插值后进行局部优化( l o p ) 。 1 2 2 章节安排 本论文围绕着基于真实数据的三维地形生成和模型构造问题进行了广泛的探 贵豫大学硕士学位论文 索，其中以建立地形的模型为重点内容，主要研究了目前建立地形模型的两种方法： 一种是规则正方形格网( g r i d ) 模型，它适用于地形比较平坦、地面比较平滑的地理 区域；另一种是不规则格网( t i n ) ，它的适用范围是地形比较陡峭、坡度系数比较 高的复杂地区。 各章研究的内容安排如下： 第一章简单介绍数字高程模型的基本概念、分类、重要特点。 第二章介绍了数字高程模型中的规则格网( g r i d ) 模型的特征和适用范围。 第三章介绍了数字高程模型中的不规则格网( t i n ) 模型，阐述了不规则格网( t i n ) 模型中d e l a u n a y 三角网的建立与生成及三角网局部优化问题。 第四章对基于地形规则格网( g r i d ) 模型和不规则三角网( t i n ) 的转化问题以及 不规则三角网中的约束性三角网进行了详细的阐述。 第五章主要讨论了不规则三角网的设计平台及实现的相关内容。 第六章介绍不规则三角网的设计、调试和软件平台的设计与应用。最后展现实 现的结果。 第二章数字高程模型的概述 地形地貌模型的生成是虚拟现实技术在地理学应用领域中的具体体现之一。计 算机所建立的地形地貌模型就是根据来自真实世界的数字离散点，运用建模技术， 在二维平面图像上生成真实感、立体感等方面都可以与三维真实环境的地形地貌相 媲美的图形图像。建立几何模型时，在几何精度和图像精度方面要尽量和真实地形 保持一致，构成逼真的地形地貌，这样，模型的建立将涉及到许多算法和许多关键 抽象的概念。 贵强大学硕士学位论文 2 1 数宇高程模型的定义和种类 2 1 1 数字高程模型的定义 数字高程模型d e m ( d i g i t a le l e v a t i o nm o d e l ) 是用数字形式来描述地形 表面的模型。 数字地面模型( d t m ) 是以数字形式存储的地球表面上所有信息的总和，是 描述地面特征空间分布的数值的集合，是地形表面形态等多种信息的一种数字表示。 把数字地面模型( d t w ) 中凡描述地表起伏形态的某类数据进行汇总集合就是数 据高程模型。一般数字高程模型只含有地形表面的高程数据，如通过航、卫片的立 体像对自动匹配生成的高程数据。而数字地形模型( d t m ) 不仅有地表的高程数据， 还有存在于地形表面的地物数据，如：建筑物、公路、河流、湖泊等。但极大多数 学者不加区分地使用这两个词。对于自然地形，我们可以用一个定义在x - y 平面上 的连通子集b 的函数z = f ( x ，y ) 来表示，即辩( d ，f ) 。而d 踊则定义为对d 域进行 划分后，得到一个平面区域的集合r = f r l ，r 2 。，r n ) 和定义在r 上的一个连续 函数族f z = f i ( x ，y ) ，( i = l ，2 ，) 组成的二元组d = ( ，f ) 。若r i 与r j 相 邻，则在公共边界处有f i = f j ，那么d e m 的面为每个f i 函数的图，d e m 的边与节点为 每个函救f i 对划分的边与节点的约束。由于对多个节点的平面划分组成的边数 和区域数，因此，具有个节点的d e m 的空间复杂性是多个节点的线性函数。 2 1 2d e m 的分类 根据目前研究的热点现状分析，d e m 在生成技术方面可分为两大总类： ( 1 ) 规则正方形格网g r i d 模型； ( 2 ) 不规则三角网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 ) 模型中，每个小区域中的f i 是一个分段线性、 二次或三次函数，它通过对格网节点值的插值获得，由于g r i d 中节点是规则排 贵确大学硕士学位论文 列的，如图2 1 ( 8 ) 示，就可以用一个二维数组d 来存放每个点的z 值，而格网 的宽和高可以是隐含的，或显式存放在数据结构的其它项中。 ， 、 ， 下面是一个典型g r i d 模型的数据结构： s t r u c tg r i d f i n td x ：规则格网中行的标量 i n td y ；规则格网中列的标量 i n tr o w n 咖：规则格网行的总数 i n tc o l n u m ；规则格网列的总数 f l o a td 口 ；每一个规则格网中存放的高程值 夺不规则三角n ( t i n ) 模型是通过对d 域的三角形划分实现的，如图2 1 ( b ) 所示。对d 域的三角划分( 也叫三角剖分) 方法有多种，但d e l a u n a y 三角划分 足较常用的一种划分，因为这种三角划分有很好的数学插值特性。t i n 模型的 数据结构有节点数据结构、边数据结构和三角形数据结构组成： 贵强大学硕士学位论文 图2 1 ( b ) 不规则格网的数字高程模型 ( 1 ) 点数据结构： s t r u c tp o i n t f l o a tx ；( x ，y ) 是平面坐标点 f l o a ty ； l o n gn e x t ；指向下一个节点索引的指针 ) ( 2 ) 边数据结构： s t r u c te d g e ( 1 0 n gf r o m ；边的起始节点索引值 l o n gt o ；边的终结点索引值 l o n g l e f t ；边的左三角形索引值 l o n g r i g h t ；边的右三角形索引值。 ( 3 ) 三角形数据结构 贵确大学硕士学位论文 s t r u c tt r i n a n g l e l o n g e d 3 ；三角形边的索引 l o n ga t 3 ；与该三角形相邻三个三角形的索弓 l o n g n e x t ：下一个三角形的索引 2 2 两种数字高程模型的比较 i i n 模型和g r i d 模型都是应用最广泛的连续表面数字表示的数据结构。正如前 面所说的，t i n 模型具有许多明显的优点和缺点。其最主要的优点就是可变的分辨 率，即当表面粗糙或变化剧烈时。t i n 模型能包含大量的数据点：而当表面相对单 一时，在同样大小的区域t i n 模型则只需要最少的数据点。另外，t i n 模型还具有 考虑重要表面数据点的能力。当然，正是这些优点导致了其数据存储与操作的复杂 性。对于t i n 模型，由于三角形是不规则排列的，计算r i 上的f z = f i ( x ，y ) 时实时 性不如g r i 6 模型，但t i n 模型是在原始采样数据集上直接生成的，并且，只生成点 与点的拓扑关系，而不产生新的点，信息无丢失。同时t i n 模型对同一d 域比g r i d 模型更节省存储空间。g r i d 的优点不言而喻，他的结构十分简单、数据存储量很少、 各种分析与计算非常方便有效等。由于g r i d 模型中每个格网节点上的高程值是经过 事先插值得到的，在每个矩形区域r i 中的f z = f i ( x ，y ) ，可通过r i 的四个顶点的 高程值获得，因此，在求f i 时具有较好的实时性，这在巡航飞行器地形相关匹配时 是十分重要的。另外，由于g r i d 模型是对数据规则排列的，更接近于人的主观直觉， 因此更容易被人理解。如果将g r i d 模型中每个节点的高程值与图像的灰度相类比， 这样d e m 模型实际就是具有一定灰值变化的图像。由此，我们可将许多图像分析的 算法引入来进行地形分析。如通过对d e g 的快速傅里叶变换，可对地形进行纹理分 析等。似g r i d 需要较大的存储空问来保存高程数据。 ( 1 ) 对于g r i d 模型，子域是按规则格网进行划分的：规则格网模型具有固定的 规则数据结构，而地形表面的特征却是极不规则的，这样就限制g r i d 模型在内部结 贵两大学硕士学位论文 构上不能与地表的起伏特征相适应，但正因为结构简单而易于构网。 ( 2 ) 而t i n 模型，每个子域被划分成三角形。不规则三角网的构网任意性可将地 表的特征表现得淋漓尽致，三角网中的点与线的分布密度和结构完全可以与地表的 特征相协调，但是构建t i n 模型的过程比较复杂，需要耗用大量的时间。 ( 3 ) 从等高线数据中选取重要的点构成t i n 模型并生成正方形格网，在二者数据 量相同的情况下，t i n 模型具有最小中的误差。 ( 4 ) 根据d e m 模型产生的地形晕渲图与正射影像的比较也可以看出基于t i n 模型 图像与正影像吻合得更好。 ( 5 ) 当用于建立d e m 模型表面的采样数据点减少时，g r i d 模型的质量明显比t i n 降低得快。而随着采样点或数据密谋的增a n - - 者之间的性能差别起来越不明显。 第三章基于g r i d 模型的d e m 模型产生 3 1 插值算法 基于g r i d 模型的d e m 模型一般可由两种途径生成： ( 1 ) 通过对航片或卫片立体像对的自动判读获得： ( 2 ) 通过对随机高程采样点插值获得。 下面主要讨论的是第二种d e m 模型的生成途径，设有一离散随机点集 p 2 岛( 膏，j ，力) ( f = 1 , 2 ，a ，h ) ，g 为x y 平面上d 域按矩形划分r 生成的格网节点上的 高程值，g g ( m ，托z ) ) ：嚣_ 1 插值过程( 也称格网化过程) 定义在p 上的一个映射f ： f ：p g 对于给定映射p = n o ，y ，z ) ) ( f = 1 , 2 ，a ，”) 映射，? - - - g g ( m ，疗，z ) ) 墨乜。得到三 维空间上新的点集g ，p e g 。插值方法有多种，较常用的是距离加权的加权插值方 法，即： 设p 1 ，p 2 ，p k 为最靠近格网节点n o d e 。的k 个已知高程值为z l ，z 2 ， z k 的点，节点n o d e 。的高程值仿照质点的万有引力定律，离节点距离越远的点， 1 6 贵撼大学硕士学位论文 对节点高程的加权值越小，反之越大。n z 。为： 盈 ，台以 矾”豇 智以 ( 3 1 式) d k 为点p k 到节点的距离，一般可采用欧氏距离。 3 2 数据分块的插值( 格网化) 算法 3 2 i 问题的提出 设d = h ，蜘，w ，h ) ，其中，蜘是平面上离散点坐标，w ，h 是离散点所在格 网的宽度和高度；将其划分成m n 个格网，即有( 卅1 ) x ( n + 1 ) 个节点和( m + 1 ) ( n + i ) + ( m n ) 一1 条边，现有离散数据点集p = 只( x ，y ，z ) ) ；。，s 为离散点的总数， 为了求出某一格网节点o 如的周围数据点的分布，则需要遍历点集p ，搜索的时 间复杂度为o ( s ) 。当格网节点为( m + i ) ( n + i ) ，完成每个节点插值的时间复杂度为 0 ( ( m + i ) ( n + 1 ) s ) 。假设当m = 1 0 0 ，n = 1 0 0 ，s = 1 0 4 时，比较次数约为1 0 8 。为了减 少数据的比较次数，以格网节点n o & 。为中心建立一矩形窗口或圆，只要数据点落 入矩形窗口的某一象限时，就认为找到了该象限的插值控制点，不再在该象限搜索 其它数据，如图3 1 所示的简化收搜示意图。这种以牺牲精确度为代价的方法，避 免了在求每个节点时必须遍历所有数据的要求。虽然减少了搜索次数，但时间复杂 度并无实质性改变。 山于格网数是固定的，所以时间复杂度是数据量s 的线性函数。数据分块算法 的口的就是变时间复杂度0 ( ( m + i ) ( n + i ) s ) 为0 ( ( m + i ) ( n + i ) + s ) 或 0 ( ( m + i ) ( n + i ) p ) ，p b 则保持原有三角形关系，如果a o ，说明点v 在直线v i v 2 的右边；如果d = o ，说明点v 在直线v i v 2 上；如 果d l 就不必再执行扩展操作，避免后面的三角形的重复检测，提高建网的效率。 上述方法只排除边界边没有重复，故必须再判断此三角形是否已存在己建三角网中。 如t i m e s = l ，则说明此三角形已建立，否则保留此三角形。 经过这两级检测可确保三角网中无重复的三角形，确保三角网的质量并完成建 网任务。 5 1 4t i n 向g r i d 转换的优化算法 ( 1 ) 优化算法基本原 优化算法基本原理是：在对原始等高线数据简化处理并对子块生成t i n 三角网 的基础上，利用点集分块的信息，判断当前的格网节点属于哪一块，然后调用与此 块子点集对应的子三角网，再计算格网节点属于哪一个三角形，在此三角形上 内插出格网节点的高程值。 ( 2 ) 自适应分块并生成子块三角网 读取离散点数据之后。依据坐标数据，对离散点进行构网，主要步骤如下： 点集分块 由于实际地形的复杂性，离散点的分布很不均匀，而要处理二维平面上分布不 规则的离敞点数据时，通常要查询“有效”点，若逐点查询、检索，显然查询的效 ；仁足非常低的，因此需要进行点集分块。 现有的数据分块方法有：均匀条带分割( 图5 2 ) 、等格网分割( 图5 3 ) 、四叉树 分割( 图5 4 ) 和自适应分块等。 责纳大学硕士学位论文 图5 2 均匀条带分割法 i l 图5 3 等格网分割法 图5 4 四叉树分割法 用前两种方法不能够随着空间点分布的不同而产生变化，在空间点分布产生异 常的时候，会降低算法的效率，即算法不够稳定。而第三种算法则会自动随着点的 空间分布不同而不同，从而在空间点分布差别很大的情况下，仍然可以保证较稳定 的算法执行效率，同时四叉树结构也有利于限定边的嵌入。第四种算法是在等格网 分割的基础上，给定一个最低限。每一格中的点数小于最低限时，动态调整网格宽 度。 采用类似四叉树的方法，给定点数的最低限，判断每一块的大小，即计算每一 块的左上角、右下角坐标。循环读取点链表中的点坐标，判断每个点在哪一块中， 并添加到块的点链表中，记录点号。程序中用b u i l d b l o c k ( d o u b l em a xx ，d o u b l e m i nx ，d o u b l e m a x _ y ，d o u b l e m i n _ y ，l o n gl i m i t ) 分块函数加以实现，其中，m a x