¿Cómo se determina si un punto se encuentra dentro de un polígono?

Question

Dadas las coordenadas de un punto $(x, y)$ ¿Cuál es el procedimiento para determinar si se encuentra dentro de un polígono cuyos vértices son $(x_1, y_1), (x_2, y_2), \ldots , (x_n,y_n)$ ?

Answer 1

Asumiré que el polígono no tiene intersecciones entre las aristas excepto en las esquinas. Llama al punto $(x_0, y_0)$ . En primer lugar, determinamos si estamos en una línea, lo cual es sencillo si utilizamos la sustitución y la comprobación del rango. Para la comprobación del rango, supongamos que tenemos un segmento $(x_1, y_1)$ , $(x_2, y_2)$ . Comprobamos que $x_1\leq x_0\leq x_2$ o $x_2\leq x_0\leq x_1$ y hacer lo mismo para $y$ .

Ahora, si no estamos en una línea, dibujamos una semirrecta desde el punto y contamos cuántas líneas se cruzan. Si la línea no interseca una esquina o contiene un segmento no degenerado de una arista, entonces un número impar de intersecciones debería significar que estás dentro y un número par significa fuera.

Si nos cruzamos con una esquina, es más difícil. Evidentemente, el rayo podría salir con sólo intersecar una esquina, pero también podría pasar por la esquina sin entrar en el polígono. Una solución es elegir el rayo de manera que no intersecte una esquina o vaya a lo largo de una línea - esto debería ser siempre posible. También podemos utilizar el producto cruzado para determinar si estamos cruzando las líneas en su esquina o no (sólo hay que comprobar si los vértices adyacentes están en el mismo lado de la línea o no).

Answer 2

Representar un polígono por su trayectoria de aristas puede no ser lo más útil, especialmente si se quiere preguntar por la inclusión de muchos puntos. Considere triangulación del polígono que es trivial para polígonos convexos, y no es difícil de encontrar O(n log(n)) para casos más peludos. Entonces, determinar si el punto está en el polígono se reduce a si está en alguno de los triángulos, lo cual es fácil.

Answer 3

Si el polígono es: $A,B,C,D,E,F$
y el punto es P.
( $\text{(angle)}_1$ = ángulo entre $PA$ y $PB$ )
( $\text{angle}_2$ = ángulo entre $PB$ y $PC$ )
( $\text{(angle)}_3$ = ángulo entre $PC$ y $PD$ )
( $\text{(angle)}_4$ = ángulo entre $PD$ y $PE$ )
( $\text{(angle)}_5$ = ángulo entre $PE$ y $PF$ )
( $\text{(angle)}_6$ = ángulo entre $PF$ y $PA$ )

En el sentido de las agujas del reloj son positivos
en sentido contrario a las agujas del reloj son negativos

Si ( $\text{(angle)}_1+ ...+ \text{(angle)}_1=2\pi\space \text{or}\space -2\pi$ ) está dentro;
si no (es cero entonces está fuera;)