基于奇偶排序改进Vatti算法的GIS矢量多边形CPU-GPU混合并行叠加分析方法

doi:10.11947/j.AGCS.2025.20230369

测绘学报 ›› 2025, Vol. 54 ›› Issue (2): 345-355.doi: 10.11947/j.AGCS.2025.20230369

• 地图学与地理信息 • 上一篇

基于奇偶排序改进Vatti算法的GIS矢量多边形CPU-GPU混合并行叠加分析方法

王珊珊¹(), 范俊甫²(), 张志锟²^,³, 韩建云¹

^1.中国自然资源航空物探遥感中心，北京　100083
^2.山东理工大学建筑工程与空间信息学院，山东　淄博　255000
^3.山东省地质矿产勘查开发局第四地质大队（山东省第四地质矿产勘查院），山东　潍坊　261021

收稿日期:2023-08-28 发布日期:2025-03-11
通讯作者: 范俊甫 E-mail:wangss1028@126.com;fanjf@sdut.edu.cn
作者简介:王珊珊（1985—），女，博士，正高级工程师，主要从事遥感地质与空间分析领域的研究。　E-mail：wangss1028@126.com
基金资助:
国家自然科学基金(42171413);自然资源部省合作试点项目(2023ZRBSHZ048);资源与环境信息系统国家重点实验室开放基金项目

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

Shanshan WANG¹(), Junfu FAN²(), Zhikun ZHANG²^,³, Jianyun HAN¹

^1.China Aero Geophysical Survey and Remote Sensing Center for Natural Resources, Beijing 100083, China
^2.School of Civil Engineering and Geomatics, Shandong University of Technology, Zibo 255000, China
^3.Fourth Geological Brigade of Shandong Province Geological and Mineral Exploration and Development Bureau (Fourth Geological and Mineral Exploration Institute of Shandong Province), Weifang 261021, China

Received:2023-08-28 Published:2025-03-11
Contact: Junfu FAN E-mail:wangss1028@126.com;fanjf@sdut.edu.cn
About author:WANG Shanshan (1985—), female, PhD, senior engineer, majors in remote sensing geology and spatial analysis.　E-mail: wangss1028@126.com
Supported by:
The National Natural Science Foundation of China(42171413);The Cooperation Pilot Project for Ministry of Natural Resources and Provinces(2023ZRBSHZ048);A Grant from the State Key Laboratory of Resources and Environmental Information System

摘要/Abstract

摘要：

矢量多边形裁剪是GIS领域中重要且常用的基础功能之一，地理空间数据规模的爆炸式增长给传统裁剪算法的计算效率提出了更高的要求，当前矢量多边形裁剪算法日益呈现计算密集和数据密集的特点。针对这一现象，本文基于矢量多边形裁剪Vatti算法，优化其数据结构，将GPU众核并行技术应用到构建局部最小点表和有序扫描束的环节中，当Block大小为128，裁剪多边形顶点数达到3 276 800时，在求交算子操作下，对多边形裁剪Vatti算法的加速比达到2.55倍。在此基础上，本文基于CPU多线程并行技术进一步利用计算资源，提出了通过顶点数量对数据集进行分割并实现混合并行加速的优化方法（VSHP）。针对一个大规模数据集，由主线程读取数据后根据顶点数和线程数对原始数据进行划分，之后交由各线程进行计算，期间依次调用GPU对最小外包矩形过滤、构建局部最小点表和有序扫描束环节进行加速，最后当所有数据任务计算完成后，由主线程完成结果的归并和输出。试验表明，当调用4个线程时可获得理想的加速效果，在动态调度策略下启用16个线程时可获得最高19.15倍的加速比。本文通过CPU-GPU的混合并行优化技术，尝试在较低的能耗下实现桌面上的高性能计算，旨在为传统矢量多边形裁剪算法在廉价消费级硬件平台上获得高性能加速优化提供一定的参考价值，降低地理信息数据规模化应用的成本。

关键词: 叠加分析, 矢量多边形裁剪, 混合并行, 奇偶排序, OpenMP, 算法优化, 高性能计算, GIS

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

中图分类号:

P208

王珊珊, 范俊甫, 张志锟, 韩建云. 基于奇偶排序改进Vatti算法的GIS矢量多边形CPU-GPU混合并行叠加分析方法[J]. 测绘学报, 2025, 54(2): 345-355.

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.

图/表 12

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

图10

图11

参考文献 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

基于奇偶排序改进Vatti算法的GIS矢量多边形CPU-GPU混合并行叠加分析方法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈帅, 苗则朗, 吴立新. 顾及坡体赋存环境的概率地震滑坡危险性制图[J]. 测绘学报, 2023, 52(9): 1548-1561.
[2]	单建晨, 李姗姗, 范雕, 李新星, 黄炎, 邢志斌. 超高阶全球地形球谐系数模型的构建方法与实现[J]. 测绘学报, 2023, 52(5): 748-759.
[3]	张永生, 张振超, 童晓冲, 纪松, 于英, 赖广陵. 地理空间智能研究进展和面临的若干挑战[J]. 测绘学报, 2021, 50(9): 1137-1146.
[4]	刘振东, 戴昭鑫, 李成名, 刘晓丽. 三维GIS场景与多路视频融合的对象快速确定法[J]. 测绘学报, 2020, 49(5): 632-643.
[5]	李清泉, 周宝定, 马威, 薛卫星. GIS辅助的室内定位技术研究进展[J]. 测绘学报, 2019, 48(12): 1498-1506.
[6]	梁伟, 徐新禹, 李建成, 朱广彬. 联合EGM2008模型重力异常和GOCE观测数据构建超高阶地球重力场模型SGG-UGM-1[J]. 测绘学报, 2018, 47(4): 425-434.
[7]	何撼东, 胡迪, 闾国年, 李安波, 李军利. 几何与语义统一的区域地质构造GIS数据模型[J]. 测绘学报, 2017, 46(8): 1058-1068.
[8]	朱杰, 孙毅中. 多约束的平面点集形状重构方法[J]. 测绘学报, 2017, 46(2): 253-264.
[9]	唐炉亮, 阚子涵, 段倩, 李清泉. 一种时空路径支持下的车辆油耗与排放估计方法[J]. 测绘学报, 2017, 46(12): 2024-2031.
[10]	黎夏, 李丹, 刘小平. 地理模拟优化系统(GeoSOS)及其在地理国情分析中的应用[J]. 测绘学报, 2017, 46(10): 1598-1608.
[11]	兰泽英, 刘洋. 领域知识辅助下基于多尺度与主方向纹理的遥感影像土地利用分类[J]. 测绘学报, 2016, 45(8): 973-982.
[12]	汶建龙, 杨春成, 符浩军, 岳志兰. 一种地图跨媒介出版数据模型[J]. 测绘学报, 2015, 44(8): 936-942.
[13]	谢潇, 朱庆, 张叶廷, 周艳, 许伟平, 吴晨. 多层次地理视频语义模型[J]. 测绘学报, 2015, 44(5): 555-562.
[14]	周晓光, 陈斐, 陈军. 引入结点度的线/面拓扑关系细分方法与应用[J]. 测绘学报, 2015, 44(4): 445-452.
[15]	刘震余洋李建松肖少辉. 面向路径优化的变分辨率栅格成本表面模型建模方法[J]. 测绘学报, 2014, 43(5): 474-480.