A strategy for parallelising polygon rasterisation algorithms using multi-core CPUs

Abstract

Polygon rasterisation is a fundamental process in geographic information science. Because of recent increases in the quantity of vector data, rapid rasterisation techniques are urgently needed. This study explores methods for combining processes and threads on multi-core CPUs to accelerate large-scale polygon rasterisation. First, a data decomposition method is adopted for effective load balancing between processes and threads. Second, a polygon processing strategy is proposed to manage four types of exceptional polygons. Using these approaches, a hybrid parallel framework is proposed to parallelise sequential rasterisation algorithms while maximising their processing speed. The experimental results show that the implemented parallel algorithm can efficiently reduce rasterisation time (from 40.62 h to 1.97 h) and obtain a satisfactory speed-up of 20.62. The proposed hybrid parallel algorithm outperforms pure process-level or pure thread-level implementations. Moreover, the proposed decomposition methods can provide consistently superior performance compared with conventional techniques and can achieve superior load balancing.

Keywords:

• geographic information science
• vector data
• polygon rasterisation
• parallel computing