留言板

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

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

一种改进的QTM地址码与经纬度坐标转换算法

王谦 赵学胜 王政 刘青平

王谦, 赵学胜, 王政, 刘青平. 一种改进的QTM地址码与经纬度坐标转换算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
引用本文: 王谦, 赵学胜, 王政, 刘青平. 一种改进的QTM地址码与经纬度坐标转换算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
WANG Qian, ZHAO Xuesheng, WANG Zheng, LIU Qingping. An Improved Transformation Algorithm Between QTM Code and Longitude/Latitude Coordinate[J]. Geomatics and Information Science of Wuhan University, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
Citation: WANG Qian, ZHAO Xuesheng, WANG Zheng, LIU Qingping. An Improved Transformation Algorithm Between QTM Code and Longitude/Latitude Coordinate[J]. Geomatics and Information Science of Wuhan University, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390

一种改进的QTM地址码与经纬度坐标转换算法

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

国家自然科学基金 41671394

国家自然科学基金 41671383

详细信息
    作者简介:

    王谦, 硕士生, 主要研究方向为全球离散格网及其三维可视化。wangqiancumtb@yahoo.com

    通讯作者: 赵学胜, 博士, 教授。zxs@cumtb.edu.cn
  • 中图分类号: P208

An Improved Transformation Algorithm Between QTM Code and Longitude/Latitude Coordinate

Funds: 

The National Natural Science Foundation of China 41671394

The National Natural Science Foundation of China 41671383

