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