2.1 Algoritmos para el trazo de líneas
La ecuación de intersección de la pendiente cartesiana de una línea recta es
Y = m * x + b (2-1)
donde m representa la pendiente de la línea y b la intersección de y dado que los dos extremos de un segmentos de líneas se especifica en las posiciones (x1,y1)y(x2,y2), como se muestra en la figura podemos determinar los valores para la pendiente y la intersección de y en b con los cálculos siguientes
m = (y2 - y1) / (x2 - x1) (2-2)
b = y1 = m * x1 (2-3)
Los algoritmos para desplegar líneas rectas se basan en la ecuación de línea 2-1 y los cálculos que se dan en las ecuaciones 2-2 y 2-3.Para cualquier x dentro del intervalo Δx a lo largo de una línea, se puede calcular el intervalo correspondiente Δy de y a partir de la ecuación 2-2 como
Δy=m*Δx (2-4)
De modo similar, podemos obtener el intervalo Δx de x correspondiente a una Δy especifica como
Δx=Δy/m (2-5)
2.2 Algoritmo DDA
El analizador diferencial digital (DDA; digital diferencial analyzer) es un algoritmo de línea de conversión de rastreo que se basa en el calculo ya sea de Δy, o de Δx por medio de las ecuaciones 2-4 o 2-5. Efectuamos un rastreo de línea en intervalos unitarios de una coordenada y determinamos los valores enteros correspondientes mas próximos a la trayectoria de la línea para la otra coordenada. Considere primero una línea de pendiente positiva, como se ilustra en la figura anterior. Si la pendiente es menor o igual que 1, llevamos a cabo un muestreo de x en intervalos unitarios (Δx=1) y calcularemos cada valor sucesivo de y como:
El subindice k toma valores enteros a partir de 1 y aumenta a razón de 1 hasta que se alcanza el valor final. Ya que m puede ser cualquier número real entre 0 y 1, los valores calculados de y deben redondearse al entero más cercano. Para líneas con pendiente positiva mayor que 1, se revierten las funciones de x y y. Es decir, se realiza un muestreo de y en intervalos unitarios (Δy = 1) y calculamos cada valor sucesivo de x como
Las ecuaciones 2-6 y 2-7 se basan en la suposición de que las líneas deben procesarse del extremo izquierdo al derecho si este procesamiento se revierte, de manera que sea el extremo derecho donde se inicia, entonces tenemos ya sea Δx= -1 y
o cuando la pendiente es mayor Δy=-1 con
Este algoritmo se resume en el procedimiento siguiente, que acepta como entrada las dos posiciones de píxel de los extremos. Las diferencias horizontal y vertical entre las posiciones de los extremos se asignan a los parámetros de dx y dy. Al iniciar con la posición de píxel (Xa,Ya), determinamos la compensación necesaria para generar la posición del píxel siguiente a lo largo de la trayectoria de la línea. Realizamos el ciclo de este proceso steps. Si la magnitud de dx es mayor que la de dy y Xa es menor que Xb, los valores de los incrementos en las direcciones de X y Y son 1 y m, respectivamente. Si la variación mas alta se en la dirección de X pero Xa es mayor que Xb, entonces los decrementos –1 y -m sirven para generar cada nuevo punto en la línea. De otra manera, utilizamos un incremento(o decremento) de 1/m en la dirección de X. Suponemos que los puntos se debe trazar en un sistema de intensidad de dos niveles, de modo que la solicitud de putpixel será con un valor de intensidad de 1.
Codigo fuente del algoritmo DDA en C/C++
void linea_DDA( double x1,double y1,double x2,double y2)
{
double x,y,dx,dy,p,xi,yi,k;
dx=abs(x2-x1);
dy=abs(y2-y1);
if(dx>dy)
p=dx;
else
p=dy;
xi=dx/p;
yi=dy/p;
if(x1>x2)
xi*=(-1);
if(y1>y2)
yi*=(-1);
x=x1;
y=y1;
for(k=1;k<=p;k++)
{
x+=xi;
y+=yi;
putpixel(x,y,7);
}
}
El algoritmo DDA es un método para calcular posiciones de píxel, que es mas rápido que la aplicación directa de la ecuación 2-1.
2.3 Algoritmo de la linea Bresenham
Muy pronto publicare esta parte
