Hispanopedia Wiki
Articulo de referencia

Regla par-impar

Una curva (arriba) se rellena según dos reglas: la regla par-impar (izquierda) y la regla de enrollamiento distinto de cero (derecha). En cada caso, una flecha muestra un rayo q...

Hispanopedia WikiContenido en espanolLectura gratuita
Una curva (arriba) se rellena según dos reglas: la regla par-impar (izquierda) y la regla de enrollamiento distinto de cero (derecha). En cada caso, una flecha muestra un rayo que parte de un punto P y sale de la curva. En el caso par-impar, el rayo es intersectado por dos líneas, un número par; por lo tanto, se concluye que P está "fuera" de la curva. Según la regla de enrollamiento distinto de cero, el rayo es intersectado dos veces en sentido horario, cada intersectado aportando -1 al valor de enrollamiento: como el total, -2, no es cero, se concluye que P está "dentro" de la curva.

La regla par-impar es un algoritmo implementado en software de gráficos vectoriales, [ 1 ] como el lenguaje PostScript y Scalable Vector Graphics (SVG), que determina cómo se rellenará una forma gráfica con más de un contorno cerrado. A diferencia del algoritmo de regla de no cero , este algoritmo coloreará y dejará sin colorear alternativamente las formas definidas por rutas cerradas anidadas, independientemente de su sinuosidad.

El SVG define la regla par-impar diciendo:

Esta regla determina si un punto del lienzo está dentro de un contorno trazando un rayo desde ese punto hasta el infinito en cualquier dirección y contando la cantidad de segmentos de la figura dada que el rayo atraviesa. Si este número es impar, el punto está dentro; si es par, el punto está fuera.

Esta regla puede observarse en muchos programas de gráficos vectoriales (como Freehand o Illustrator ), donde el cruce de un contorno consigo mismo provoca que las formas se rellenen de maneras extrañas.

En una curva simple, la regla par-impar se reduce a un algoritmo de decisión para el problema del punto en el polígono .

El estándar de gráficos vectoriales SVG puede configurarse para usar la regla par-impar al dibujar polígonos, aunque por defecto usa la regla de no cero . [ 2 ]

Implementación

A continuación se muestra un ejemplo parcial de implementación en Python , [ 3 ] utilizando un rayo a la derecha del punto que se está comprobando:

def is_point_in_path ( x : int , y : int , poly : list [ tuple [ int , int ]]) -> bool : """Determina si el punto está en la ruta, esquina o límite del polígono Argumentos:  x -- Las coordenadas x del punto.  y -- Las coordenadas y del punto.  poly -- una lista de tuplas [(x, y), (x, y), ...] Devuelve:  Verdadero si el punto está en la ruta o es una esquina o en el límite""" c = Falso para i en rango ( len ( poly )): ax , ay = poly [ i ] bx , by = poly [ i - 1 ] si ( x == ax ) y ( y == ay ): # el punto es una esquina devolver Verdadero si ( ay > y ) != ( by > y ): pendiente = ( x - ax ) * ( by - ay ) - ( bx - ax ) * ( y - ay ) si pendiente == 0 : # el punto está en el límite devolver Verdadero si ( pendiente < 0 ) != ( by < ay ): c = no c devolver c

Véase también

Referencias

  1. ↑ JD Foley, A. van Dam, SK Feiner y JF Hughes. Gráficos por computadora: principios y práctica. Serie de programación de sistemas. Addison-Wesley, Reading, 2.ª edición, 1990.
  2. ↑w3c.org, consultado el 28 de marzo de 2019.
  3. ↑ "PNPOLY - Prueba de inclusión de puntos en polígonos - WR Franklin (WRF)" .
  • Definición de reglas de relleno en SVG