Implemente um algoritmo para determinar se um ponto está no interior ou no exterior de um polígono simples.

Passo 1

O problema pede que, dado um polígono simples definido pelos seus n vértices (x_0,y_0),(x_1,y_1),\dots,(x_{n-1},y_{n-1}) em ordem (horária ou anti-horária) e um ponto P=(x_p,y_p), decidamos se P está no interior ou no exterior do polígono. O conteúdo aqui é geometria computacional, mais especificamente o teste “point-in-polygon”. Vamos usar o algoritmo de “ray casting” (lançar um raio horizontal para a direita a partir de P e contar interseções com as arestas do polígono).

Passo 2

Descrevemos a ideia principal do “ray casting”: traçamos um semi-raio horizontal para a direita de P. Cada vez que esse raio cruza uma aresta do polígono, incrementamos um contador. Se o número total de interseções for ímpar, P está dentro; se for par, P está fora.

Passo 3

Precisamos testar para cada aresta \bigl((x_i,y_i),(x_j,y_j)\bigr) (com j=(i+1)\bmod n) se o raio de P cruza essa aresta. O critério é:
\bigl(y_i \le y_p < y_j\bigr)\;\lor\;\bigl(y_j \le y_p < y_i\bigr).
Se essa condição se satisfaz, calculamos a abscissa x_{\text{int}} do ponto de interseção da aresta com a reta y=y_p:
x_{\text{int}} = x_i + (y_p - y_i)\,\frac{x_j - x_i}{y_j - y_i}.
Se x_{\text{int}}>x_p, então a aresta cruza o raio à direita de P e incrementamos o contador.

Passo 4

Agora juntamos tudo num pseudocódigo:
function pontoInterior(polygon, P):
 let count ← 0
 for i from 0 to n−1:
 j ← (i \(+1\)) mod n
 (\(x_i\),\(y_i\)) ← polygon[i]
 (\(x_j\),\(y_j\)) ← polygon[j]
 if (\(y_i\) ≤ \(y_p\) < \(y_j\)) or (\(y_j\) ≤ \(y_p\) < \(y_i\)) then
 \(x_int\) ← \(x_i\) + (\(y_p\) − \(y_i\)) * (\(x_j\) − \(x_i\)) / (\(y_j\) − \(y_i\))
 if \(x_int\) > \(x_p\) then
 count ← count \(+1\)
 end if
 end if
 end for
 if (count mod 2) \(=1\) then
 return “INTERIOR”
 else
 return “EXTERIOR”
 end if
end function

Passo 5

Explicação final:
  • A condição em y garante que o semi-raio horizontal em y=y_p “alcance” verticalmente a aresta.
  • O cálculo de x_{\text{int}} usa semelhança de triângulos para achar onde a aresta cruza y=y_p.
  • Só contamos se essa interseção cair à direita de P.
  • Por fim, se o número de cruzamentos for ímpar, concluímos que P está dentro; caso contrário, está fora.

Resposta

function pontoInterior(polygon, P):
 let count ← 0
 for i from 0 to n−1:
 j ← (i \(+1\)) mod n
 (\(x_i\),\(y_i\)) ← polygon[i]
 (\(x_j\),\(y_j\)) ← polygon[j]
 if (\(y_i\) ≤ \(y_p\) < \(y_j\)) or (\(y_j\) ≤ \(y_p\) < \(y_i\)) then
 \(x_int\) ← \(x_i\) + (\(y_p\) − \(y_i\)) * (\(x_j\) − \(x_i\)) / (\(y_j\) − \(y_i\))
 if \(x_int\) > \(x_p\) then
 count ← count \(+1\)
 end if
 end if
 end for
 if (count mod 2) \(=1\) then
 return “INTERIOR”
 else
 return “EXTERIOR”
 end if
end function

Exercícios de Livros Relacionados