Algoritmo Bersenham y Algoritmo DDA

Algoritmo Bersenham:

Un algoritmo preciso y efectivo para la generación de líneas de rastreo, desarrollado por Bresenham, convierte mediante rastreo las líneas al utilizar sólo cálculos incrementales con enteros que se pueden adoptar para desplegar circunferencias y otras curvas. El algoritmo de línea de Bresenham se basa en probar el signo de un parámetro entero, cuyo valor es proporcional a la diferencia entre las separaciones de las dos posiciones de pixel de la trayectoria real de la línea. Para realizar el trazo de línea de Bresenham para una línea con una pendiente positiva menor que 1 se deben seguir los siguientes pasos: 1.Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0 , y0). 2.Se carga (x0 , y0)en el búfer de estructura; es decir, se traza el primer punto. 3.Se calculan las constantes Δx , Δy, 2Δy y 2Δy-2Δx y se obtiene el valor inicial para el parámetro de decisión como p0 = 2Δy - Δx. 4.En cada xk,a lo largo de la línea, que inicia en k=0, se efectúa la prueba siguiente: si pk <0, el siguiente punto que se debe trazar es (xk +1, yk) y  pk +1 = pk + 2Δy. De otro modo, el siguiente punto que se debe trazar es (xk +1, yk+1) y pk +1 = pk + 2Δy - 2Δx 5.Se repite el paso 4 Δx veces. Algoritmo DDA: El analizador diferencial digital (DDA; digital differential analyzer) es un algoritmo de línea de conversión de rastreo que se basa en el cálculo ya sea de Δy, o de Δx, por medio de las siguientes ecuaciones: Δy = m Δx Δx = Δy/m Se efectúa un muestreo de la línea e intervalos unitarios en una coordenada y se determinan los valores enteros correspondientes más próximos a la trayectoria de la línea para la otra coordenada. Se debe considerar primero una línea con pendiente positiva. Si la pendiente es menor o igual que 1, se lleva a cabo un muestreo de x intervalos unitarios (Δx = 1) y se calcula cada valor sucesivo de y como   yk+1 = yk + m. El subíndice k toma valores enteros a partir de 1 y aumenta a razón de 1 hasta que se alcance 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 las líneas con una pendiente positiva mayor que 1, se revierten la funciones de x yde y. Es decir, se realiza un muestreo de y en intervalos unitarios (Δy = 1 ) y se calcula cada valor sucesivo de x como xk+1 = xk + 1/m. Las ecuaciones anteriores 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 se tiene ya sea Δx = -1 y yk+1 = yk - m o ( cuando la pendiente es mayor que 1 ) Δy - 1 con xk+1 = xk - 1/m