留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

徐光晶 周坚鑫 舒晴

徐光晶, 周坚鑫, 舒晴. 四叉树分解在海空重力测网交叉点搜索中的应用[J]. 武汉大学学报 ( 信息科学版), 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
引用本文: 徐光晶, 周坚鑫, 舒晴. 四叉树分解在海空重力测网交叉点搜索中的应用[J]. 武汉大学学报 ( 信息科学版), 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
XU Guangjing, ZHOU Jianxin, SHU Qing. Application of Quadtree Decomposition to Intersections Search of Air-Sea Gravity Survey Grid[J]. Geomatics and Information Science of Wuhan University, 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
Citation: XU Guangjing, ZHOU Jianxin, SHU Qing. Application of Quadtree Decomposition to Intersections Search of Air-Sea Gravity Survey Grid[J]. Geomatics and Information Science of Wuhan University, 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404

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

doi: 10.13203/j.whugis20200404
基金项目: 

中国自然资源航空物探遥感中心青年创新基金 2020YFL15

国家自然科学基金 41604066

国家重点研发计划 2017YFC0601601

详细信息
    作者简介:

    徐光晶,博士,高级工程师,主要研究方向为重力学及航空物探。bdxgj@163.com

  • 中图分类号: P223

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

Funds: 

The Key Laboratory of Airborne Geophysics and Remote Sensing Geology Ministry of Natural Resources 2020YFL15

The National Natural Science Foundation of China 41604066

the National Key Research and Development Program of China 2017YFC0601601

More Information
    Author Bio:

    XU Guangjing, PhD, senior engineer, specializes in aero geophysical survey. E-mail: bdxgj@163.com

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

    Figure  1.  Diagram of Quadtree Decomposition, Survey Lines and Intersections

    图  2  快速排斥判断

    Figure  2.  Rapid Rejection Judgment

    图  3  包络矩形重合区域示意图

    Figure  3.  Diagram of Overlapping Area of Envelope Rectangle

    图  4  交叉点搜索程序流程

    Figure  4.  Flowchart of Intersections Search

    图  5  不同预定值的归一化计算时间变化图

    Figure  5.  Normalized Calculation Time Variation for Different Predetermined Values

    图  6  EN01数据块的四叉树分解及交叉点分布

    Figure  6.  Quadtree Decomposition and Intersections Distribution of Data Blocks EN01

    表  1  EN01数据块的设计参数

    Table  1.   Parameters of Data Block EN01

    参数名 参考值
    测线间距/km 主测线:10
    副测线:80
    名义飞行高度/m 6 096
    名义飞行速度/(km∙h-1) 407.44
    采样率/Hz 1
    主测线:26
    测线条数/条 副测线:5
    重复线:0
    测点数量/个 102 844
    交叉点数量/个 62
    下载: 导出CSV

    表  2  EN01用不同搜索方法的相关统计信息

    Table  2.   Statistics of Different Search Methods for EN01

    搜索方法 搜索时间/s 正确率/%
    逐一遍历法 77.3 100
    坐标平均法 8.2 85.4
    主副测线斜率法 7.7 89.5
    滑动窗口法 7.9 100
    本文搜索方法 0.28 100
    下载: 导出CSV

    表  3  国内某测网不同搜索方法的相关统计信息

    Table  3.   Statistics of Different Search Methods for Domestic Data

    搜索方法 搜索时间/s 正确率/%
    逐一遍历法 3 167.3 100
    Oasis Montaj 33.4 100
    本文搜索方法 9.7 100
    下载: 导出CSV
  • [1] 宁津生, 黄谟涛, 欧阳永忠, 等. 海空重力测量技术进展[J]. 海洋测绘, 2014, 34(3): 67-72 https://www.cnki.com.cn/Article/CJFDTOTAL-HYCH201403024.htm

    Ning Jinsheng, Huang Motao, Ouyang Yongzhong, et al. Development of Marine and Airborne Gravity Measurement Technologies[J]. Hydrographic Surveying and Charting, 2014, 34(3): 67-72 https://www.cnki.com.cn/Article/CJFDTOTAL-HYCH201403024.htm
    [2] 欧阳永忠. 海空重力测量数据处理关键技术研究[D]. 武汉: 武汉大学, 2013

    Ouyang Yongzhong. On Key Technologies of Data Processing for Air-Sea Gravity Surveys[D]. Wuhan: Wuhan University, 2013
    [3] Bell R. High Resolution Marine And Airborne Gravity Surveys: Applications To Rifted Margins[D]. Columbia: Columbia University, 1989
    [4] 黄谟涛, 翟国君, 管铮, 等. 海洋重力场测定及其应用[M]. 北京: 测绘出版社, 2005

    Huang Motao, Zhai Guojun, Guan Zheng, et al. Determination of Ocean Gravitational Field and Its Application[M]. Beijing: Surveying and Mapping Press, 2005
    [5] Verdun J, Bayer R, Klingelé E E, et al. Airborne Gravity Measurements over Mountainous Areas By Using a Lacoste and Romberg Air-Sea Gravity Meter[J]. Geophysics, 2002, 67(3): 807–816 doi:  10.1190/1.1484525
    [6] Bell R, Coakley B, Stemp R. Airborne Gravimetry from a Small Twin Engine Aircraft over the Long Island Sound[J]. Geophysics, 1991, 56: 1486-1493 doi:  10.1190/1.1443170
    [7] 夏哲仁, 孙中苗. 航空重力测量技术及其应用[J]. 测绘科学, 2006(6): 43-46 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD200606010.htm

    Xia Zheren, Sun Zhongmiao. Airborne Gravimetry Technique and Its Applications[J]. Science of Surveying and Mapping, 2006(6): 43-46 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD200606010.htm
    [8] 孙中苗. 航空重力测量理论、方法及应用研究[D]. 郑州: 信息工程大学, 2004

    Sun Zhongmiao. Theory, Methods and Application of Airborne Gravimetry[D]. Zhengzhou: Information Engineering University, 2004
    [9] 黄谟涛, 刘敏, 欧阳永忠, 等. 海洋重力场特征统计模型计算与分析[J]. 武汉大学学报·信息科学版, 2019, 44(3): 317-327 doi:  10.13203/j.whugis20160529

    Huang Motao, Liu Min, Ouyang Yongzhong, et al. Analysis and Calculation of the Statistical Models of Marine Gravity Field Character[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 317-327 doi:  10.13203/j.whugis20160529
    [10] 黄谟涛, 翟国君, 欧阳永忠, 等. 海洋测量误差处理技术研究[J]. 海洋测绘, 2003, 23(3): 57-62 https://www.cnki.com.cn/Article/CJFDTOTAL-HYCH200303019.htm

    Huang Motao, Zhai Guojun, Ouyang Yongzhong, et al. Error Theory Research in Processing Data of Marine Surveying[J]. Hydrographic Surveying and Charting, 2003, 23(3): 57-62 https://www.cnki.com.cn/Article/CJFDTOTAL-HYCH200303019.htm
    [11] 李海. 航空重力测量测线网平差的理论与方法[D]. 郑州: 信息工程大学, 2002

    Li Hai. Theory and Methods of Outliers in Network Adjustment of Airborne Gravimetry[D]. Zhengzhou: Information Engineering University, 2002
    [12] 蔡劭琨. 航空重力测量网络平差方法研究[D]. 长沙: 国防科学技术大学, 2009

    Cai Shaokun. Research on the Network Adjustment of Airborne Gravimetry[D]. Changsha: National University of Defense Technology, 2009
    [13] 戢锐, 康双双, 李川, 等. 基于Matlab的航空重力交叉点搜索[J]. 工程地球物理学报, 2011, 8(5): 551-555 doi:  10.3969/j.issn.1672-7940.2011.05.008

    Ji Rui, Kang Shuangshuang, Li Chuan, et al. Intersection Search of Airborne Gravity Based on Matlab[J]. Chinese Journal of Engineering Geophysics, 2011, 8(5): 551-555 doi:  10.3969/j.issn.1672-7940.2011.05.008
    [14] 韦建成, 肖云, 王利, 等. 一种优化的航空重力测量测线交叉点算法[J]. 测绘科学, 2019, 44(5): 27-31 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201905005.htm

    Wei Jiancheng, Xiao Yun, Wang Li, et al. An Optimized Intersection Algorithm of Airborne Gravity Survey[J]. Science of Surveying and Mapping. 2019, 44(5): 27-31 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201905005.htm
    [15] 韦建成, 肖云, 王利, 等. 一种航空重力测线交叉点搜索新方法[J]. 大地测量与地球动力学, 2018, 38(12): 1302-1305 https://www.cnki.com.cn/Article/CJFDTOTAL-DKXB201812017.htm

    Wei Jiancheng, Xiao Yun, Wang Li, et al. A New Method for Searching Intersection of Airborne Gravity Survey[J]. Journal of Geodesy and Geodynamics, 2018, 38(12): 1302-1305 https://www.cnki.com.cn/Article/CJFDTOTAL-DKXB201812017.htm
    [16] 李德仁, 钱新林. 浅论自发地理信息的数据管理[J]. 武汉大学学报·信息科学版, 2010, 35(4): 379-383 http://ch.whu.edu.cn/article/id/913

    Li Deren, Qian Xinlin. A Brief Introduction of Data Management for Volunteered Geographic Information[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4): 379-383 http://ch.whu.edu.cn/article/id/913
    [17] 周芹, 钟耳顺, 黄耀欢, 等. 大型空间数据库的并发索引策略CQR树[J]. 武汉大学学报·信息科学版, 2009, 34(7): 856-858 http://ch.whu.edu.cn/article/id/1295

    Zhou Qin, Zhong Ershun, Huang Yaohuan, et al. CQR-Tree: Concurrent Strategy for Spatial Index Structure in Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 856-858 http://ch.whu.edu.cn/article/id/1295
    [18] Wei L. A Faster Triangle-to-Triangle Intersection Test Algorithm[J]. Computer Animation and Virtual Worlds, 2014, 25(1): 553-559
    [19] Prasad M I. 2-Intersection of Line Segments[J]. Graphics Gems Ⅱ, 1991(1): 7-9
    [20] GRAV-D Team (2013). Gravity for the Redefinition of the American Vertical Datum (GRAV-D) Project, Airborne Gravity Data; Block EN01[EB/OL]. (2013-07-11)[2020-06-04]. https://www.ngs.noaa.gov/GRAV-D/data_en01.shtml
    [21] Damiani T, Youngman M. GRAV-D General Airborne Gravity Data User Manual[EB/OL]. (2013-07-11)[2020-06-04]. http://www.ngs.noaa.gov/GRAV-D/data_en01.shtml
    [22] 周波阳, 罗志才, 钟波, 等. 航空重力测量的数据归算方法[J]. 大地测量与地球动力学, 2015, 35(2): 336-341 https://www.cnki.com.cn/Article/CJFDTOTAL-DKXB201502037.htm

    Zhou Boyang, Luo Zhicai, Zhong Bo, et al. Data Reduction Methods of Airborne Gravimetry[J]. Journal of Geodesy and Geodynamics, 2015, 35(2): 336-341 https://www.cnki.com.cn/Article/CJFDTOTAL-DKXB201502037.htm
  • [1] 黄谟涛, 邓凯亮, 欧阳永忠, 吴太旗, 翟国君, 陆秀平, 陈欣, 刘敏, 王许.  海空重力测量及应用技术研究若干进展 . 武汉大学学报 ( 信息科学版), 2022, 47(10): 1635-1650. doi: 10.13203/j.whugis20210561
    [2] 薛帅, 王光霞, 郭建忠, 李冬辉, 徐振.  一种多规则可逆元胞自动机的栅格地图加密算法 . 武汉大学学报 ( 信息科学版), 2018, 43(5): 773-778. doi: 10.13203/j.whugis20160345
    [3] 刘敏, 黄谟涛, 马越原, 欧阳永忠, 邓凯亮, 陆秀平, 翟国君.  海空重力测量平台倾斜改正修正模型 . 武汉大学学报 ( 信息科学版), 2018, 43(4): 586-591. doi: 10.13203/j.whugis20150630
    [4] 汪海洪, 罗北.  计算测高卫星地面轨迹交叉点的快速数值算法 . 武汉大学学报 ( 信息科学版), 2017, 42(3): 293-298. doi: 10.13203/j.whugis20140866
    [5] 黄谟涛, 宁津生, 欧阳永忠, 刘敏, 陆秀平, 翟国君, 邓凯亮.  海空重力测量平台倾斜改正模型等价性证明与验证 . 武汉大学学报 ( 信息科学版), 2016, 41(6): 738-744. doi: 10.13203/j.whugis20140535
    [6] 万 雪, 张祖勋, 柯 涛.  一种利用零交叉点理论的改进SIFT特征提取算法 . 武汉大学学报 ( 信息科学版), 2013, 38(3): 270-273.
    [7] 一种利用零交叉点理论的改进SIFT特征提取算法 . 武汉大学学报 ( 信息科学版), 2013, 38(3): 270-273.
    [8] 黄海兰, 王正涛, 金涛勇, 超能芳.  利用ICESat激光测高数据确定极地冰盖高程变化 . 武汉大学学报 ( 信息科学版), 2012, 37(10): 1221-1223.
    [9] 欧阳永忠, 陆秀平, 黄谟涛, 翟国君.  L&R海空重力仪测量误差综合补偿方法 . 武汉大学学报 ( 信息科学版), 2011, 36(5): 625-629.
    [10] 徐天河, 贺凯飞.  利用交叉点不符值对GOCE卫星重力梯度数据进行精度评定 . 武汉大学学报 ( 信息科学版), 2011, 36(5): 617-620.
    [11] 欧阳永忠, 陆秀平, 暴景阳, 邓凯亮.  计算S型海洋重力仪交叉耦合改正的测线系数修正法 . 武汉大学学报 ( 信息科学版), 2010, 35(3): 294-297.
    [12] 赵学胜, 崔马军, 李昂, 张美娟.  球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ( 信息科学版), 2009, 34(4): 479-482.
    [13] 史红岭, 陆洋, 鲍李峰, 王正亮.  利用ICESat交叉点分析探测恩德比地冰盖近年高程变化 . 武汉大学学报 ( 信息科学版), 2009, 34(4): 440-443.
    [14] 吴芳, 芮国胜.  基于四叉树和纠错编码的数字图像水印算法 . 武汉大学学报 ( 信息科学版), 2007, 32(3): 208-211.
    [15] 白建军, 赵学胜, 陈军.  基于线性四叉树的全球离散格网索引 . 武汉大学学报 ( 信息科学版), 2005, 30(9): 805-808.
    [16] 徐天河, 杨元喜.  利用卫星轨迹交叉点标定CHAMP卫星加速度计数据 . 武汉大学学报 ( 信息科学版), 2004, 29(11): 955-959.
    [17] 盛业华, 唐宏, 杜培军.  线性四叉树快速动态编码及其实现 . 武汉大学学报 ( 信息科学版), 2000, 25(4): 324-328.
    [18] 翟国君, 欧阳永忠, 黄谟涛, 王瑞.  测高数据在计算海平面时的取权 . 武汉大学学报 ( 信息科学版), 1999, 24(2): 103-106.
    [19] 邓朝晖, 贾华.  直接表达区域的四叉树链式编码 . 武汉大学学报 ( 信息科学版), 1995, 20(3): 224-227.
    [20] 李征航, 许志諴, 吴北平, 邱水车.  用同步摄影法测定多普勒激光动力测地网的经度零点差 . 武汉大学学报 ( 信息科学版), 1983, 8(1): 51-63.
  • 加载中
图(6) / 表(3)
计量
  • 文章访问数:  147
  • HTML全文浏览量:  60
  • PDF下载量:  24
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-09-26
  • 刊出日期:  2022-11-05

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

doi: 10.13203/j.whugis20200404
    基金项目:

    中国自然资源航空物探遥感中心青年创新基金 2020YFL15

    国家自然科学基金 41604066

    国家重点研发计划 2017YFC0601601

    作者简介:

    徐光晶,博士,高级工程师,主要研究方向为重力学及航空物探。bdxgj@163.com

  • 中图分类号: P223

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

English Abstract

徐光晶, 周坚鑫, 舒晴. 四叉树分解在海空重力测网交叉点搜索中的应用[J]. 武汉大学学报 ( 信息科学版), 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
引用本文: 徐光晶, 周坚鑫, 舒晴. 四叉树分解在海空重力测网交叉点搜索中的应用[J]. 武汉大学学报 ( 信息科学版), 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
XU Guangjing, ZHOU Jianxin, SHU Qing. Application of Quadtree Decomposition to Intersections Search of Air-Sea Gravity Survey Grid[J]. Geomatics and Information Science of Wuhan University, 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
Citation: XU Guangjing, ZHOU Jianxin, SHU Qing. Application of Quadtree Decomposition to Intersections Search of Air-Sea Gravity Survey Grid[J]. Geomatics and Information Science of Wuhan University, 2022, 47(11): 1847-1853. doi: 10.13203/j.whugis20200404
  • 海空重力测量[1-3]是以舰船或飞机为载体,综合应用重力仪(或加速度计)、惯性导航系统(inertial navigation system,INS)、全球导航卫星系统(global navigation satellite system,GNSS)和测高、测姿设备测定海面或近地空中重力加速度的一种动态重力测量方法[4-6]。目前,海空重力仍是快速获取全球高精度、高分辨率重力数据的必然选择[7-9]。海空重力测量中,由于明显的动态效应,要求各个观测量同时进行测量[10],但同一观测量无法进行重复观测,因此测线往往布设成纵横交错的网状,需要根据测网交叉点的符合程度来评估整个测区的测量精度。交叉点快速搜索是海空重力测量数据质量评定的前提和基础。

    海空重力测量中,数据往往是离散的一系列点,每条测线测点数量众多,用传统的逐一对比的遍历搜索法求取交叉点效率非常低。因此,目前常规的搜索方法主要采用非遍历搜索来提高搜索效率。如常用的跳跃搜索法[11]、主副测线斜率法[8]、坐标平均法[12]、多项式拟合法[13]等,以交叉点附近相距最近的两个测点作为交叉点来处理,理论上不严密,也难以保证搜索到所有的交叉点。滑动窗口平均法[14-15]对上述方法进行了改进,先给出近似交叉点,然后在搜索范围内滑动进行遍历搜索,是一种提升遍历搜索效率的尝试,但是其滑动窗口的宽度需要多次尝试才能确定,而不合适的宽度可能导致无法找到所有交叉点。此外,该搜索方法的遍历效率有待进一步提升。总体而言,非遍历搜索方法效率一般较高,但在一定程度上牺牲了准确率,且搜索方法缺少普遍适用性,需要分别考虑不同的情况。而遍历搜索方法对测网中所有的测点都会进行查询和判断,不会有遗漏的情况发生,可以保证100%的准确率。因此,遍历搜索方法的核心问题是如何提高遍历搜索的效率。

    四叉树是地理信息系统中常用的空间索引之一[16-17]。四叉树的结构比较简单,具有比较高的空间数据插入和查询效率,比较适合遍历搜索交叉点的情况。测网数据中的大部分线段往往是不相交的,首先通过利用当前矩形内主、副测线测点数的乘积是否大于预定值作为判定条件,实现了交叉点附近的自适应加密;其次,通过遍历对比取出四叉树叶节点中主、副测线包络矩形重合区域的索引;然后,针对这些索引集合,构建线性方程组求解来进一步判定和确定交叉点位置。本文将四叉树分解引入到海空重力测网交叉点的搜索中,优化了流程,改进了现有交叉点搜索方法存在的不足,提升了海空重力测网交叉点搜索的准确率和效率。

    • 一般而言,重力测线数据文件按照固定的采样间隔对重力测量值进行存储,其中包括测点的时间、飞行高度、经纬度(或平面坐标)及其重力值等信息。交叉点搜索实际上是一个三维搜索问题,利用水平方向的坐标信息,假定重力值数据已被归算到同一水平面,这样可以将三维问题简化为二维问题来进行考虑。

      因此,第i个测点的模型可以简化为:

      $$ {P}_{i}=\left({x}_{i}, {y}_{i}, {g}_{ai}\right) $$

      式中,$ {P}_{i} $表示第i个测点的重力异常序列;$ {x}_{i} $表示东西方向坐标;$ {y}_{i} $表示南北方向坐标;$ {g}_{ai} $表示测点上的重力异常值。

      航迹线可以近似表示成平面坐标内的若干个点连接而成,将相邻两个测点组成一个线段,这样可以得到大量的线段序列,如图 1所示的简化测网由两条主测线和两条副测线组成,每条测线包含有大量的线段序列。交叉点的求取本质上是判断这些线段是否相交并计算出相应的交点坐标,这是一个平面几何的问题。从平面几何的角度来说,如何得到确定交叉点的两条线段的4个端点位置或索引,是交叉点搜索的本质问题。

      图  1  四叉树分解和测网、交叉点分布示意图

      Figure 1.  Diagram of Quadtree Decomposition, Survey Lines and Intersections

    • 四叉树是一种树状数据结构,每一个节点上会有4个子区块。四叉树常应用于二维空间数据的分析与分类。四叉树索引的基本思想是将平面空间递归划分为不同层次的树结构。将已知范围的空间等分成4个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停止分割,图 1中的灰色矩形框展示了四叉树递归分解的过程。

      已有的交叉点搜索方法通常是逐一取出主、副测线,进行循环处理,从而得出交叉点的位置。引入四叉树,可以将循环判定的过程转化为四叉树递归分解,进而获取端点索引的过程。

      在四叉树分解时,首先要将最小外包矩形取出。最小外包矩形的定义来自于计算机图形学,是指平行于纵横坐标轴,能包围整个测网的最小外接矩形。判断线段是否相交通常是进行排斥判断[18-19],即主测线的最小外包矩形和副测线的最小外包矩形是否存在重合区域(见图 2),如果不存在重合区域,则肯定不会相交。分别取出测网中主、副测线的外包矩形,交叉点只可能出现在这两个外包矩形的重合区域,因此将该重合矩形作为交叉点的搜索范围。以图 1为例,主测线和副测线外包矩形的重合区域对应的就是其中最大的灰色矩形,利用该矩形中心进行四分,得到4个子矩形,针对4个子矩形再进行递归分解,图 1中对应的分解层数为6层。

      图  2  快速排斥判断

      Figure 2.  Rapid Rejection Judgment

      四叉树分解的终止条件如何选择是提高交叉点搜索效率的另一个关键问题,本文通过判定当前矩形内主、副测线上测点数量乘积是否超过预定值来决定是否需要继续剖分,通过利用判定条件来实现控制剖分的精细程度,实现了四叉树分解在测线密集、存在交点的区域自适应的加密剖分,图 1中的灰色矩形分布清晰地反映出这一特点。

      对四叉树分解完成后的叶节点,查询其中主、副测线包络矩形的重合区域并输出该区域内的测点索引,如图 3所示。假设图 3中最大的灰色矩形对应四叉树剖分的某一叶节点,其中存在主测线1和副测线2,小的灰色矩形分别为测线上连续两点的包络矩形集合,通过遍历比较大小(即多次应用排斥判断),可以得到3个彩色矩形为存在相交的区域,而交叉点必然在这个区域中。因此,针对这一叶节点,只需要取出这3个矩形对应的测点索引即可。

      图  3  包络矩形重合区域示意图

      Figure 3.  Diagram of Overlapping Area of Envelope Rectangle

      通过四叉树分解和包络矩形重合区域的选取,使得最终取出的索引数量和真正交叉点需要的索引数量的量级相当。通过搜索查询和比较大小,避免了大量冗余的计算判定过程,提高了遍历搜索交叉点的效率。

    • 判定线段是否两两相交的方法包括行列式法、投影法和面积法等,文献[13]的研究表明,3种方法的计算效率相当。选用最常用的行列式法来求解,令两线段的4个端点坐标分别为(x1y1)、(x2y2)、(x3y3)、(x4y4),则两线段所在直线的参数方程分别为:

      $$ x={x}_{1}+{t}_{1}\times \left({x}_{2}-{x}_{1}\right) $$ (1)
      $$ y={y}_{1}+{t}_{1}\times \left({y}_{2}-{y}_{1}\right) $$ (2)
      $$ x={x}_{3}+{t}_{2}\times \left({x}_{4}-{x}_{3}\right) $$ (3)
      $$ y={y}_{3}+{t}_{2}\times \left({y}_{4}-{y}_{3}\right) $$ (4)

      若两直线相交,则(xy)为交点坐标,$ {t}_{1}{\mathrm{和}}{t}_{2} $为待求参数,正好4个方程、4个未知数,写成矩阵形式为:

      $$ \left[\begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 1\end{array}& \begin{array}{cc}-({x}_{2}-{x}_{1})& 0\\ -({y}_{2}-{y}_{1})& 0\end{array}\\ \begin{array}{cc}1& 0\\ 0& 1\end{array}& \begin{array}{cc}0& -({x}_{4}-{x}_{3})\\ 0& -({y}_{4}-{y}_{3})\end{array}\end{array}\right]\times [x\;y\;{t}_{1}\;{t}_{2}{]}^{{\mathrm{T}}} = [{x}_{1}\;{y}_{1}\;{x}_{3}\;{y}_{3}{]}^{{\mathrm{T}}} $$ (5)

      式(5)可以利用三角分解法进行求解。需要注意的是,只有当$ 0\le {t}_{1}\le 1{\mathrm{且}}0\le {t}_{2}\le 1 $时,直线的交点才在线段上,是真正的交叉点。

    • 依照上述的相关原理,设计了海空重力测网交叉点搜索流程,如图 4所示。首先载入测网,分别取出测网中主、副测线的最小外接矩形,将两个外接矩形的重合矩形作为交叉点搜索范围,对该范围进行四叉树递归分解,直至子矩形中主、副测线测点数乘积小于预定值,取出该四叉树叶节点中主、副测线包络矩形重合区域的测点索引,然后利用测点索引构建线性方程组,解方程并输出所有的交叉点。程序核心主要是通过查询和判定比较大小实现四叉树分解,数学模型简单并且比较容易实现。

      图  4  交叉点搜索程序流程

      Figure 4.  Flowchart of Intersections Search

      需要注意的是四叉树递归的终止条件,本文选取的是当前矩形内主、副测线上测点数量乘积的大小是否超过预定值来决定是否需要继续剖分。这个预定值过大会导致四叉树分解不彻底,线性方程组求解时间会延长;而预定值过小,则会导致四叉树分解过度,虽然求解方程少了,但是程序整体效率并不高。

      为了确定预定值的大小,进行了多次对比实验。假定测网中确定一个交叉点的规模大致为:

      $$ A=m\times n/k $$ (6)

      式中,A表示计算规模的大小;$ m $表示所有主测线包含的测点数;$ n $表示所有副测线包含的测点数;$ k $为测网中实际交叉点的个数。

      取某测网为例,其中$ m=4\;694\;519 $,$ n=1\;440\;546 $,$ k=310 $,按式(6)计算得$ A={A}_{0} $,约为2.18×1010。进行多次计算,将同一规模测网(A保持不变)的计算时间按照其最小值进行归一化,计算时间随不同预定值的变化情况如图 5所示。蓝色系的3条线对应$ A={A}_{0} $的3次计算结果,绿色系的3条线对应将原数据按照5倍采样间隔进行抽稀后的3次实验结果,红色系的3条线对应将原数据按照10倍采样间隔进行抽稀后的3次实验结果,黑色系的3条线对应$ m $和$ n $大致不变,而$ k $放大289倍的3次实验结果。可以看出,针对同样的$ A $值,曲线只存在细微的波动,说明程序的计算时间比较稳定。对不同规模的曲线而言,将曲线细微波动视为系统误差,测网规模越大,归一化曲线的最小时间分布相对越宽(蓝 > 绿 > 红 > 黑),对应可选择的比较好的预定值范围越大。另外,当预定值在1×104~1×105之间时,图 5中的曲线存在一个比较明显的斜率突变,对应的是电脑性能导致的拐点,该拐点反映了电脑运算性能在测网分解和构建方程求解运算之间达到的最佳平衡点,不同性能的电脑,拐点位置可能会有所不同。

      图  5  不同预定值的归一化计算时间变化图

      Figure 5.  Normalized Calculation Time Variation for Different Predetermined Values

      对于不同规模的测网做了大量实验,都得到了类似的结果。总体来说,利用拐点处横坐标对应的预定值可以获得程序计算的最小时间,考虑到系统误差和拐点两侧曲线的斜率变化,通常取小于拐点一定范围内的预定值即可以满足实际需要。

    • 2013年3月美国大地测量局(National Geodetic Survey,NGS)对外发布航空重力测量EN01数据块[14, 20-22],包含观测点的测线号、采样时间、纬度、经度、大地高以及绝对重力值,共102 844个数据点。表 1给出了EN01数据块的设计参数。

      表 1  EN01数据块的设计参数

      Table 1.  Parameters of Data Block EN01

      参数名 参考值
      测线间距/km 主测线:10
      副测线:80
      名义飞行高度/m 6 096
      名义飞行速度/(km∙h-1) 407.44
      采样率/Hz 1
      主测线:26
      测线条数/条 副测线:5
      重复线:0
      测点数量/个 102 844
      交叉点数量/个 62

      图 6中给出了四叉树分解的矩形分布和最终的交叉点,可以看出四叉树分解主要在交叉点附近进行自适应加密。实际处理中,EN01数据块约十万个测点,四叉树剖分进行了1 077次,取出的测点索引共608个,经过解方程,最终利用索引中的248个确定交叉点62个(每4个索引确定一个交叉点)。这些数据客观反映了算法提高计算效率的过程。

      图  6  EN01数据块的四叉树分解及交叉点分布

      Figure 6.  Quadtree Decomposition and Intersections Distribution of Data Blocks EN01

      此外,考虑到矩形分解对于水平或垂直方向的测线效率最佳,可以将主测线或副测线旋转到近似水平方向。这时,整个测网的外包矩形更小,通过四叉树分解查询和比较的效率更高。在实际计算中,旋转后的生成索引效率提升了约10%~30%。表 2给出了时间对比情况,逐一遍历法和本文搜索方法的运行环境为:Intel Xeon E3-1230 v5@3.4 GHz,内存8 GB。其他搜索方法的搜索时间来自文献[14],其使用的硬件信息为:Intel Core i3-2350M@2.3 GHz,内存4 GB。可以看出本文搜索方法的搜索时间明显少于其他方法,在十万级测点的测网规模找到交叉点只要0.28 s即可完成,且正确率为100%。

      表 2  EN01用不同搜索方法的相关统计信息

      Table 2.  Statistics of Different Search Methods for EN01

      搜索方法 搜索时间/s 正确率/%
      逐一遍历法 77.3 100
      坐标平均法 8.2 85.4
      主副测线斜率法 7.7 89.5
      滑动窗口法 7.9 100
      本文搜索方法 0.28 100
    • 另有国内某重力测网数据包含有4 877 988个测点,约16×104 km测线,具体的软件运行环境和§4.1中相同。利用本文方法搜索并找到全部24 251个交叉点用时约9.7 s。表 3列出了本文方法与现有成熟软件Oasis Montaj之间交叉点搜索的耗时情况对比,本文方法大幅度缩短了航空重力测网交叉点搜索的运行时间。

      表 3  国内某测网不同搜索方法的相关统计信息

      Table 3.  Statistics of Different Search Methods for Domestic Data

      搜索方法 搜索时间/s 正确率/%
      逐一遍历法 3 167.3 100
      Oasis Montaj 33.4 100
      本文搜索方法 9.7 100
    • 海空重力测量中求取测线交叉点的核心思想就是能够快速准确地确定交叉点的位置[13]。常规的各种搜索方法都有一定的适用范围,可能存在效率或准确率不高的问题。本文提出的基于四叉树分解的海空重力测网交叉点搜索方法可以普遍适用于所有测线交叉点的求取情况。和传统的逐一遍历比对方法相比,四叉树分解提升了数百倍的搜索效率;和其他的非遍历方法相比,四叉树分解效率更高且具有100%的准确率;和成熟商业软件对比,本文方法也具有比较明显的时间优势。有关测网的应用表明,本文方法简单有效,实际应用效果较好。

参考文献 (22)

目录

    /

    返回文章
    返回