Teste interior/exterior de um ponto em relação a um polígono

Este problema, muito importante em diversas aplicações de computação gráfica, por exemplo, pode ser formulado da seguinte forma: dado um polígono e um ponto, verificar se o ponto está dentro da área compreendida pelo polígono ou fora dela.

Existe para esse problema uma solução interessante. Dado um ponto p que desejamos verificar se é interno ou externo a um polígono P, traçamos a partir de p uma semi-reta r em alguma direção escolhida. Se o p é um ponto interno ao polígono, a semi-reta terá um número ímpar de intersecções com as arestas do polígono. Se o ponto for externo o número de cruzamentos será par. Basta então contar o número de cruzamentos da semi-reta com os lados do polígono.

Porém, temos que tomar cuidado nesse algoritmo com os casos especiais onde algum vértice do polígono pertence a semi-reta r. Esses casos podem aparecer de diversas formas. É muito fácil errar a resposta se isso ocorrer, pois não sabemos ao certo se devemos contar uma intersecção, duas ou nenhuma. Existem algumas técnicas com vista a contornar essas situações, porém uma solução conveniente é mudar a direção escolhida de modo que a semi-reta analisada não passe sobre nenhum vértice. Esse algoritmo funciona para qualquer polígono simples e tem complexidade de tempo O(n).

Se tratarmos do caso particular onde o polígono é convexo, podemos adotar outra estratégia para resolver o problema. Usando o fato de que o polígono é definido por uma seqüência de pontos que obedece uma certa ordem, podemos realizar busca binária nas arestas do polígono, obtendo um algoritmo que executa em tempo O(log n). A idéia é traçarmos uma reta que passa por 2 vértices de forma que divida o polígono em 2 polígonos com n/2+1 vértices cada. Em seguida verificamos qual o lado da reta que contém o ponto procurado. Agora basta reaplicarmos o algoritmo recursivamente para a metade do polígono que está do lado correspondente até obtermos um triângulo.

Voltar

Para saber mais

Consulte a seguinte bibliografia:

  1. L.H. Figueiredo, P.C.P. Carvalho - Introdução à Geometria Computacional
    IMPA (1991).
  2. M.J. Laszlo - Computational Geometry and Computer Graphics in C++
    Prentice Hall (1996).

Last modified: Tue Jan 18 15:51:20 EDT 2000