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

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

作　　者：王珊珊 范俊甫[2] 张志锟 韩建云 WANG Shanshan;FAN Junfu;ZHANG Zhikun;HAN Jianyun(China Aero Geophysical Survey and Remote Sensing Center for Natural Resources,Beijing 100083,China;School of Civil Engineering and Geomatics,Shandong University of Technology,Zibo 255000,China;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)

机构地区：[1]中国自然资源航空物探遥感中心,北京100083 [2]山东理工大学建筑工程与空间信息学院,山东淄博255000 [3]山东省地质矿产勘查开发局第四地质大队(山东省第四地质矿产勘查院),山东潍坊261021

出　　处：《测绘学报》2025年第2期345-355,共11页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金(42171413);自然资源部省合作试点项目(2023ZRBSHZ048);资源与环境信息系统国家重点实验室开放基金项目。

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

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

分 类 号：P208[天文地球—地图制图学与地理信息工程]