CPU-GPU hybrid parallel overlay analysis method for GIS vector polygons based on improved Vatti algorithm using even-odd sorting

doi:10.11947/j.AGCS.2025.20230369

Abstract

Abstract:

Vector polygon clipping is one of the important and commonly used basic functions in the field of GIS. The explosive growth of geographic spatial data scale has put higher demands on the computational efficiency of traditional clipping algorithms. Currently, vector polygon clipping algorithms are increasingly showing characteristics of computation intensive and data intensive. In response to this phenomenon, this article optimizes the data structure of the vector polygon clipping Vatti algorithm and applies GPU multi-core parallel technology to the construction of ordered scanning beams. When the block size is 128 and the number of clipped polygon vertices reaches 3 276 800, the acceleration ratio of the polygon clipping Vatti algorithm reaches 2.55 times under the intersection operator operation. On this basis, this article further utilizes computing resources based on CPU multi-threaded parallel technology and proposes an optimization method called vertex segmentation hybrid parallel (VSHP) that divides the dataset by the number of vertices and achieves hybrid parallel acceleration. For a large-scale dataset, the main thread reads the data and divides the raw data based on the number of vertices and threads, and then hands it over to each thread for calculation. During this process, the GPU is sequentially called to filter the minimum bounding rectangle and accelerate the construction of ordered scanning beam segments. Finally, when all data tasks are calculated, the main thread completes the merging and output of the results. Experiments have shown that ideal acceleration can be achieved when calling 4 threads, and a maximum acceleration ratio of 19.15 times can be achieved when enabling 16 threads under dynamic scheduling strategy. This article attempts to achieve desktop supercomputing with low energy consumption through mixed parallel computing of CPU-GPU, aiming to provide some reference value for traditional vector polygon clipping algorithms to achieve high-performance acceleration optimization on low-cost consumer hardware platforms and reduce the cost of large-scale applications of geographic information data.

Key words: overlay analysis, vector polygon clipping, hybrid parallel, odd-even sort, OpenMP, algorithm optimization, high performance computing, GIS

CLC Number:

P208

Shanshan WANG, Junfu FAN, Zhikun ZHANG, Jianyun HAN. CPU-GPU hybrid parallel overlay analysis method for GIS vector polygons based on improved Vatti algorithm using even-odd sorting[J]. Acta Geodaetica et Cartographica Sinica, 2025, 54(2): 345-355.

Figures/Tables 12

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Tab. 1

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

References 25

[1]	李德仁. 论时空大数据的智能处理与服务[J]. 地球信息科学学报, 2019, 21(12): 1825-1831.
	LI Deren. The intelligent processing and service of spatiotemporal big data[J]. Journal of Geo-information Science, 2019, 21(12): 1825-1831.
[2]	王结臣, 王豹, 胡玮, 等. 并行空间分析算法研究进展及评述[J]. 地理与地理信息科学, 2011, 27(6): 1-5.
	WANG Jiechen, WANG Bao, HU Wei, et al. Review on parallel spatial analysis algorithms[J]. Geography and Geo-Information Science, 2011, 27(6): 1-5.
[3]	范俊甫. 并行化矢量多边形叠加算法研究[J]. 测绘学报, 2016, 45(4): 502. DOI:. doi: 10.11947/j.AGCS.2016.20150495
	FAN Junfu. Parallel algorithms for polygon overlapping[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 502. DOI:. doi: 10.11947/j.AGCS.2016.20150495
[4]	SUTHERLAND I E, HODGMAN G W. Reentrant polygon clipping[J]. Communications of the ACM, 1974, 17(1): 32-42.
[5]	WEILER K, ATHERTON P, WEILER K, et al. Hidden surface removal using polygon area sorting[C]//Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques. San Jose: ACM Press, 1977: 214-222.
[6]	VATTI B R. A generic solution to polygon clipping[J]. Communications of the ACM, 1992, 35(7): 56-63.
[7]	RUSHMEIER H, GREINER G, HORMANN K. Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998, 17(2): 71-83.
[8]	刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4): 845-856.
	LIU Yongkui, GAO Yun, HUANG Youqun. An efficient algorithm for polygon clipping[J]. Journal of Software, 2003, 14(4): 845-856.
[9]	张志锟, 范俊甫, 徐少波, 等. 多边形叠加Vatti算法的VCS优化方法与GPU并行化[J]. 地球信息科学学报, 2022, 24(3): 437-447.
	ZHANG Zhikun, FAN Junfu, XU Shaobo, et al. VCS optimization method of Vatti algorithm for polygon overlay and parallelization using GPU[J]. Journal of Geo-information Science, 2022, 24(3): 437-447.
