一种球面退化四叉树格网的多层次邻近搜索算法
|
摘要
格网单元的邻近搜索是聚类、索引、查询等空间操作的基础,但现有方法大都局限于单个剖分层次,无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网(DQG)模型基础上,提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型,然后引入细分评价函数确定格网单元的邻近单元层次,设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法,最后与单层次邻近搜索算法进行了对比实验。结果表明,搜索同一区域,该算法的耗时成本约为DQG单层次搜索算法的1/3(层次为11);将该算法用于全球地形实时可视化表达,平均刷新帧率达到60帧/s。
The model of Global Discrete Grid is the base of Digital Earth and Spatial Information Grid.Adjacent search of grid cell is the basis of spatial operations,such as aggregation,index,and query,and has become one of the key problems in the global discrete grids researches.However,most existing methods are limited to single-level,cannot directly meet the application requirements of the global multi-scale data integration query and operation.A multi-level adjacent searching algorithm is proposed based on spherical DQG(degenerate quadtree grid)model in this paper.Firstly,the partition principle and encoding rules of the degenerate quadtree grid on sphere were analyzed,the multi-level DQG-based grid model is established by using view-dependent technique.Then,the segmentation evaluation function is introduced to determine the adjacent cell level of grid unit.A dynamic and multilevel adjacent searching algorithm is designed and implemented as level difference between adjacent grids is not more than 1.Finally,the contrast experiment with the single-level algorithm and the multi-level algorithm is done.The results show that the time consume of this algorithm is only about1/3 to that of the DQG-based single-level algorithm(level 11)when searching for the same area,and the average frame refresh rate reaches 60 frames/s when this algorithm is used to real-time visualization of the global terrain.The new method not only eliminates the grids cracks between the same level or the different levels completely,but avoids the phenomenons of T connection and steep as well.In the end,the conclusions and future works are presented.
The model of Global Discrete Grid is the base of Digital Earth and Spatial Information Grid.Adjacent search of grid cell is the basis of spatial operations,such as aggregation,index,and query,and has become one of the key problems in the global discrete grids researches.However,most existing methods are limited to single-level,cannot directly meet the application requirements of the global multi-scale data integration query and operation.A multi-level adjacent searching algorithm is proposed based on spherical DQG(degenerate quadtree grid)model in this paper.Firstly,the partition principle and encoding rules of the degenerate quadtree grid on sphere were analyzed,the multi-level DQG-based grid model is established by using view-dependent technique.Then,the segmentation evaluation function is introduced to determine the adjacent cell level of grid unit.A dynamic and multilevel adjacent searching algorithm is designed and implemented as level difference between adjacent grids is not more than 1.Finally,the contrast experiment with the single-level algorithm and the multi-level algorithm is done.The results show that the time consume of this algorithm is only about1/3 to that of the DQG-based single-level algorithm(level 11)when searching for the same area,and the average frame refresh rate reaches 60 frames/s when this algorithm is used to real-time visualization of the global terrain.The new method not only eliminates the grids cracks between the same level or the different levels completely,but avoids the phenomenons of T connection and steep as well.In the end,the conclusions and future works are presented.
引文
[1]Vince A,Zheng X.Arithmetic and Fourier Transform for the PYXIS Multi-resolution Digital Earth Model[J].International Journal of Digital Earth,2009,2(1):59-79
[2]Bernardin T,Cowgill E,Kreylos O,et al.Crusta:A New Virtual Globe for Real-Time Visualization of Sub-meter Digital Topography at Planetary Scales[J].Computers&Geosciences,2011,37(1):75-85
[3]Goodchild M F,Yang S.A Hierarchical Spatial Data Structure for Global Geographic Information Systems[M].New York:Academic Press Inc.,1992
[4]Bartholdi J,Goldsman P.Continuous Indexing of Hierarchical Subdivisions of the Globe[J].International Journal of Geographic Information Science,2001,15(6):489-522
[5]Sun Wenbin,Zhao Xuesheng.Algorithm of Neighbor Finding on Sphere Triangular Meshes with Quaternary Code[J].Geomatics and Information Science of Wuhan University,2007,32(4):350-352(孙文彬,赵学胜.基于Quaternary编码的球面三角格网邻近搜索算法[J].武汉大学学报·信息科学版,2007,32(4):350-352)
[6]Bai Jianjun,Zhao Xuesheng,Chen Jun.Indexing of Discrete Global Grids Using Linear Quadtree[J].Geomatics and Information Science of Wuhan University,2005,30(9):805-808(白建军,赵学胜,陈军.基于线性四叉树的全球离散格网索引[J].武汉大学学报·信息科学版,2005,30(9):805-808)
[7]Amiri A M,Bhojani F,Samavati F.One-to-Two Digital Earth[M]//Bebis G,Boyle R,Parvin B,et al.Advances in Visual Computing.Berlin Springer Berlin Heidelberg,2013:681-692
[8]Sahr K.Icosahedral Modified Generalized Balanced Ternary and Aperture 3 Hexagon Tree:US8229237[P].2012-7-24
[9]Peterson P.Close-Packed Uniformly Adjacent,Multi-resolutional Overlapping Spatial Data Ordering:US 8018458[P].2011-9-13
[10]Tong X,Ben J,Wang Y,et al.Efficient Encoding and Spatial Operation Scheme for Aperture 4Hexagonal Discrete Global Grid System[J].International Journal of Geographical Information Science,2013,27(5):898-921
[11]Ben Jin,Tong Xiaochong,Yuan Chaopeng.Indexing Schema of the Aperture 4 Hexagonal Discrete Global Grid System[J].Acta Geodaetica et Cartographica Sinica,2011,40(6):785-789(贲进,童晓冲,元朝鹏.孔径为4的全球六边形格网系统索引方法[J].测绘学报,2011,40(6):785-789)
[12]Hou Miaole,Xing Huaqiao,Zhao Xuesheng,et al.Computing of Complicated Topological Relation in Spherical Surface Quaternary Triangular Mesh[J].Geomatics and Information Science of Wuhan University,2012,37(4):468-471(侯妙乐,邢华桥,赵学胜,等.球面四元三角网的复杂拓扑关系计算[J].武汉大学学报·信息科学版,2012,37(4):468-471)
[13]Chen J,Zhao X,Li Z.An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM[J].Photogrammetric Engineering&Remote Sensing,2003,69(1):79-89
[14]Tong Xiaochong,Ben Jin,Zhang Yongsheng.Expression of Spherical Entities and Generation of Voronoi Diagram Based on Truncated Icosahedron DGG[J].Geomatics and Information Science of Wuhan University,2006,31(11):966-970(童晓冲,贲进,张永生.基于二十面体剖分格网的球面实体表达与Voronoi图生成[J].武汉大学学报·信息科学版,2006,31(11):966-970)
[15]Wang Jiaojiao.Geometric Overlay Algorithm for Egration of Vector Polyline and Dem Based on Spherical DQG[J].Journal of Liaoning Technical University(Natural Science),2013,32(10):1 399-1 405(王姣姣.矢量线与球面DQG地形集成的几何叠加算法[J].辽宁工程技术大学学报:自然科学版,2013,32(10):1 399-1 405)
[16]Chen H,Meer P.Robust Fusion of Uncertain Information[J].Systems,Man,and Cybernetics,Part B:Cybernetics,IEEE Transactions on,2005,35(3):578-586
[17]Dutton G.Modeling Locational Uncertainty via Hierarchical Tessellation[M]//Goodchild M,Gopal S.Accuracy of Spatial Databases.London:Taylor&Francis,1989:125-140
[18]Cui Majun,Zhao Xuesheng.Tessellation and Distortion Analysis Based on Spherical DQG[J].Geography and Geo-Information Science,2007,23(6):23-25(崔马军,赵学胜.球面退化四叉树格网的剖分及变形分析[J].地理与地理信息科学,2007,23(6):23-25)
[19]Zhao Xuesheng,Cui Majun,Li Ang,et al.An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J].Geomatics and Information Science of Wuhan University,2009,34(4):479-482(赵学胜,崔马军,李昂,等.球面退化四叉树格网单元的邻近搜索算法[J].武汉大学学报·信息科学版,2009,34(4):479-482)
[20]Xu Miaozhong.Research on Real-Time Rendering for Large Scale Terrain[J].Geomatics and Information Science of Wuhan University,2005,30(5):392-395(许妙忠.大规模地形实时绘制的算法研究[J].武汉大学学报·信息科学版,2005,30(5):392-395)
[21]Cui Majun,Gao Yanli,Zhao Xuesheng.A Fast Translating Algorithm Between DQG Code and Longitude/Latitude Coordinates[J].Geography and Geo-Information Science,2009,25(3):42-44(崔马军,高彦丽,赵学胜.球面DQG地址码与经纬度坐标的快速转换算法[J].地理与地理信息科学,2009,25(3):42-44)
[2]Bernardin T,Cowgill E,Kreylos O,et al.Crusta:A New Virtual Globe for Real-Time Visualization of Sub-meter Digital Topography at Planetary Scales[J].Computers&Geosciences,2011,37(1):75-85
[3]Goodchild M F,Yang S.A Hierarchical Spatial Data Structure for Global Geographic Information Systems[M].New York:Academic Press Inc.,1992
[4]Bartholdi J,Goldsman P.Continuous Indexing of Hierarchical Subdivisions of the Globe[J].International Journal of Geographic Information Science,2001,15(6):489-522
[5]Sun Wenbin,Zhao Xuesheng.Algorithm of Neighbor Finding on Sphere Triangular Meshes with Quaternary Code[J].Geomatics and Information Science of Wuhan University,2007,32(4):350-352(孙文彬,赵学胜.基于Quaternary编码的球面三角格网邻近搜索算法[J].武汉大学学报·信息科学版,2007,32(4):350-352)
[6]Bai Jianjun,Zhao Xuesheng,Chen Jun.Indexing of Discrete Global Grids Using Linear Quadtree[J].Geomatics and Information Science of Wuhan University,2005,30(9):805-808(白建军,赵学胜,陈军.基于线性四叉树的全球离散格网索引[J].武汉大学学报·信息科学版,2005,30(9):805-808)
[7]Amiri A M,Bhojani F,Samavati F.One-to-Two Digital Earth[M]//Bebis G,Boyle R,Parvin B,et al.Advances in Visual Computing.Berlin Springer Berlin Heidelberg,2013:681-692
[8]Sahr K.Icosahedral Modified Generalized Balanced Ternary and Aperture 3 Hexagon Tree:US8229237[P].2012-7-24
[9]Peterson P.Close-Packed Uniformly Adjacent,Multi-resolutional Overlapping Spatial Data Ordering:US 8018458[P].2011-9-13
[10]Tong X,Ben J,Wang Y,et al.Efficient Encoding and Spatial Operation Scheme for Aperture 4Hexagonal Discrete Global Grid System[J].International Journal of Geographical Information Science,2013,27(5):898-921
[11]Ben Jin,Tong Xiaochong,Yuan Chaopeng.Indexing Schema of the Aperture 4 Hexagonal Discrete Global Grid System[J].Acta Geodaetica et Cartographica Sinica,2011,40(6):785-789(贲进,童晓冲,元朝鹏.孔径为4的全球六边形格网系统索引方法[J].测绘学报,2011,40(6):785-789)
[12]Hou Miaole,Xing Huaqiao,Zhao Xuesheng,et al.Computing of Complicated Topological Relation in Spherical Surface Quaternary Triangular Mesh[J].Geomatics and Information Science of Wuhan University,2012,37(4):468-471(侯妙乐,邢华桥,赵学胜,等.球面四元三角网的复杂拓扑关系计算[J].武汉大学学报·信息科学版,2012,37(4):468-471)
[13]Chen J,Zhao X,Li Z.An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM[J].Photogrammetric Engineering&Remote Sensing,2003,69(1):79-89
[14]Tong Xiaochong,Ben Jin,Zhang Yongsheng.Expression of Spherical Entities and Generation of Voronoi Diagram Based on Truncated Icosahedron DGG[J].Geomatics and Information Science of Wuhan University,2006,31(11):966-970(童晓冲,贲进,张永生.基于二十面体剖分格网的球面实体表达与Voronoi图生成[J].武汉大学学报·信息科学版,2006,31(11):966-970)
[15]Wang Jiaojiao.Geometric Overlay Algorithm for Egration of Vector Polyline and Dem Based on Spherical DQG[J].Journal of Liaoning Technical University(Natural Science),2013,32(10):1 399-1 405(王姣姣.矢量线与球面DQG地形集成的几何叠加算法[J].辽宁工程技术大学学报:自然科学版,2013,32(10):1 399-1 405)
[16]Chen H,Meer P.Robust Fusion of Uncertain Information[J].Systems,Man,and Cybernetics,Part B:Cybernetics,IEEE Transactions on,2005,35(3):578-586
[17]Dutton G.Modeling Locational Uncertainty via Hierarchical Tessellation[M]//Goodchild M,Gopal S.Accuracy of Spatial Databases.London:Taylor&Francis,1989:125-140
[18]Cui Majun,Zhao Xuesheng.Tessellation and Distortion Analysis Based on Spherical DQG[J].Geography and Geo-Information Science,2007,23(6):23-25(崔马军,赵学胜.球面退化四叉树格网的剖分及变形分析[J].地理与地理信息科学,2007,23(6):23-25)
[19]Zhao Xuesheng,Cui Majun,Li Ang,et al.An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J].Geomatics and Information Science of Wuhan University,2009,34(4):479-482(赵学胜,崔马军,李昂,等.球面退化四叉树格网单元的邻近搜索算法[J].武汉大学学报·信息科学版,2009,34(4):479-482)
[20]Xu Miaozhong.Research on Real-Time Rendering for Large Scale Terrain[J].Geomatics and Information Science of Wuhan University,2005,30(5):392-395(许妙忠.大规模地形实时绘制的算法研究[J].武汉大学学报·信息科学版,2005,30(5):392-395)
[21]Cui Majun,Gao Yanli,Zhao Xuesheng.A Fast Translating Algorithm Between DQG Code and Longitude/Latitude Coordinates[J].Geography and Geo-Information Science,2009,25(3):42-44(崔马军,高彦丽,赵学胜.球面DQG地址码与经纬度坐标的快速转换算法[J].地理与地理信息科学,2009,25(3):42-44)