Regla par-impar , la enciclopedia libre
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
[editar]Python
[editar]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
[editar]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
[editar]- ↑ 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.
- ↑ «Copia archivada». Archivado desde el original el 21 de diciembre de 2014. Consultado el 28 de diciembre de 2014.