地理科学进展

地理科学进展 ›› 2013, Vol. 32 ›› Issue (1): 114-120.doi: 10.11820/dlkxjz.2013.01.012

• 模型与方法 • 上一篇    下一篇

GPU加速的多边形叠加分析

赵斯思, 周成虎   

  1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101
  • 收稿日期:2012-06-01 修回日期:2012-09-01 出版日期:2013-01-25 发布日期:2013-01-25
  • 作者简介:赵斯思(1983-), 男,博士,主要研究方向为高性能地学计算、空间分析、地统计等。E-mail: zhaoss@lreis.ac.cn
  • 基金资助:

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

Accelerating polygon overlay analysis by GPU

ZHAO Sisi, ZHOU Chenghu   

  1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographical Sciences and Natural Resources Research, CAS, Beijing 100101, China
  • Received:2012-06-01 Revised:2012-09-01 Online:2013-01-25 Published:2013-01-25

PDF (PC)

赞

被引次数

31 | 9

摘要： 叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。

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

Abstract: 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 and implemented in the future.

Key words: GPGPU, overlay analysis, parallel computing, polygon clipping, spatial analysis