球面四元三角网修正方向编码的邻近搜索算法  

Algorithm of neighbor finding on quaternary triangular mesh with modified direction coding

作　　者：王金鑫[1,2] 陈艺航 曹泽宁 秦子龙 石焱 WANG Jinxin;CHEN Yihang;CAO Zening;QIN Zilong;SHI Yan(School of Geoscience and Technology,Zhengzhou University,Zhengzhou 450001,China;School of Water Conservancy and Environment,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]郑州大学地球科学与技术学院,郑州450001 [2]郑州大学水利科学与工程学院,郑州450001

出　　处：《测绘科学》2021年第5期196-202,共7页Science of Surveying and Mapping

基　　金：河南省科技攻关项目(152102210031);河南省高等学校基础研究计划重点科研项目(16A170003);地理空间信息与数字技术国家测绘地理信息局工程技术研究中心开放基金项目(SIDT2017501);河南省地质矿产勘查开发局2018年财政规划项目(HNGM2018103)。

摘　　要：针对球体测地线八叉树网格(SGOG)采用的修正方向编码邻近关系复杂的问题,该文提出了其邻近搜索算法。先对修正方向编码特征进行分析,发现在递归剖分过程中,子三角形(剖分层次n≥3)相对于其二级父三角形的位置是固定的,随后给出了三角网格方向判断及邻近规则。结果表明,本文算法的效率大约为传统球面四元三角网(QTM)Bartholdi搜索算法的6倍。本研究对SGOG在时空大数据管理与建模中的应用具有重要意义。Aiming at the problem of complex neighbor relation of modified direction coding adopted by the Spherical Geodesic Octree Grid(SGOG),this paper presented its algorithm of neighbor finding.Firstly,the characteristics of directional coding were analyzed,and it was found that the location of sub-triangle(split level n≥3)remained unchanged relative to its secondary parent triangle during the recursive splitting process.Finally,the triangular mesh direction judgment and adjacent rules were approached.The experimental results showed that the efficiency of the proposed algorithm was about 6 times that of the Bartholdi search algorithm on traditional quaternary triangular mesh(QTM).This study was of great significance for the application of SGOG in space-time big data management and modeling.

关 键 词：邻近搜索 四元三角网 修正方向编码 球体测地线八叉树网格 地球剖分网格 

分 类 号：P208[天文地球—地图制图学与地理信息工程]