Um Algoritmo Eficiente para Cálculo de Viewshed em Memória Externa
Resumo
Com a maior disponibilidade de dados detalhados de terrenos, muitas aplicações precisam processar grandes áreas geográficas em alta resolução. O processamento massivo de dados envolvido em tais aplicações criou grandes desafios para sistemas de SIG e demanda algoritmos otimizados tanto para processamento interno quanto para movimento de dados. Uma dessas aplicações é o cálculo do viewshed, que consiste em obter o conjunto de pontos visíveis a partir de um ponto p. Nesse artigo, apresentaremos um algoritmo eficiente para calcular o viewshed de terrenos armazenados em memória externa. Como mostram os resultados, o algoritmo proposto é mais eficiente do que os algoritmos conhecidos 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.
Ben-Moshe, B., Ben-Shimol, Y., and Y. Ben-Yehezkel, A. Dvir, M. S. (2007). Automated antenna positioning algorithms for wireless fixed-access networks. Journal of Heuristics, 13(3):243–263.
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.
Commons, C. (2007). [link] (acessado em Março de 2008).
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 Março de 2008).
Floriani, L. D. and Magillo, P. (2003). Algorithms for visibility computation on terrains: a survey. Environment and Planning B - Planning and Design, 30:709–728.
Floriani, L. D., Puppo, E., and Magillo, P. (1999). Applications of computational geometry to geographic information systems. In J. R. Sack, J. U., editor, Handbook of Computational Geometry, pages 303–311. Elsevier Science.
Franklin, W. R. (2002). Siting observers on terrain. In Springer-Verlag, editor, In D. Richardson and P. van Oosterom editors, Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling, pages 109–120.
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.
Franklin, W. R. and Vogt, C. (2006). Tradeoffs when multiple observer siting on large terrain cells. In 12th International Symposium on Spatial Data Handling.
Haverkort, H., Toma, 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).
The Shuttle Radar Topography Mission (SRTM) (2007). [link] (acessado em Março de 2008).
Schwartz, W. R. and Pedrini, H. (2001). Determinação de mapas de visibilidade em modelos digitais de terrenos. In II Colóquio Brasileiro de Ciências Geodésicas (CBCG’2001), pages 44–45, Curitiba-PR, Brazil.
Stewart, A. J. (1998). Fast horizon computation at all points of a terrain with visibility and shading applications. In IEEE Trans. Visualization Computer Graphics, pages 82 – 93.
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.
Ben-Moshe, B., Ben-Shimol, Y., and Y. Ben-Yehezkel, A. Dvir, M. S. (2007). Automated antenna positioning algorithms for wireless fixed-access networks. Journal of Heuristics, 13(3):243–263.
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.
Commons, C. (2007). [link] (acessado em Março de 2008).
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 Março de 2008).
Floriani, L. D. and Magillo, P. (2003). Algorithms for visibility computation on terrains: a survey. Environment and Planning B - Planning and Design, 30:709–728.
Floriani, L. D., Puppo, E., and Magillo, P. (1999). Applications of computational geometry to geographic information systems. In J. R. Sack, J. U., editor, Handbook of Computational Geometry, pages 303–311. Elsevier Science.
Franklin, W. R. (2002). Siting observers on terrain. In Springer-Verlag, editor, In D. Richardson and P. van Oosterom editors, Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling, pages 109–120.
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.
Franklin, W. R. and Vogt, C. (2006). Tradeoffs when multiple observer siting on large terrain cells. In 12th International Symposium on Spatial Data Handling.
Haverkort, H., Toma, 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).
The Shuttle Radar Topography Mission (SRTM) (2007). [link] (acessado em Março de 2008).
Schwartz, W. R. and Pedrini, H. (2001). Determinação de mapas de visibilidade em modelos digitais de terrenos. In II Colóquio Brasileiro de Ciências Geodésicas (CBCG’2001), pages 44–45, Curitiba-PR, Brazil.
Stewart, A. J. (1998). Fast horizon computation at all points of a terrain with visibility and shading applications. In IEEE Trans. Visualization Computer Graphics, pages 82 – 93.
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.
Publicado
12/07/2008
Como Citar
MAGALHÃES, Salles V. G.; ANDRADE, Marcus V. A.; MAGALHÃES, Mirella A..
Um Algoritmo Eficiente para Cálculo de Viewshed em Memória Externa. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 27. , 2008, Belém/PA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2008
.
p. 31-40.
