区域CORS网络构造优化算法

吕洪标,郭 英,卢秀山

(山东科技大学海岛(礁)测绘技术国家测绘局重点实验室,山东青岛266510)

0 引 言

全球定位系统(GPS)的广泛应用和现代通信技术的成熟为网络RTK定位技术的应用和推广提供了有利条件,使现代连续运行参考站服务系统(CORS)网络的发展呈现出实时化和规模化的特点。局域范围内,国外典型的网络有美国的南加州GPS综合网、德国的卫星定位导航服务网。在国内,从2000年起,香港、深圳、北京、成都、昆明、上海等城市率先建立了城市多功能GPS服务网。迄今为止,中国国内有近二十个城市已经建设了各自的区域CORS网,更有不少地区正处在筹备计划中。

随着计算机技术的发展,拓扑网络生成技术越来越多地应用到各种工程领域,在众多网络结构中,Delaunay三角网(DTIN)最具代表性,适合于区域CORS网络构造。它具有以下特点:

1)网络构成唯一,便于CORS网络识别和管理;

2)每个三角形尽量接近等边三角形,有利于保证CORS网络改正数的内插精度;

3)三角形的边长之和最小,有利于基线上模糊度的快速可靠求解[1]。

中国是一个国土面积相当大的国家,可依据建设管理形式、任务要求和应用范围,先发展行业的、区域的CORS网络。这就需要区域CORS网络构造算法来完成区域CORS网络的构造。以往的区域CORS网络构造算法在特殊区域的离散点集内有它的局限性,不能有效完成构网任务,甚至构网中断。

基于已有的算法,研究区域CORS构网算法优化问题,也就是在区域范围内能够有效完成CORS网络构造,为CORS网的数据处理工作奠定了良好的基础。

1 Delaunay三角网

在区域范围内,通常使用Delaunay构网方法即可满足实际的构网需求。

1.1 Delaunay三角网构网定义及其性质

DTIN的定义是[2]:

①网内任何一个三角形的外接圆内不包含第四点;

②若出现四点共圆的情况,则连接该凸四边形的较短的对角线形成2个新三角形。如果网络中任何一个三角形都满足上述两点,则称该网络是一个DTIN。

为方便描述DTIN的构网算法,现给出DTIN的如下性质:

①三角单元的最大最小角

相邻两个Delaunay三角形构成凸四边形,在交换凸四边形的对角线之后,六个内角的最小者不再增加。

②三角单元的空外接圆

任何一个Delaunay三角形的外接圆内不能包含任何其他离散点。

这两个性质,决定了Delaunay三角网具有极大的应用价值。Miles证明Delaunay三角网是“最好”的三角网;Lingas进一步论证了“在一般情况下,Delaunay三角网是最优的”;Sibson认定“在一个有限点集中,只存在一个局部等角的三角网,这就是Delaunay三角网”。

1.2 Delaunay三角网的构网步骤

直接按DTIN的定义搜索三角形单元的效率很低,时间复杂度为O(n3),利用DTIN的最大最小角性质以及空外接圆性质可大大提高搜索效率,使算法的时间复杂度减小为O(n2)[1]。根据性质①,②,提出了一种区域CORS网络构造优化算法,设计的数据结构包括顶点结构、边结构、三角形结构、队列结构以及集合结构,集合结构包含点结构和三角形结构。边结构中,设计了一个标志变量,用来判断该边是否被扩展过。该算法输入集合顶点集,输出集合为三角形集。已有的区域CORS网络构造算法是以2最大最小角性质和空外接圆性质构造网络算法的实现步骤(见图1)

图1 区域CORS网络构造算法流程图

1)将所有离散的WGS-84点中心投影到以地心为球心,以地球赤道半径为半径的球上,生成顶点集;

2)在顶点集中搜索距离最小的两点为初始边,并生成初始三角形;

3)以三角形的另两条边为扩展边,生成新的三角形;

4)判断是否还有未扩展的边。若有,转到3);若无,则输出三角形集,构网结束。

2 区域CORS网络构造优化算法

