Regla par-impar

La regla par-impar (Even-Odd Rule) es un algoritmo implementado en software gráfico basado en vectores[1] como el lenguaje PostScript y los Gráficos Vectoriales Redimensionables (del inglés Scalable Vector Graphics) o SVG, que determina como se llena una forma gráfica con más de un contorno cerrado. La especificación de SVG dice: "Esta regla determina la "Interioridad" de un punto sobre un lienzo mediante la elaboración de una Semi-recta desde ese punto hacia el infinito en cualquier dirección y contando el número de veces que atraviesa un segmento trazado. Si el número es impar, el punto está dentro; si es par, el punto esta fuera."

Esta regla se puede ver, en efecto, en muchos programas gráficos vectoriales (como FreeHand o Illustrator), donde cruzar una línea en sí misma causa formas a llenar de extrañas maneras.

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.

Implementación

Python

Debajo un ejemplo de una implementación básica en Python:[2]

def EstaenRuta(x, y, poly):
        '''
        x, y -- x e y coordenadas del punto
        poly -- una lista de tuplas [(x, y), (x, y), ...]
        '''
        num = len(poly)
        j = num - 1
        c = False
        for i in range(num):
                if  ((poly[i][1] > y) != (poly[j][1] > y)) and \
                        (x < (poly[j][0] - poly[i][0]) * (y - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0]):
                    c = not c
                j = i
        return c

Matlab

Debajo una implementación del algoritmo en Matlab:

function p=EstaenPoligono(x,y,pol),
% x,y coordenadas del punto
% pol matriz con los puntos [[x,y];[x,y];....]
format long
n = length(pol);
j = n;
p = false;
for i=1:n,
    v = [pol(i,:);pol(j,:)];
    ymax = max(v(:,2));
    ymin = min(v(:,2));
    inter =((pol(j,1)-pol(i,1))*(y-pol(i,2))/(pol(j,2)-pol(i,2))+pol(i,1)); 
    if ((ymax > y) & (ymin < y)) & (x < inter),
        p = ~p;
    end
end
end

Referencias
  1. J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principles and Practice. The Systems Programming Series. Addison-Wesley, Reading, 2nd edition, 1990.
  2. «Copia archivada». Archivado desde el original el 21 de diciembre de 2014. Consultado el 28 de diciembre de 2014.

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.