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

doi:10.12082/dqxxkx.2022.210409

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

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

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

张志锟¹(), 范俊甫¹^,^*(), 徐少波², 陈政¹

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 Zhikun¹(), FAN Junfu¹^,^*(), XU Shaobo², CHEN Zheng¹

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)

摘要/Abstract

摘要：

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

张志锟, 范俊甫, 徐少波, 陈政. 多边形叠加Vatti算法的VCS优化方法与GPU并行化[J]. 地球信息科学学报, 2022, 24(3): 437-447.DOI:10.12082/dqxxkx.2022.210409

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.DOI:10.12082/dqxxkx.2022.210409

图/表 10

图1

表1

图2

图3

图4

图5

表2

图6

图7

图8

参考文献 37

[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. doi: 10.3724/SP.J.1047.2017.00437
	[ 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 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 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 doi: 10.1145/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 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 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 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 doi: 10.1080/13658816.2018.1508689
[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 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 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 doi: 10.1109/Access.6287639
[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 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 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 doi: 10.1111/tgis.v24.6
[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 doi: 10.1080/13658816.2018.1508689
[30]	陈达伦, 陈荣国, 谢炯. 基于MPP架构的并行空间数据库原型系统的设计与实现[J]. 地球信息科学学报, 2016, 18(2):151-159. doi: 10.3724/SP.J.1047.2016.00151
	[ 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. doi: 10.3724/SP.J.1047.2014.00517
	[ 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.

年份	多边形数/个	顶点数/个	单个多边形最大顶点数/个
2009	9129	856 238	9475
2010	9383	832 827	9472

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

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

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 37

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	刘琳琳, 郑伯红, 骆晨. 基于交通大数据的南昌市中心城区等时圈划分及特征分析[J]. 地球信息科学学报, 2022, 24(2): 220-234.
[2]	王烁棋, 赵亮. 山城眺望空间OSCA模型构建及应用[J]. 地球信息科学学报, 2021, 23(9): 1559-1574.
[3]	王杏锋, 李代超, 吴升, 谢晓苇, 卢嘉奇. 水稻种植环境综合适宜性评价方法研究[J]. 地球信息科学学报, 2021, 23(8): 1484-1496.
[4]	李清嘉, 彭建东, 杨红. 武汉市不同站域建成环境与轨道交通站点客流特征关系分析[J]. 地球信息科学学报, 2021, 23(7): 1246-1258.
[5]	廖心治, 王华, 赵万民. 融合地图数据的山地城市医疗设施服务覆盖评估方法研究[J]. 地球信息科学学报, 2021, 23(4): 604-616.
[6]	曹中浩, 张健钦, 杨木, 贾礼朋, 邓少存. 基于GIS新冠智能体仿真模型及应用——以广州市为例[J]. 地球信息科学学报, 2021, 23(2): 297-306.
[7]	胡毅荣, 王超, 杜震洪, 张丰, 刘仁义. 一种与地图服务结合的栅格瓦片计算模型[J]. 地球信息科学学报, 2021, 23(10): 1756-1766.
[8]	宋关福, 陈勇, 罗强, 武梦瑶. GIS基础软件技术体系发展及展望[J]. 地球信息科学学报, 2021, 23(1): 2-15.
[9]	李锐, 石佳豪, 董广胜, 刘朝辉. 多粒度时空对象组成结构表达研究[J]. 地球信息科学学报, 2021, 23(1): 113-123.
[10]	姚可桢, 岳书平. 网络大数据下的中国现代食甜习惯空间分布特征及其影响因素研究[J]. 地球信息科学学报, 2020, 22(6): 1202-1215.
[11]	朱亚茹, 高峻, 邴振华, 张中浩, 付晶. 基于参与式制图方法的景观服务评估与空间结构研究[J]. 地球信息科学学报, 2020, 22(5): 1106-1119.
[12]	赵耀龙, 巢子豪. 历史GIS的研究现状和发展趋势[J]. 地球信息科学学报, 2020, 22(5): 929-944.
[13]	王英杰, 张桐艳, 李鹏, 虞虎. GIS在中国旅游资源研究与应用中的现状及趋势[J]. 地球信息科学学报, 2020, 22(4): 751-759.
[14]	杨艳昭, 郎婷婷, 张超, 贾琨. 基于GIS的“一带一路”地区气温插值方法比较研究[J]. 地球信息科学学报, 2020, 22(4): 867-876.
[15]	单渌铱, 王海军, 张彬, 潘鹏. 顾及土地生态安全的环鄱阳湖城市群土地利用情景模拟[J]. 地球信息科学学报, 2020, 22(3): 543-556.