基于GPU的任意多边形相交面积计算方法

An efficient algorithm of arbitrary polygons intersection area

一直以来,任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS,在此基础上,分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法,并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比,结果表明:GPURAS算法精度高,通用性较好但效率受CPU与GPU通信延迟的影响;GPURASMC算法效率较高但牺牲了部分精度;GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比,文中所提3种算法效率更高,在处理包含大量顶点的多边形时,效率提升尤为明显。

For a long time,the fast processing the intersection area of arbitrary polygons has been an important research topic in spatial analysis algorithm of geographic information system.A GPU-based rasterized polygon intersection area algorithm is proposed as GPURAS.And its accelerated versions:GPURASMC and GPURASQ,which use Monte Carlo method and occlusion query technique respectively,are also presented and the correctness of these algorithms is proved.Experiments and comparisons are performed using simple,arbitrary complex,and large-scale polygons.The result shows the GPURAS algorithm has better universality but the efficiency is affected by CPU and GPU communication delay.The GPURASMC algorithm has higher efficiency but compromises a bit on accuracy.The GPURASQ algorithm has excellent accuracy and the highest efficiency,but its usage is limited by the running environment.The average efficiency of all the three proposed algorithms is higher than their CPU counterparts,especially in handling large-scale polygons.