改进的最小独立闭合环剥蚀搜索算法研究

李靖，朱丽强

(1.苏州高新区测绘事务所有限公司，江苏苏州 215129;2.苏州工业园区测绘有限责任公司，江苏苏州 215021)

1 引言

在GPS网的数据处理过程中，基线解算所得到的基线向量确定了GPS网的几何形状，并将作为GPS网平差的起算数据［1］。独立多边形闭合环闭合差的大小是评价基线解算成果的一个重要指标，它是对整网观测精度的初步评判，能够及时发现基线向量间的系统误差或粗差，从而控制整个控制网的解算质量。部分商用GPS数据处理软件虽然具有搜索闭合环功能，然而这类软件中有些闭合环的搜索和计算速度比较慢，而且不能搜索到所有可能的异步环，易产生遗漏［2］。因此，一个有效快速的、易实现的最小独立闭合环自动化搜索算法在实际工程应用中显得尤为重要。

目前较常见的闭合环搜索方法主要有:矩阵变换方法［3～5］，该方法基于矩阵理论进行变换，但涉及系数矩阵是否满秩或条件方程的系数阵系数不一定为±1等限制，需要人工干预构造矩阵;图论生成树法［6］，该方法用到了Dijkstra或类似复杂算法，且需要依赖于观测值文件或网点信息文件;剥蚀法［7］，该方法需计算GPS点位概略平面坐标、方位角、联测方向数等，但对控制网图形结果过于理想化，自动化后遇到某些图形并不能搜索得到正确的闭合环信息。基于以上方法，本文提出了一种基于通用基线数据交换格式的改进剥蚀算法，避免了人工构建系数矩阵或网点文件，减少了中间环节的干预，真正实现了最小独立闭合环的自动化搜索。

2 算法设计

由于实际工程控制网的网型结构情况较为复杂，因此在最小独立闭合环的自动化处理过程中需要综合考虑。本算法以单个点为基础，在基线信息中逐点构造独立环，构造完毕即剔除该点及其相关基线。

算法流程如下:

(1)读取通用数据格式(*.asc)的基线信息，形成点列表与基线列表。

点列表中点号按照纵坐标由大至小重新排列，形成点列表信息。基线列表中根据基线的唯一性形成基线列表信息。

(2)孤点、极条件等点位与基线信息进行处理。

在基线列表中循环判断网点的出现次数，确定该点是否为孤点或只出现一次，同时在基线列表、点列表中进行无效标记更新信息。

(3)点信息、基线信息的完善计算。

根据有效的点信息，确定该点的有效连接数、有效连接点等信息。根据有效的基线信息，确定每条基线的最终基线连接数、坐标方位角、基线边长、观测时间等信息。

(4)点列表中有效点与第一点(纵坐标最大的点)有关的闭合环搜索。

以第一点A为起点，按基线方位角从小到大进行搜索，依次确定第二点为B，以第二点B为起点，确定与基线BA的顺时针夹角最大的基线BC，以C为第三点，如果C与A之间存在基线CA，则需要判断在以A为起点的闭合环中CA边是否已经使用了两次。

当CA边使用次数没有超过两次时，则以AB为起点的三边独立闭合环ABCA搜索完成。在保存入库时需要判断是否与现在有的以A为起点的闭合环存在重复，当满足不重复时搜索结果可保存，否则放弃ABC三点构成的闭合环，重新从A点开始再进行搜索。当CA边使用超过了两次时，视CA边为无效，即认为C点与A点之间不存在基线(实际为存在)，继续按上述查找第3点C一样查找与基线CB的顺时针夹角最大的基线(基线CD)的第4点D，然后再按上述判断C点是否有效的方法进行判断D点是否有效，从而判断是否需要查找第5个点E，进行循环查找并判断。第一点A的搜索流程见图1。在生成独立闭合环的过程中，可以记录环点名及基线编号，以便同步对独立闭合环的质量进行检核。

图1 A点搜索流程示意图

原剥蚀法中提到的，如与第一点(x坐标最大)的扣除支点后的联测方向数为Ni，则与第一点有关的独立闭合环个数一定为Ni－1，但实际工程中控制网的网型结果往往存有多样性，实际的独立闭合环数最多只能是Ni－1，有很多情况下达不到Ni－1个，因此原程序设计时设定为非要找到Ni－1个，结果会出现异常情况。如图2就是为例外，E01为x坐标最大的点，与点E01有关的联测方向数为6个，但很明显与E01有关的独立闭合环个数只有4个，而非5个。

