2022 , Vol. 24 >Issue 3: 437 - 447

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

• ZHANG Zhikun , 1 ,
• FAN Junfu , 1, * ,
• XU Shaobo 2 ,
• CHEN Zheng 1
Expand
• 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
*FAN Junfu, E-mail:

Request revised date: 2021-08-19

Online 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)

### 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.

ZHANG Zhikun , FAN Junfu , XU Shaobo , CHEN Zheng . VCS Optimization Method of Vatti Algorithm for Polygon Overlay and Parallelization Using GPU[J]. Journal of Geo-information Science, 2022 , 24(3) : 437 -447 .

### 2 Vatti算法优化过程

#### 2.1 Vatti算法计算流程及效率分析

Vatti算法的步骤主要包括预处理、扫描束的构建、裁剪以及结果写入、数据清理等其他部分,其流程如图1（a）所示。在Vatti算法的预处理阶段,读取矢量多边形后需要利用最小外包矩形（MBR）过滤掉不存在相交可能性的多边形。在扫描束构建过程中,通过如图1（b）所示的扫面线M与扫描线N构成的有序扫描线集合自下而上来遍历多边形的所有顶点,提取多边形的每个节点的位置信息存放到边表（Edge Table）中,同时将所有不相同的y值存放到二叉树中。找到所有的局部最小点,将局部最小点存储到局部最小点表（LMT）中,所有的局部最小点以单向链表的形式连接在一起。同时,从LMT的最低点处递归,根据每条边界线的第一条边的x值和斜率信息确定当前边界线在边界线列表中插入的位置,其结构如图1（c）所示。
##### 图1 Vatti算法流程

Fig. 1 Flow chart of Vatti algorithm

###### 表1 实验数据详细信息

Tab. 1 Details of experimental data

2009 9129 856 238 9475
2010 9383 832 827 9472

##### 图2 Vatti算法各部分耗时

Fig. 2 Time consumption of each part of Vatti algorithm

#### 2.2 VCS优化方法

##### 图3 原始算法与VCS优化方法的扫描线赋值、边界线位置查询过程

Fig. 3 The process of scan line assignment and boundary line position query between the original algorithm and VCS optimization method

##### 图4 VCS优化方法的并行化流程

Fig. 4 Flow chart of algorithm parallelization

##### 图5 使用VCS方法优化前后耗时对比

Fig. 5 Comparison of time consumption before and after optimization using VCS method

#### 2.3 VCS优化方法的并行化

CUDA框架下的程序流程一般为：主机端首先准备数据,将信息复制到设备端的内存中,在设备端完成并行计算后将结果拷贝回主机端。将图3中元素排序的过程转移到设备端实现并行化,其具体流程如图4所示,在主机端将多边形的顶点坐标信息提取出来,存放到数组中,利用极值将数组扩充从而得到一个无序数组。当启动CUDA内核时,利用CUDA的内存拷贝函数将该数组的信息从主机端拷贝到设备端。此时,流多处理器中将被分配足够多的线程块,同时对线程块再次划分成为更加细致的结构——由32个线程组成的线程束。在设备端实现数据大小的比较、交换等操作之后将数据拷贝回主机端,此时数组中的要素已是有序的。对有序数组中的要素过滤,去除无效值和重复值,便可以为每条扫描线赋值。

### 3 实验及算法优化效率分析

#### 3.1 实验及VCS优化方法效率分析

###### 表2 实验环境配置

Tab. 2 Experimental environment configuration

/位

/ MHz

/GB

/ GB SSD

HP Pavilion 15-ak004TX Intel Core i7-6700HQ四核2.6 GHz NVIDIA GTX 950 M 640 128 1000 8 128 Windows 10 Visual Studio 2017

#### 3.2 VCS优化方法并行化效率分析

##### 图6 不同数量的并行线程扫描束构建耗时情况

