GPU加速的多边形叠加分析  

Accelerating polygon overlay analysis by GPU

作　　者：赵斯思[1] 周成虎[1] 

机构地区：[1]中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101

出　　处：《地理科学进展》2013年第1期114-120,共7页Progress in Geography

基　　金：国家自然科学基金项目(40830529);国家"863"计划项目(2011AA120305)

摘　　要：叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。Overlay analysis is one of the most important analysis capabilities of geographic information systems.Overlay analysis with polygon layers is a time-intensive process.To improve time efficiency,modern approaches of overlay analysis are generally divided into two stages,filtering and refinement（also known as polygon clipping）.A great deal of effort has been taken to significantly reduce the number of candidates in the first stage（filtering） in order to alleviate the workload of the second stage（refinement）.However,the second stage is still the most time-consuming part of the process.In this paper we applied GPGPU（General-purpose Graphics Processing Unit） computing to the two key stages of overlay analysis： MBR filtering（part of the filtering） and polygon clipping,and restricted the search area to polygon intersection analysis.We proposed GPU-based MBR filtering algorithm by combining histogram and parallel prefix-sum algorithms,and introduced GPU-based polygon clipping algorithm by improving Weiler-Atherton algorithm.There are two differences between our algorithm and Weiler-Atherton algorithm： First,it adopts a new method to insert intersecting points which reduces computing workload,making it more suitable to be implemented on GPU.Second,it simplifies the algorithm used to mark entry and exit points.Furthermore,based on dynamic programming,we provided a solution to avoid load imbalance caused by spatial data skew.The improved algorithms and the solution have been applied to filtering stage and refinement stage to achieve better performance.The experimental results show that the speedup ratio between GPU-based MBR filtering implementation and CPU implementation is 3.8.The GPU-based polygon clipping implementation runs 3.4 times faster than the CPU＇s.Overall,GPU-accelerated polygon intersection implementation achieves performance that is up to three times faster than CPU implementation.Accelerating other types of overlay analyses,such as union,difference,etc.,by GPU needs to be studied an

关 键 词：叠加分析 图形处理单元 多边形剪裁 并行计算 空间分析 

分 类 号：P208[天文地球—地图制图学与地理信息工程] P209[天文地球—测绘科学与技术]