Uma abordagem eficiente para o cálculo de viewshed em terrenos armazenados em memória externa

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

Resumo

Uma importante aplicação de SIGs é o cálculo da região visível (viewshed) a partir de um determinado ponto em um terreno representado por um modelo digital de elevação (MDE). Muitas vezes, o processamento de MDEs de alta resolução não pode ser realizado em memória interna e, portanto, é importante o desenvolvimento de algoritmos para processar estes dados em memória secundária. Este trabalho apresenta um algoritmo para cálculo de viewshed que é capaz de lidar com grande volume de dados em memória externa de forma eficiente. Os testes realizados indicam que o método proposto é mais eficiente do que outros métodos descritos em literatura.

Referências

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.