GIS Polygon Overlay Processing: New Parallel Algorithm and System Prototype

Satish Puri, Sushil K. Prasad
Department of Computer Science, Georgia State University, Atlanta – 30303, USA
DIMOS Lab., Technical Report, 2014


   title={GIS Polygon Overlay Processing: New Parallel Algorithm and System Prototype},

   author={Puri, Satish and Prasad, Sushil K},



Polygon overlay is one of the complex operations in computational geometry. It is applied in many fields such as Geographic Information Systems (GIS), computer graphics, VLSI CAD, etc. We have two significant results to report. Our first result is the first output-sensitive CREW PRAM algorithm for simple polygons, which can perform typical set operations including intersection, union, and difference in O(logn) time using (n+k) processors, where n is the number of vertices and k is the number of edge intersections. The current best algorithm by Karinthi, Srinivas, and Almasi [1] does not handle self-intersecting polygons, is not output-sensitive and must employ Theta(n^2) processors to achieve O(logn) time. Our algorithm is superior to [1] in all three aspects. Spatial data files tend to be large in size (in GBs) and the underlying overlay computation is highly irregular and compute intensive. Our second result is a GIS system, namely MPI-GIS, for end-to-end polygonal overlay processing over heterogeneous clusters. It employs R-tree for efficient indexing and identification of potentially intersecting set of polygons across two input GIS layers. MPI-GIS can leverage multi-cores and many-cores using a combination of MPI and CUDA to accelerate polygon overlay. This system achieves 44X speedup on a 32-node IBM iDataPlex cluster while processing about 600K polygons in two GIS layers within 19 seconds.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: