A importância de saber trabalhar com triângulos, polígonos que são simples e planos
Uma parcela importante do trabalho de geometria computacional em GIS é realizada sobre polígonos. Estes tipos de objetos são muito comuns em GIS, e são usados para representar graficamente entidades bidimensionais, tais como o contorno de edificações, propriedades, regiões de uso do solo e, genericamente, todo tipo de divisão territorial, tais como estados, municípios, bairros e setores censitários.
Assim, considerando o uso intensivo de polígonos em GIS, e a natureza das aplicações usuais, os algoritmos empregados para trabalhar com polígonos precisam ser escolhidos cuidadosamente. Neste sentido, é importante conhecer de perto o que se pode conseguir eficientemente a partir de triângulos, que além de serem os polígonos mais simples, são também figuras garantidamente planas, muito usadas na representação de superfícies. O trabalho com triângulos é bastante interessante, e facilitado pelo conhecimento de algumas de suas propriedades e formulações básicas.
Área do triângulo
Uma vez que na representação vetorial se trabalha com vértices e suas coordenadas, a fórmula elementar da geometria para cálculo da área de um triângulo ("a área de um triângulo é igual à metade do produto entre sua base e sua altura") não é muito prática. Em vez dela, são utilizados dois resultados equivalentes da álgebra linear. O primeiro usa o produto de dois vetores, que determina a área de um paralelogramo, o dobro da área do triângulo que interessa. Outro método calcula a área diretamente, por meio de um determinante 3×3.
O primeiro método pode ser descrito como se segue. Sejam U e V vetores. A área do paralelogramo com lados U e V é wwwww(Figura 1). O produto vetorial pode ser calculado a partir do seguinte determinante:
î ^j ^k
xu yu zu = (yuzv-zuyv)î + (zuxv – xuzv)^j + (xuyv – yuxv)^k
xv yv zv
Onde î, ^J, ^k são vetores unitários nas direções x, y e z respectivamente. Como se está tratando de vetores bidimensionais, temos zU = zV = 0, e portanto a área S do triângulo é dada por
S=(xuyv – yuxv)/2
Mas, na realidade, U = B – A, e V = C – A. Portanto, a expressão acima pode ser reescrita como
S=1/2[(xayb – yaxb + yaxc – xayc + xbyc – ybxc)]
A área calculada pela expressão acima será positiva se os vértices A, B e C formarem um circuito em sentido anti-horário, e negativa se formarem um circuito no sentido horário. A área será exatamente zero se os três vértices estiverem alinhados.
A expressão acima pode ser também obtida quando se calcula o determinante dos três pares de coordenadas, substituindo a coordenada z por 1:
xA yA 1
S=1/2 |xB yB 1 = 1/2 [(xAyB – yAxB + yAxC – xAyC + xByC – yBxC)]
xC yC 1
Também neste caso a área será negativa se a seqüência de vértices estiver orientada em sentido horário, e positiva caso contrário.
Coordenadas baricêntricas e ponto em triângulo
Para determinar se um determinado ponto pertence ou não a um triângulo, utiliza-se um método baseado em coordenadas baricêntricas. Parte-se do fato de que qualquer ponto p do triângulo pode ser definido a partir das coordenadas de seus três vértices, de modo que p = l1p1 + l2p2 + l3p3 = 1, onde l1, l2 e l3 são números reais e l1 + l2 + l3 = 1 . Os coeficientes l1, l2 e l3 são denominados coordenadas baricêntricas de p em relação a p1, p2 e p3.
Com as coordenadas dos pontos p, p1, p2 e p3, e a equação l1 + l2 + l3 = 1, constrói-se um sistema de três equações e três incógnitas para encontrar as coordenadas baricêntricas:
y1x1 + y2x2 + y3x3 = xP
y1x1 + y2x2 + y3y3 = yP
O sistema acima tem por determinante exatamente aquele apresentado na Equação 2, cujo valor corresponde ao dobro da área do triângulo p1p2p3. A área é não-nula, pois p1, p2 e p3 não são alinhados por hipótese, já que são vértices de um triângulo. Assim, o sistema tem solução única para cada p.
Os valores de l1, l2 e l3 podem ser obtidos usando a regra de Cramer, e expressos em termos de áreas de triângulos. Temos, portanto:
y1=S(PP2P3)/S(P1P2P3)
y2=S(P1PP3)/S(P1P2P3)
y3=S(P1P2P)/S(P1P2P3)
A análise do sinal das coordenadas baricêntricas indica a região do plano em que se encontra p, em relação ao triângulo p1p2p3 (Figura 2). Observe-se que, para isso, as áreas devem ser orientadas, ou seja, devem ser calculadas com sinal.
Com esse resultado, torna-se simples implementar um algoritmo que determine se um ponto está contido em um triângulo. Basta obter as coordenadas do ponto e dos vértices do triângulo, e calcular as coordenadas baricêntricas. Se todas as três forem positivas, o ponto pertence ao interior do triângulo. Se todas as três forem maiores que ou iguais a zero, o ponto pertence ao interior ou à fronteira do triângulo.
Alguém poderia imaginar que seria possível, considerando o algoritmo simples para determinar se um ponto pertence ou não a um triângulo, simplesmente dividir o polígono em triângulos e checar o ponto dado contra cada um deles. O problema é justamente dividir o polígono em triângulos, um algoritmo mais complexo que o usado para determinar diretamente se um ponto pertence a um polígono, apresentado nesta coluna na edição ??. De qualquer maneira, um algoritmo baseado em coordenadas baricêntricas funciona muito bem quando se tem estruturas com triângulos já definidos, como TINs (Triangular Irregular Networks).
Área de polígono
A área de um polígono pode ser calculada usando um somatório simples, baseado na soma de áreas de triângulos.
O cálculo pode ser feito como se segue. Sejam xi e yi as coordenadas do vértice vi do polígono P, com n vértices. A área do polígono é dada por
n-1
A(P) = 1/2 [E (XiYi+1 – YiXi+1)]
i=0
Observe-se que, na expressão acima, quando se tem i = n – 1 , é necessário ter xn = x0 e yn = y0 , de acordo com a definição de polígono, caracterizando o seu fechamento.
O sinal da área calculada indica o sentido da seqüência de vértices. A área será negativa se os vértices estiverem em sentido horário, ou positiva se em sentido anti-horário, exatamente como no caso da área do triângulo (Equação 1). Como já foi dito, a base do raciocínio para o desenvolvimento do somatório é o mesmo do cálculo da área de um triângulo. O somatório da Equação 3 corresponde à soma da área de n triângulos, formados entre um ponto arbitrário (no caso, a origem do sistema de coordenadas) e cada par seqüencial de vértices (vi, vi+1).
Centróide de um polígono
Em muitas situações práticas, é necessário determinar, dado um polígono qualquer, seu centro de gravidade ou centro de massa, mais conhecido em GIS como centróide. Em GIS, o centróide é muitas vezes criado e relacionado ao polígono para viabilizar o armazenamento de dados alfanuméricos associados no banco de dados geográfico. É também usado como ponto de lançamento automático de textos gráficos, para identificação de elementos em tela e plotados.
O centro de gravidade de um triângulo é simplesmente a média das coordenadas de seus vértices, ou seja, as coordenadas do centro de gravidade de um triângulo ABC seriam:
Xg = Xa+Xb+Xc /3
e
Yg = Ya+Yb+Yc / 3
Novamente, seria possível estender esse resultado para calcular o centróide de todo o polígono a partir de sua divisão em triângulos. No entanto, existe uma solução mais simples e independente da triangulação, e que leva em conta triângulos com áreas positivas e negativas, como no cálculo da área do polígono. O mesmo processo de média ponderada pela área pode ser usado, considerando todos os triângulos formados entre um ponto fixo, por exemplo (0, 0), e cada par de vértices sucessivos, (vi, vi+1).
Assim, temos que
n-1
A(P) = 1/2 [E (XiYi+1 – YiXi+1)
i=0
n-1
Xc = [E (Xi+1 + Xi) x (XiYi+1 – YiXi+1)] / 3A(P)
i=0
n-1
Yc = [E Yi+1 + Xi) x (XiYi+1 – YiXi+1)] / 3A(P)
i=0
Curiosamente, parte dos GIS considera uma definição alternativa de centróide, em que mesmo se situa "aproximadamente no centro do polígono". Assim, o centróide pode ser determinado por diversos processos, como o centro do retângulo envolvente mínimo, o centro de um círculo inscrito ou circunscrito ao polígono, ou mesmo definido intuitivamente pelo usuário. Uma forma freqüentemente usada para determinar um centróide consiste em simplesmente obter a média aritmética das coordenadas x e y dos vértices. Embora menos computacionalmente intensivo do que o método apresentado nesta seção, o processo da média tem seus resultados afetados por características dos objetos, ou mesmo pelo processo de digitalização dos polígonos. Como se pode perceber na Figura 3, a existência, por alguma razão, de uma concentração de vértices em uma região do polígono causa um deslocamento indesejável do centróide. O deslocamento ocorre justamente em direção à região com maior densidade de vértices, o que pode prejudicar aplicações simples, como o posicionamento de textos gráficos.
Aprofunde-se neste assunto em:
Figueiredo, L. H., Carvalho, P. C. P. Introdução à Geometria Computacional, Instituto de Matemática Pura e Aplicada, 1991.
ORourke, J. Computational Geometry in C, Cambridge University Press, 1994.
Clodoveu Davis é engenheiro civil, doutor 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.
e-mail: cdavis@uol.com.br