A Parallel Sweep Line Algorithm for Visibility Computation
Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. Randolph Franklin, Guilherme C. Pena · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2013
This paper describes a new parallel raster terrain visibility (or viewshed) algorithm, based on the sweep-line model of [Van Kreveld 1996]. Computing the terrain visible from a given observer is required for many GIS applications, with applications ranging from radio tower siting to aesthetics. Processing the newly available higher resolution terrain data requires faster architectures and algorithms. Since the main improvements on modern processors come from multi-core architectures, parallel programming provides a promising means for developing faster algorithms. Our algorithm uses the economical and widely available shared memory model with OpenMP. Experimentally, our parallel speedup is almost linear. On 16 parallel processors, our algorithm is up to 12 times faster than the serial implementation.