More Information
    Author Bio:

    WANG Qian, postgraduate, specializes in modeling & 3D visualization of the global discrete grids. wangqiancumtb@yahoo.com

    Corresponding author: ZHAO Xuesheng, PhD, professor. zxs@cumtb.edu.cn
  • 摘要: 地址码与经纬度转换是影响球面四元三角网(quarternary triangular mesh,QTM)应用的主要因素之一。现有算法中,等三角投影法(equal-triangles projection,ETP)转换精确,但算法复杂,效率较低;天顶正交(zenithal ortho triangular,ZOT)投影法转换速度快,但生成的编码缺少方向性;行列逼近法和三向转换法兼顾效率和方向性,但存在较大转换误差。为此,提出了一种改进的转换算法,其基本原理是:根据QTM的行和列,在按一定方向递归逼近地址码的基础上,引入判断点与线段位置关系的操作,从而得到精确的转换结果。该算法在保证精确转换的同时,时间消耗仅为ETP投影法的10.1%~10.4%,且得到的地址码依旧具有方向性,对传统QTM和纬线法剖分的QTM均适用。
  • 图  1  参考点经纬度转换原理

    Figure  1.  Transformation Principle of Reference Points' Lontitudes and Latitudes

    图  2  经纬度向地址码转换原理示意图

    Figure  2.  Diagram of Transformation Principle from Latitude/Longitude to QTM Codes

    图  3  5种算法在不同点数、不同层次的效率比较

    Figure  3.  Efficiency Comparision of Five Methods in Different Points and Different Levels

    表  1  5种算法效率的实验结果/s

    Table  1.   Experimental Efficiencies of Five Methods/s

    层次 点数/万 改进算法 行列逼近法 三向转换法 ZOT投影法 ETP投影法
    地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码
    12 1 0.05 0.06 0.05 0.06 0.06 0.10 0.05 0.05 0.39 0.66
    10 0.42 0.56 0.41 0.40 0.27 0.93 0.43 0.68 3.08 5.67
    100 3.94 5.33 3.25 3.75 3.05 9.20 4.40 6.93 32.89 60.38
    1 000 38.51 55.51 32.10 37.85 26.98 96.05 45.21 68.75 380.56 610.56
    14 1 0.05 0.07 0.05 0.05 0.04 0.12 0.05 0.05 0.37 0.70
    10 0.46 0.69 0.36 0.44 0.30 1.31 0.48 0.68 4.10 6.90
    100 4.30 6.64 3.28 4.20 3.10 10.82 4.92 8.32 41.26 73.42
    1 000 42.39 68.48 32.94 43.03 30.25 110.13 48.56 84.23 414.57 742.88
    16 1 0.06 0.09 0.05 0.05 0.04 0.14 0.06 0.05 0.70 1.01
    10 0.49 0.86 0.39 0.45 0.36 1.23 0.56 0.77 5.06 7.85
    100 4.67 8.86 3.55 4.61 3.68 12.54 5.72 7.52 50.89 80.25
    1 000 48.15 83.68 36.06 46.56 36.92 121.03 56.89 73.56 511.25 809.14
    19 1 0.08 0.12 0.09 0.06 0.05 0.16 0.06 0.11 0.82 1.06
    10 0.55 0.91 0.42 0.45 0.35 1.63 0.61 0.82 5.89 8.05
    100 5.26 9.19 4.07 4.58 3.70 16.98 6.12 8.09 59.23 80.56
    1 000 52.41 87.86 39.85 46.89 37.12 170.23 61.23 79.82 599.24 812.25
    21 1 0.07 0.13 0.10 0.05 0.05 0.17 0.10 0.11 0.90 1.09
    10 0.59 1.32 0.47 0.50 0.42 1.62 0.65 0.83 6.40 10.26
    100 5.66 12.12 4.72 5.21 4.21 16.11 6.64 8.43 67.25 103.67
    1 000 56.60 120.42 43.60 53.61 42.39 165.23 66.42 84.23 692.47 1 096.25
    下载: 导出CSV
  • [1] Dutton G H. A Hierarchical Coordinate System for Geoprocessing and Cartography[M]. Berlin:Springer Verlag, 1999
    [2] 胡海, 游涟, 宋丽丽, 等.地球格网化剖分及其度量[J].测绘学报, 2016, 45(S1):56-65 doi:  10.11947/j.AGCS.2016.F007

    Hu Hai, You Lian, Song Lili, et al. Some Metric Problems on the Global Grid Systems[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):56-65 doi:  10.11947/j.AGCS.2016.F007
    [3] Fekete G. Rendering and Managing Spherical Data with Sphere Quadtree[C]. The First IEEE Confe-rence on Visualization, San Francisco, CA, USA, 1990
    [4] Goodchild M, Yang S. A Hierarchical Spatial Data Structure for Global Geographic Information Systems[J]. CVGIP, 1992, 54(1):31-44 http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_11a3b9c98d822e0e2297fcb369b1d604
    [5] 白建军, 孙文彬, 赵学胜.基于QTM的WGS-84椭球面层次剖分及其特点分析[J].测绘学报, 2011, 40(2):243-248 http://d.old.wanfangdata.com.cn/Periodical/chxb201102019

    Bai Jianjun, Sun Wenbin, Zhao Xuesheng. Character Analysis and Hierarchical Partition of WGS-84 Ellipsoidal Facet Based on QTM[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2):243-248 http://d.old.wanfangdata.com.cn/Periodical/chxb201102019
    [6] 赵学胜, 苑争一, 赵龙飞, 等.一种改进的近似等面积QTM剖分模型[J].测绘学报, 2016, 45(1):112-118 http://d.old.wanfangdata.com.cn/Periodical/chxb201601016

    Zhao Xuesheng, Yuan Zhengyi, Zhao Longfei, et al. An Improved QTM Subdivision Model with Approximate Equal-Area[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(1):112-118 http://d.old.wanfangdata.com.cn/Periodical/chxb201601016
    [7] 袁文, 马蔼乃, 管晓静.一种新的球面三角投影:等角比投影(EARP)[J].测绘学报, 2005, 34(1):78-84 doi:  10.3321/j.issn:1001-1595.2005.01.014

    Yuan Wen, Ma Ainai, Guan Xiaojing. A New Projection for Spherical Triangle:Equal Angle Ratio Projection (EARP)[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(1):78-84 doi:  10.3321/j.issn:1001-1595.2005.01.014
    [8] Dutton G. Scale, Sinuosity and Point Selection in Digital Line Generalization[J]. Cartography and Geographic Information Science, 1999, 26(1):33-53 doi:  10.1559/152304099782424929
    [9] 王磊, 赵学胜, 赵龙飞, 等.基于多层次QTM的球面Voronoi图生成算法[J].武汉大学学报·信息科学版, 2015, 40(8):1111-1115 http://ch.whu.edu.cn/CN/abstract/abstract3421.shtml

    Wang Lei, Zhao Xuesheng, Zhao Longfei, et al. Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2015, 40(8):1111-1115 http://ch.whu.edu.cn/CN/abstract/abstract3421.shtml
    [10] 王磊, 赵学胜, 官亚勤, 等. QTM格网空间中的球面Voronoi图并行生成算法[J].武汉大学学报·信息科学版, 2017, 42(5):691-696 http://ch.whu.edu.cn/CN/abstract/abstract5738.shtml

    Wang Lei, Zhao Xuesheng, Guan Yaqin, et al. A Parallel Algorithm for Generating Spherical Voronoi Diagrams in QTM Space[J]. Geomatics and Information Science of Wuhan University, 2017, 42(5):691-696 http://ch.whu.edu.cn/CN/abstract/abstract5738.shtml
    [11] 袁文, 庄大方, 袁武, 等.离散三角网格系统距离量测方法[J].测绘学报, 2011, 40(1):59-65 http://d.old.wanfangdata.com.cn/Periodical/chxb201101012

    Yuan Wen, Zhuang Dafang, Yuan Wu, et al. Distance Function for the Triangular Grids[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1):59-65 http://d.old.wanfangdata.com.cn/Periodical/chxb201101012
    [12] 赵学胜, 白建军, 王志鹏.基于QTM的全球地形自适应可视化模型[J].测绘学报, 2007, 36(3):316-320 doi:  10.3321/j.issn:1001-1595.2007.03.013

    Zhao Xuesheng, Bai Jianjun, Wang Zhipeng. An Adaptive Visualized Model of the Global Terrain Based on QTM[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):316-320 doi:  10.3321/j.issn:1001-1595.2007.03.013
    [13] Kolar J. Representation of the Geographic Terrain Surface Using Global Indexing[C]. The 12th International Conference on Geoinformatics, Sweden, 2004
    [14] Satoshi I, Feng X. A Global Shallow Water Model Using High Order Multimoment Constrained Finite Volume Method and Icosahedra Grid[J]. Journal of Computational Physics, 2010, 229(5):1774-1796 doi:  10.1016/j.jcp.2009.11.008
    [15] 邢华桥.基于QTM的全球多分辨率水淹模拟[D].北京: 北京建筑工程大学, 2012

    Xing Huaqiao. Global Multi-resolution Submerging Simulation Based on QTM[D]. Beijing: Beijing University of Civil Engineering and Architecture, 2012
    [16] Seong J C. Implementation of an Equal-Area Gridding Method for Global-Scale Image Archiving[J]. Photogrammetric Engineering & Remote Sensing, 2005, 71(5):623-627
    [17] Lee M, Samet H. Navigating Through Triangle Meshes Implemented as Linear Quadtree[J]. ACM Transaction on Graphics, 2000, 19(2):79-121 doi:  10.1145/343593.343598
    [18] 赵学胜, 陈军. QTM地址码与经纬度坐标的快速转换算法[J].测绘学报, 2003, 32(3):272-277 doi:  10.3321/j.issn:1001-1595.2003.03.017

    Zhao Xuesheng, Chen Jun. Fast Translating Algorithm Between QTM Code and Longitude/Latitude Coordination[J]. Acta Geodaetica et Cartographica Sinica, 2003, 32(3):272-277 doi:  10.3321/j.issn:1001-1595.2003.03.017
    [19] Dutton G. Encoding and Handling Geospatial Data with Hierarchical Triangular Meshes[C]. The 7th International Symposium on Spatial Data Handling, Delft, Netherlands, 1996
    [20] 童晓冲, 张永生, 贲进.经纬度坐标与QTM编码的三向互化算法及其精度评价标准[J].武汉大学学报·信息科学版, 2006, 31(1):27-30 http://ch.whu.edu.cn/CN/abstract/abstract2360.shtml

    Tong Xiaochong, Zhang Yongsheng, Ben Jin. Three Orientation Translating Algorithm of Long./Lat. Coordination and QTM Code Along with Its Criterion Judge of Precision[J]. Geomatics and Information Science of Wuhan University, 2006, 31(1):27-30 http://ch.whu.edu.cn/CN/abstract/abstract2360.shtml
    [21] 王谦, 赵学胜, 李亚路.一种基于球面QTM格网的面要素边界跟踪填充算法[J].地理与地理信息学报, 2019, 35(3):16-20 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj201903003

    Wang Qian, Zhao Xuesheng, Li Yalu. An Edge-Following Algorithm of Surface-Entity Based on the Spherical QTM Grid[J]. Geography & Geo-information Science, 2019, 35(3):16-20 http://d.old.wanfangdata.com.cn/Periodical/dlxygtyj201903003
    [22] 赵学胜, 孙文彬, 陈军.基于QTM的全球离散格网变形分布及收敛分析[J].中国矿业大学学报, 2005, 34(4):438-442 doi:  10.3321/j.issn:1000-1964.2005.04.007

    Zhao Xuesheng, Sun Wenbin, Chen Jun. Distortion Distribution and Corvergent Analysis of the Global Discrete Grid Based on QTM[J]. Journal of China University of Mining & Technology, 2005, 34(4):438-442 doi:  10.3321/j.issn:1000-1964.2005.04.007
  • [1] 王政, 赵学胜, 罗富丽, 李亚路, 孙中昶.  球面三角格网单元面积的分形计算 . 武汉大学学报 ● 信息科学版, 2020, 45(10): 1541-1546. doi: 10.13203/j.whugis20180478
    [2] 严韦, 刘建军, 任鑫, 王奋飞.  嫦娥三号月基光学望远镜几何定位精度分析 . 武汉大学学报 ● 信息科学版, 2018, 43(1): 133-137, 166. doi: 10.13203/j.whugis20150162
    [3] 赵龙飞, 赵学胜, 朱思坤, 付瑞全.  一种球面退化四叉树格网的多层次邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2018, 43(4): 529-535. doi: 10.13203/j.whugis20150611
    [4] 孙文彬, 周长江.  一种近似等积球面菱形格网的构建方法 . 武汉大学学报 ● 信息科学版, 2016, 41(8): 1040-1045. doi: 10.13203/j.whugis20140397
    [5] 张清华, 隋立芬, 甘雨, 肖国锐, 戚国宾.  WGS84与ITRS基准转换参数估计及长期演化特性分析 . 武汉大学学报 ● 信息科学版, 2015, 40(3): 395-400.
    [6] 王磊, 赵学胜, 赵龙飞, 殷楠.  基于多层次QTM的球面Voronoi图生成算法 . 武汉大学学报 ● 信息科学版, 2015, 40(8): 1111-1115. doi: 10.13203/j.whugis20140381
    [7] 余接情, 吴立新.  球体坐标与SDOG-ESSG格网码的相互转换算法 . 武汉大学学报 ● 信息科学版, 2015, 40(8): 1116-1122. doi: 10.13203/j.whugis20140032
    [8] 魏二虎, 殷志祥, 李广文, 李智强.  虚拟观测值法在三维坐标转换中的应用研究 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 152-156. doi: 10.13203/j.whugis20120648
    [9] 黄令勇, 吕志平, 任雅奇, 陈正生, 王宇谱.  多元总体最小二乘在三维坐标转换中的应用 . 武汉大学学报 ● 信息科学版, 2014, 39(7): 793-798.
    [10] 王金鑫, 禄丰年, 郭同德, 陈 杰.  球体大圆弧QTM八叉树剖分 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 344-348.
    [11] 罗广祥, 刘苗, 樊鸿宇, 杨芳.  全球等面积四叉树离散格网建模与编码体系研究 . 武汉大学学报 ● 信息科学版, 2012, 37(10): 1252-1255.
    [12] 束蝉方, 李斐, 沈飞.  空间直角坐标向大地坐标转换的新算法 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 561-563.
    [13] 赵学胜, 崔马军, 李昂, 张美娟.  球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 479-482.
    [14] 姜卫平, 马强, 刘鸿飞.  CORS系统中坐标移动转换方法及应用 . 武汉大学学报 ● 信息科学版, 2008, 33(8): 775-778.
    [15] 白建军, 赵学胜, 陈军.  基于线性四叉树的全球离散格网索引 . 武汉大学学报 ● 信息科学版, 2005, 30(9): 805-808.
    [16] 焦文海, 魏子卿, 刘光明, 何涛.  PZ-90 GLONASS与ITRF之间转换参数的谱分析 . 武汉大学学报 ● 信息科学版, 2003, 28(6): 740-744.
    [17] 杨元喜, 徐天河.  不同坐标系综合变换法 . 武汉大学学报 ● 信息科学版, 2001, 26(6): 509-513.
    [18] 徐天河, 杨元喜.  坐标转换模型尺度参数的假设检验 . 武汉大学学报 ● 信息科学版, 2001, 26(1): 70-74.
    [19] 邱卫宁, 王新洲, 陈士银.  我国天文大地网的应变分析 . 武汉大学学报 ● 信息科学版, 1996, 21(2): 115-119,133.
    [20] 周建彬, 贲进, 王蕊, 郑明阳.  四孔六边形全球离散格网一致瓦片层次结构编码运算 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20200530
  • 加载中
图(3) / 表(1)
计量
  • 文章访问数:  547
  • HTML全文浏览量:  122
  • PDF下载量:  84
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-10-24
  • 刊出日期:  2020-02-05

一种改进的QTM地址码与经纬度坐标转换算法

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

    国家自然科学基金 41671394

    国家自然科学基金 41671383

    作者简介:

    王谦, 硕士生, 主要研究方向为全球离散格网及其三维可视化。wangqiancumtb@yahoo.com

    通讯作者: 赵学胜, 博士, 教授。zxs@cumtb.edu.cn
  • 中图分类号: P208

摘要: 地址码与经纬度转换是影响球面四元三角网(quarternary triangular mesh,QTM)应用的主要因素之一。现有算法中,等三角投影法(equal-triangles projection,ETP)转换精确,但算法复杂,效率较低;天顶正交(zenithal ortho triangular,ZOT)投影法转换速度快,但生成的编码缺少方向性;行列逼近法和三向转换法兼顾效率和方向性,但存在较大转换误差。为此,提出了一种改进的转换算法,其基本原理是:根据QTM的行和列,在按一定方向递归逼近地址码的基础上,引入判断点与线段位置关系的操作,从而得到精确的转换结果。该算法在保证精确转换的同时,时间消耗仅为ETP投影法的10.1%~10.4%,且得到的地址码依旧具有方向性,对传统QTM和纬线法剖分的QTM均适用。

English Abstract

王谦, 赵学胜, 王政, 刘青平. 一种改进的QTM地址码与经纬度坐标转换算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
引用本文: 王谦, 赵学胜, 王政, 刘青平. 一种改进的QTM地址码与经纬度坐标转换算法[J]. 武汉大学学报 ● 信息科学版, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
WANG Qian, ZHAO Xuesheng, WANG Zheng, LIU Qingping. An Improved Transformation Algorithm Between QTM Code and Longitude/Latitude Coordinate[J]. Geomatics and Information Science of Wuhan University, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
Citation: WANG Qian, ZHAO Xuesheng, WANG Zheng, LIU Qingping. An Improved Transformation Algorithm Between QTM Code and Longitude/Latitude Coordinate[J]. Geomatics and Information Science of Wuhan University, 2020, 45(2): 303-308, 316. doi: 10.13203/j.whugis20170390
  • 球面四元三角网(quarternary triangular mesh,QTM)结构[1]具有层次组织、全球连续和格网单元形状统一等特性,是目前较为基础、最有影响、应用最为普遍的球面离散格网剖分模型[2],在全球数据组织与管理[3-7]、全球数据质量与地图综合[1, 8]、全球地形可视化[9-13]、全球多分辨率水淹模拟[14-15]、全球影像数据检索[16]、全球导航[17]等领域均有广泛的应用。作为一种球面栅格数据结构,QTM对地理空间数据和信息的表达是建立在矢量数据向QTM地址码转换的基础之上的。对于不断更新的全球海量数据,地址码与经纬度的转换精度及效率已经成为影响系统应用的主要因素[18]

    针对该问题,许多学者进行了深入研究。例如,Goodchild等[4]提出了等三角投影法(equal-triangles projection, ETP),利用ETP投影和距离比较的思想准确地对地址码和经纬度进行了转换,但其计算过程复杂,需要求幂和无理算术等操作,效率较低。Dutton[19]提出了天顶正交(zenithal ortho triangular, ZOT)投影法,在ZOT空间利用Manhattan距离进行转换,将转换效率提高了一个量级,但该算法转换得到的地址码丧失了方向性,不利于计算机的邻近搜索。为解决转换速度和编码方向性之间的矛盾,部分学者提出了行列逼近法[18]及三向互化算法[20],这两种算法的转换效率均与ZOT投影法处于同一量级,且生成的地址码具有方向性,但也产生了新的问题。行列逼近法在经纬度向地址码转换的过程中多出了半个格网的误差,三向互化算法则在格元边界处存在“交叉地带”。这种误差的存在为球面QTM模型空间应用分析与操作埋下了隐患。

    为建立一种既保证转换效率与方向性(以适应于当今海量数据应用需求),又保证较高精度的QTM地址码与经纬度转换算法,本文在行列逼近法和ETP投影法的基础上进行了一系列改进,即建立行列号(ij)与球面经纬度坐标(λφ)以及球面三角形经ETP投影后的平面坐标(xy)之间的转换关系,利用判断点与线段的位置关系代替判断最短距离来确定地址码。在保证转换效率的同时,得到了精确的转换结果,且生成的地址码具有方向性,为球面实体的邻近查询及空间分析奠定了基础。

    • 本文选取改进的QTM作为研究模型。该模型以球内切正八面体作为球面格网划分的基础,在按八面体投影划分时,能与经纬度格网中的标志性要素(如极点、赤道、主子午线等)重合,更容易确定球面上点要素的归属八面体,便于QTM格网与常用的球面经纬度格网之间的转化[21]

      细分方法采用纬线法[22],即对QTM模型中的每一个球面三角形,取其三边中点作为划分点,中点连线的球面投影作为划分线,把球面三角形一分为四,依次类推,根据剖分的层次对整个球面进行近似的均匀划分,其中格网的底(顶)边用纬线代替,这样可以减小格网的变形量,提高了格网数据与地理坐标之间的转换效率,是一种更理想的QTM模型。

    • 在QTM层次数据结构中,点的位置由QTM格元的中心点确定,随着剖分层次的增加,点位精度越来越高。任意一对经纬度坐标有且只有一个三角形地址码与之对应;反之,对于任意一个QTM地址码,就一定有一对经纬度坐标在相应的精度范围内与之对应。一个QTM位置码是由八分数(0~7)和最多30位叶结点四分数字(0~3)组成,在第k个剖分层次,三角形A的地址码表示为Lk=a0a1a2a3ak。其中,a1akk个四分码,a0是八分码,表达最初在0层次的球面正八面体剖分。由于地球被剖分为8个等球面三角形,a0用0~7这8个数字来表达每个三角形面的地址码。对于以下递归划分的三角四叉树码a1a2a3ak,中心三角面的ID码为0,上或下三角面的ID码为1,左三角面的ID码为2,右三角面的ID码为3。这样进行的地址码具有固定的“上下左右”方向性,有利于三角形格网的邻近查询。

    • 根据行列逼近法中的方法对行和列进行定义:行对应与纬线平行的一条格网离散线,列是一行内从经度为0°开始的三角形个数。算法原理如下:

      1) 由地址码向经纬度转换的过程中,首先根据行列逼近算法的原理求出该地址码对应的行号i和列号j;然后应用行列号(ij)解算出对应的经纬度(λφ)。

      2) 由经纬度向地址码转换的过程中,首先根据待求点的纬度φ得到行号i;然后结合已知的地址码Lk-1和行号i求列号j;再将经纬度(λφ)转换到平面上得到平面坐标(xy),并利用行列号ij以及地址码Lk-1求出0号三角形格网中两条非纬线的格边在平面上的线段方程;最后通过比较行号i的奇偶性以及平面点(xy)与格网边线段的位置关系来确定地址码Lk

      为计算方便,可将其他八分体单元的数据首先转换至0号单元,再进行经纬度与地址码之间的转换。

    • 1) 根据三角形的层次K,可以求解出最大行数I

      $$ I = {2^K}$$ (1)

      2) 对地址码Lk按一定顺序进行逐层递归求解出行号i。该过程省去了行列逼近法中借助最大行号I的递归,转换计算更加简单,效率更高。由于三角形格网存在格网方向不一致的问题,需要在层次解算中设置一个标识变量p来标识格元的方向。当p=1时,为顶三角形;当p=-1时,为底三角形。

      (1) 当ak=1时,若p=1,i=2×(i-1)+1;若p=-1,i=2×(i-1)+2。

      (2) 当ak=2或3时,若p=1,i=2×(i-1)+2;若p=-1,i=2×(i-1)+1。

      (3) 当ak=0时,若p=1,i=2×(i-1)+2;若p=-1,i=2×(i-1)+1,p=-p

      (4) 循环步骤(1)~(3),直到求出三角形的行数i

      3) 结合三角形的行数i和剖分层次,对地址码进行逐层递归,求解格元的列数j。具体步骤沿用行列逼近法中的转换步骤,详见文献[18]。

      4) 由行列号ij求得对应3个格网点的经纬度坐标,再求其算术平均值得到格网参考点的经纬度坐标,如图 1所示。

      图  1  参考点经纬度转换原理

      Figure 1.  Transformation Principle of Reference Points' Lontitudes and Latitudes

      (1) 计算格网点经度:

      三角形为正向时(i为奇数):

      $$ {L_T} = 90^\circ \times \frac{{\left( {j - 1} \right)/2}}{{I - i}}$$ (2)
      $$ {L_L} = 90^\circ \times \frac{{\left( {j - 1} \right)/2}}{{I - i + 1}}$$ (3)
      $$ {L_R} = 90^\circ \times \frac{{\left( {j - 1} \right)/2 + 1}}{{I - i + 1}}$$ (4)

      式中,LTLLLR分别为三角形3个顶点的经度。

      三角形为反向时(i为偶数):

      $$ {L_T} = 90^\circ \times \frac{{j/2}}{{I - i + 1}}$$ (5)
      $$ {L_L} = 90^\circ \times \frac{{j/2 - 1}}{{I - i}}$$ (6)
      $$ {L_R} = 90^\circ \times \frac{{j/2}}{{I - i}}$$ (7)

      (2) 计算格网点纬度:

      $$ {L_U} = 90^\circ \times \frac{i}{I}$$ (8)
      $$ {L_D} = 90^\circ \times \frac{{i - 1}}{I}$$ (9)

      式中,LULD分别为顶边、底边纬度。

      (3) 计算格网点经纬度(λφ)的算术平均值:

      $$ \lambda = \frac{{{L_T} + {L_L} + {L_R}}}{3}$$ (10)

      三角形为正向时(i为奇数):

      $$ \varphi = \left( {{L_U} + 2{L_D}} \right)/3$$ (11)

      三角形为反向时(i为偶数):

      $$ \varphi = \left( {2{L_U} + {L_D}} \right)/3$$ (12)
    • 1) 根据三角形的层次K可以求解出最大行数I

      2) 定义N为地址码中除八分码外0的个数。当N为奇数时,为正向格网;当N为偶数时,为反向格网。

      $$ N = \mathop {\sum\limits_{i = 1} }\limits^{k - 1} \left[ {{a_i} = 0} \right]$$ (13)

      式中,[ai=0]为第i位地址码等于0的情况,若等于0,则个数加1。

      3) 根据纬度坐标φ求解格网的行号i,并判断其奇偶性。

      $$ i = {\rm{int}}\left[ {\frac{{\varphi \times I}}{{90}}} \right] + 1$$ (14)

      当格网为正向(N为奇数)且i为偶数时,或当格网为反向(N为偶数)且i为奇数时,ak=1;否则进行下一步计算。

      4) 将经纬度坐标(λφ)转换为平面坐标(xy):

      $$ x = \frac{I}{{\rm{ \mathit{ π} }}}\left[ {\varphi + 2\lambda \left( {1 - \frac{2}{{\rm{ \mathit{ π} }}}\varphi } \right)} \right]$$ (15)
      $$ y = \frac{{\sqrt 3 I}}{{\rm{ \mathit{ π} }}}\varphi $$ (16)

      5) 将前一层地址码Lk-1加0,得到第k层对应四元格网中0号格网单元的地址码code0,由code0与行号i(参考前文转换过程)得到对应列号j

      6) 由行列号ij经数学运算得到0号格网底边(顶边)两格网点的平面坐标分别为P1(xy)、P2(xy)。

      7) 在平面坐标系中,0号格网中两格网边的直线方程为LlLr(以正向格网为例):

      $$ {L_l}:y = - \sqrt 3 x + {b_1}$$ (17)
      $$ {L_r}:y = \sqrt 3 x + {b_2}$$ (18)

      因为P1P2分别为LlLr上的点,可利用式(17)和式(18)求得b1b2

      8) 根据待求点的x坐标判断所属格网,如图 2所示。

      图  2  经纬度向地址码转换原理示意图

      Figure 2.  Diagram of Transformation Principle from Latitude/Longitude to QTM Codes

      P1.xP2.x分别表示P1P2点在平面坐标系中的x坐标,以下仅以正向三角格网为例,判断所属格网的过程,倒向三角格网的判断原理相同。

      (1) 当x < P1.x时,ak=2。

      (2) 当x > P2.x时,ak=3。

      (3) 当P1.x < x < (P1.x+P2.x)/2时,将x代入式(17)得到y1,若y > y1,则ak=0;若y < y1,则ak=2。

      (4) 当(P1.x+P2.x)/2 < x < P2.x时,将x代入式(18)得到y2,若y > y2,则ak=0;若y < y2,则ak=3。

      9) 重复步骤1)~8),循环次数由所需地址码位数决定。

      改进后的算法利用判断点与线段的位置来代替ETP投影法中判断最短距离的过程,在计算过程中只有加、减、乘、除等简单的矢量算术运算,在保证准确转换的基础上大大提高了转换效率,且生成的地址码依然具有方向性,能有效进行邻近查询。

    • 为了比较不同算法间的转换效果,本文选取不同层次(12、14、16、19、21层,分别对应1:400万、1:100万、1:25万、1:5万、1:1万比例尺)、不同数量的坐标点(1万、10万、100万、1 000万),依次利用5种算法(ETP投影法、ZOT投影法、行列逼近法、三向转换法、改进算法)进行地址码与经纬度之间的相互转换。采用的实验设备为ASUS X550V笔记本;硬件配置为Inter(R) Core(TM) i5-3230M CPU @ 2.60 GHz,4 GB RAM;操作系统为Windows 10专业版;开发工具为Visual Studio 2010。

    • 5种算法效率的实验结果如表 1所示。通过表 1可以看出,改进算法的转换效率达到该类算法的最优级别,与ZOT投影法、行列逼近法、三向转换法处于同一量级。改进算法的时间消耗为ETP投影法的10.1%(地址码→经纬度,见图 3(a))和10.4%(经纬度→地址码,见图 3(b))。

      表 1  5种算法效率的实验结果/s

      Table 1.  Experimental Efficiencies of Five Methods/s

      层次 点数/万 改进算法 行列逼近法 三向转换法 ZOT投影法 ETP投影法
      地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码 地址码→经纬度 经纬度→地址码
      12 1 0.05 0.06 0.05 0.06 0.06 0.10 0.05 0.05 0.39 0.66
      10 0.42 0.56 0.41 0.40 0.27 0.93 0.43 0.68 3.08 5.67
      100 3.94 5.33 3.25 3.75 3.05 9.20 4.40 6.93 32.89 60.38
      1 000 38.51 55.51 32.10 37.85 26.98 96.05 45.21 68.75 380.56 610.56
      14 1 0.05 0.07 0.05 0.05 0.04 0.12 0.05 0.05 0.37 0.70
      10 0.46 0.69 0.36 0.44 0.30 1.31 0.48 0.68 4.10 6.90
      100 4.30 6.64 3.28 4.20 3.10 10.82 4.92 8.32 41.26 73.42
      1 000 42.39 68.48 32.94 43.03 30.25 110.13 48.56 84.23 414.57 742.88
      16 1 0.06 0.09 0.05 0.05 0.04 0.14 0.06 0.05 0.70 1.01
      10 0.49 0.86 0.39 0.45 0.36 1.23 0.56 0.77 5.06 7.85
      100 4.67 8.86 3.55 4.61 3.68 12.54 5.72 7.52 50.89 80.25
      1 000 48.15 83.68 36.06 46.56 36.92 121.03 56.89 73.56 511.25 809.14
      19 1 0.08 0.12 0.09 0.06 0.05 0.16 0.06 0.11 0.82 1.06
      10 0.55 0.91 0.42 0.45 0.35 1.63 0.61 0.82 5.89 8.05
      100 5.26 9.19 4.07 4.58 3.70 16.98 6.12 8.09 59.23 80.56
      1 000 52.41 87.86 39.85 46.89 37.12 170.23 61.23 79.82 599.24 812.25
      21 1 0.07 0.13 0.10 0.05 0.05 0.17 0.10 0.11 0.90 1.09
      10 0.59 1.32 0.47 0.50 0.42 1.62 0.65 0.83 6.40 10.26
      100 5.66 12.12 4.72 5.21 4.21 16.11 6.64 8.43 67.25 103.67
      1 000 56.60 120.42 43.60 53.61 42.39 165.23 66.42 84.23 692.47 1 096.25

      图  3  5种算法在不同点数、不同层次的效率比较

      Figure 3.  Efficiency Comparision of Five Methods in Different Points and Different Levels

    • 在转换精度方面,保证了转换效率以及方向性的改进算法同样可以得到准确的转换结果。由经纬度到地址码的转换过程中,行列逼近法较改进算法、ETP投影法和ZOT投影法多出半个格网误差,由地址码转换所得的经纬度坐标没有固定规则,不具参考性。三向转换算法在确定三轴坐标的过程中,将所有格网边均作为小圆弧处理,由于球面为非欧空间,当格网边均以小圆弧处理时,不可避免地存在边界“交叉地带”,从而造成转换误差,且影响范围随着剖分层次的增加而增大。改进算法中,格网的参考点是通过格网点坐标计算所得,可根据不同应用需求改变参考点的计算公式,灵活选择参考点。

    • 本文针对已有算法存在的问题,提出了一种改进的QTM地址码与经纬度转换算法,并给出了详细的算法原理及转换步骤,通过实验对比得出如下结论:

      1)改进算法在行列逼近的基础上加入判断点与线段位置关系的操作,在不丢失效率的基础上得到精确的转换结果;解决了行列逼近法和三向转换法中无法保证转换精度的问题;且改进算法可根据应用需求,灵活确定转换所得的参考点位置,更具普遍适用性。

      2)与ETP投影法相比,改进算法的计算过程仅涉及简单的算术运算,转换效率大大提高,转换时间消耗与ZOT投影法和行列逼近法处于同一量级,其中经纬度→地址码转换过程仅为ETP投影法时间消耗的10.4%,地址码→经纬度转换过程仅为ETP投影法时间消耗的10.1%。

      3)改进算法得到的地址码同样具有方向性,利于计算机的邻近搜索等操作。

参考文献 (22)

目录

    /

    返回文章
    返回