基于区域CORS网络构造算法,在特殊区域范围内,不能有效构网。提出了区域CORS网络构造优化算法。算法核心是以最小角降序且空外接圆约束构造网络,其实现步骤如下(见图2)。

1)将所有离散的WGS-84点中心投影到以地心为球心,以地球赤道半径为半径的球上,生成顶点集;

2)在顶点集中搜索距离最小的两点为初始边,搜索以初始边为扩展边的所有三角形,按照最小角从大到小的顺序,进行空外接圆约束,并生成初始三角形;

3)以三角形的另两条边为扩展边,按照最小角降序且空外接圆约束来生成新三角形;

4)判断是否还有未扩展的边。若有,转到3);若无,则输出三角形集,构网结束。

图2 区域CORS网络构造优化算法流程图

3 实例分析

在大多数区域CORS网络构造中,两种算法的构网结果都是一样的,但是在特殊区域的情况下,构造的CORS网络结果存在一定的差异。针对在特殊区域内,对构网的差异进行试验分析。试验用ITRF的7个IGS站点构造区域CORS网络来验证区域CORS网络构造优化算法的可靠性,同时比较两种算法的有效性。如图3、4所示。

试验结果为:

图3 区域CORS网络构造算法构网结果

1)已有的区域CORS网络构造算法得出图3结果,生成两个三角形(hivi,ormt,lewi)和(lewi,ormt,fred)(黑色标记)就结束了,原因在于以扩展边(fred,lewi)构造网络,搜索到三个三角形(fred,lewi，tswy）（绿色标记),(fred,lewi,bcyi)和(fred,lewi,coon)(红色标记),其中三角形(fred,ewi,tswy)为最小角最大的,但是它不满足空外接圆性质(包含点coon),没有完成构网任务,数据处理工作无法继续进行。

图4 区域CORS网络构造优化算法构网结果

2)用区域CORS网络构造优化算法得出图4结果,在以扩展边(fred,lewi)搜索到的三个三角形中按每个三角形的最小角降序排列,依次进行空外接圆约束,最后得出三角形(fred,lewi,coon)满足空外接圆性质,进而得以顺利向下进行构造网络。

3)实例比较分析说明,区域CORS网络构造优化算法避免了区域CORS网络构造算法的局限性,证明了在任何区域范围内,区域CORS网络构造优化算法是可靠的,而且也是有效的。

4 结论与建议

在区域范围内,用DTIN构造CORS网络具有可靠性和优越性。针对 DTIN提出的区域CORS网络构造优化算法,较之以往的区域CORS构网算法大大提高了可靠性,并用ITRF的IGS站点构成了区域CORS网络,证明和比较了该算法是可靠和有效的。该算法在区域性CORS网络组成全国性CORS网络中也能解决相应问题,有着非常广阔的应用前景。

区域CORS网络构造作为新的大地基准以及坐标参考框架为国土测绘起着重要作用,此外,还为气象学、电离层等研究提供了时空高密度的大量原始观测数据,为相关领域的科学研究做出了宝贵的贡献。CORS网络构造除了在地壳运动监测和大地测量基准专业领域发挥重要作用外,还将促进定位信息市场的发展壮大和新产品的开发。

[1]周乐韬,黄丁发,李成钢,等.基于球面Delaunay三角网的GPS网络构造算法[J].西南交通大学学报,2007,42(3):380-383.

[2]王建华,徐强勋,张 锐.任意形状三维物体的Delaunay网格生成算法[J].岩石力学与工程学报,2003,22(5):717-722.

[3]梅胜强,宫煦利,姚宜斌,等.基于Delaunay三角网的大规模CORS基准站组网技术研究[J].大地测量与地球动力学,2008,28(1):131-135.

[4]武晓波,王世新,肖春生.Delaunay三角网的生成算法研究[J].测绘学报,1999,28(1):28-35.

[5]邹 荣,刘 晖,姚宜斌,等.Delaunay三角网构网技术在连续运行卫星定位服务系统中的应用[J].测绘信息与工程,2005,30(6):9-11.

[6]宋占峰,蒲 浩,詹振炎.快速构建Delaunay三角网算法研究[J].铁道学报,2001,23(5):85-91.