原剥蚀法中是以C为第3点后，直接寻找CA之间是否有基线存在，而未考虑到基线CA是否已经被使用了两次或是否存在重复，因此在某些图形下会导致不能得到正确的搜索结果，在图2中按照原设计思想基线E01E05将会被使用4次，从而也会得出与E01有关的闭合环个数是5个。

图2 某GPS控制网网型图

(5)标记搜索完毕的点和与之相关的基线。

由于直接删除搜索完毕点的基线信息过程较繁杂，特别是对大型控制网而言。因此，可采用布尔值在点列表中对已搜索完毕点进行无效标记，这样可大大提高效率。重复第(4)步搜索，直到搜索完全部独立闭合环为止。

3 理论分析

由测量平差的知识可知，同属于独立闭合环的环与环之间不存在相关性，环与环之间类似于独立观测值，即不存在由闭合环A和闭合环B构成闭合环C的情况。对于剥蚀法而言，第一，由于在搜索完包含某一点的独立闭合环后，涉及该点的基线将全部视为无效，因此在后续的搜索中将不会包含与该点相关的基线边，前后搜索出的环之间也将不会存在关联性。第二，如果包含点A的所有搜索出的闭合环中两两不存在相关性，那么所有搜索出的闭合环也将全部独立。

对于一个有M个测量点，N条基线的GPS控制网，最小独立闭合环的个数为N－M+1。以测量点A为例，首先，包含该点A的独立闭合环个数最大可能为该点连接数NA－1，此处连接数NA为去除比点A纵坐标(X)大的点后的剩余有效连接数，该限制条件确保了独立闭合环在个数上的完整性。其次，在本次搜索中对包含点A的连接基线的出现次数也做出了限制，不能超过两次，避免了环1、环2和环3中都出现同一条基线的不独立情况。最后，是对搜索出的最小独立闭合环的重复性进行判断，在一些比较特殊的网图中，不排除这种重复情况的出现，因此需要在保存结果前进行重复判断。综上所述，可以稳定的求出各种复杂控制网图形中包含的最小独立闭合环。

4 工程算例

根据上述方法编写了基于通用基线数据交换格式的基线解算质量检核软件，并运用工程实例进行了验证。图2为某GPS工程控制网，最小独立闭合环搜索结果见表1所示。

最小独立闭合环搜索结果 表1

图3 文献6中网型图

图3为参考文献［6］中涉及的分析网型图，运用本文提出的改进算法搜索到闭合环结果与该文献中涉及的3种搜索方法结果进行比较，如表2所示。

本文算法与文献［6］中涉及算法的搜索结果比较 表2

由表2可以发现，本文算法可以搜索出的最小独立环个数等于应有环个数，搜索结果完整，可靠。

同时，在最小独立闭合环搜索完成后，利用环点信息也可以对重复基线、同步环和异步环的处理质量进行检核并生成报告。

5 结语

GPS观测获得的是控制点之间的基线向量值，由于误差的存在，基线构成闭合环的闭合差并不为零。为了在后续平差工作中保证参与平差的基线不存在粗差并满足相应的限差要求，要对基线构成的重复边和独立环进行检验。同步环闭合差只能反应软件模型误差和实际观测条件，不能反应系统误差和人为粗差，而异步环闭合差能反映出不同时段中的星历误差、电离层延迟、对流层折射和仪器误差等因素的综合影响［7］，因此同步环与异步环检核是同等的重要。本文通过对原剥蚀算法的优化设计，提高了构环的准确性，算法简单，自动化程度高，并且基于通用基线数据交换文件，同步搜索出重复基线与最小独立闭合环，计算出闭合差，在实际工作中可以显著提高工作效率。

［1］李征航，黄劲松.GPS测量与数据处理［M］.武汉:武汉大学出版社，2005.

［2］徐昌荣，葛山运.基于Delaunay三角网的GPS控制网同步环和异步环自动搜索算法研究［J］.大地测量与地球动力学，2011，31(1):55 ～58.

［3］赵一晗，伍吉仓.控制网闭合环搜索算法的探讨［J］.铁道勘察，2006(3):12～14.

［4］李光炎，王解先.闭合环搜索方法的探讨［J］.工程勘察，2004(6):52～53.

［5］游为，范东明，付淑娟.最短独立闭合环与附合路线的快速搜索方法［J］.测绘科学，2009，34(4):139～140.

［6］邹进贵，冯晨.控制网最小独立闭合环搜索算法研究［J］.地理空间信息，2008，6(6):97～99.

［7］刘根友.剥蚀法计算GPS观测网独立环闭合差［J］.测绘工程，2001，10(1):33 ～36.

［8］朱广轶，贾瑞英.GPS测量数据处理的应用研究［J］.沈阳大学学报，2003，15(2):54 ～56.