O colunista Clodoveu Davis ensina algumas formas de como determinar se um ponto está dentro ou fora de um polígono
Um dos problemas mais importantes em SIG consiste em determinar se um dado ponto está dentro ou fora de um polígono. É resolvido, por exemplo, várias vezes cada vez que se usa o botão do mouse para selecionar um objeto na tela. Embora a solução seja relativamente simples, é necessário tomar muito cuidado com casos especiais e problemas numéricos, fazendo com que uma implementação realmente robusta seja relativamente difícil de alcançar.
O princípio fundamental para determinar se um ponto Q, de coordenadas xQ e yQ, está ou não dentro de um polígono P consiste em traçar, a partir de Q, uma semi-reta em uma direção qualquer. Quando esta semi-reta intercepta o polígono um número ímpar de vezes, então o ponto está dentro do polígono; caso contrário, ou seja, caso exista um número par de interseções, o ponto está fora (Figura 1).
Figura 1 – Ponto em polígono
Por conveniência, adota-se em geral uma semi-reta paralela ao eixo dos x passando por Q e se estendendo para a direita. A contagem do número de interseções pode ser feita com facilidade, verificando quantos segmentos da fronteira do polígono têm um ponto extremo acima e outro abaixo de yQ. Destes, é preciso verificar em quantos a interseção com a semi-reta ocorre em um ponto de abscissa maior que xQ. A maior dificuldade está no tratamento de casos degenerados, como:
a semi-reta passa por uma aresta do polígono (Figura 2a);
a semi-reta passa por um vértice do polígono (Figura 2b);
o ponto Q está sobre a fronteira do polígono (Figura 2c);
o ponto Q coincide com um vértice do polígono (Figura 2d).
Figura 2 – Ponto em polígono – casos degenerados
Para estes casos, a solução está em adotar um critério para a contagem de interseções de modo que:
se a reta passa por um vértice, a interseção deve ser considerada apenas se for o vértice com maior coordenada do segmento, e ignorada caso contrário;
se a reta passa por um segmento do contorno do polígono, nenhuma interseção deve ser considerada;
se o ponto Q pertence a um segmento do contorno (exceto pontos extremos), considerar como uma interseção.
O caso em que Q coincide com um vértice pode ser tratado pelo primeiro critério. O terceiro critério faz com que todos os pontos da fronteira sejam considerados como pertencentes ao polígono.
Programa 1 – Função ponto Em Retângulo.
Assim, pode-se construir um algoritmo (Programa 2), que claramente tem complexidade O(n), sendo n o número de vértices do polígono. Observe-se que foi incluído um teste de rejeição rápida (Programa 1), comparando o ponto com o retângulo envolvente mínimo do polígono, considerando que este tenha sido previamente determinado e armazenado. Este teste, que tem complexidade O(1), pode representar um ganho de desempenho importante para SIG, onde pontoEmPolígono é freqüentemente usada.
Programa 2 – Função ponto Em Polígono
Programa 3 – Função ponto Em Polígono1
(variação de pontoEmPolígono)
Existe uma variação em que a interseção é considerada apenas se um dos pontos extremos do segmento da fronteira estiver estritamente acima ou abaixo da semi-reta, enquanto o outro pode estar do lado oposto ou sobre a semi-reta (Programa 3). Dessa forma, é intencionalmente forçada uma situação em que pontos pertencentes a determinados segmentos da fronteira são considerados como pertencentes ao polígono, enquanto outros são considerados como não pertencentes. Como exemplo, considere-se um retângulo com lados paralelos aos eixos. Pelo algoritmo do Programa 3, pontos nas laterais esquerda e inferior são considerados dentro, e pontos nas laterais direita e superior são considerados fora do polígono. Este critério é o mais recomendável em situações de particionamento do plano, em que se deseja que qualquer ponto pertença a exatamente um polígono. Pelo critério anterior, pontos sobre a fronteira comum entre dois polígonos pertenceriam a ambos.
A aplicação do teste de ponto em polígono em SIG depende também do modelo adotado para representar entidades de área. Caso apenas sejam permitidos polígonos simples (ou seja, polígonos cujos segmentos de fronteira não se interceptam fora dos vértices), o teste poderá ser usado conforme apresentado. No entanto, caso o modelo do SIG permita a existência de regiões formadas por vários polígonos simples isolados, e formando ilhas e buracos, o teste precisará ser aperfeiçoado. Uma possibilidade é testar a inclusão do ponto em todos os polígonos simples que compõem a região, verificando os seguintes casos:
Ponto contido em apenas um polígono: nesse caso, o polígono só poderá ser uma ilha, e portanto o ponto está dentro da região.Caso o polígono seja um buraco, existe erro topológico.
Ponto contido em mais de um polígono: se o número de ilhas for igual ao número de buracos, o ponto está fora da região (Figura 3b); se o número de ilhas for maior que o número de buracos, o ponto está dentro da região (Figura 3a). O caso de se ter o número de buracos superior ao número de ilhas indica um erro topológico.
Para o teste em regiões, conforme descrito acima, recomenda-se usar o Programa 3, para evitar conflitos em situações em que o ponto fique na fronteira entre dois ou mais polígonos, o que pode mascarar o resultado. Em qualquer caso, considera-se que não existe superposição entre os polígonos que compõem a região.
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