| 基于多层次QTM的球面Voronoi图生成算法 |
| |
| 引用本文： | 王磊,赵学胜,赵龙飞,殷楠.基于多层次QTM的球面Voronoi图生成算法[J].武汉大学学报(信息科学版),2015,40(8):1111-1115. |
| |
| 作者姓名： | 王磊 赵学胜 赵龙飞 殷楠 |
| |
| 作者单位： | 1中国矿业大学(北京地球科学与测绘工程学院,北京,100083 |
| |
| 基金项目： | 国家自然科学基金资助项目(41171306；41171304) |
| |
| 摘 要： | 随着格网层次的增大,基于全球离散格网的球面Voronoi图生成算法的格网数据量与Voronoi图生成时间都呈指数增长,在高层次时容易出现算法效率较低,甚至内存溢出无法执行等情况。利用球面四元三角格网的层次性,提出了一个基于多层次QTM的球面Voronoi图生成算法。首先用全球低层次QTM格网生成Voronoi图,然后对Voronoi边界格网进行再次剖分,得到下一层次的Voronoi图,重复进行,直至达到目标层次。实验结果表明,相对于单一层次的确定归属算法和扩张算法,该算法能够生成更高层次的Voronoi图,且效率较前两者分别提高了22倍和25倍(第9层)。
|
| 关 键 词： | 球面Voronoi图 全球离散格网 四元三角网 多层次 邻近搜索 |
| 收稿时间： | 2014-05-13 |
Multi-level QTM Based Algorithm for Generating Spherical Voronoi Diagram |
| |
| Institution: | 1College of Geoscience &Surveying Engineering,China University of Mining &Technology(Beijing;,Beijing 100083,China |
| |
| Abstract: | A spherical Voronoi diagram of point sets,line sets and area sets can be well handled byGDG-based(GDG:Global Discrete Grid)algorithms.However,the grid data volume and the timeconsumed for generating spherical Voronoi diagrams increases exponentially with the growth of theGDG levels,which leads to lower efficiency at higher levels.To overcome these deficiencies,a multi-level QTM-based(QTM:Quaternary Triangular Mesh)algorithm is proposed.Firstly,a sphericalVoronoi diagram is generated in a lower level.Then,the triangles that form the Voronoi boundariesare subdivided to get Voronoi diagrams at higher levels.The results show that a spherical Voronoi di-agram of higher levels can be generated by this algorithm more efficently than those single-level algo-rithms;as it was improved about 22and 25times at Level 9. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《武汉大学学报(信息科学版)》浏览原始摘要信息 |
| 点击此处可从《武汉大学学报(信息科学版)》下载免费的PDF全文 |
|
