An efficient approach for viewshed calculation on terrain stored in external memory

• Chaulio R. Ferreira UFV
• Marcus V. A. Andrade UFV
• Salles V. G. Magalhães UFV
• André M. Pompermayer UFV

Abstract

An important GIS application is computing the viewshed of a point on a DEM terrain, i. e. determining the visible region from this point. In some cases, it is not possible to process high resolution DEMs entirely in internal memory and, thus, it is important to develop algorithms to process such data in the external memory. This paper presents an efficient algorithm for handling huge terrains in external memory. As tests have shown, this new method is more efficient than other methods described in the literature.

References

Aggarwal, A. and Vitter, J. S. (1988). The input/output complexity of sorting and related problems. Communications of the ACM, 9:1116–1127.

Andrade, M. V. A., Magalhães, S. V. G., Magalhães, M. A., Franklin, W. R., and Cutler, B. M. (2011). Efficient viewshed computation on terrain in external memory. GeoInformatica, pages 381 – 397.

Ben-Moshe, B., Mitchell, J. S. B., Katz, M. J., and Nir, Y. (2002). Visibility preserving terrain simplification an experimental study. In Proceedings of ACM Symposium of Computational Geometry, pages 303–311, Barcelona, Spain.

Bespamyatnikh, S., Chen, Z., Wang, K., and Zhu, B. (2001). On the planar two-watchtower problem. In In 7th International Computing and Combinatorics Conference, pages 121–130.

Bresenham, J. (1965). An incremental algorithm for digital plotting. IBM Systems Journal.

Dementiev, R., Kettner, L., and Sanders, P. (2005). Stxxl : Standard template library for xxl data sets. Technical report, Fakultat fur Informatik, Universitat Karlsruhe. [link] (acessado em 05/03/2012).

Felgueiras, C. A. (2001). Modelagem numérica de terreno. In In G. Câmara, C. Davis, A. M. V. M., editor, Introdução à Ciência da Geoinformação, volume 1. INPE.

Franklin, W. R. and Ray, C. (1994). Higher isn’t necessarily better visibility algorithms and experiments. In 6th Symposium on Spatial Data Handling, Edinburgh, Scotland.

Haverkort, H., ], L., and Zhuang, Y. (2007). Computing visibility on terrains in external memory. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments / Workshop on Analytic Algorithms and Combinatorics (ALENEX/ANALCO).

Laurini, R. and Thompsom, D. (1992). Fundamentals of Spatial Information Systems. Academic Press.

Magalhães, S. V. G., Andrade, M. V. A., Ferreira, C. R., Pena, G. C., Luange, T. G., and Pompermayer, A. M. (2012). Uma biblioteca para o gerenciamento de grandes matrizes em memória externa. Technical report, Departamento de Informática, Universidade Federal de Viçosa.

Magalhães, S. V. G., Andrade, M. V. A., and Franklin, W. R. (2011). Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management Applications, pages 143–149.

Patterson, D. A. and Hennessy, J. L. (2008). Computer Organization and Design, Fourth Edition, Fourth Edition: The Hardware/Software Interface (The Morgan Kaufmann Series in Computer Architecture and Design). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 4th edition.

Rabus, B., Eineder, M., Roth, A., and Bamler, R. (2003). The Shuttle Radar Topography Mission (SRTM). [link]. Acessado em março de 2012.

Ray, C. K. (1994). Representing Visibility for Siting Problems. Phd thesis, Rensselaer Polytechnic Institute.

van Kreveld, M. (1996). Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals. In Symposium on Spatial Data Handling, pages 15–27.