Método par impar y número de devanado Método: prueba interior y exterior de un polígono

Introducción:
un polígono se puede representar como una serie de segmentos de línea conectados, al final de una figura cerrada.
Los polígonos se pueden representar de dos maneras: 
(i) contorno mediante el uso de comandos de movimiento y 
(ii) como objetos sólidos al configurar los píxeles en lo alto del polígono, incluidos los píxeles en el límite.

Para determinar si un punto se encuentra dentro de un polígono o no, en gráficos por computadora, tenemos dos métodos:
(a) Método par-impar (regla de paridad impar)
(b) Número de bobinado Método-dentro 

Método par-impar:
la construcción de un segmento de línea entre el punto (P) a examinar y un punto conocido fuera del polígono es la única forma de determinar si un punto se encuentra dentro de un polígono o no. Luego se cuenta el número de veces que el segmento de línea intersecta el límite del polígono. El punto (P) es un punto interno si el número de aristas del polígono intersectadas por esta línea es impar; de lo contrario, el punto es un punto externo.

En la figura, el segmento de línea de ‘A’ cruza un solo borde y, por lo tanto, el punto A está dentro del polígono. El punto B también está dentro del polígono ya que el segmento de línea de B cruza tres bordes (impares). Pero el punto C está fuera del polígono porque el segmento de línea de C cruza dos bordes (pares).

Pero esta prueba de par-impar falla cuando el punto de intersección es un vértice.
Para manejar este caso, tenemos que hacer algunas modificaciones. 
Debemos mirar los otros puntos extremos de los dos segmentos de un polígono que se encuentran en este vértice. Si estos puntos se encuentran en el mismo lado de la línea construida A’P’, entonces el punto de intersección cuenta como un número par de intersecciones. Pero si se encuentran en el lado opuesto de la línea construida AP, entonces los puntos de intersección cuentan como una sola intersección.

Como podemos ver, el segmento de línea A’P’ se cruza en M, que es un vértice, y L y Z son los otros puntos finales de los dos segmentos que se encuentran en M. L y Z se encuentran en el mismo lado del segmento de línea A’P’ , por lo que la cuenta se toma como par.

Método del Número de Vueltas:
Hay otro método alternativo para definir el punto interior de un polígono que se llama el método del número de vueltas. Conceptualmente, se puede estirar un trozo de elástico entre el punto (P) a verificar y el punto en el límite del polígono.
Trata que, el elástico está amarrado al punto (P) que se va a verificar firmemente y el otro extremo del elástico se desliza a lo largo del límite del polígono hasta que haya hecho un circuito completo. Luego verificamos cuántas veces se ha enrollado el elástico alrededor del punto de intersección. Si se enrolla al menos una vez, la punta está adentro. Si no hay devanado neto, entonces el punto está afuera.

En este método, en lugar de solo contar las intersecciones, le damos a cada línea de límite cruzada un número de dirección y sumamos estos números de dirección. El número de dirección indica la dirección del borde del polígono que se dibujó en relación con el segmento de línea que construimos para la prueba.

Ejemplo: para probar un punto (x _i , y _i ), consideremos un segmento de línea horizontal y = y _i que va desde fuera del polígono hasta (x _i , y _i ). Encontramos todos los lados que cruzaron este segmento de línea.
Ahora hay 2 formas de cruzar el lado, el lado podría dibujarse comenzando por debajo del final, cruzarlo y terminar por encima de la línea. En este caso, podemos dar números de dirección: 1, al lado o el borde podría comenzar por encima de la línea y terminar debajo de ella, en este caso, dada una dirección 1. La suma de los números de dirección de los lados que cruzan la línea horizontal construida. segmento producen el «Número de bobinado» para el punto. 

Si el número de bobinado es distinto de cero, el punto es interior al polígono, de lo contrario, exterior al polígono.

En la figura anterior, el segmento de línea cruza 4 bordes que tienen diferentes números de dirección: 1, -1, 1 y -1 respectivamente, luego:
Número de bobinado = 1 + (-1) + 1 + (-1) = 0
Entonces el punto P está fuera del Polígono. El borde tiene la dirección Número -1 porque comienza debajo del segmento de línea y termina arriba. De manera similar, el borde tiene la dirección Número +1 porque comienza desde arriba del segmento de línea y termina debajo del segmento de línea (consulte las direcciones en la figura).