Breve descripción sobre Analizador diferencial digital (DDA)

El algoritmo DDA es un método de conversión de exploración incremental. Aquí realizamos cálculos en cada paso utilizando los resultados del paso anterior. La característica del algoritmo DDA es dar un paso unitario a lo largo de una coordenada y calcular el valor correspondiente a lo largo de la otra coordenada.

Un paso unitario siempre está a lo largo de la coordenada del cambio más grande, por ejemplo, si dx = 10 y dy = 5, entonces daremos un paso unitario a lo largo de x y calcularemos el paso a lo largo de y. Supongamos que en el paso i calculamos que (xi, yi) es un punto en la recta.

Dado que el siguiente punto (xi+1, yi+1) debe satisfacer ?y/?x = m donde ?y= yi+1 – yi y ?x= xi+1 – xi, tenemos yi+1 = yi + m ? x o xi+1 = xi + ?y / m.

Estas fórmulas se utilizan en el algoritmo DDA de la siguiente manera.

La explicación es la siguiente: en el algoritmo DDA, tenemos que encontrar nuevos puntos xi+1 y yi+1 a partir de los puntos xi e yi existentes.

Como primer paso, determinamos los ejes mayor y menor de la línea a dibujar. Una vez que se encuentra el eje mayor, muestreamos el eje mayor a intervalos unitarios y usamos la ecuación de la pendiente de la línea para encontrar el valor del otro eje.

Por ejemplo, si los extremos de la recta son (x1,y1)= (2,2) y (x2, y2)= (9,5). Aquí calcularemos y2-y1 y x2-x1 para saber cuál es mayor. Aquí y2-y1 =3 y x2-x1 =7, por lo que el eje principal aquí es el eje x.

Entonces, aquí necesitamos muestrear el eje x a intervalos unitarios, es decir.

x = 1

Encontraremos para cada ?x en el eje x usando la ecuación de la pendiente. En DDA necesitamos considerar dos casos, uno es que la pendiente de la línea es menor o igual a uno (|m| ? 1) y la pendiente de la línea es mayor que uno (m| 1). Cuando |m|? 1 significa que y2-y1 = x2-x1 o y2-y1 x2-x1. En ambos casos asumimos que x es el eje principal. Por lo tanto, muestreamos el eje x a intervalos unitarios y encontramos el valor y correspondiente para cada valor x.

Tenemos la ecuación de la pendiente como ?

¿y = metros? X

Y2-y1 = m (x2-x1)

En general, podemos decir que y i+1 – yi = m(xi+1 – xi ). ¿Pero aquí? x = 1, por lo que la ecuación se simplifica a y i+1 = yi + m = yi + dy/dx.

Cuando m|1 denota y2-y1 x2-x1, suponemos que y es el eje principal. Aquí muestreamos el eje y a intervalos unitarios y encontramos el valor x correspondiente a cada valor y.

Tenemos la ecuación de la pendiente como y2-y1 = m(x2-x1).

En general, podemos decir que y i+1 – yi = m(xi+1 – xi). ¿Pero aquí? y = 1, por lo que la ecuación se simplifica a 1 = m(xi+1 – xi).

Xi+1=xi+1/m

Xi+1=xi+dx/dy

El algoritmo DDA es el siguiente:

Procedimiento DDA(x1, y1, x2, y2: entero);

Variable

Dx, dy, número de pasos: entero;

X_inc, y_inc, x, y: números reales;

Comenzar

Dx:= x2 – x1; dy:= y2 – y1;

Si abs(dx) > abs(dy) entonces

Pasos:= valor absoluto(dx); {pasos mayores que dx, dy}

Otro

Paso:= valor absoluto(dy);

X_inc:= dx/pasos; y_inc:= dy/pasos;

{x_inc o y_inc = 1.0, el otro es la pendiente}

X:= x1; y:= y1;

Set_pixel(círculo(x), círculo(y));

Para i:= 1 al paso do

Comenzar

X:= x + x_inc;

Y:= y + y_inc;

Set_pixel(círculo(x), círculo(y));

Fin;

Fin; {DDA}

Ventajas del algoritmo DDA

1. El algoritmo es el más simple y no requiere habilidades especiales para implementar.

2. Es una forma más rápida de calcular la posición del píxel que usar directamente la ecuación y = mx + b. Utiliza propiedades de trama para eliminar la multiplicación de la ecuación, aplicando el incremento apropiado en la dirección x o y para encontrar la posición del píxel a lo largo de la ruta de la línea.

Desventajas del algoritmo DDA

1. El algoritmo no es tan preciso como otros métodos, especialmente cuando la pendiente es grande o si la línea es muy corta.

La operación de punto flotante en el algoritmo DDA aún requiere mucho tiempo.

El algoritmo depende de la orientación. Por lo tanto, la precisión del punto final es pobre. Veamos algunos ejemplos para ilustrar este algoritmo.

Considere la línea de (0,0) a (4,6). Rasterice esta línea usando un algoritmo DDA simple. Evaluando los pasos 1 a 5 en el algoritmo DDA que tenemos

SG=0 y 1=0

X2=4 y2=6

Longitud = |y2-Y1| = 6

∆X = |X2-X1| / longitud = 4/6

∆Y = |y2-y1| / longitud = 6/6 = 1

El valor inicial es:

X = 0 + 0,5 * signo(4) = 0,5

Y = 0 + 0,5 * signo(1) = 0,5

Tabulando los resultados de cada iteración en el paso 6 obtenemos: El resultado se representa como se muestra.

Muestra que la línea rasterizada está a ambos lados de la línea real, es decir, el algoritmo depende de la dirección.

Ejemplo 2: Considere la línea de (0, 0) a (-6, -6). Utilice el algoritmo DDA simple.

Sol. Evaluemos los pasos 1 a 5 en el algoritmo DDA que tenemos: SG = 0 y 1 = 0

X₂ = – 6 años, Y₂ = – 6, Longitud = l x₂-X₁l | Y₂-Y₁l = 6

∆X = ∆Y = -1

Valor inicial de X = 0 + 0,5 * signo (-1) = -0,5, Y = 0 + 0,5 * signo (-1) = -0,5. Tabulando los resultados de cada iteración en el paso 6 obtenemos:

Los resultados se grafican como se muestra en la figura. Muestra que la línea rasterizada está en la línea real y es una línea de 45°.