多边形叠加Vatti算法的VCS优化方法与GPU并行化  

VCS Optimization Method of Vatti Algorithm for Polygon Overlay and Parallelization Using GPU

作　　者：张志锟 范俊甫[1] 徐少波 陈政 ZHANG Zhikun;FAN Junfu;XU Shaobo;CHEN Zheng(School of Civil and Architectural Engineering,Shandong University of Technology,Zibo 255000,China;School of Architecture&Urban Planning,Shenzhen University,Shenzhen 51800,China)

机构地区：[1]山东理工大学建筑工程学院,淄博255000 [2]深圳大学建筑与城市规划学院,深圳518060

出　　处：《地球信息科学学报》2022年第3期437-447,共11页Journal of Geo-information Science

基　　金：国家自然科学基金项目(42171413);国家重点研发计划项目(2017YFB0503500);山东省自然科学基金项目(ZR2020MD015、ZR2020MD018);山东省重大科技创新工程项目(2019JZZY020103);山东理工大学青年教师发展支持计划项目(4072-115016)。

摘　　要：Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS(Vertex Coordinate Pre-Sorting)方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。Vatti algorithm is one of the widely used vector polygon clipping algorithms.In the process of intersection calculation based on the construction of scanning beams,the data structure of binary tree and recursive calculation method lead to an obvious increase in time consumption when dealing with polygons with plenty of vertices.The calculation efficiency of the algorithm is significantly affected by the boundary vertex number of the overlapping polygons.Aiming at the efficiency improvement of the time-consuming scanning beam construction process of Vatti algorithm,this paper proposes an optimization approach based on polygon boundary vertex pre-sorting method,which is named VCS(Vertex Coordinate Pre-Sorting)method,and realizes a fine-grained level parallel Vatti algorithm on GPU device based on CUDA.The VCS method replaces the original binary tree data structure of Vatti algorithm with a double linked list,and obtains an obvious efficiency improvement on polygon boundary vertex information searching process with a smaller additional storage space.In GPU environment,the bitonic sorting method is used to sort the elements of polygon boundary vertex array in parallel and filter out the valid values,which overcomes the defect of low efficiency caused by the original algorithm using binary tree data structure.Experimental results show that the improved algorithm presents higher efficiency with the same calculation accuracy as the original algorithm.When the number of polygon vertices is 920000 and the number of threads in each thread block is 32,compared with the serial algorithm which builds scan beams using CPU,the VCS optimization method with GPU-based parallel polygon clipping algorithm obtains a relative acceleration ratio of 39.6 times,and the efficiency of vector polygon superposition analysis algorithm is improved by 4.9 times overall.

关 键 词：叠加分析 多边形裁剪 CUDA并行 双调排序 VCS Vatti算法 数据结构 高性能计算 GIS 

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