A triangulação de DELAUNAY e suas aplicações em GIS
Segundo o que foi apresentado na última coluna, o principal recurso de que se dispõe para resolver problemas que envolvem o conceito de proximidade no plano é o diagrama de Voronoi (Figura 1) Este diagrama é formado com base na seguinte regra: 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, pode-se resolver com eficiência uma grande variedade de problemas ligados ao conceito de proximidade no plano.
Figura 1 – Doagrama de Voronoi com 12 locais
O diagrama de Voronoi é formado por polígonos, que são constituídos por seqüências de arestas e vértices. O número de arestas que se conecta a um vértice do diagrama de Voronoi é denominado grau do vértice. Considerando que o máximo grau de um vértice seja igual a três, define-se o dual de um diagrama de Voronoi através de um grafo. Neste grafo, os nós correspondem aos locais e os arcos conectam locais cujos polígonos de Voronoi compartilham uma aresta do diagrama. Traçando o grafo com linhas retas entre os vértices (locais), é produzida uma triangulação do conjunto de locais, que é denominada triangulação de Delaunay (pronuncia-se "deloné"). A Figura 2 mostra a triangulação de Delaunay sobre o diagrama de Voronoi da Figura 1.
Figura 2 – Diagrama de Voronoi (linhas cheias) e triangulação de Delaunay (linhas pontilhadas)
Uma vez que as arestas dos polígonos de Voronoi e dos triângulos são perpendiculares, a transformação do diagrama de Voronoi para a triangulação de Delaunay é bastante simples. Assim, os algoritmos em geral constróem apenas uma das estruturas, e a partir dela produzem a outra. Parece existir uma tendência, no entanto, a preferir a construção da triangulação de Delaunay, derivando dela, se necessário, o diagrama de Voronoi.
Existem diversos programas para a construção do diagrama de Voronoi e da triangulação de Delaunay disponíveis na Internet. O URL http://www.geog.umn.edu/software/cglist contém links para diversas páginas que oferecem freeware na área de geometria computacional. Uma ótima implementação dos algoritmos de construção do diagrama de Voronoi e da triangulação de Delaunay pode ser encontrada em http://netlib.bell-labs.com/netlib/voronoi/ index/html, incluindo o código fonte.
A triangulação de Delaunay é usada sempre que se tem a necessidade de repartir o plano com base em um conjunto de pontos. São freqüentes as situações em que os pontos representam locais onde se consegue amostrar alguma variável física, como altitude, temperatura ou índice de chuvas, sendo necessário produzir um mapeamento contínuo da variável para toda uma região de interesse. Nestas situações, a triangulação de Delaunay é imbatível, pois foi demonstrado que maximiza o menor ângulo interno de cada triângulo, o que confere à malha triangular uma aparência mais regular. Além disso, a possibilidade de sua transformação no diagrama de Voronoi abre toda uma série de perspectivas de aplicação.
Uma das principais aplicações da triangulação de Delaunay é a criação de modelos digitais do terreno (MDT). Parte-se em geral de um conjunto de amostras (pontos cotados) distribuídos de maneira irregular pelo terreno. As fontes de informação são a restituição de fotos aéreas por processo estereoscópico ou levantamentos topográficos de campo. A partir destas amostras deseja-se construir uma superfície que represente o relevo do local. Para isso, é criada uma triangulação contida no fecho convexo dos pontos amostrais, e a superfície é então aproximada pelos triângulos tridimensionais formados. Como os três vértices de um triângulo definem um plano, esta estratégia equivale a imaginar que o relevo varia linearmente entre dois pontos cotados conhecidos, o que é suficiente para a maioria das aplicações. Se o grau de aproximação obtido não for satisfatório, pode-se densificar a malha de triângulos, introduzindo novos pontos.
A partir da triangulação (denominada por alguns GIS de TIN – Triangulated Irregular Network) pode-se produzir mapas de curvas de nível, usando um algoritmo simples. Basta determinar a interseção de cada triângulo com o plano correspondente à cota da curva de nível que se pretende traçar. Esta interseção pode ser nula (Figura 3a), pode ser um ponto (Figura 3b), um segmento de reta (Figura 3c) ou mesmo todo o triângulo (Figura 3d). Nos casos em que a interseção é um segmento, este é determinado e armazenado para compor a curva de nível. Os outros casos podem ser ignorados para efeito de traçado das curvas. A continuidade de cada curva está garantida pelo fato de que os pontos extremos do segmento de interseção entre plano e triângulo são os mesmos nos triângulos adjacentes.
Figura 3 – Interseção entre o triângulo e plano
Naturalmente, a qualidade do resultado depende da densidade de triângulos – quanto mais triângulos, mais refinado será o aspecto da curva gerada, especialmente nas regiões onde o relevo muda mais bruscamente. Mesmo assim, curvas de nível traçadas por este processo tendem a adquirir um aspecto anguloso, pouco natural. Assim, é executada uma etapa de pós-processamento, em que a curva é suavizada por uma spline ou outro processo qualquer. Observe-se que é necessário que a suavização não altere as características topológicas das curvas de nível, ou seja, as curvas suavizadas, assim como as originais, não podem se interceptar. A Figura 4 mostra o resultado do traçado da curva de nível de cota 50 sobre a triangulação apresentada na Figura 2.
Um tipo de consulta freqüentemente associada com o MDT é a determinação da cota do terreno em um ponto q dado. Isto pode ser feito determinando qual triângulo contém q, e fazendo uma interpolação linear entre os vértices do triângulo para obter a cota procurada. Existem também processos de interpolação que utilizam as curvas de nível para obter a cota de pontos intermediários quaisquer.
O mesmo processo descrito para MDT pode ser usado para tratar outras variáveis de distribuição contínua e que são medidas em pontos discretos, tais como temperatura, índice pluviométrico ou ruído ambiental.
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
