（大地测量学与测量工程专业论文）数字高程模型建模算法研究.pdf

论文题目： 专业： 硕士生： 指导教师： 数字高程模型建模算法研究 大地测量学与测量工程 张咏 刘长星 摘要 ( 签名) 丛! ：坠 c 签名，斟也l 本文主要研究空间离散点的数字高程模型建模算法。首先基于s u a lc + + 6 o 和 o p e n g l 编程实现了空间离散点的t i n 建模；其次增加了任意点删除、插入、约束三角 网的构建和等高线追踪等功能；最后对算法进行了验证。 本文利用包容壳求解二维点集凸壳的方法，集目前各种算法之长，方法简单、易于 实现，是一种高效的自适应算法；针对d e l a u n a y 三角网任意点定位，将三角形面积坐 标、重心、点与有向线段的关系三者有机结合，构建了一种定位路径唯一、速度快、健 壮高效的融和算法；对于局部编辑时用到的点删除，针对目前基于影响域多边形剖分的 算法缺陷，首先利用具有拓扑关系的三角网搜索影响多边形，并以三角形矢量面积为工 具三角剖分影响域多边形，最后通过镶嵌优化后的剖分三角网完成对点的删除；点的插 入，则是动态扩展凸壳，弥补了一般算法不能插入凸壳外点的缺陷，并利用融和点定位 算法，提高了插入效率：约束网的构建，首先利用改进的线段相交判断算法分离影响域 多边形，然后以本文的任意多边形剖分和优化算法完成影响域多边形的d e l a u n a y 重构， 最后将重构后的三角网镶嵌到原位置，向t i n 网加入约束条件；等高线搜索则利用三角 网的拓扑信息快速搜索出三角网的边界边，基于边界边高效完成开区线搜索，并改进现 有三角网数据结构，追踪闭曲线。 本文算法不仅对同类方法进行了完善改进，而且通过验证，算法效率高、切实可行， 具有一定创新性。对三维建模研究有一定参考借鉴价值。 关键词：数字高程模型；算法；不规则三角网；凸壳；点定位；点删除；点插入； 多边形三角剖分 研究类型：应用基础研究 s u b j e c t ：s t u d yo nt h ea l g o r i t h mf ；d rc o n s t r u c t i o nd i g i t a le l e v a t i o n m o d e l s p e c i a i t y：g e o d e s ys u r v e y i n ga n de n g i n e e r i n g n a m e：z h a n g y 0 n g i n s t r u c t o r ：l i uc h a n g - x i n g a b s t r a c t ( s i g n a t ur e ) ( s i g n a t ur e ) t h i sp 印e rs t u d i e so nt h ea l g o r i t h m sf o rc o n s t r u c t i o nd i g i t a le l e v a t i o nm o d e lu s i n g s p a c ep o i n t s i ta c h i e v eat i nm o d e l i n gb a s e do nv i s u a lc + + 6 0 龇l do p e n g la sat 0 0 1 t h e r e a r em a n y 丘m c t i o na sc d - t i n ，p o i n ti n s e r t ，p o i md e l e t ea n d c o n t o u r 订a c k n g t h e r ea r cm 甜l y a l g o r i t h m sf o rc o n s t r u c t i o nc o n v e xh u l l ，i no r d e rt om a k eu pf o r s h o r t a g eo ft h i sa l g o r i 也m s ，t h ep a p e rs t a r t s 、v i t h 锄a l y z i n gt h e3t o8 劬d a m e n t a le x t r e m e p o i n t so fc o n v e xh u l l t h ep u i p o s eo fs t e pi su s et h ei m t i a li n c l u s i o nh u l lt oc o n t r o la l l i n s t a i l c e s t h e na l li m p r o v e dn e w a l g o r i t h mi sg i v e nw m c hi st r a c l ( i n gt h ec o n v e xh u l l 1 l l i s m e m o dh a si 1 1 1 1 e r i t e dt h em e r i to fm 砒l ya l g o r i t ，n o to i l l yc o n s i d e r sr o u n d l y ，m o r e o v e r c o r e r tc o m p l e xi n s t a n c e si n t os i m p l e ，a i l di so n e 心n do fa l l t o a d a p t e da l g o r i t h m t h ep 印e rf i r s tc o n s 煳t et t l ei n n u e n c ep o l y g o n ss e a r c hm e t h o dm r o u 曲t a l ( i n ga d v e n t a g eo ft l l et o p 0 1 0 9 i c a lr e l a t i o no ft r i a n g u l a t i o nn e t ，s e c o n d l yt a k et h et r i a n g l ev e c t o ra r e at o o lt o t r i a n g u l a t i o nt h e 删【l d o mp o l y g o n ，l a s t l yc o m p l e t ep o i n td e l e t i o na 氛e rm o s a i co p t i m i z em et r i a n g u l a rn e tt ot h eo r i g i n a lp o s i t i o n t h et r i a n g u l a t i o nm e t h o di ss i m p l e ，e 哟7t 0u i l d e r s t a j l d ， s i m p l e1 1 i g h l ye 仃e c t i v e a 舭n 莉h a sc 硎e do nt h ee 衔c i e n c ya n a l y s i st ot h ea l g o r i t h m ，p r 0 v e dt l l a tt h ee m c i e n c yi sl l i 曲e rm a no t h e rs i m i l a ra l g o r i t h m s t w o - d i m e n s j o n a ld e l a u l l a y 嘶a n g u l a t i o nc o n s t r u c t i o na 1 1 de d i t o ri sa s s o c i a t e dw i t ht h e p o i n ti n s e r t i o n i ti st h es p e e do ft h ee n t i r ei n s e r tt l l ek e yf a c t o r 、h e r et 1 1 ep o i mi si nt h e t r i a l l g l ep o s i t i o m n ga l g o r i t l l m ，m o r e o v e rt h ep o i n tb yp o i mi n s e r ti su n a b l et oc o m p l e t et h e i 1 1 s e r t i o no ft r i a n g u l a rn e te x t e r i o rp o i n t f i r s ta i m sa tt h ep o i n tp o s i t i o n ，c o n s t m c t i n gt h e m o s ts h o r t p a t hh 锄o n i o u sb l e n do fa l g o r i t b ym et h r e eo 玛a n i cs y n t h e s i so f t h et r i a u l g l e a r e ac o o r d i n a t e s ，t h ec e n t e ro f 莎a v i t ) ，a 1 1 dt h er e l a t e sb e t 、v e e np o i n t sa i l d l i n e ，锄dt h e n b u i l d i n gt h ep o i mi n s i d e 锄do u t s i d et h eb o r d e ri n s e r tb yu s ed y n 锄i cc o n v e xh u l l p o i n t p o s i t i o no ft h es e a r c hp a t hi su n i q u e t h ep o i n to u t s i d et h en 咖o r kc a nb eq u i c k l yi n s e n e d n i saf 瓠ta n de m c i e n ti n s e r t i o na l g o r i t h mo fa r b i t r a r yp o i n t a tp r e s e n tt h e r ea r e4k i n d so fa l g o r i t t u i l so ft h ep o i n td e l e t i o ni i ld o m e s t i ca n df o r e i g n 1 1 1 ep o i n td e l e t i o na l g o r i t h m sb a s e do nt h ei n f l u e n c et e r r i t o 巧p o l y g o nt r i 叽g u l a t i o ni ss i m p l y a n de a s yt ou n d e r s t a n da n dr e a l i z e s a l t h o u 曲t h ea l g o r i t h m se m c i e n c yi sh i 曲，t h ei n n u e n c e p 0 1 y g o n ss e a r c hi si m p e r f e c t ，o i l l yp r o c e s st h ei n n u e n c et e 玎i t o 巧f o r t h es i m p l e p o l y g o n s i t u a t i o n t h ep a p e rf i r s tc o n s u m m a t et h ei n f l u e n c ep o l y g o n ss e a r c hm e t h o dt h r o u g ht a k i n g a d v 锄协g eo ft h et o p o l o g i c a lr e l a t i o no f 仃i a i l g u l a t i o nn e t ，s e c o n d l yt ；a k et h et r i a l l g l ev e c t o ra r e a t o o l t ot r i a n g u l a t i o nt h er a n d o mp o l y g o n ，l a s t l yc o m p l e t ep o i n td e l e t i o na r e rm o s a i co p t i m i z e t h et r i a n g u l a rn e tt ot h e o r i g i n 越 p o s i t i o n t h et r i a n g u l a t i o nm e t h o d i ss i m p l e ，e a s yt o u n d e r s 切n d ，s i m p l eh i 曲l ye 仃e c t i v e a r e n 硼r dh a sc a r r i e do nt h ee 衔c i e n c ya 1 1 a l y s i s t ot h e a l g o r i t h m ，p r o v e dt h a tt h ee m c i e n c yi sh i 曲e rt h a no t h e rs i m i l a ra l g o r i t l l i l l s t h ea l g o r i t h mh 嬲 c e r t a i l l l yv a i u e 7 i h ea j g o r i t h mf o rc o n s t m c t i o nd i g i t a le l e v a t i o nm o d e l i nt l l i sp 印e rn o to n l yf o rt h e s a m ea l g o r i t h mt oi m p r o v ea 1 1 di l u l o v a t i o n ，a 1 1 dh a sp 2 u s s e d 恤的u 曲d i g i t a le l e v a t i o nm o d e l t e s ts y s t e mv a l i d a t i o na n dp r a c t i c a l t h ep 印e rh a sar e f e r e n c ev a l u et ot h er e s e a r c h e r s 、) ，：h o s t u d y 咖e e d i m e n s i o n a lc o n s t r u c t i o nm o d e l i n g k e yw o r d s ：d i g i t a le l e v a t i o nm o d e l a j g o r i t h i nt r a l l g u l a t e di 玎e g u l a rn e 觚o r k c o n v e xh u l lp o i n tp o s i t i o np o i n td e l e t ep o i n ti i l s e n p o l y g o n 嘶a 1 1 刚a t i o n t h e s i s ：a p p l i e db a s i cr e s e a r c h 要料技土攀 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：弓弋哆习日期： 沙一7 ，多，p 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期问 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名： 毒孙 长f 0 ，年 ，多叶，移q 名 2 签 】 i y 教 导指 1 绪论 1 1 研究意义 1 绪论 数字高程模型d e m ( d 磷t a le l e v a t i o nm o d e l ) 是通过有限的地形高程数据实现对地 形曲面的数字化模拟或者说是地形表面形态的数字化表示【i 】。d e m 实现了区域地形表面 的数字化表达，是新一代的地形图，因此应用领域遍及地形图应用所涉及的行业【l 2 j 。从 模拟的纸质地形图到数字化的d e m ，不仅仅是地形表达方式和存储介质的改变，还是 人类对地形认知的一次质的飞跃，实现了地形从二维表达向三维表达的转变，其理论与 技术的影响不再局限于测绘学领域，而是遍及与之相关的各个学科领域。从地学分析应 用、非地形特性应用、产业化和社会化服务三方面考虑，d e m 在科学研究领域、工业 部门、商业、管理和军事等领域有着广泛应用。 随着科学技术特别是计算技术的迅速发展，对d e m 的数据获取方法、数据存储和 数据处理速度等方面己经取得了一些突破性进展。数字地形模拟已经成为地球科学重要 的分支之一。实际上，由于地理信息系统g i s ( g c o 掣a p l l i ci n f o m a t i o ns y s t e m ) 的普及， 在美国、中国、德国和英国等国家，d e m 作为数字地形模拟的重要成果已经成为国家 空间数据基础设施n s d i ( n a t i o n a ls p a t i a ld a t ah l 觚t m c t u r e ) 的基本内容之一，并被纳入 数字化空间数据框架d s d f ( d i g l 协ls p a t i a ld a _ t af 删 i l e w o r k ) 进行规模化生产。目前，d e m 己成为各勘测部门的基本任务和日常工作之一。d e m 作为地球空间框架数据的基本内 容，是各种地理信息的载体，在国家空间数据基础设施的建设和数字地球战略的实施进 程中都具有十分重要的作用【l 刮。 1 2 研究内容 本文在分析总结当前数字地面模型建模方法【i ，6 ，1 0 。2 9 】的基础上，利用离散地面点三维 数据，采用双向链表数据结构，基于动态凸壳以逐点内插法构建t i n 网，并基于v c + + 6 o 和o p e n g l 编程对算法的j 下确性和效率加以验证，实现编辑、约束和等高线的追踪功能。 主要研究内容有： 、研究和改进具有拓扑关系的双向链表t i n 数据结构。 、研究凸壳搜索方法，改进目前算法的不足之处；研究基于凸壳和任意多边形的 三角剖分算法。 、研究基于凸壳的逐点插入法构建、编辑t i n 的算法：优化点在三角网中的定位 算法；完善目前基于影响域多边形三角剖分的点删除方法，提高删除效率；弥补常规算 法无法插入凸壳外点的不足之处，减少点插入耗费时间。 西安科技大学硕士学位论文 、研究提高线段相交判断算法的效率，并利用任意多边形三角剖分来构建约束三 角网的算法。 、研究基于t i n 和凸壳的等高线追踪算法。 2 2 国内外研究现状及存在问题 2 1 国内外研究现状 2 国内外研究现状及存在问题 不规则三角网模型t i n ( t r i a n g u l a t e di r r e g u l a rn 咖o r k ) 是d e m 中一种很重要的模 型，也是最基本的一种网络，既可适应规则分布数据，也可适应不规则分布数据；既可 通过对t i n 的内插生成规则格网，也可根据t i n 直接建立连续或光滑表面。因而t 狲 也是g i s 数据表达、管理、集成和可视化的一项重要内容，也是地学分析、计算机视觉、 表面目标重构、有限元分析、道路c a d 等领域的一项重要的应用技术【6 j 。 t i n 作为d e m 构建的基本方式，文献【6 】依据数据源和产生过程的差异，将其分为 基于离散点、基于规则格网、基于等高线和基于混合数据四类，而每类又根据构网过程 中是否需要破坏原有三角网分为静态和动态构网两种，如表2 1 所示。 表2 1t i n 的产生和分类6 1 本文重点研究二维离散点的数字高程模型构建算法，所以在此只介绍基于离散点的 生长法、分治( 分割合并) 和逐点插入三种算法的基本思路和优缺点。 三角网生长算法基本思路：首先找出离散点集中相距最短的两点，连线成 d t i n ( d e l 啪a y t i n ) 的初始基线；然后按d t i n 的判断法则找出包含此基线的d e l u a n a y 三角形的第3 端点，该端点应位于基线右侧；连接新点与原来两点形成两条新边；再按 d t i n 的判断法则找出包含此两边的另外两个d e l u a n a y 三角形的第3 端点；依次循环 处理所有新生成的边，直到所有离散点均为d t i n 的端点【6 】。算法思路清晰，实现简单， 但效率不高，在此基础上有许多改进算法，其改进点主要集中在“第三点 的搜索和三 角形全等的判断上【i j 。 分治算法基本思路：首先将数据排序，分成两个互不相交的子集，在每一个子集中 建立t i n 后，将两个t i n 合并以生成最终的d t 烈。也可以将数据分成垂直条块，再 用相交边界将条块分为区域，然后用带约束条件的局部优化法则将对角线进行交换。不 同的实现方法主要区别在于点集划分、子三角网生成与合并方法的不同。总体上，分治 3 西安科技大学硕士学位论文 算法以递归方式将数据排序成大小相同的单元子集，直至每一个单元子集都能同样处 理。一个规范的单元子集包括3 6 个点，使用其中的前3 个点生成一个三角形，然后 将其余点逐个插入即可建立各单元子集的局部d t i n 。最后，从单元子集开始，将其局 部d t 州合并；依次往上进行合并，直到生成最终的全局d t i n 。分治算法的合并原则 是：同层优先，由下往上，递归进行【6 1 。该算法将复杂的问题简单化，但其数据分区、 凸壳搜索比较耗时，在编程实现上过于复杂。 逐点插入法基本思路：在一个包含所有数据点的初始多边形中，将未处理的点逐次 加入到已经存在的d t 烈中，每次插入一个点后，将d t i n 重新定义。逐点插入法有 多种不同实现方式，其差别主要在于定义的初始多边形不同，如超三角形、矩形等【6 j 。 从构网过程来看，三角网生长法和分治算法属于静态构网，在整个三角网形成过程 中，已形成的三角网不会因为新点的的介入而破坏。逐点插入法则是一动态过程，新点 的插入会导致已有三角网改变。实际应用中，由于数据域的引入和对象的动态变化( 如 景观改造、地表沉陷、道路建设等) ，需要对已有的数字地形模型不断进行动态修改， 即插入新的数据点和删除己变化的数据点，从而实现对模型的更新，保持模型的现势性。 为了不影响模型的完整性，必须在一个有限的范围内完成模型的更新工作，并维护已有 的拓扑关系。因此，算法的选择与效率是关键【6 j 。 基于离散点的t 构建可分静态和动态两种构建模式，动态如逐点插入法：而前者 则有生长算法、分治算法、凸包算法、辐射扫描算法和改进层次算法等。目前较为常用 的分治和逐点插入及两者结合的算法。 2 2 存在问题 基于前述分析，目前国内外的t i n 网构建算法较多，不仅在专著( 如文献【1 ，2 ，6 】) 中 有专门介绍，而且期刊杂志上的算法也层出不穷( 如文献 1 0 2 7 】) ，但还存在以下问题： 、分析目前数字高程模型建模算法，论述时面向的只是专业学者和研究者，而没 有兼顾一般读者，且涉及的范围广而深度不够，多数只有算法思路，没有详细的算法设 计和步骤。如t i n 构建相关算法，要用代码实现或者在此基础上对算法进一步研究改进， 必须具有深厚的计算机编程功底，对于不擅长于计算机语言，但有志于数字高程模型或 者三维建模的读者和爱好者，进入的门槛过高。 、查阅数字高程模型建模相关的硕博论文，不乏创新者，但多数还是专著和期刊 的引用，自我创新思想较少，也是全而不深，内容多，深度不够。对于后学者，开拓思 路、抛砖引玉的作用不显著。 、目前还没有专门针对数字高程模型建模及其相关算法详细文献资料( 及硕士论 文) ，即缺少t 网构建、编辑、约束和等高线追踪系统、详细的算法。 4 2 国内外研究现状及存在问题 2 3 技术路线 基于以上分析，当前数字高程模型构建算法多且成熟，选择任何一种算法都可以完 成对t i n 网构建、编辑、约束和等高线追踪系统详细的算法研究。但如何完善和改进当 前算法，寻找提高效率的突破口，才是本文研究的一个关键性问题。 算法是指为了完成某项特定工作所设计出的一连串用来说明工作是如何被完成的 步骤，简单的说，算法是一个具有次序、步骤清楚，最后一定会执行结束的可执行步骤。 所有算法必须满足5 个条件【7 j ： 、输入，不具有输入数据或具有多个输入数据。 、输出，具有一个以上的结果输出。 、定义明确，每一个步骤的语句必须很明确。 、有限的步骤，按照算法所描述的步骤执行，在有限步骤内，一定会结束。 、有效地步骤，算法中的每一个步骤必须是基本的指令( 即使是用纸和笔也可以 完成计算) 。 唯一可以客观的判断算法好坏的是“算法运行效率”，即该算法是否能以最短的时 间以及最小的空间来运行出结果【7 】。但是“时间”与“空间”常常是“鱼与熊掌无法兼 得，所以就需在算法设计时，具体问题具体分析和对待，以便有所倾向。对于“空间 ， 本文采用链表数据结构，可动态变化；而对于“时间 效率将是本文研究重点。 使用任何编程语言的算法，归根结底是要落实到计算机硬件上实现，而计算机实现 指令耗费的时间是不同的，由文献 8 ，9 】可以得到计算机整数算术运算所需时钟周期，如 表2 2 所示。 表2 2 整数运算指令效率比较 由表2 2 可知，在计算机中央处理器c p u ( c e n t r a lp r o c e s su n i t ) 频率相同条件下( 以 p e n t i u m 为例，不考虑浮点数计算) ，整数加减法计算机耗时是相同的，而整数乘法耗时 是加减法的1 0 倍，整数除法耗时是加减法的4 1 倍。即使随着计算机c p u 频率的大幅 提高，算术运算的计算机耗时总是如下： 加减耗时 o 。 、如果点p 在有向线段三上，则f ( x ，y ) = 血+ 砂+ c = o 。 、如果点p 在有向线段三的右侧，则f ( x ，y ) = 血+ 缈+ c d 2 ，按if ( x ，少) i 计算的值，同样是d 1 d 2 。 3 2 2 三角形矢量面积 设有向线段尸，n 坐标为 ，y ，) 和( 砀弦) ，点n 伍d ，y 矽为任意点，尸j n 与尸d 组成的三 角形尸尸鼎矢量面积s 如下式： s = ：一y 。妇。一x 。) 一。一y ，：一x 。) ) 9 西安科技大学硕士学位论文 如果s o ，则n 位于有向线段左侧；如果s = o ，则p o 位于有向线段或其延长线上； 如果s 0 ，则p o 位于有向线段右侧。在应用中只关心s 的正负号，所以将上式简化后的 三角形矢量面积公式如下： s = 2 一y 1 ) ( x o x 1 ) 一( y o y 1 ) ( 2 一石1 ) ( 3 3 ) 如图3 4 中( a ) 所示，点尸d 位于有向线段尸，尸2 的右侧，三角形尸j n n 的矢量面积s 为负。( b ) 中三角形尸，尸2 乃为逆时针顺序，点p d 位于三角形p ，p 以中，所以三角形p ，脚d 、 p 如、尸护，岛的矢量面积均为正。通过点与有向线段组成的三角形矢量面积符号即可 判断点与有向线段和三角形的拓扑关系。 【劬 ( b ) 图3 4 三角形矢量面积 3 3t m 的构建算法 对原始离散数据进行预处理后，就可利用原始数据构建t i n 网，首先求解凸壳，然 后再对凸壳进行三角剖分和l o p 优化，最后将非凸壳点采用逐点插入法运用l o p 法则插 入已有的初始t i n 网。 3 3 1 二维离散点凸壳求解 凸壳是数据点的自然极限边界，为包含所有数据点的最小凸多边形，连接任意两点 的线段必须完全位于该凸壳多边形中，同时区域的面积也达到最小值【l 】，也相当于一条 包围数据的最短路径【2 】。凸壳求解算法在许多领域有着广泛的应用，是g i s 中构建t n ( a ) 图3 5 格雷厄姆凸壳生成算法川 1 0 ( c ) 3 数字高程的建模算法 分割合并算法和逐点插入算法不可缺少的步骤。 传统的典型凸壳算法如格雷厄姆算法、卷包裹法、快速凸包算法、分治算法等。比 较常用的格雷厄姆算法的时间复杂度为o ( n l 驴) ( n 为数据点个数) ，算法步骤如下【l 】： 、找出点集中纵坐标最小的点p l ，如图3 5 ( a ) 。 、将p l 和点集中其他各点用线段连接，并计算这些线段与水平线的夹角。 、按夹角大小对数据点进行排序，如果夹角相同，则按距离排序。设得到的序列 为p l ，p 2 ，p n 。 、依次连接所有点，得到一多边形，如图3 5 ( b ) 。显然，p l ，p 2 ，p n 是凸壳 边界上的点。然后根据“凸多边形的各顶点必在该多边形的任意一条边的同一侧 这一 定理，除去边界序列中的非凸壳顶点。最后，得到凸壳点集，如图3 5 ( c ) 。 按照算法的关键步骤来分析，格雷厄姆算法的关键步骤中会涉及到角度的计算，具 体来说，就是格雷厄姆算法的第步需要计算一些线段与水平线的夹角，其时间复杂性 为o ( n l o g n ) ，尽管格雷厄姆算法是求解平面点集凸壳的最佳算法，但是角度计算的计 算机实现是很费时间的，由于角度计算的引入，即使是求整数平面点集的凸壳也会引入 浮点运算，因而仅仅靠比较算法的整体时间复杂性来判断算法的优劣是不够的，还应该 从计算机的实现角度更多地关注实现算法的每一关键步骤的时间复杂性【l5 1 。 文献 1 5 】详细分析了传统的典型算法的优点和不足。并从计算机实现角度出发来降 低关键算法的时间复杂性，以局部最优才能全局最优为规，运用合理简化后的距离判断 式为矩，彻底抛弃了角度运算，仅以加、减、乘和比较运算，在前人的基础之上加以创 新，探索出了一种新的求解凸壳的算法。但是还存在极值点分布情况不全，算法任需分 情况讨论的缺点。本文在完善和改进文献【1 5 】算法的基础上，构建了一种新的求解凸壳 的自适应算法【l ，简单高效。在插入点时，可以根据点的范围来动态扩展凸壳，满足网 外点的插入。 对于任意二维点集，分别寻找点集中x 和y 坐标值最大最小点，可得四组数据点脚、 胁、k 和加，然后对x 组寻找y 坐标值最大最小点，对】，组寻找x 坐标值最大最 小点。这样，可找到8 个初始极值点e l e 8 ，依次按小价k 和斌顺序将搜 索到的极值点存储到链表c o n v e x h l i s t 。删除c o n v e ) 【i l l i s t 中的重复点，会有3 8 个点的 6 种情况，将c o n v e x h l i s t 中的点及首尾依次连接，可得一封闭图形。如图3 6 所示为8 极值点都不同的一种情况。由点与有向线段关系可知，沿着图形的逆时针方向，对于其 内侧的点，和任意一条有向线段计算得到的舷值，都为正；而对其外侧的点，有正 有负，但只有在有向线段右侧的点为负；对于f 似纠值为o 的点，不会成为凸壳点，可 归类到内侧点。由于水平和竖直线段外侧不会存在二维点，所以可将二维点集分为s 、 s l 、s 2 、s 3 和s 4 子集，内侧点为s 子集，外侧点会出现3 或4 个子集。 西安科技大学硕士学位论文 e 7 e 5 b 图3 6 子集的分区图3 7 子集凸壳极值点的追踪 对外侧点集逐个分层搜索就可以求解出二维点集的凸壳。以s l 子集为例的算法步 骤： 、如果s l 子集不为空，则搜索s 1 中相对于有向线段e 2 e 3 的讯纠值最大点i m 戕， 如有好几个，取两端点，如图3 7 中i m 缸和i m i n 两个点，存储到子集极值点链表e x t r e m e l i s t 中。这样第一层的极值点和原有的e 2 和e 3 又组成新的有向线段e 2 i m 舣、i m a xe 3 或者e 2 i m 附 i m 觚i m i n 、i m i ne 3 ，接着将s l 位于这些线段左侧和线上的点删除，只保留右侧点，即只保 留撇值出现负值的点。 、判断s l 是否为空，若为空，则s l 中的凸壳点追踪完毕，若不为空，则继续逐条 搜索s l 中的点相对于上一步追踪出的极值点组成的有向线段的舷值最大点i m 觚，如有 好几个，取两端点，这样每条线段又可搜出o 2 个极值点，存储到子集极值点链表 e x t r e m e l i s t 的对应位置。保留s l 中位于这些线段右侧的点。 、判断s l 是否为空，若为空，则s l 中的凸壳点追踪完毕，若不为空，继续执行第 步。 每个子集通过这3 步，可以搜索出子集的极值点，将这些极值点插入基本极值点的 相应位置，四个子集都搜索后，即为求解的凸壳。这种自适应算法，没有除法和角度运 算，只有加、减、乘和比较运算，简化了距离计算，时间复杂度低。较文献 1 5 】不仅考 虑全面，而且避免了分情况讨论，更适合逐点插入法的速度要求。 3 3 2 多边形三角剖分 凸壳三角剖分相对于任意多边形考虑的问题就简单一些，只需按一定顺序和规则连 接凸壳的边就可以，常用环切边界剖分法。任意多边形三角剖分在点删除时用到，相对 凸壳较为复杂。 ( 1 ) 凸壳的三角剖分 环切边界剖分法：首先在凸壳链表中每次寻找一个由相邻两条凸壳边组成的三角 形，而在该三角形的内部和边界上都不包含凸壳上任何其他点。然后将这两条凸壳边的 公共点去掉，得到新的凸壳链表。重复以上过程，直到凸壳链表中只剩下3 个离散点为 1 2 3 数字高程的建模算法 止。将凸壳链表中的最后3 个点构成一个三角形，该三角形同已经找到的三角形形成整 体，成为凸壳三角剖分结果【6 j 。算法步骤如下： 设l p o i n t 、l e d g e 、l t r i 分别为t i n 网的点、边和三角形链表，m 曲x a 、ma _ t r i x b 和 m a t r i x c 为3 维数组，v e r t e x 【3 】为点节点数组，c h u l l “s t c o p y 为凸壳链表的拷贝；将 c h u l l l i s t c o p y 的首节点赋予数组m 撕x a ，由凸壳数据创建点链表l p o i n t 。 、搜寻c h u l l l i s t c o p y 中m a n i x a 及其后的2 个节点m a 仃i x b 和m a t r i x c 。若其后 有2 个节点，则继续步；若没有2 个节点，则凸壳三角剖分结束。 、将点链表l p o i n t 中数据为m a t r i x a 、m a t r i x b 、m a t r i x c 的点节点分别赋予v e n e x ， 由v e n e x 创建当前三角形的边和三角形节点，存入边链表l e d g e 和三角形链表l t r i ，并 修改边相应的拓扑关系。 、删除两条凸壳边的公共点，即c h u l l l i s t c o p y 中数据为m a t r i x b 的节点，将数 据为m a n 仅a 的节点移动到链表尾部；m a t r i x c 赋予m a n 议a 。 、如果c h u l l l i s t c o p y 为空，则凸壳三角剖分结束；若不为空，则继续执行步。 ( 2 ) 任意多边形的三角剖分u 妇 任意多边形三角剖分时，需要满足两个条件：第一是剖分的三角形边不能在多边形 外部，如图3 8 ( c ) 所示，剖分的三角形p 6 p 7 p 8 的边位于多边形外部；第二个是剖分的三 角形不能包含多边形其它顶点，如( b ) 所示，剖分的三角形p l p 2 p 3 包含顶点p 4 和p 7 。 q p 为多边形点链表，三角剖分步骤如下： 、判断q p 包含的顶点数，如果等于3 ，将这3 个顶点组建三角形，三角剖分结 束；如果大于3 ，继续步。 、从q p 的首节点依次取3 个顶点p i 1 p i p i + l ，判断三角形p i 1 p i p i + 1 的p i 点是否在 有向线段p i + lp i 1 右侧( 三角形p i + l p i 1 p i 的矢量面积符号为负) ，若在，跳过p i _ 1 点，并将 其移到q p 尾部，从p i 点开始执行第一步。否则，执行步。 图3 8 多边形三角剖分 1 3 西安科技大学硕士学位论文 、判断三角形p i - l p i p i + l 是否包含q p 中的其它顶点( 即其它顶点与三角形p i - l p i p i + l 的3 个矢量面积全为正) ，若包含，跳过p i - l 点，并将其移到q p 尾部，从p i 点开始执行 步。若不包含，则组建三角形，删除q p 中的p i 点，继续执行步。 如图3 8 ，( a ) 中为一任意多边形q p ，依次取顶点p 1 p 2 p 3 组建三角形，如图( b ) ，三 角形包含多边形其它顶点，不满足第二个条件，跳过p l ，判断p 2 p 3 p 4 ，满足两个条件， 删除q p 中的p 3 。继续判断三角形p 4 p 5 p 6 ，满足条件，删除q p 中的p 5 。三角形p 6 p 7 p 8 的边p 8 p 6 在多边形外部，不满足第一个条件，如图( c ) ，跳过p 6 ，判断三角形p 7 p 8 p l ， 满足条件，如( d ) 。最终剩余p 7 p l p 4 ，组建三角形，多边形剖分结束，如图( f ) 。该剖分方 法容易理解和实现，判断中只用到加减乘和比较运算，执行效率高。完全可以满足点删 除对任意多边形三角剖分的速度要求。 ( 3 ) 三角剖分后的l o p 优化 对多边形三角剖分形成的初始三角网未必是d e l 啪a y 三角网，所以还需要对其运用 l o p 法则进行优化。逐点插入时的优化可以用堆栈，因为每次只针对涉及到的已存在边 邻接三角形检查优化；在对初始三角网进行优化时，不能用堆栈，因为没有初始d e l u a n a y 三角网，需要对所有三角形进行检查优化。所以采用整体法，利用控制标记，只有对所 有三角形计算空外接圆系数时都小于等于o ，才是结束循环的条件。算法步骤如下： 、将初始三角网的个数赋予整形变量e n d f l a g ，给整形变量c i r c l e f l a g 赋初始值o ， 定义三角形节点指针c l 】玎e n t p t r 。 、如果e n d f l a g 等于c i r c i e f l a g 为真，则优化结束：若不为真，将e n d f l a g 值赋予 c i r c l e f l a g ，将三角形链表尾节点指针赋予c u r r e n t p 仃，执行步。 、如果c u r r e n t p t r 为空，则执行步；不为空，将c u l l r e n t p 打赋予当前三角形节点 t o p 晡，则从当前三角形的第一条边判断否满足空圆法则，若不满足，交换相应对角线， 并修改相关三角形和边的拓扑信息，c i r c l e f l a g 自减1 ，执行步；若满足，继续判断当 前三角形的下一条边，直到3 条边检查完毕。 、如果e n d f l a g 不等于c i r c l e f l a g 为真，执行步；若不为真，将指针指向c l l n - e n t p t r 的前一个节点，执行步。 3 3 3 点的融和定位算法 将搜索的凸壳三角剖分优化为初始三角网后，即可采用内插法将非凸壳点逐个插入 已构建的三角网中。逐点插入时，需要首先确定点在已有三角网中的位置，然后再将其 插入该三角形，最后局部优化，使新构建的三角网满足l o p 法则。 一般将在三角网中查找包含插入点的三角形算法称为点定位问题。数字地面模型的 更新、局部高程内插、c d t 心( c o n s t r a i n e dd e l a u n a y t 烈) 构建和模型叠加都需要用 到点定位。为此点定位算法的总结和改进研究具有现实意义。 1 4 3 数字高程的建模算法 计算机是基于o 、l 的二进制计算方式，只能直接计算加减，乘除运算是通过多步 移位和加法运算实现，运算的次数和被乘数的二进制的位数成正比。由表2 2 可知，对 于配置相同的计算机，加减法的计算就要比乘法快，而乘法比除法快。所以算法的优略， 通过比较其计算机计算步骤就完全可以判断。对算法的设计和优化，也可以通过减少计 算步骤和改变运算方式来达到目的。 当前流行和有效的点定位算法主要思路为“先跳后走 【l ，1 6 1 ：即首先确定第一个首 三角形，然后利用各种数学方法判断点是否在三角形中，若不在，再利用三角形拓扑关 系判断下一个三角形，直到查询到包含定位点的三角形。首三角形的确定可采用分块建 立点和三角形区域索引1 ，1 6 ，1 7 ，1 9 1 ，或者通过对三角网顶点进行索引的方法解决【1 8 】，本文 对此不予阐述。点在三角形中的判断和下一个需要判断三角形的选择问题，出现了较多 算法。文献【l ，1 6 】利用建立的三角形间的拓扑关系和三角形面