Como calcular a área de um polígono irregular

Recentemente precisei calcular a área de um polígono irregular. Mas como? Fiz uma pesquisa sobre geometria computacional, e uma das formas que encontrei foi em dividir o polígono em vários triângulos e, após isso, calcular a área de cada triângulo. Tudo bem, mas como dividir o polígono em vários triângulos menores? Por exemplo, como dividir automaticamente o polígono da figura 1 em triângulos? Existem algoritmos para isso, para fazer a triangulação de polígonos.

Figura 1 – Um polígono dividido em vários triângulos

Basicamente o algoritmo funciona da seguinte forma. Divide o polígono em vários polígonos monotone* e depois faz a triangulação de cada um desses algoritmos usando um algoritmo para fazer a triangulação.

Essa é uma das formas de se fazer isso. Uma outra forma é baseada na técnica descrita no post “Como calcular computacionalmente o valor de PI“. Nesse caso podemos fazer o seguinte. Desenhamos o polígono em cima de um outro polígono já conhecido, no caso um retângulo. Sabemos como calcular a área do retângulo. Depois disso, começamos a gerar pontos aleatórios dentro do retângulo (o polígono que queremos calcular a área está em cima do retângulo). Para cada ponto, vemos se o ponto caiu dentro do polígono irregular. Se dividirmos a quantidade de pontos que caiu dentro do polígono pela quantidade de pontos gerada, temos a relação entre a área do polígono e a área do retângulo. Como a área do retângulo é conhecida, fica simples calcular a área do polígono, basta fazer uma multiplicação.

No entanto, fica a questão: Como saber se um ponto está dentro do polígono?  Para efeitos práticos para o cálculo da área dessa forma, podemos traçar uma semi-reta paralela ao eixo x em direção a +x. Se essa semi-reta interceptar um número ímpar de arestas, podemos dizer que ele está dentro do polígono – Figura 2.

Figura 2 – Ponto dentro e fora do polígono

Agora que sabemos quando um ponto está dentro de um polígono, precisamos saber que essa semi-reta interceptou uma das arestas. Isso pode ser feito da seguinte forma:

Primeiro, calculamos a equação da aresta. Considerando que os vértices da aresta são (x1, y1) e (x2,y2), temos que a equação é:

Aplicando a coordenada y do ponto nessa equação, temos um valor de x. Se esse valor for maior que o valor da coordenada x do ponto, sabemos então que o ponto está a esquerda da aresta.

Além disso, se verificarmos que a coordenada y está entre min(y1,y2) e max(y1,y2), então sabemos que a semi-reta intercepta a aresta.

Com isso já podemos calcular a área de um polígono irregular.

Para ilustrar, segue um código Java para isso.

Classe Ponto

Classe Aresta

Classe Poligono

Como primeiro teste, desenhei um polígono e gerei vários pontos aleatórios para testar se o método para verificar se está dentro do polígono está funcionando. Os pontos verdes estão fora do polígono e os amarelo dentro. Desenhei pequenos círculos em volta do ponto gerado, para aproveitar uma rotina que já tenho aqui. Podemos ver que a rotina se mostra adequada para o problema.

Figura 3 – Teste do método para verificar se pontoe stá dentro do polígono

Resta agora testar se isso funciona para calcular a área. Para isso, vamos criar um quadrado de lado 1 e gerar pontos aleatórios dentro de um quadrado de lado 2 e calcular a relação entre a quantidade de pontos dentro do quadrado e a quantidade de pontos gerada. Esse valor multiplicado pela área do quadrado maior (4), deve dar a área do quadrado, que sabemos que é 1. Na verdade, como esse método não é exato, a área deve ser próxima de 1, e não exatamente 1. Segue trecho de código usado para teste:

Uma das saídas desse programa é mostrada na figura abaixo. Note que o valor da área calculado por esse método é muito próximo ao valor real. Na verdade, podemos aumentar a precisão do algoritmo aumentando o número de pontos gerados.

Figura 4 – Resultado do programa

A Figura 5 mostra uma figura de exemplo para esse teste, com os pontos gerados:

Figura 5 – Exemplo do teste efetuado

* – optei por não fazer a tradução dessa palavra pois não sei como ela é traduzida em geometria computacional.

Tags: geometria computacional, java, matemática, polígono