Fig. 6 Time consumption of scanning bundle construction with different number of parallel threads

##### 图7 不同数据量耗时情况及加速比

Fig. 7 Time consumption and speedup ratio for different data volumes

##### 图8 并行化前后的Vatti算法耗时对比

Fig. 8 Time consumption comparison of Vatti algorithm before and after parallelization

### 4 结论与讨论

 [1] 王结臣, 王豹, 胡玮, 等. 并行空间分析算法研究进展及评述[J]. 地理与地理信息科学, 2011, 27(6):1-5. [ Wang J C, Wang B, Hu W, et al. Review on parallel spatial analysis algorithms[J]. Geography and Geo-information Science, 2011, 27(6):1-5. ] DOI: CNKI:SUN:DLGT.0.2011-06-002
 [2] 左尧, 王少华, 钟耳顺, 等. 高性能GIS研究进展及评述[J]. 地球信息科学学报, 2017, 19(4):437-446. [ Zuo Y, Wang S H, Zhong E S, et al. Research progress and review of high-performance GIS[J]. Journal of Geo-Information Science, 2017, 19(4):437-446. ] DOI: 10.3969/j.issn.1560-8999.2017.04.001
 [3] 赵银利, 范俊甫, 王崇倡. GIS典型几何计算算法的并行化及优化研究[J]. 测绘与空间地理信息, 2017, 40(7):163-166. [ Zhao Y L, Fan J F, Wang C C. Parallelization and optimization for several typical geometic-analysis algorithms in GIS[J]. Geomatics & Spatial Information Technology, 2017, 40(7):163-166. ] DOI: 10.3969/j.issn.1672-5867.2017.07.052
 [4] 邱强, 秦承志, 朱效民, 等. 全空间下并行矢量空间分析研究综述与展望[J]. 地球信息科学学报, 2017, 19(9):1217-1227. [ Qiu Q A, Qin C Z, Zhu X M, et al. Overview and prospect on spatial analysis of parallel vectors in pan-spatial concept[J]. Journal of Geo-information Science, 2017, 19(9):1217-1227. ] DOI: 10.3724/SP.J.1047.2017.01217
 [5] 范俊甫. 并行化矢量多边形叠加算法研究[J]. 测绘学报, 2016, 45(4):502. [ Fan J F. Parallel algorithms for polygon overlapping[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):502. ] DOI: 10.11947/j.AGCS.2016.20150495
 [6] 彭志云, 王惜民, 赖美森, 等. 并行计算时代:基于CUDA的通用GPU计算的发展[J]. 科技与企业, 2016, 11:80. [ Peng Z Y, Wang X M, Lai M S, et al. The era of parallel computing: the development of general GPU computing based on CUDA[J]. Technology And Enterprise, 2016, 11:80. ] DOI: 10.3969/j.issn.1004-9207.2016.11.074
 [7] 姚晓, 邱强, 肖茁建, 等. Spark框架下矢量多边形求交算法研究[J]. 高技术通讯, 2018, 28(6):500-507. [ Yao X A, Qiu Q A, Xiao Z J, et al. Research on vector polygon intersection algorithm in Spark framework[J]. Chinese High Technology Letters, 2018, 28(6):500-507. ] DOI: 10.3772/j.issn.1002-0470.2018.06.003
 [8] Sutherland I E, Hodgman G W. Reentrant polygon clipping[J]. Communications of the ACM, 1974, 17(1):32-42. DOI: 10.1145/360767.360802
 [9] Weiler K, Atherton P. Hidden surface removal using polygon area sorting[J]. ACM SIGGRAPH Computer Graphics, 1977, 11(2):214-222. DOI: 10.1145/965141.563896
 [10] Vatti B R. A generic solution to polygon clipping[J]. Communications of the ACM, 1992, 35(7):56-63. DOI: 10.114 5/129902.129906
 [11] Greiner G, Hormann K. Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998, 17(2):71-83. DOI: 10.1145/274363.274364
 [12] 苏诚, 韩俊刚. Sutherland-Hodgman裁剪算法的改进[J]. 西安邮电大学学报, 2013, 18(3):80-82. [ Su C, Han J G. An advanced Sutherland-Hodgman algorithm[J]. Journal of Xi'an University of Posts and Telecommunications, 2013, 18(3):80-82. ] DOI: 10.3969/j.issn.1007-3264.2013.03.020
 [13] 白晨. 一种任意多边形的裁剪算法[D]. 电子科技大学, 2012. [ Bai C. A clipping algorithm for arbitrary polygon[D]. University Of Electronic Science And Technology Of China, 2012. ] DOI: CNKI:CDMD:2.1011.054140
 [14] 刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4):845-856. [ Liu Y K, Gao Y, Huang Y Q. An efficient algorithm for polygon clipping[J]. Journal of Software, 2003, 14(4):845-856. ] DOI: CNKI:SUN:RJXB.0.2003-04-018
 [15] 范俊甫. 并行化矢量多边形叠加算法研究[D]. 北京:中国科学院大学, 2014. [ Fan J F. Parallel algorithms for polygon overlapping[D]. Beijing: University of Chinese Academy of Sciences, 2014. ]
 [16] 彭杰, 刘南, 唐远彬, 等. 一种基于交点排序的高效多边形裁剪算法[J]. 浙江大学学报(理学版), 2012, 39(1):107-111,122. [ Peng J E, Liu N, Tang Y B, et al. An efficient algorithm for polygon clipping based on intersection points sorting[J]. Journal of Zhejiang University (Science Edition), 2012, 39(1):107-111,122. ] DOI: 10.3785/j.issn.1008-9497.2012.01.022
 [17] Martínez F, Rueda A J, Feito F R. A new algorithm for computing Boolean operations on polygons[J]. Computers & Geosciences, 2009, 35(6):1177-1185. DOI: 10.1016/j.cageo.2008.08.009
 [18] Zhao K, Jin B, Fan H, et al. High-performance overlay analysis of massive geographic polygons that considers shape complexity in a cloud environment[J]. ISPRS International Journal of Geo-Information, 2019, 8(7):290. DOI: 10.3390/ijgi8070290
 [19] Zhou C, Chen Z J, Li M C. A parallel method to accelerate spatial operations involving polygon intersections[J]. International Journal of Geographical Information Science, 2018, 32(12):2402-2426. DOI: 10.1007/s10586-019-02944-y
 [20] Zhou C, Li M C. A systematic parallel strategy for generating contours from large-scale DEM data using collaborative CPUs and GPUs[J]. Cartography and Geographic Information Science, 2021, 48(3):187-209. DOI: 10.1080/15230406.2020.1854862
 [21] Zhou C, Li M C. Performance evaluation of spatial indexing to identify polygon intersection[J]. Geocarto International, 2020, 35(16):1850-1872. DOI: 10.1080/10106049.2019.1624987
 [22] Zhao K, Jin B X, Fan H, et al. A data allocation strategy for geocomputation based on shape complexity in A cloud environment using parallel overlay analysis of polygons as an example[J]. IEEE Access, 2020, 8:185981-185991. DOI: 10.1109/ACCESS.2020.3030700
 [23] Zhou Y K, Wang S H, Guan Y. An efficient parallel algorithm for polygons overlay analysis[J]. Applied Sciences, 2019, 9(22):4857. DOI: 10.3390/app9224857
 [24] 范俊甫, 孔维华, 马廷, 等. RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报, 2015, 44(3):338-345. [ Fan J F, Kong W H, Ma T, et al. RaPC: A rasterization-based polygon clipping algorithm and its error analysis[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(3):338-345. ] DOI: 10.11947/j.AGCS.2015.20140017.
 [25] Fan J F, He H X, Hu T Y, et al. Rasterization computing-based parallel vector polygon overlay analysis algorithms using OpenMP and MPI[J]. IEEE Access, 2018, 6:21427-21441. DOI: 10.1109/ACCESS.2018.2825452
 [26] 张鹏, 俞宵, 马子云, 等. 统一计算设备架构的D8算法并行化研究[J]. 测绘科学, 2020, 45(3):163-169. [ Zhang P, Yu X A, Ma Z Y, et al. Research on parallelization of D8 algorithm based on CUDA[J]. Science of Surveying and Mapping, 2020, 45(3):163-169. ] DOI: 10.16251/j.cnki.1009-2307.2020.03.025
 [27] 吴旭桥, 吴烨, 陈荦, 等. 面向大规模DEM数据的并行填挖算法[J]. 地理信息世界, 2019, 26(6):21-25. [ Wu X Q, Wu Y, Chen L, et al. A parallel cut-fill algorithm for large-scale DEM data[J]. Geomatics World, 2019, 26(6):21-25. ] DOI: 10.3969/j.issn.1672-1586.2019.06.004
 [28] Guo M Q, Han C D, Guan Q F, et al. A universal parallel scheduling approach to polyline and polygon vector data buffer analysis on conventional GIS platforms[J]. Transactions in GIS, 2020, 24(6):1630-1654. DOI: 10.1111/tgis.12670
 [29] Zhou C, Chen Z J, Li M C. A parallel method to accelerate spatial operations involving polygon intersections[J]. International Journal of Geographical Information Science, 2018, 32(12):2402-2426. DOI: 0.1080/13658816.2018.1508689
 [30] 陈达伦, 陈荣国, 谢炯. 基于MPP架构的并行空间数据库原型系统的设计与实现[J]. 地球信息科学学报, 2016, 18(2):151-159. [ Chen D L, Chen R G, Xie J. Research of the parallel spatial database proto system based on MPP architecture[J]. Journal of Geo-Information Science, 2016, 18(2):151-159. ] DOI: 10.3724/SP.J.1047.2016.00151
 [31] 范俊甫, 马廷, 周成虎, 等. 几何部件缓冲区域合并的Buffer算法及其并行优化方法[J]. 测绘学报, 2014, 43(9):969-975. [ Fan J F, Ma T, Zhou C H, et al. Research on a buffer algorithm based on region-merging of buffered geometry components and its parallel optimization[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9):969-975. ] DOI: 10.13485/j.cnki.11-2089.2014.0122
 [32] 范俊甫, 马廷, 周成虎, 等. 基于集群MPI的图层级多边形并行合并算法[J]. 地球信息科学学报, 2014, 16(4):517-523. [ Fan J F, Ma T, Zhou C H, et al. Implementation of cluster MPI-based parallel polygon union algorithm at the feature layer level[J]. Journal of Geo-Information Science, 2014, 16(4):517-523. ] DOI: 10.3724/SP.J.1047.2014.00517
 [33] Alan Murta. A general polygon clipping library[EO/OL]. http://www.cs.man.ac.uk/~toby/alan/software/gpc.html 2020-05-30.
 [34] Angus Johnson. Clipper-an open source freeware library for clipping and offsetting lines and polygons[EO/OL].
 [35] 张林波. 并行计算导论[M]. 北京: 清华大学出版社, 2006. [ Zhang L B. An introduction to parallel computing[M]. Beijing: Tsinghua University Press Co., Ltd., 2006. ]
 [36] Velusamy K, Rolinger T B, McMahon J. Performance strategies for parallel bitonic sort on a migratory thread architecture[C]// 2020 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 2020:1-7. DOI: 10.1109/HPEC43674.2020.9286172
 [37] Leonov M. Comparison of the different algorithms for polygon boolean operations[EO/OL]. http://www.complex-a5.ru/polyboolean/comp.html 2020-05-30.
Options
Outlines

/

 〈 〉