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
vértices
em ordem (horária ou anti-horária) e um ponto
, decidamos se
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
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
. Cada vez que esse raio cruza uma aresta do polígono, incrementamos um contador. Se o número total de interseções for ímpar,
está dentro; se for par,
está fora.
Passo 3
Precisamos testar para cada aresta
(com
) se o raio de
cruza essa aresta. O critério é:
Se essa condição se satisfaz, calculamos a abscissa
do ponto de interseção da aresta com a reta
:
Se
, então a aresta cruza o raio à direita de
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
garante que o semi-raio horizontal em “alcance” verticalmente a aresta. - O cálculo de
usa semelhança de triângulos para achar onde a aresta cruza . - Só contamos se essa interseção cair à direita de
. - Por fim, se o número de cruzamentos for ímpar, concluímos que
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