Rasterization Computing-Based Parallel Vector Polygon Overlay Analysis Algorithms Using OpenMP and MPI

Abstract

Vector polygon overlay is a complex type of a geo-spatial analysis algorithm used in geographical information system, which requires increasingly higher computational efficiency given the rapid growth of spatial data sets. Parallel computing has provided an effective approach to improve the computational efficiency and expand the processing scales of polygon overlay algorithms. Polygon overlay analysis algorithms that are based on traditional vector polygon clipping algorithms will experience significant efficiency decreases when handling overlap among polygons that have quantities of vertices. The discretization processing method-based rasterization-based polygon clipping algorithm (RaPC) algorithm exhibits higher efficiency for addressing clipping issues among such polygons. In this paper, we designed and implemented two types of parallel polygon overlay analysis algorithms to determine the differences in efficiency between the RaPC algorithm and the Vatti algorithm under the open multi-processing and message passing interface parallel computing environments. The results show that parallel polygon overlay analysis methods based on the RaPC algorithm present advantages for processing overlap among large data sets. The parallel algorithm based on the Vatti algorithm presents higher efficiency when handling overlap among small spatial data sets. The discretization process between two overlapped geometries of the RaPC algorithm provided a potential approach to solve the polygon overlay problem using a fine-grained parallelization method.

Keywords

• Overlay analysis
• parallel computing
• rasterization
• vector polygon clipping
• OpenMP and MPI