La regla par-impar es un algoritmo implementado en software gráfico basado 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 reglas distintas de cero , este algoritmo alternativamente coloreará y dejará formas sin colorear definidas por rutas cerradas anidadas independientemente de su devanado.
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 desde la forma dada que cruza el rayo. Si este número es impar, el punto está dentro; si incluso, el punto está fuera.
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 vector de gráficos por computadora SVG puede configurarse para usar la regla par-impar al dibujar polígonos, aunque usa la regla distinta de cero por defecto. [2]
Implementación
A continuación se muestra una implementación de ejemplo en Python : [3]
def is_point_in_path ( x : int , y : int , poly ) -> bool : # Determina si el punto está en el 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 la ruta o es una esquina o en el límite num = len ( poli ) j = num - 1 c = Falso para i en el rango ( num ): if ( x == poli [ i ] [ 0 ]) y ( y == poli [ i ] [ 1 ]): # el punto es una esquina return Verdadero si (( poli [ i ] [ 1 ] > y ) ! = ( poli [ j ] [ 1 ] > y )): pendiente = ( x - poli [ i ] [ 0 ]) * ( poli [ j ] [ 1 ] - poli [ i ] [ 1 ]) - ( poli [ j ] [ 0 ] - poli [ i ] [ 0 ]) * ( y - poli [ i ] [ 1 ]) si pendiente == 0 : # el punto está en el límite devolver Verdadero si ( pendiente < 0 ) ! = ( poli [ j ] [ 1 ] < poli [ i ] [ 1 ]): c = no c j = i retorno c
Ver también
Referencias
- ^ 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, segunda edición, 1990.
- ^ [1] , w3c.org, consultado el 28 de marzo de 2019
- ^ "PNPOLY - Prueba de inclusión de puntos en polígono - WR Franklin (WRF)" .