|
|
- 2018
一种球面退化四叉树格网的多层次邻近搜索算法
|
Abstract:
格网单元的邻近搜索是聚类、索引、查询等空间操作的基础，但现有方法大都局限于单个剖分层次，无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网（DQG）模型基础上，提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型，然后引入细分评价函数确定格网单元的邻近单元层次，设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法，最后与单层次邻近搜索算法进行了对比实验。结果表明，搜索同一区域，该算法的耗时成本约为DQG单层次搜索算法的1/3（层次为11）；将该算法用于全球地形实时可视化表达，平均刷新帧率达到60帧/s
| [1] | Tong Xiaochong, Ben Jin, Zhang Yongsheng. Expression of Spherical Entities and Generation of Voronoi Diagram Based on Truncated Icosahedron DGG[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2006, 31(11):966-970(童晓冲, 贲进, 张永生. 基于二十面体剖分格网的球面实体表达与Voronoi图生成[J]. 武汉大学学报·信息科学版, 2006, 31(11):966-970) |
| [2] | Xu Miaozhong. Research on Real-Time Rendering for Large Scale Terrain[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2005, 30(5):392-395(许妙忠. 大规模地形实时绘制的算法研究[J]. 武汉大学学报·信息科学版, 2005, 30(5):392-395) |
| [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].<em>International Journal of Geographic Information Science</em>, 2001, 15(6):489-522 |
| [5] | Bai Jianjun, Zhao Xuesheng, Chen Jun. Indexing of Discrete Global Grids Using Linear Quadtree[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2005, 30(9):805-808(白建军, 赵学胜, 陈军. 基于线性四叉树的全球离散格网索引[J]. 武汉大学学报·信息科学版, 2005, 30(9):805-808) |
| [6] | Tong X, Ben J, Wang Y, et al. Efficient Encoding and Spatial Operation Scheme for Aperture 4 Hexagonal Discrete Global Grid System[J]. <em>International Journal of Geographical Information Science</em>, 2013, 27(5):898-921 |
| [7] | Ben Jin, Tong Xiaochong, Yuan Chaopeng. Indexing Schema of the Aperture 4 Hexagonal Discrete Global Grid System[J]. <em>Acta Geodaetica et Cartographica Sinica,</em> 2011, 40(6):785-789(贲进, 童晓冲, 元朝鹏. 孔径为4的全球六边形格网系统索引方法[J]. 测绘学报, 2011, 40(6):785-789) |
| [8] | Wang Jiaojiao. Geometric Overlay Algorithm for Egration of Vector Polyline and Dem Based on Spherical DQG[J]. <em>Journal of Liaoning Technical University (Natural Science),</em> 2013, 32(10):1399-1405(王姣姣. 矢量线与球面DQG地形集成的几何叠加算法[J]. 辽宁工程技术大学学报:自然科学版, 2013, 32(10):1399-1405) |
| [9] | Sun Wenbin, Zhao Xuesheng. Algorithm of Neighbor Finding on Sphere Triangular Meshes with Quaternary Code[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2007, 32(4):350-352(孙文彬, 赵学胜. 基于Quaternary编码的球面三角格网邻近搜索算法[J]. 武汉大学学报·信息科学版, 2007, 32(4):350-352) |
| [10] | 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 |
| [11] | Sahr K. Icosahedral Modified Generalized Balanced Ternary and Aperture 3 Hexagon Tree:US 8229237[P]. 2012-7-24 |
| [12] | Cui Majun, Gao Yanli, Zhao Xuesheng. A Fast Translating Algorithm Between DQG Code and Longitude/Latitude Coordinates[J]. <em>Geography and Geo-Information Science</em>, 2009, 25(3):42-44(崔马军, 高彦丽, 赵学胜. 球面DQG地址码与经纬度坐标的快速转换算法[J]. 地理与地理信息科学, 2009, 25(3):42-44) |
| [13] | Peterson P. Close-Packed Uniformly Adjacent, Multi-resolutional Overlapping Spatial Data Ordering:US 8018458[P]. 2011-9-13 |
| [14] | Vince A, Zheng X. Arithmetic and Fourier Transform for the PYXIS Multi-resolution Digital Earth Model[J]. <em>International Journal of Digital Earth</em>, 2009, 2(1):59-79 |
| [15] | 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]. <em>Computers & Geosciences</em>, 2011, 37(1):75-85 |
| [16] | Hou Miaole, Xing Huaqiao, Zhao Xuesheng, et al. Computing of Complicated Topological Relation in Spherical Surface Quaternary Triangular Mesh[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2012, 37(4):468-471(侯妙乐, 邢华桥, 赵学胜, 等. 球面四元三角网的复杂拓扑关系计算[J]. 武汉大学学报·信息科学版, 2012, 37(4):468-471) |
| [17] | Chen H, Meer P. Robust Fusion of Uncertain Information[J]. <em>Systems, Man, and Cybernetics</em>, <em>Part B:Cybernetics, IEEE Transactions on</em>, 2005, 35(3):578-586 |
| [18] | Dutton G. Modeling Locational Uncertainty via Hierarchical Tessellation[M]//Goodchild M, Gopal S. Accuracy of Spatial Databases. London:Taylor & Francis,1989:125-140 |
| [19] | Cui Majun, Zhao Xuesheng. Tessellation and Distortion Analysis Based on Spherical DQG[J].<em>Geography and Geo-Information Science</em>,2007, 23(6):23-25(崔马军, 赵学胜. 球面退化四叉树格网的剖分及变形分析[J]. 地理与地理信息科学, 2007, 23(6):23-25) |
| [20] | Zhao Xuesheng, Cui Majun, Li Ang, et al. An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2009, 34(4):479-482(赵学胜, 崔马军, 李昂, 等. 球面退化四叉树格网单元的邻近搜索算法[J]. 武汉大学学报·信息科学版, 2009, 34(4):479-482) |
| [21] | Chen J, Zhao X, Li Z. An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM[J].<em>Photogrammetric Engineering & Remote Sensing</em>, 2003, 69(1):79-89 |