[10]	ZHOU Yuke, WANG Shaohua, GUAN Yong. An efficient parallel algorithm for polygons overlay analysis[J]. Applied Sciences, 2019, 9(22): 4857.
[11]	苏诚, 韩俊刚. Sutherland-Hodgman裁剪算法的改进[J]. 西安邮电大学学报, 2013, 18(3): 80-82.
	SU Cheng, HAN Jungang. An advanced Sutherland-Hodgman algorithm[J]. Journal of Xi'an University of Posts and Telecommunications, 2013, 18(3): 80-82.
[12]	赵斯思, 周成虎. GPU加速的多边形叠加分析[J]. 地理科学进展, 2013, 32(1): 7.
	ZHAO Sisi, ZHOU Chenghu. Accelerating polygon overlay analysis by GPU[J]. Progress in Geography, 2013, 32(1): 7.
[13]	蒋元义, 金宝轩, 赵康, 等. 叠置计算中多边形形状复杂度的度量研究[J]. 测绘科学, 2020, 45(11): 177-184.
	JIANG Yuanyi, JIN Baoxuan, ZHAO Kang, et al. Research on measurement of polygon shape complexity in overlay calculation[J]. Science of Surveying and Mapping, 2020, 45(11): 177-184.
[14]	HUANG Fang, TIE Bo, TAO Jian, et al. Methodology and optimization for implementing cluster-based parallel geospatial algorithms with a case study[J]. Cluster Computing, 2020, 23(2): 673-704.
[15]	ZHOU Chen, LI Manchun. 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.
[16]	ZHOU Chen, LI Manchun. Performance evaluation of spatial indexing to identify polygon intersection[J]. Geocarto International, 2020, 35(16): 1850-1872.
[17]	ZHAO Kang, JIN Baoxuan, FAN Hong, 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.
[18]	范俊甫, 孔维华, 马廷, 等. RaPC：一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报, 2015, 44(3): 338-345. DOI:. doi: 10.11947/j.AGCS.2015.20140017
	FAN Junfu, KONG Weihua, MA Ting, 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:. doi: 10.11947/j.AGCS.2015.20140017
[19]	FAN Junfu, HE Huixin, HU Taoying, et al. Rasterization computing-based parallel vector polygon overlay analysis algorithms using OpenMP and MPI[J]. IEEE Access, 2018, 6: 21427-21441.
[20]	卢风顺, 宋君强, 银福康, 等. CPU/GPU协同并行计算研究综述[J]. 计算机科学, 2011, 38(3): 5-9.
	LU Fengshun, SONG Junqiang, YIN Fukang, et al. Survey of CPU/GPU synergetic parallel computing[J]. Computer Science, 2011, 38(3): 5-9.
[21]	MITTAL S, VETTER J S. A survey of CPU-GPU heterogeneous computing techniques[J]. ACM Computing Surveys, 2015, 47(4): 1-35.
[22]	方留杨, 王密, 李德仁. CPU和GPU协同处理的光学卫星遥感影像正射校正方法[J]. 测绘学报, 2013, 42(5): 668-675.
	FANG Liuyang, WANG Mi, LI Deren. A CPU-GPU co-processing orthographic rectification approach for optical satellite imagery[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 668-675.
[23]	VESTIAS M, NETO H. Trends of CPU, GPU and FPGA for high-performance computing[C]//Proceedings of 2014 International Conference on Field Programmable Logic and Applications. Munich: IEEE, 2014: 1-6.
[24]	徐云耘, 周琛, 李满春. CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架[J]. 测绘通报, 2022(5): 110-119.
	XU Yunyun, ZHOU Chen, LI Manchun. A parallel framework for data-intensive geospatial analysis on large-scale vector polygons over hybrid CPUs and GPUs[J]. Bulletin of Surveying and Mapping, 2022(5): 110-119.
[25]	ZHANG Peng, FAN Junfu, ZHANG Panpan, et al. Comparative study on the effect of shape complexity on the efficiency of different overlay analysis algorithms[J]. IEEE Access, 2021, 9: 144179-144194.

软硬件环境	配置情况
处理器（CPU）	Intel i7-10700F
核心及线程数量	8核16线程
CPU主频/GHz	2.9
系统内存/GB	32.0
硬盘容量/TB	5.0
GPU	NVIDIA RTX 3070
GPU显存/GB	8.0
显存带宽/（GB/s）	448
CUDA核心数	5888
操作系统	Windows 10
计算平台	CUDA 11.2
开发工具	Visual Studio 2019