由矢量电子海图构建海底 TINDEM方法研究

矢量电子海图是目前常用的航海设备,但它只能以水深点和等深线等二维信息表达海底地形,存在表达不直观、不利于地形分析等缺陷.数字高程模型(digitalelevationmodal,DEM)是对地球表面地形的离散数学表达,是在地形采样基础上对地形表面进行的重建.矢量电子海图中包含了详细的水深和岛屿海岸线信息,利用这些二维信息构建海底DEM,使可观测维数增加,表现力更加丰富.DEM通常是将有限的采样点用某种规则连接成一系列的曲面或平面片来逼近原始曲面,根据连接规则的不同,DEM有不同的数据结构,其中规则格网DEM(gridDEM)和不规则三角网DEM(TINDEM)是目前两种主要的数据结构.海图中的水深点基本上是呈密度不均匀的菱形分布[1],岛屿海岸线是不规则的曲线,TIN模型可以很好地适应这样的数据特点,所以选择TIN作为表达海底DEM的数据模型,它的缺点可以通过较好的设计克服.TIN模型的基本要求:1)力求最佳的三角形形态,即每个三角形尽量接近等边三角形;2)保证最邻近的点构成三角形,即三角形边长之和最小;3)TIN是唯一的.研究表明,在所有TIN中,基于DT(Delaunaytriangulation)规则构建的D-TIN满足上述要求最为出色,是给定区域的最佳三角剖分[2].海图中岛屿边界、海岸线是典型的特征约束,对于带约束条件的区域,需要按CDT(constrainedDelaunaytriangulation)规则来构建约束Delaunay三角网(简称CD-TIN).

1海底CD-TINDEM构建方法

1.1主要的数据结构

各国研究人员已经提出很多构建DEM的方法[3-4],其中数据结构的设计对方法效率有重要影响,下面是本方法所使用的数据结构.

Triangle记录三角形信息,包括三角形编号、3个顶点索引、是否与边界线段相交的标志位、3个邻接三角形指针(没有则为NULL)、链表前后节点指针;TriIndex为三角形指针链表;Edge记录边或线段的信息,包括边编号、起点终点索引、左右三角形指针、使用次数;Vertex表达点状要素(水深点、边界线上的点),包括点编号、横纵坐标、水深值、所属边界线指针、所属三角形指针链表头、点链表中下一个节点指针;LineNode表达边界曲线线状要素,包括曲线编号、曲线上点的个数、曲线上一个点的横纵坐标、高程值、该点为所属曲线的第几个点、曲线上下一个点的指针、下一条曲线的指针.

1.2方法概述

提出由矢量电子海图数据构建海底地形CDTINDEM的方法包括:数据读入、边界线化简、初始三角网构建、边界线嵌入、区域合理边界表达、DEM输出6部分.

1)从电子海图(electronicnavigationchart,ENC)的数据文件中提取水深要素和岛屿海岸线要素作为数据源,航道组织还会定期或不定期以航海通告的形式对海图进行补充和修改,如果航海通告中有关于水深或海岸线的内容,也要把这部分内容读入.

2)在矢量海图中,岛屿边界线由一系列密集的点连接而成,边界点密度比水深点密度(以邻点间的平均距离计)大10倍左右(统计值),由于2类要素的数据分布密度相差一个数量级,所以在边界线附近会有狭长三角形出现,网格质量对地形的显示和地形分析都有重要影响.通过对边界曲线进行适当化简,在保持边界曲线形态和所围区域面积基本不变的情况下,删去一些对形态特征贡献小的点,使边界点间距适当扩大,可以提高边界线附近三角形的质量;另外,由于化简减少了数据量,构建耗时降低,方法见2.1节.

3)把化简后的边界点与水深点统一进行标准DT剖分,得到初始D-TIN.DT剖分算法很多,有逐点插入法、生长法、分治法等[3],这里使用生长法.

4)边界点的分布相对水深点的分布较密,即使化简后,大多数情况下一条边界线段的长度也要比D-TIN的平均边长小3~10倍(统计值),所以边界点所属三角形的顶点中通常会包含此点在边界曲线上的前后邻点,即边界线段通常已被包含在D-TIN的边集中;少数情况下(试验统计不超过边界线段总数的10%),可能出现边界线段没有被包含在初始D-TIN中的情况,为保证在TIN中包含这些边界特征,需要嵌入这些未被包含的边界线段,得到初始CD-TIN,方法见2.2节.

5)初始CD-TIN网格分布范围与数据分布范围并不吻合,需要采用一定的方法使区域的合理边界得到表达[4],方法见2.3节.

6)与GridDEM的规则阵列相比,不规则三角网DEM的存储结构要复杂得多,由于三角形的不规则性,TIN不仅要存储每个节点的高程,还要存储其平面坐标,节点连接关系和邻接三角形等拓扑信息,使三角形定义及其与相邻三角形的关系显式地表达出来.CDTIN的存储结构有特征线链表、三角形链表和点数组三部分,如图1所示,这样的存储结构可以方便地实现在TIN中数据编辑、检索与快速插值等应用

.

2相关算法

2.1基于特征点分段的Dauglas-Pecuker算法

D.Douglas和T.Peucker于1973年提出经典的线状要素化简算法Dauglas-Pecuker(简称DP)算法[5-6].矢量海图中岛屿海岸线所围区域是面状要素,直接采用传统DP算法会有一个问题:如果δ取得过大,边界曲线会化简成一条线段,二维测度为零,不再以面状要素的形式存在.针对这个问题提出基于特征点分段的DP算法,方法如下:

Algorithm1:Predigest-a-Curve(Γ){

如果曲线Γ所含点数大于4,则根据一定规则先在曲线上选择少量的特征点,这些特征点把曲线分为若干段,对每段分别进行DP化简,然后把化简后的分段连接起来组成新的

Γ.}使用Algorithm1化简的极限情况是还剩这些特征点,它们代表这条曲线的最基本特征.这里以Γ上最大最小纬度点(或经度点)的连线作为基线段,和基线段两侧距离基线段最远的点作为特征点,这4个点中包含Γ的最大最小经纬度,这是面状要素很重要的特征,应当保留.由于化简后边界线的点数大于等于4,可以保证边界线的二维测度大于零,所围区域还是以面状要素的形式存在.

这里δ=dpdl.式中:dp为水深点平均距离;dl为边界线段平均长度.图2(a)是化简前的岛屿边界曲线,大岛上共有94个点;图2(b)是采用传统DP算法化简后的边界曲线,有2个小岛被化简为一条线段,大岛被化简为26个点;图2(c)是采用特征点分段DP算法化简后的边界曲线,小岛的依然以面状要素的形式存在,大岛被化简为33个点;图3是图2相应的剖分网格,图3(a)中有大量窄三角形,图3(b)中三角形网格的形态有了较大改善;图3(c)中三角形的形态也有较大改善.δ为7个单位长度,虚线为未被包含的边界线.

2.2改进的特征约束细分嵌入算法

嵌入特征线段的方法分为直接嵌入和细分嵌入,细分嵌入是通过在特征线段上插入有限个附加点,把特征线段分段嵌入剖分网格中,使剖分网格在保持特征约束的同时仍满足DT特性,避免了在TIN中出现非DT三角形.文献[7-8]各提出一种细分嵌入算法:在起点与终点的中点位于起始三角形外接圆和终止三角形外接圆相交区域的外部时文献[9]的算法会失效.文献[7-8]的算法都存在剖分结果不稳定的缺陷:分别以特征线段2个端点为起点时,大多数情况下得到附加点的位置并不一致.提出一种改进的特征线段细分嵌入算法,相对文献[7-8]的算法,可以保证剖分结果的正确性和稳定性.方法如下,设PiPj是一条特征线段.

1)判断Pi的邻接三角形顶点中是否包含Pj,包含则返回;

2)找到与PiPj相交的三角形,组成PiPj的影响域E1,约定Δi是以Pi为顶点并与PiPj相交的三角形,Δj是以Pj为顶点并与PiPj相交的三角形,⊙(Δi)和⊙(Δj)分别为Δi和Δj的外接圆;

3)设Ji=⊙(Δi)∩PiPj,Jj=⊙(Δj)∩PiPj,如果Ji∩Jj≠,则取Ji∩Jj的中点作为附加点Pa,约束线段剩余部分为零;如果Ji∩Jj=,则取Ji、Jj中较长一个所对应的交点作为附加点Pa;若Pa∈Ji,则以PaPj作为约束线段的剩余部分,若Pa∈Jj,则以PiPa作为特征线段的剩余部分;

4)在E中找到包含Pa的三角形,通过邻接关系向外寻找外界圆包含Pa的三角形,构成Pa的影响域E2,更新E1=E1-(E1∩E2),连接Pa和E2的顶点形成新的三角形,先替换E2中三角形的信息,余者再加到三角形链表尾部;如果特征线段没有剩余,则嵌入完毕;如果特征线段存在剩余,则把新生成的三角形中与特征线段剩余部分相交的那个加入E1,返回至3);}对所有边界线段执行以上操作,就得到了满足DT特性的初始CD-TIN.

2.3合理边界表达算法

1)表达外边界.

初始CD-TIN所表示的外边界只是数据域的凸边界,而并不一定是数据域合理的外边界.为保证数据域边界的凸性,边界附近存在形态很扁、边长很长的三角形,与其它三角形的形态有明显差异,根据这个现象,提出得到区域合理外边界的方法:计算由水深点构成的边的平均长度,如果一个三角形某条边的边长大于6倍该长度,则删除这个三角形.

2)表达内边界.

岛屿边界属于内边界,在初始CD-TIN中,岛屿内还存在三角形,需要删除这部分三角形.方法:Δi的3个顶点中是否有边界点,若有,则判断Δi的重心是否在该边界点顶点所属边界曲线的内部,如果在,则把Δi从三角形链表中删掉.

3数值实验

为检验所提方法,以3幅具有代表性的海图为测试实例,13791为1:2万港湾图,要素主要为岛屿;17100为1:25万航海图,要素主要为小型岛屿;13000为1:50万航海图,要素主要为海岸线和沿海岛屿,剖分过程见图5~7.

3.1剖分结果

图4分别为海图13791、17100和13000中的水深点、岛屿边界和海岸线;图5是3幅海图嵌入特征约束之后的初始CD-TIN,在边界处存在一些又长又窄的三角形,岛屿内部也有三角形;图6是3幅海图合理边界表达后的最终CD-TN





4结束语

提出一种由二维矢量电子海图中水深点和岛屿海岸线2类要素构建海底CD-TINDEM的方法,可在现有电子海图数据的基础上更直观地表达海底地形,实现了对海底地形的2.5维重建.测试实验

结果表明,该方法能够适用于各种类型的海底地形环境构

建的网格形态较好,运行时间满足应用需求,为相关领域的研究提供了一个更直观的平台,对提高航行安全也具有重要的现实意义