La regla par-impar es un algoritmo implementado en software de gráficos basados en vectores, [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 distinta de cero , este algoritmo alternativamente coloreará y dejará formas sin colorear definidas por caminos cerrados anidados, independientemente de su sinuoso.
El SVG define la regla par-impar diciendo:
Esta regla determina el "interior" de un punto en el lienzo dibujando un rayo desde ese punto hasta el infinito en cualquier dirección y contando el número de segmentos de trayectoria de la forma dada que cruza el rayo. Si este número es impar, el punto está dentro; si es así, el punto está afuera.
La regla se puede ver en efecto en muchos programas de gráficos vectoriales (como Freehand o Illustrator ), donde un cruce de un contorno consigo mismo hace que las formas se llenen de formas 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 de computadora SVG se puede configurar para usar la regla par-impar al dibujar polígonos, aunque usa la regla distinta de cero de forma predeterminada. [2]
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á verificando:
def is_point_in_path ( x : int , y : int , poly : list [ tupla [ int , int ]]) -> bool : """Determina si el punto está en la ruta, esquina o límite del polígono Args: x: las coordenadas x del punto. y: las coordenadas y del punto. poli: una lista de tuplas [(x, y), (x, y), ...] Devuelve: Verdadero si el punto está en el camino o es una esquina o en el límite""" c = False para i en el rango ( len ( poly )): ax , ay = poly [ i ] bx , by = poly [ i - 1 ] si ( x == ax ) y ( y == ay ): # punto es una esquina retorno Verdadero si ( ay > y ) != ( by > y ): pendiente = ( x - ax ) * ( by - ay ) - ( bx - ax ) * ( y - ay ) si pendiente == 0 : # punto está en el límite return Verdadero si ( pendiente < 0 ) != ( por < ay ): c = no c return c