四叉树分解在海空重力测网交叉点搜索中的应用

Application of Quadtree Decomposition to Intersections Search of Air-Sea Gravity Survey Grid

交叉点快速搜索是海空重力测量数据质量评定的前提和基础。随着海空重力测网规模的不断扩大和不规则测线的出现,现有的交叉点搜索方法无法保证快速、精确地搜索到所有交叉点。引入四叉树分解方法来遍历测网交叉点,实现了交叉点附近的自动加密剖分;利用遍历比较大小取出主、副测线包络矩形的重合区域,取出的索引和实际交叉点数量相当,有效避免了大量的冗余计算。实验结果表明,该方法对于十万测点级别的美国EN01数据块,只要0.28 s即可完成搜索,对于数百万测点的测网的搜索效率也大幅优于常规方法和成熟商业软件。该方法利用遍历搜索保证了100%的准确率,同时具有很高的搜索效率,普遍适用于海空重力测网的交叉点搜索。

Objectives: How to search intersections fast is the premise requirements of the quality evaluation of air-sea gravimetry data. With the continuous expansion of the scale of the air-sea gravity survey network and the emergence of irregular survey lines, the existing intersections search methods are hard to ensure that all the intersections can be quickly and accurately searched.Therefore,how to improve the searching efficiency and accuracy, has attracted much attention.Methods: We introduce the quad tree decomposition method to search the intersections of survey network, conduct the automatic refined subdivision near the intersections and then use the traversal comparison size to extract the overlapping area of the envelope rectangle of the main and auxiliary survey lines. By using rapid rejection judgment and repeated iterative search,the magnitude of indexes’ number retained is equivalent to the actual intersections, which effectively avoids the large amount of redundant calculation. The method was programed and verified.Results: One experiment shows that the method can complete the search in only 0.28 s for the block EN01 airborne gravity data from gravity for the redefinition of the American vertical datum(GRAV-D) project, which has about100 000 survey points;and another one shows that the search efficiency of the method for a survey network of 4 877 988 survey points is also significantly better than the existing methods and mature commercial software.Conclusions: This method uses traversal search to ensure 100% accuracy, and has high searching efficiency. It is universally applicable to the intersections’ search of air-sea gravity network, and has excellent practical application effect.