O Diagrama de VORONOI e suas aplicações em GIS
O principal recurso de que se dispõe para resolver problemas que envolvem o conceito de proximidade no plano é o diagrama de Voronoi. Trata-se de uma estrutura geométrica inicialmente estudada em meados do século XIX pelos famosos matemáticos Gauss e Dirichlet e refinada em 1.908 por Voronoi. Os conceitos relacionados a esta estrutura surgiram, de forma independente dos círculos matemáticos, em diversas outras áreas, tais como cristalografia, biologia e climatologia. Por isso o diagrama de Voronoi tem diversos outros nomes na literatura: tesselação de Dirichlet, zonas de Wigner-Seitz, polígonos de Thiessen, zonas proximais, e outros.
O diagrama de Voronoi é formado com base em uma regra muito simples: dado um conjunto de locais (pontos) no plano, associar a cada local a região do plano mais próxima dele do que de qualquer outro. Com isso, é possível responder com eficiência a uma grande variedade de perguntas a respeito de proximidade: qual local está mais próximo de um ponto dado, qual a maior região desocupada, qual é o vizinho mais próximo de um local, entre outras. Diversos trabalhos acadêmicos buscaram destacar a importância desta estrutura para GIS, mas até o momento os pacotes comerciais não a incorporam explicitamente, para prejuízo de aplicações que demandam com freqüência a solução de problemas de proximidade.
A Figura 1 mostra um exemplo de diagrama de Voronoi com 12 locais. Observe-se que existem 12 polígonos, denominados polígonos de Voronoi, um para cada local. Os 7 polígonos externos se estendem infinitamente no plano, e por isso são desenhados como figuras abertas. Cada aresta do diagrama constitui um lugar onde os pontos são eqüidistantes a dois locais. Os vértices dos polígonos estão ligados a três ou mais arestas, e portanto são pontos de eqüidistância entre três ou mais locais.
Figura 1 – Diagrama de Voronoi com 12 locais
O diagrama de Voronoi tem muitas aplicações em GIS. Como estrutura de dados básica para resolver problemas de proximidade, pode ser empregada sempre que a aplicação envolver um número grande de consultas sobre os mesmos dados básicos, de modo a justificar o custo de sua criação e manutenção. Um exemplo: informar ao público, por telefone, qual o posto de vacinação mais próximo de sua residência. Neste caso, são potencialmente milhares de consultas sobre um conjunto de dados que praticamente não muda.
Apesar das vantagens que se tem em usar esta estrutura na solução de problemas como os relacionados a seguir, a maioria das aplicações baseadas em GIS comerciais prefere adotar estratégias mais genéricas, usando recursos básicos de localização individual de objetos disponíveis no próprio GIS ou no banco de dados subjacente. No entanto, a grande utilidade do diagrama de Voronoi no contexto de GIS tem conduzido a propostas no sentido de incrementar seu uso, incorporando estratégias de manutenção dinâmica e a possibilidade de trabalhar com objetos móveis em tempo real.
A seguir, são apresentadas algumas aplicações do diagrama de Voronoi que são significativas no contexto de GIS, sem a pretensão de esgotar o assunto.
Ponto mais próximo. Dado um conjunto P de locais, deseja-se saber qual é o mais próximo de um ponto q dado. Trata-se de uma consulta tradicional em geoprocessamento com diversas aplicações em análise espacial. Quando se dispõe do diagrama de Voronoi, a solução do problema consiste simplesmente em determinar o local correspondente ao polígono de Voronoi que contém q. Naturalmente, existem maneiras de resolver este problema sem utilizar o diagrama de Voronoi (por exemplo, analisar seqüencialmente a distância entre q e todos os pontos ), mas quando se pretende realizar um número razoável de consultas, sobre um conjunto de pontos relativamente estável, construir antecipadamente o diagrama de Voronoi pode ser muito vantajoso. Um exemplo prático: informar aos usuários do sistema de transporte coletivo qual é o ponto de parada de ônibus mais próximo de sua residência ou local de trabalho. Outro exemplo: localizar o hidrante mais próximo de um determinado prédio.
Vizinhos mais próximos. Este problema consiste em, dado um conjunto P de locais, encontrar o local pj mais próximo de cada local pi (o vizinho mais próximo de pi) pertencente a P. Um exemplo prático está na geração de indicações de quiosque mais próximo para caixas automáticos, de modo a informar os clientes sobre alternativas em caso de falha de algum deles. Outro exemplo é, dado um conjunto de aeroportos satisfazendo a certas condições (comprimento da pista, instrumentação de pouso, equipamentos de emergência), determinar qual é o aeroporto mais indicado para redirecionamento dos pousos em caso de fechamento por mau tempo de qualquer um dos aeroportos.
O resultado do problema é um grafo de proximidade (Figura 2), definido como sendo um grafo em que os nós são os locais e as arestas são direcionadas entre cada local e seu vizinho mais próximo. Este grafo pode ser usado para responder com facilidade a questões como qual é o local mais próximo deste e que locais são mais próximos deste do que de qualquer outro. No segundo exemplo, estas questões seriam traduzidas como qual é o aeroporto mais próximo do Aeroporto de Confins e que aeroportos redirecionarão seus pousos para Confins em caso de fechamento. Observe que este grafo não é necessariamente conexo, e também que as ligações entre os nós não são sempre reflexivas.
Figura 2 – Grafo de proximidade
Este problema pode ser resolvido a partir da disponibilidade do diagrama de Voronoi. Basta analisar cada aresta definida no diagrama, calcular a distância entre os locais separados por aquela aresta, e armazenar o menor valor associado a cada local. Uma alternativa a esta solução é utilizar a triangulação de Delaunay, verificando para cada vértice de triângulo (correspondente a um local) qual é a aresta de menor comprimento que incide sobre ele. O local na outra extremidade desta aresta é o vizinho mais próximo.
Maior círculo vazio. Este problema consiste em determinar o maior círculo cujo centro pertence ao fecho convexo dos locais de P e que não contém nenhum local. Foi demonstrado que, caso o centro do círculo seja interior ao fecho convexo (que é o menor polígono convexo que contém todos os locais), então deve coincidir com um vértice de Voronoi. O centro do maior círculo vazio pode também estar sobre alguma aresta do fecho convexo, e neste caso estará situado no ponto médio da aresta, eqüidistante a dois vértices. Um algoritmo para resolver este problema a partir do diagrama de Voronoi consiste, portanto, em verificar o raio do círculo definido sobre cada vértice, que corresponde à distância do vértice a um dos três locais eqüidistantes a ele. Também deve ser verificado o raio de cada círculo definido com centro no ponto médio de cada aresta do fecho convexo. Ao final, o resultado é o círculo de maior raio dentre os verificados (Figura 3).
Figura 3 – Maior círculo vazio
Esta técnica pode ser usada para escolher o ponto de implantação de um novo empreendimento, desde que se faça algumas hipóteses simplificadoras: (1) a distribuição da clientela pelo território é uniforme, e (2) é possível encontrar espaço para a implantação do empreendimento no centro aproximado do círculo vazio. Caso estas simplificações não sejam aceitáveis, torna-se necessário utilizar técnicas mais avançadas para escolher o local do empreendimento, tais como a determinação da superfície de potencial de vendas, ou semelhante.
Outra situação em que este problema se aplica está na escolha de uma área para a localização de uma atividade potencialmente poluidora, em um lugar que seja tão distante quanto possível de centros populacionais.
A literatura sobre o diagrama de Voronoi e suas aplicações em GIS é bastante extensa, e continua crescendo. Além do diagrama de Voronoi com locais estáticos, existem muitas variações:
· O diagrama de Voronoi de ordem k, em que cada polígono corresponde ao lugar geométrico dos pontos do plano que compartilham o mesmo conjunto de k locais mais próximos. Esta variação pode ser usada para resolver problemas em que se deseja ter como resposta, além do local mais próximo, uma segunda alternativa.
O diagrama de Voronoi com locais em movimento, em que o deslocamento de um determinado local provoca alterações apenas no polígono correspondente ao local que se move e em seus vizinhos. Este diagrama tem aplicações em despacho de viaturas, como monitoramento dinâmico da posição geográfica de cada uma delas.
O diagrama de Voronoi para pontos e segmentos de reta, em que cada polígono contém os pontos do plano mais próximos de um objeto determinado (ponto ou segmento) do que de qualquer outro. Esta variação pode ser interessante em problemas ligados a endereçamento urbano, se construída sobre uma camada de eixos de logradouro.
Em resumo, o diagrama de Voronoi é uma estrutura geométrica muito importante em problemas de proximidade, e como grande parte dos problemas resolvidos com GIS encontra-se nessa categoria, torna-se fundamental conhecê-la melhor e integrar sua potencialidade a nossas aplicações.
Clodoveu Davis é engenheiro civil, analista de sistemas, mestre em Ciência da Computação e Assessor de Desenvolvimento e Estudos da Prodabel – Empresa de Informática e Informação do Município de Belo Horizonte. Email: cdavis@uol.com.br