第23卷 第2期重 庆 交 通 学 院 学 报2004年4月Vo1 23No 2JOURNAL OF C HONGQI NG JIAOTONG UNIVE RSI TY Apr.,2004基于不规则三角网的DTM若干问题的探讨赖鸿斌, 李永树(西南交通大学测量工程系,四川成都610031)摘要:介绍了用不规则三角网(TIN)建立数字地面模型(DTM)的基本思路,讨论了在建模过程中所遇到问题的解决方法,分析了混合模型的应用问题及TIN数据结构.最后,运用实例说明了由TIN生成的DTM在工程中的应用方法.关 键 词:不规则三角网;数字地面模型;数据结构中图分类号:U412 24 文献标识码:A 文章编号:1001 716X(2004)02 0090 04数字地形模型(Digital Terrain Mode,简称D TM)是表示地形表面的数学(数字)模型.从数学的观点看,地面模型是一个空间连续函数,或是地形模型的离散化表示.对地形表面进行表达的各种处理可称为表面重建或表面建模,重建的表面通常被认为是DTM表面[1].DTM的核心是地面特征点的三维坐标数据和一套对地表提供连续描述的算法,最基本的DTM至少包含了相关区域内平面坐标(X,Y)与高程Z之间的映射关系,即Z=F(X,Y) (X,Y) DTM所在区域[2].目前,DTM模型的建立和利用已成为地理信息系统的重要组成部分.1 基于不规则三角网建立DTM地形表面的建模主要有4种方法:基于点的建模方法、基于不规则三角形的建模方法、基于规则格网的建模方法和混合建模方法[1],其中用得较多的是基于不规则三角形的建模方法和基于规则格网的建模方法.基于不规则三角形建模是直接利用野外实测的地形特征点(离散点)构造出邻接的三角形,从而组成不规则三角网结构.相对于规则格网,不规则三角网具有以下优点:利用原始资料作为网格结点;不改变原始数据和精度;能够插入地性线以保存原有关键的地形特征,以及能很好地适应复杂、不规则地形等.不规则三角网(TI N)作为一种主要的DTM表示法,虽然其生成算法比较复杂,但却有许多优点.根据生成三角网算法的不同,可以将生成三角网的算法分为以下三种:分而治之算法、数据点逐次插入算法和三角网生长算法[1].分而治之算法的思想以及生成V 图的分治算法最先是由Shamos和Hoey提出的.Le wis和Robinson将分而治之算法思想应用于生成三角网并给出了一个简化算法:即递归地分割点集,直至子集中只包含三个点而形成三角形,然后自上而下地逐级合并生成最终的三角网;数据点逐次插入算法的思想是由Lawson提出的,以后,Lee和Schachter、Sloan、Watson、Pareschi和Macedonio、Puppo 和Floriani等人先后对这一算法做进一步的改进和完善;三角网生长算法是由Green和Sibson在1978年首先给出的.后来,Reif、Maus和Brassel等人也发表了类似的算法.下面主要讨论利用三角网生长算法来构建不规则三角网.如图1所示,在数据点集中任取一点A,查找距图1 其始三角形的确定收稿日期:2003 02 21;修订日期:2003 06 19基金项目:国家自然科学基金项目(40371098)资助作者简介:赖鸿斌(1978-),男,福建莆田人,硕士生,从事3S的应用研究.离此点最近的点B 作为三角形的第二个顶点,相连后以AB 的连线作为基线.然后再从附近的点中选取第三个顶点C .选取时主要有以下几种准则:1)空圆准则[1]:在TI N 中,过每个三角形的外接圆均不包含点集中的其余任何点(图2a).2)最短距离和准则[3]:在TI N 的每个三角形中,一点到基边两端的距离和最小(图2b).3)最大最小角准则[1]:在TIN 的两个相邻三角形形成的凸四边形中,这两个三角形中的最小内角一定大于交换凸四边形对角线后形成的两三角形的最小内角(图2c).4)张角最大准则[3]:在每个三角形中,第3点到两基边的张角为最大(图2d).图2 T IN 的三角化准则当起始三角形构建后,以起始三角形的三边作为基边依次向外扩展,直至将点集内所有的离散点都构成三角网为止.需要注意的是,虽然目前计算机的存储能力和计算速度在不断地提高和加快,但在搜索最佳点构建不规则三角网时,如果对所给的每个点都按某种准则进行搜索,就会减慢搜索的速度,从而影响构网的效率.对于小数据量,效果不明显;而对于大数据量进行构网则会显得非常耗时.因此,在构网时,我们应事先把数据点集按某种规律进行分块存储,这样可以大幅度地提高搜索的速度,从而减少构网的时间.具体方法如下:在初次调入原始数据时,先计算出原始点集中X ,Y 的最大值和最小值:X max 、Y max 、X min 、Y min ,则所有的点均落在(X min 、Y min )、(X min 、Y max )、(X max 、Y min )、(X max 、Y max )4点构成的矩形区域内;然后将此矩形划分成适当数量的正方形格网;最后计算各点落入的网格并统计每一网格存储有哪些点,记录下来.当搜索第3点时,我们首先确定底边之中点P 所在的网格,搜索此网格内所有点,直到找到一个距P 最近的点.为了确保找到的点是最近的点,还需要补充此网格周围的8个网格.若在P 点所属网格内没有点,则需对该网格周围8个网格分别做与上面情况同样的处理.2 特殊地貌和地物的处理由于实际地貌、地物的复杂性,因此,在TI N 生成的过程中,还应考虑对特殊地貌和地物的处理,即将地形特征点作为模型的顶点,地形特征边和地物作为模型的限制边参与建模,使得所生成的不规则三角网的顶点包含地形特征点,边包含地形特征线和地物.把地性线、地物和断裂线等作为约束条件构建不规则三角网,可有效消除TIN 中的 平三角形和不合理的三角化现象,从而保证所生成DTM 的正确性[2].2.1地性线的处理由于不规则三角网结构的DTM 是以三角形为基本单元表达实际地形,所以,山脊线、山谷线等地性线就不应该通过TIN 中的任一三角形的内部,否则三角形就会 进入 或 悬空 于地面,与实际地形不符,产生的数字地形模型有误[4].因此,在原始数据的采集过程中,必须用特征码记录地性线的编码信息.当构造TI N 时,应使地性线作为约束线段(强制线段)来处理,即作为三角网的一条边,以此作为基线向外扩展三角形(图3).这样,就保证了实际地形和DTM 相符,从而提高DTM 的精度.其处理的具体步骤如下:a)调整前三角网 b)调整后三角网图3 含有地性线的不规则三角网1)利用原始数据点集建立初级的不规则三角网;2)在初级三角网中插入一约束线(地性线);3)确定边界与约束线段相交的三角形,如果两个这样的三角形有公共边,则将此公共边删除,最后形成带约束线段的影响多边形(影响区域);4)将影响多边形其它顶点与约束线段的起始点相连;5)应用带约束条件的局部最优方法(LOP Lo cal Optimization Procedure)交换凸四边形的对角线,以更新影响多边形内的三角形,使约束边成为三角网中的一边;91第2期 赖鸿斌,等:基于不规则三角网的DTM 若干问题的探讨6)重复上面4步,直至所有约束线段都加入到三角网中.2.2地物的处理由于房屋、河流、池塘等地物的内部标高基本上是一致的,所以,在建立DTM 时,应该将它们作为闭合区域来处理.具体的处理方法是:首先按处理地性线类似的方法调整三角网;然后,利用 射线法 或 垂线法 判定三角网中各三角形的重心是否落在该区域内.若是(即 射线 或 垂线 与地物边界的交点个数为奇数2n +1个),则消去该三角形;若不是(即 射线 或 垂线 与地物边界的交点个数为偶数2n 个),则保留该三角形.经测试后,除去所有重心落在地物区域内部的三角形,从而形成 空白区域 .最后,在扩展三角形时,应以地物的边线作为一条基边向外扩展.3 不规则三角网与规则格网的混合模型TI N 模型的主要优点就是可以根据地形的起伏变化而改变采样点的密度,并决定采样点的位置.这样既能避免地形起伏不大地区产生冗余数据问题,从而节省存储空间,同时,TI N 还能根据地性线、地物等来生成符合实际地形情况的DTM.但是,正是这些优点导致了其数据存储与操作的复杂性[1],不便于规范化管理.因此,在实际应用中,应将不规则三角网与规则格网结合起来形成混合模型,用来表示DTM.图4 TIN 和规则格网的混合模型在混合表面建模中,大部分的软件是首先根据系统格网采样建立初级的正方形和三角形,初级网构建后,如果数据中还包含地性线,则规则格网进一步分解成局部不规则三角网(图4).4 TIN 数据结构TI N 的数据存储方式比格网DTM 复杂,它不仅要存储每个点的高程,还要存储其平面坐标、节点连接的拓扑关系、三角形及邻接三角形等关系.目前,国内外已有很多学者对TI N 拓扑结构的存储方式作了深入的研究并给出了其数据的存储结构.表1是对应于图5的不规则三角网的一种表示方法,包括点数据结构、边数据结构和三角形数据结构,其各自的数据结构用C 语言定义如下:表1 TIN 的数据结构点边结点点号坐标三角形相邻三角形三角形结点1x 1,y 1,z 1A B ,E A 1,2,62x 2,y 2,z 2B C ,A B 2,3,63x 3,y 3,z 3C F ,D ,B C 3,4,64x 4,y 4,z 4D H ,E ,C D 4,5,65x 5,y 5,z 5E D ,A E 5,6,16x 6,y 6,z 6F C ,G F 3,7,47x 7,y 7,z 7G F ,H G 7,8,48x 8,y 8,z 8HD ,GH8,5,4图5 TIN 的平面图形点数据结构Struct Point{float x,y,z; 三维坐标}*Ppoint 边数据结构Struct Line{int firstIndex,lastInde x ; 起点坐标int Tri1,Tri2; 左右三角形号}*Pline 三角形数据结构Struct Triangle{int iPoint1,iPoint2,iPoint3; 三角形三个点号int Tri1,Tri2,Tri3; 左右三角形号}*Ptriangle5 实际应用用不规则三角网生成的DTM 在工程中应用十分广泛,例如在铁路、公路的勘察和设计工作中,可利用DTM 生成等高线,绘制断面图、坡面图,以及立体透视图,并计算测区的面积、土方量等.下面实例就是利用野外测量的原始数据生成不规则三角网,从而绘制该测区的等高线.表2是利用Leica 全站仪配合电子手簿在某高速公路测区采集的部分原始资料.由于受各种因素的影响,必须对所采集的原始数据进行一些适当的92 重庆交通学院学报 第23卷表2 某高速公路段采集数据编号X Y Z 1589 820567 88050 1002547 880551 08049 6003561 120551 08048 6004505 490574 69053 3005513 170561 73051 300 40553 027536 81744 19841539 855528 03142 52542528 879516 10141 96643500 000500 00050 000(比例尺1 1000 等高距1m)图6 生成的不规则三角网和等高线处理才能够满足实际应用的需要.当数据处理后进行构网时,应考虑对地性线、地物等的处理,最后,利用基于不规则三角网的DTM 生成等高线.在等高线的生成中,一般先追踪生成折线等高线,然后,以一定的拟合方式(例如张力样条拟合、三次B 样条拟合、SPLINE 拟合等)生成曲线等高线.图6是利用三次B 样条拟合方式生成比例尺为1 1000、等高距为1m 的测区等高线.6 结束语利用基于不规则三角网的D TM 生成等高线、断面图,以及计算土方填、挖量等,从根本上改变了传统的作业方式,大大提高工作效率.近几年来,随着计算机软件、硬件、网络及测绘手段的不断改进,DTM 必将具有越来越广泛的应用.参考文献:[1] 李志林,朱 庆.数字高程模型[M].武汉:武汉大学出版社,2000.[2] 杨德麟.数字高程模型[J].测绘通报,1998,(3):37 38.[3] 刘学军,符锌砂.三角网数字地面模型的理论、方法现状及发展[J].长沙交通学院学报,2001,(2):24 30.[4] 谢祥根,符锌砂.考虑地形特征的三角网数模建立方法[J].中国公路学报,2000,(1):10 13.Discussion of several problems in DTM based on TINLAI Hong bin, LI Yong shu(Department of Surveying Engineering,South west Jiaoton g Universi ty,Chengdu 610031,China)Abstract :A method of estabisihing digital terrain models(DTM)with TIN is introduced,and problems during modeling are discussed in the paper.Furthermore,application problems about the hybrid model,as well as the data structure of TIN,are analyzed.In the end,the method of applying DTM based on TIN in engineering is illustrated.Key words :TIN;DTM ;data structrue责任编辑:袁本奎93第2期 赖鸿斌,等:基于不规则三角网的DTM 若干问题的探讨。