地球信息科学学报 ›› 2022, Vol. 24 ›› Issue (3): 437-447.doi: 10.12082/dqxxkx.2022.210409
收稿日期:
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
基金资助:
ZHANG Zhikun1(), FAN Junfu1,*(
), XU Shaobo2, CHEN Zheng1
Received:
2021-07-18
Revised:
2021-08-19
Online:
2022-03-25
Published:
2022-05-25
Supported by:
摘要:
Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS(Vertex Coordinate Pre-Sorting)方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。
张志锟, 范俊甫, 徐少波, 陈政. 多边形叠加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
[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. |
[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. |
|