Cómo crear un algoritmo que pueda determinar si un punto está contenido en un polígono irregular definido por los puntos de sus esquinas

Answer 1

Suponiendo que se trata de un polígono simple (sin líneas cruzadas o regiones múltiples), el algoritmo consiste básicamente en contar cuántos segmentos cruza al “salir” del polígono en una dirección particular. Y la forma más sencilla de hacer esto es contar cuántos segmentos están “por encima” del punto en cuestión.

Iterar a través de cada segmento (definido como pares consecutivos de vértices). Determine si el segmento está “por encima” del punto. Esto se realiza en dos pasos: primero, es la coordenada x del punto entre las coordenadas x de los vértices; segundo, si es así, es la coordenada y del punto debajo de la línea en la que se encuentra el segmento. (¡Este último bit requiere que encuentres la ecuación de una línea!)

Si hay un número impar de segmentos, entonces estás dentro del polígono. De lo contrario, estás afuera.

Hay muchos casos de esquina a considerar, como el punto que está directamente debajo de un vértice, o directamente en un borde, etc. Puede resolver esto.

Answer 2

El algoritmo más genérico para este problema utiliza el teorema de la curva de Jordan. Equivale a trazar el límite del polígono para ver cuántas veces cruza la línea horizontal (mismo valor y) que contiene el punto de prueba a cada lado del punto de prueba, y señala que tiene que cruzar un número impar de veces en cada lado si el punto está en el polígono. Puede ver una descripción más completa aquí: Determinar si un punto está dentro de un polígono complejo

Answer 3

Si los vértices están en el orden correcto, mi primer intento sería:

El punto que desea estudiar es [matemática] A [/ matemática] y los vértices son [matemática] B_n [/ matemática]. Entonces tomaría ángulos

[math] \ theta_i = \ mathrm {ang} \ left (AB_ {i + 1}, AB_i \ right) \ in \ left [- \ pi, \ pi \ right) [/ math]

y calcular su suma. Para un polígono convexo, esto debería dar [math] \ pm 2 \ pi [/ math] para un punto dentro del polígono ([math] \ pm [/ math] dependiendo del orden de los vértices) y [math] 0 [ / math] para un punto afuera.

Para los polígonos no convexos, esto seguirá funcionando para algunos puntos, pero no para todos, y necesitaría un algoritmo más complejo.

Answer 4

Triangular y ver si el punto está en uno de los triángulos. La triangulación se puede hacer recursivamente eliminando un triángulo y considerando el polígono restante.