Ponto dentro de polígono

Recentemente precisei implementar um algoritmo que detecta se um dado ponto está dentro ou fora de um polígono simples.

Para o caso especial em que o polígono é convexo, existe um algoritmo que faz a consulta em . Uma descrição do algoritmo e um exemplo de execução podem ser encontrados na minha página pessoal.

Para o caso geral, existe um algoritmo O(n) que é bem diferente daquele do caso convexo, mas igualmente simples e engenhoso.

Problema: Decidir se o ponto está dentro ou fora do polígono.

A ideia é a seguinte: traçamos uma semi-reta a partir do ponto de consulta até o infinito, em uma direção arbitrária, e contamos quantas vezes ela cruzou a borda do polígono. Desconsiderando casos especiais, o polígono estará dentro se e somente se, o número de cruzamentos for ímpar.

O algoritmo é simples de descrever, mas como boa parte de algoritmos geométricos, a parte difícil está em implementar. Para contar o número de cruzamentos, processamos cada segmento do polígono. Supondo que o polígono P é dado por uma lista de pontos em sentido horário (se estiver em sentido anti-horário basta inverter a lista). Assim, um segmento é dado por um par de pontos , incluindo o par . Vamos supor também que um dado ponto p possui coordenadas . Sem perda de generalidade, também consideramos que a semi-reta está na direção horizontal e se estende para a direita (tal qual a Figura 1).

Uma condição necessária para que a semi-reta do ponto p intercepte um segmento qualquer (a, b), é de que p esteja verticalmente entre a e b, ou seja, supondo que , então

(1) .

Figura 1: Para a semi-reta cruzar o segmento, o ponto deve estar verticalmente entre seus extremos.

Porém, como se trata de uma semi-reta com sentido para a direita, queremos considerar apenas os segmentos “à direita” do ponto. Vemos pela Figura 2, que não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento. Para decidir de qual “lado” do segmento está um ponto, podemos usar produto vetorial.

Figura 2: Não basta verificar se o ponto p está à esquerda do ponto mais a esquerda do segmento

Dados dois vetores e , podemos decidir a orientação entre eles através de um produto vetorial . Dependendo do sentido do vetor resultante, é possível dizer se possui orientação horária ou anti-horária em relação a .

Com os três pontos p, a e b, podemos obter os vetores e e usar a ideia do produto vetorial para decidir a orientação de p em relação ao segmento ab. Mais especificamente, podemos usar a seguinte equação [1]:

Se , então o vetor está orientado em sentido anti-horário em relação ao vetor . Se a orientação é horária e se , os vetores são paralelos.

Figura 3: Valor de r e a correspondência geométrica.

Casos especiais

Há dois casos especiais que devemos tratar: o caso em que está na borda do polígono e o caso em que o raio cruza um segmento no seu extremo. Vamos analisar o segundo caso. A figura abaixo elenca todos os possíveis casos.

Figura 4: Casos especiais.

A presença dos casos (a), (b), (d) e (e), não muda de que “lado” do polígono o ponto está, ao contrário dos casos (c) e (f). Assim, as interseções do raio com (a), (b), (d) e (e), não devem mudar a paridade do número de cruzamentos, enquanto as interseções com (c) e (f) sim. Note porém, que no algoritmo apresentado, (d) e (e) aumentarão o número de cruzamentos em 3 (mudando a paridade dos cruzamentos) e (c) aumentará em 2 (mantendo a paridade dos cruzamentos).

Uma maneira bem elegante de se tratar tais casos, é considerar que o raio só intercepta segmentos cujo extremo inferior esteja estritamente abaixo de p e com extremo superior acima ou na mesma altura de p. Ou seja, a equação (1) fica,

(2) .

Agora, o número de cruzamentos com os casos (a) e (d) é 0; com (b) e (e) é 2; e com (c) e (f) é 1, preservando a paridade como gostaríamos.

Finalmente, vamos tratar o caso em que o ponto esteja na borda do polígono. Uma condição necessária, mas não suficiente, é que o ponto p seja colinear a algum dos segmentos do polígono. Além disso, é preciso que p esteja entre os pontos de tal segmento.

Uma vez que sabemos que p é colinear ao segmento , podemos determinar se ele está no meio de a e b através de um produto escalar!

Lembre que o produto escalar entre dois vetores e é equivalente a:

onde é o ângulo entre e .

Podemos definir os vetores e e calcular o produto escalar entre eles. Por hipótese, esses vetores são paralelos. Se p estiver entre a e b, e têm sentido oposto, o ângulo entre eles é . Caso contrário, têm mesmo sentido e o ângulo é 0.

Figura 5: Possíveis orientações entre a, b e p colineares.

Observando que o módulo é sempre positivo e e , concluimos que p está entre a e b se e somente se . Há o caso em que p é coincidente com a ou b. Nesse caso o produto escalar é 0. Resumindo, p está na borda do polígono se existe segmento tal que

Pseudo-código

O pseudo-código abaixo recebe como parâmetros um ponto p e um polígono P, conforme especificado anteriormente, e decide se o ponto está dentro, fora ou na borda do polígono.

Aplicação

Estou desenvolvendo um aplicativo web usando Google Maps onde o usuário define um polígono simples e apenas cidades dentro da região delimitada são consideradas. O algoritmo verifica, para cada cidade, se o ponto correspondente ao centro dela está dentro do polígono definido.

Figura 6: Interface do aplicativo

São necessárias algumas projeções, pois as coordenadas estão em latitude-longitude e o polígono é construído com coordenadas cartesianas,  mas essencialmente o algoritmo usado é o de detecção de ponto
dentro de polígono.

Referências

[1] Wikipedia – Cross Product

5 respostas a Ponto dentro de polígono

  1. Ildebrando diz:

    Oi Guilherme, gostei do seu algoritmo para definir o ponto dentro do polígono. Mas não entendi a linha 6. Como calcular pa * pb?
    Sei que pa = a – p, mas o ponto ‘a’ e ‘p’ possui valores ‘x,y’. Como calcular ‘a – p’?
    Gosto de matemática, mas nunca fui muito bom em geometria (rsrs).
    Abs

    • kunigami diz:

      Olá Ildebrando,

      A operação pa = a – p é só uma maneira simplificada de representar a operação ‘-‘ componente a componente. Em outras palavras,

      pa.x = a.x – p.x
      pa.y = a.y – p.y

      Quanto à linha 6, supondo pa = (pa.x, pa.y) e pb = (pb.x, pb.y), o produto escalar é dado por: pa.x*pb.x + pa.y*pb.y.

  2. Joaquim diz:

    Oi Guilherme, estou trabalhando num sistema que utiliza a API do google maps, mas estou tendo um problema, preciso atribuir um valor para o polígono e recuperá-lo através de um evento onclick, você tem alguma dica?

    abs

  3. Hermiton diz:

    Bom dia Guilherme, preciso desenvolver uma aplicação em Access com esta finalidade, gostaria de saber se você se interessa em ser contratado para criar um procedimento para este cálculo para o sistema Access?

    • kunigami diz:

      Oi Hermiton,

      Infelizmente estou sem tempo algum para trabalhos extras e também não tenho experiência com Access.
      Obrigado pelo convite.

%d bloggers like this: