|
|
- 2017
QTM格网空间中的球面Voronoi图并行生成算法
|
Abstract:
根据球面四元三角网（quaternary triangular mesh， QTM）的离散特征及图形处理器（graphics processing unit，GPU）的多线程原理，用距离的计算与比较代替传统的扩张操作，提出了一种基于QTM的球面Voronoi图并行生成算法，并给出了Voronoi边界提取算法。利用C++语言及统一计算设备架构（compute unified device architecture，CUDA）开发了实验系统。实验结果表明，本文算法能够在球面上快速生成点、线、面数据集的Voronoi图，且能够将Voronoi误差控制在两个格网以内。同时，GPU并行计算的使用，提高了算法的效率
| [1] | Augenbaum J M, Peskin C S. On the Construction of the Voronoi Mesh on a Sphere[J]. <em>Journal of Computational Physics</em>, 1985, 59(2):177-192 |
| [2] | Ma Y, Chen Q. Fast Delaunay Triangulation and Voronoi Diagram Generation on the Sphere[C]. The Second World Congress on Software Engineering, Wuhan, 2010 |
| [3] | Dinis J, Mamede M. Sweeping the Sphere[C]. International Symposium on Voronoi Diagrams in Science and Engineering, Quebec, Canada, 2010 |
| [4] | Zhao Xuesheng, Chen Jun, Wang Jinzhuang. QTM-Based Algorithm for the Generating of Voronoi Diagram for Spherical Object[J]. <em>Acta Geodaetica et Cartographica Sinica</em>, 2002, 31(2):158-163(赵学胜, 陈军, 王金庄. 基于O-QTM的球面Voronoi图的生成算法[J]. 测绘学报, 2002, 31(2):158-163) |
| [5] | Rong G, Tiow-S T. Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform[C]. The 2006 ACM Symposium on Interactive 3D Graphics and Games, Redwood City, 2006 |
| [6] | Cao T-T, Tang K, Mohamed A, et al. Parallel Banding Algorithm to Compute Exact Distance Transform with GPU[C]. The 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, Bethesda, 2010 |
| [7] | Majdandzic I, Trefftz C, Wolffe G. Computation of Voronoi Diagrams using a Graphics Processing Unit[C]. IEEE International Conference on Electro/Information Technology,Ames, 2008 |
| [8] | Yan Haowen, Wang Bangsong. A MWVD-Based Algorithm for Point Cluster Generation[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2013, 38(9):1088-1091(闫浩文, 王邦松. 地图点群综合的加权Voronoi算法[J]. 武汉大学学报·信息科学版, 2013, 38(9):1088-1091) |
| [9] | Tong Xiaochong, Ben Jin, Zhang Yongsheng. The Generation Algorithm for Spherical Voronoi Diagram of Different Aggregation[J].<em>Acta Geodaetica et Cartographica Sinica</em>, 2006, 35(1):83-89(童晓冲, 贲进, 张永生. 不同集合的球面矢量Voronoi图生成算法[J]. 测绘学报, 2006, 35(1):83-89) |
| [10] | Ben J, Tong X, Zhang H, et al. A Spherical Voronoi Algorithm Based on Hexagonal Grid[J]. <em>Journal of Zhengzhou Institute of Surveying and Mapping</em>, 2006, 23(5):328-330(贲进, 童晓冲, 张衡, 等. 基于球面六边形格网的球面Voronoi图生成算法[J]. 测绘科学技术学报, 2006, 23(5):328-330) |
| [11] | Chen Weifeng, Wang Rui, Pan Minghao, et al. GPU-Based Fast Spherical Distance Transform[J]. <em>Chinese Journal of Computers</em>,2011, 34(3):499-507(陈伟锋, 王锐, 潘明皓, 等. 基于GPU的快速球面距离变换[J].计算机学报, 2011, 34(3):499-507) |
| [12] | Wang Zhonghui, Yan Haowen. Computation of Direction Relations Between Object Groups Based on Direction Voronoi Diagram Model[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2013, 38(5):584-588(王中辉, 闫浩文. 基于方向Voronoi图模型的群组目空间方向关系计算[J]. 武汉大学学报·信息科学版, 2013, 38(5):584-588) |
| [13] | Hu Wei, Tao Weidong, Yuan Zhenyu, et al. A Method of Vectorization of Scanning Map Based on Voronoi Diagrams[J]. <em>Geomatics and Information science of Wuhan University</em>, 2013, 38(4):470-474(胡玮, 陶伟东, 苑振宇, 等. 一种Voronoi图的扫描地图矢量化方法[J]. 武汉大学学报·信息科学版, 2013, 38(4):470-474) |
| [14] | 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 |
| [15] | Renka R J. Delaunay Triangulation and Voronoi diagram on the Surface of a Sphere[J]. <em>ACM Transactions on Mathematical Software</em>, 1997, 23(3):416-434 |
| [16] | Zhao Xuesheng. Spherical Voronoi Data Model Based on QTM[M]. Beijing:Surveying and Mapping Press, 2004(赵学胜. 基于QTM的球面Voronoi数据模型[M]. 北京:测绘出版社, 2004) |
| [17] | 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) |
| [18] | Kenneth E H, Tim C, John K, et al. Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware[C]. The 26th Annual Conference on Computer Graphics and Interactive Techniques,Los Angeles, 1999 |
| [19] | Rong G, Liu Y, Wang W, et al. GPU-Assisted Computation of Centroidal Voronoi Tessellation[J]. <em>IEEE Transactions on Visualization and Computer Graphics</em>, 2011, 17(3):345-356 |
| [20] | Hyeon-Suk N, Chung-Nim L, Otfried C. Voronoi Diagrams on the Sphere[J]. <em>Computation Geometry:Theory and Applications</em>, 2002, 23(2):183-194 |
| [21] | Christopher G, Mir A M. Towards the Global GIS[J]. <em>ISPRS Journal of Photogrammetry & Remote Sensing</em>, 2000, 55(3):150-163 |
| [22] | Yang W, Christopher G. Managing Spatial Objects with the VMO-Tree[C]. The 7th International Symposium on Spatial Data Handling,the Netherlands, 1996 |
