Algoritmo DDA para generación de líneas

El algoritmo de Bresenham es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo un monitor de ordenador, que determina qué pixeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

Es un algoritmo preciso para la generación de lineas de ratreo que convierte mediante rastreo las líneas al utilizar solo cálculos incrementales con enteros que se pueden adaptar para desplegar circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican columnas de pixel.

El algoritmo sería el siguiente:

Si 0<|m|<1

  *Se capturan los extremos de la línea y se almacena el extremo izquierdo en (x₀,y₀).

  *Se carga (x₀,y₀) en el bufer de estructura (se traza el primer punto)

  *Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el

    parametro de decisión p₀=2Δy-Δx.

  Para j=0 mientras j<Δx

  *En cada x_k a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente:

      Si p_k<0

          *Trazamos (x_k+1,y_k).

          *Asignamos p_k+1= p_k+2Δy.

      Sino

          *Trazamos (x_k+1,y_k+1).

          *Asignamos p_k+1= p_k+2Δy-2Δx.

  Fin Para

Si |m|>1

   *Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos   

     de x que se aproximen más a la trayectoria de la línea.

Algoritmo de Bresenham para trazar circunferencias

Una circunferencia se define como un conjunto de puntos que se encuentran, en su totalidad, a una distancia determinada r de una posicion central.

Es posible reducir el cálculo al considerar la simetría de las circunferencias, la forma de la circunferencia es similar entre cuadrantes y simetrica entre octantes.

Para aplicar el método del punto medio, definimos una función de circunferencia como:

p_k = f_{circunferencia}(x,y)= x² + y² − r²

f_{circunferencia}(x,y)<0 si (x,y) está dentro de la frontera de la circunferencia.

f_{circunferencia}(x,y)=0 si (x,y) está en la frontera de la circunferencia.

f_{circunferencia}(x,y)>0 si (x,y) está fuera de la frontera de la circunferencia.

Los parámetros de decisión sucesivos se obtienen al utilizar cálculos incrementales.

El algoritmo será el siguiente:

 *Se capturan el radio r y el centro de la circunferencia (x_c, y_c).

 *Se obtiene el primer punto de la circunferencia centrada en origen (x_c, y_c) como (0, r).

 *Se cacula el valor incial del parametro de decisión como p₀=5/4 - r.

 Para k=0 hasta x>=y incrementa k

  Si p_k < 0

       *Siguiente punto de la circunferencia con centro (0,0) es (x_k+1, y_k).

       *p_k+1=p_k+2x_k+1+1.

    Sino

        *Siguiente punto de la circunferencia con centro (0,0) es (x_k+1, y_k-1).

       *p_k+1=p_k+2x_k+1+1-2y_k+1.

    //Donde 2x_k+1=2x_k+2  y  2y_k+1=2y_k-2

 *Se determinan los puntos de simetría para los otros siete octantes.

 *Se mueve cada posición del pixel calculada (x,y) a la trayectoria circular centrada en (x_c, y_c)

   y trazamos los valores de las coordenadas: x=x+x_c y y=y+y_c.

 Fin Para

Fuentes:

http://es.wikipedia.org/wiki/Algoritmo_de_Bresenham

http://es.wikipedia.org/wiki/Algoritmo_del_Punto_Medio_para_Circunferencias