Mapas de visibilidade em grandes terrenos representados por grades regulares

Abstract

Uma operação muito comum em sistemas de informações geográficas (SIG) consiste no cálculo de mapas de visibilidade, ou viewsheds. Um mapa de visibilidade indica quais regiões de um terreno são visíveis a partir de um determinado ponto de observação, normalmente chamado de observador. Este trabalho apresenta dois novos algoritmos para cálculo de viewshed em grandes terrenos representados por grades regulares, ambos mais eficientes do que os demais encontrados em literatura. O primeiro algoritmo chama-se TiledVS e foi projeto especialmente para memória externa, ou seja, para reduzir o número de operações de entrada e saída (E/S) re- alizadas. Para isso, ele utiliza uma estrutura de dados denominada TiledMatrix, que subdivide o terreno em diversos blocos retangulares e gerencia os acessos aos dados de forma eficiente. De acordo com os resultados experimentais obtidos, este algoritmo é mais de 4 vezes mais rápido do que todos os outros encontrados em literatura. O segundo algoritmo é um algoritmo paralelo que utiliza o modelo de memória compartilhada (OpenMP ). Este algoritmo subdivide o terreno em diversos setores em volta do observador, de modo que cada um destes setores possa ser pro- cessado de forma independente. Os resultados experimentais mostraram que com um computador com 4 cores é possível obter processamentos 4 vezes mais rápidos do que a versão sequencial do mesmo algoritmo. Já com um computador com 16 cores, foram obtidos processamentos até 12 vezes mais rápidos.

In geographical information science (GIS) it is usual to compute the viewshed of a given point on a terrain. This point is usually called observer, and its viewshed indicates which terrain regions are visible from it. In this work we present two novel algorithms for viewshed computation on large grid terrains, both more efficient than other approaches found in related work. The first algorithm is called TiledVS . It was specially designed for external memory processing, that is, it performs a smaller number of in/out (I/O) operations. To do that, it uses a special library called TiledMatrix, which subdivides the terrain into several rectangular blocks and efficiently manages the accesses to the terrain cells. According to our experimental results, TiledVS is more than 4 times faster than all other previous algorithms. The second one is a parallel algorithm that uses the shared memory model (OpenMP). It subdivides the terrain into several sectors around the observer, such that each sector may be processed independently. Our experimental results showed that, using a personal computer with 4 cores, it is possible to compute the viewshed 4 times faster than with the serial implementation of the same algorithm. Using a computer with 16 cores, we obtained up to 12 times speedups.