地球信息科学学报 ›› 2022, Vol. 24 ›› Issue (3): 437-447.doi: 10.12082/dqxxkx.2022.210409

• 地球信息科学理论与方法 • 上一篇    下一篇

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

张志锟1(), 范俊甫1,*(), 徐少波2, 陈政1   

  1. 1.山东理工大学 建筑工程学院,淄博 255000
    2.深圳大学 建筑与城市规划学院,深圳 518060
  • 收稿日期:2021-07-18 修回日期:2021-08-19 出版日期:2022-03-25 发布日期:2022-05-25
  • 通讯作者: *范俊甫(1985— ),男,山东聊城人,博士,副教授,主要从事高性能地学计算与遥感智能计算研究。 E-mail: fanjf@sdut.edu.cn
  • 作者简介:张志锟(1995— ),男,山东泰安人,硕士生,主要从事高性能地学计算研究。E-mail: 1870506231@qq.com
  • 基金资助:
    国家自然科学基金项目(42171413);国家重点研发计划项目(2017YFB0503500);山东省自然科学基金项目(ZR2020MD015);山东省自然科学基金项目(ZR2020MD018);山东省重大科技创新工程项目(2019JZZY020103);山东理工大学青年教师发展支持计划项目(4072-115016)

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

ZHANG Zhikun1(), FAN Junfu1,*(), XU Shaobo2, CHEN Zheng1   

  1. 1. School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255000, China
    2. School of Architecture & Urban Planning, Shenzhen University, Shenzhen 518060, China
  • Received:2021-07-18 Revised:2021-08-19 Online:2022-03-25 Published:2022-05-25
  • Supported by:
    National Natural Science Foundation of China(42171413);National Key R&D Program of China(2017YFB0503500);Natural Science Foundation of Shandong Province(ZR2020MD015);Natural Science Foundation of Shandong Province(ZR2020MD018);Major Scientific And Technological Innovation Projects of Shandong Province(2019JZZY020103);Young Teacher Development Support Program of Shandong University of Technology(4072-115016)

摘要:

Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS(Vertex Coordinate Pre-Sorting)方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。

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

Abstract:

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 920 000 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.

Key words: overlay analysis, polygon clipping, CUDA parallel, bitonic sort, VCS, Vatti algorithm, data structure, high performance computing, GIS