Clodoveu Davis fala da importância de simplificar a representação de entidades como rios, estradas e ruas em um GIS
Muitas entidades do mundo real podem ser modeladas como poligonais em sua transposição para um GIS. Essas entidades são freqüentes: existem estudos que indicam que objetos lineares correspondem a cerca de 80% do volume de dados vetoriais em um banco de dados geográfico. Poligonais são usadas para representar feições tais como rios, estradas, ruas, linhas de transmissão e adutoras. Os nomes dados pelos GIS comerciais a essas entidades, no entanto, variam muito: linha, polilinha (polyline), line string, arco, 1-cell, poligonal, cadeia (chain), e outros. A complexidade das representações lineares pode variar, indo de simples segmentos de reta (dois pares de coordenadas), como um trecho de tubulação de esgoto, até poligonais contendo milhares de pares de coordenadas, como um rio ou uma curva de nível.
Os algoritmos que trabalham com poligonais são muito importantes para os GIS, uma vez que diversas operações básicas, freqüentemente repetidas, são baseadas neles. Muitas vezes é necessário simplificar a representação de poligonais, buscando (1) evitar o desperdício de memória, (2) melhorar o desempenho dos sistemas, ou (3) melhorar a legibilidade da informação em um mapa. O objetivo geral dessa classe de algoritmos é determinar, dentre os vértices que definem uma poligonal, quais são os mais importantes para a preservação de sua forma geométrica, e quais podem ser dispensados. Em geral, é estabelecido um parâmetro de tolerância, que corresponde à distância a que um vértice da poligonal deve estar em relação ao segmento que une o vértice anterior e o vértice posterior a ele. Por exemplo, na Figura 1 o vértice 2 deve ser mantido, pois se encontra a uma distância superior à tolerância em relação ao segmento 1-3. Já o vértice 3 provavelmente poderá ser descartado, pois encontra-se aproximadamente alinhado com os vértices 2 e 4.
Figura 1 – Tolerância
O problema de simplificação de linhas é particularmente importante em cartografia e GIS, e é estudado intensivamente desde os anos 60, quando ocorreram as primeiras experiências com o uso de instrumentos de transcrição de mapas para o computador, como a mesa digitalizadora. No processo de digitalização de linhas com esses instrumentos freqüentemente são introduzidos vértices em excesso, vértices que, se descartados, não provocariam uma alteração visual perceptível na poligonal. Assim, um primeiro objetivo para algoritmos de simplificação de poligonais é "limpar" (significativamente, o verbo utilizado em inglês é weed, "capinar") a poligonal de pontos claramente desnecessários, do ponto de vista de sua visualização, mantendo a qualidade de sua aparência gráfica. Como conseqüência, o espaço necessário para o armazenamento da poligonal diminui, e a velocidade na sua recuperação e apresentação aumentam. Outro objetivo é o de gerar uma nova versão da linha, uma versão mais adequada para a representação do mesmo fenômeno geográfico em outra escala, menor que a escala original de digitalização. Neste caso, está sendo obtida uma generalização da linha.
O ideal, para um algoritmo que se proponha a resolver o problema de simplificação de poligonais, é combinar os dois objetivos: métodos desenvolvidos apenas pensando na redução do número de vértices da linha podem não ser adequados para alcançar o objetivo de generalização, em geral por não conseguirem uma representação geométrica adequada ao uso em cartografia.
Existem diversos algoritmos para a simplificação de poligonais, mas o mais conhecido e adotado pelos GIS comerciais é o de Douglas-Peucker (pronuncia-se Poiker). Foi proposto em 1973, e é até hoje reconhecidamente o melhor em termos de preservação das características da poligonal original, especialmente se utilizado com tolerâncias pequenas. Curiosamente, o algoritmo foi proposto quase que simultaneamente por Ramer, em 1972, e por Duda e Hart, em 1973, embora visando aplicações diferentes. O algoritmo Douglas-Peucker permanece sendo o mais citado na literatura de geoprocessamento, uma vez que foi originalmente publicado em um periódico da área de cartografia.
O algoritmo é recursivo, e a cada passo processa o intervalo de pontos contido entre um vértice inicial (chamado de âncora) e um vértice final (denominado flutuante). É estabelecido um corredor de largura igual ao dobro da tolerância, formando duas faixas paralelas ao segmento entre o âncora e o flutuante. A seguir, são calculadas as distâncias de todos os pontos intermediários ao segmento básico, ou seja, contidos entre o âncora e o flutuante.
Caso nenhuma das distâncias calculadas ultrapasse a tolerância, ou seja, nenhum vértice fique fora do corredor, então todos os vértices intermediários são descartados. Caso alguma distância seja maior que a tolerância, o vértice mais distante é preservado, e o algoritmo é reiniciado em duas partes: entre o âncora e o vértice mais distante (novo flutuante), e entre o vértice mais distante (novo âncora) e o flutuante. De acordo com esse processo, os pontos tidos como críticos para a geometria da linha, a cada passo, são mantidos, enquanto os demais são descartados.
As figuras seguintes ilustram melhor o comportamento do algoritmo Douglas-Peucker. Inicialmente, são calculadas as distâncias dos vértices 2 a 28 até a reta definida pelos vértices 1 e 29. O vértice mais distante nesta primeira iteração (repetição) é o 15, a uma distância muito superior à tolerância (Figura 2). Assim, o vértice 15 é selecionado e o procedimento é chamado recursivamente duas vezes, entre os vértices 1 e 15 e entre os vértices 15 e 29. Continuando pela primeira chamada, o vértice mais distante da reta entre 1 e 15 é o 9, também a uma distância superior à tolerância, e portanto é selecionado (Figura 3). Duas novas chamadas recursivas são feitas, e agora estão empilhados os intervalos 1-9, 9-15 e 15-29. No intervalo 1-9, temos também que preservar o vértice 3, e portanto ficamos na pilha com os intervalos 1-3, 3-9, 9-15 e 15-29 (Figura 4). Analisando agora o intervalo 1-3, verificamos que o vértice 2 pode ser dispensado (Figura 5). Ao final, são preservados os vértices 1, 3, 4, 6, 9, 15, 16, 17, 22, 24, 27 e 29, ou seja, 41% do número original de vértices (Figura 6).
Figura 2 – Douglas-Peucker, primeiro passo: seleção do vértice 15
Figura 3 – Douglas-Peucker, segundo passo: seleção do vértice 9
Figura 4 – Douglas-Peucker, terceiro passo: seleção do vértice 3
Figura 5 – Douglas-Peucker, passo 4: eliminação do vértice 2
Figura 6 – Douglas-Peucker, final
Embora de implementação simples e relativamente eficiente, o uso universal do algoritmo Douglas-Peucker é comprometido pelo seu comportamento em situações de generalização mais radical, ou seja, com tolerâncias maiores. Conforme a situação, o algoritmo pode ser levado a escolher vértices que terminam por deixar a linha com uma aparência pouco natural, com tendência a apresentar "picos", com ângulos agudos e mudanças bruscas de direção. Alguns autores atribuem este fato à escolha de um valor único para a tolerância, indicando que é mais razoável te variações neste valor de acordo com a geomorfologia da linha, mas até o momento nenhuma variação proposta provou resolver integralmente o problema.
Em situações de generalização radical, existe também a possibilidade de que o algoritmo Douglas-Peucker produza modificações na topologia da linha (como por exemplo auto-interseções), ou modificações na sua situação com relação a linhas vizinhas (como interseções entre curvas de nível simplificadas). Trata-se de um comportamento francamente indesejável, que precisa ser verificado em implementações mais robustas do algoritmo, com o uso de rotinas específicas.
Outro problema amplamente reportado na literatura diz respeito à variação que se pode obter no resultado final quando se varia a linha âncora-flutuante inicial. É o caso da aplicação do algoritmo Douglas-Peucker a poligonais fechadas: dependendo do ponto de partida, ou da estratégia de particionamento da poligonal fechada em duas ou mais poligonais abertas, um resultado diferente será obtido.
O resultado desse algoritmo é aclamado pela literatura como sendo o que mais respeita as características das linhas cartográficas. Assim, esse algoritmo veio a ser a principal escolha dos desenvolvedores de software comercial na implementação de funções de simplificação de linhas para processamento pós-digitalização, ou seja, para limpeza de vértices desnecessários.
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. Rua Alagoas, 314/1501
CEP 30130-160 – Belo Horizonte – MG . Tel.:(031)9978-1422 . Fax:(031)224-0022 . e-mail: cdavis@uol.com.br