Generacion de lineas rectas

Definición de líneas

Una línea es una sucesión continua de puntos (trazado), como por ejemplo un trazo o un guion. Las líneas suelen utilizarse en la composición artística, se denomina en cambio «raya» a trazos rectos sueltos, que no forman una figura o forma en particular. En matemáticas y geometría, línea suele denotar línea recta o curva.

Algoritmo DDA para generación de rectas

El Algoritmo DDA es un algoritmo de línea de conversión de rastreo que se basa en el cálculo ya sea en el incremento de X o en el incremento de Y. La finalidad de este algoritmo es determinar los valores enteros correspondientes más próximos a la trayectoria de la línea para la otra coordenada.

El Codigo es el Siguiente :

void DDA(int x_0,int y_0, int x_fin, int y_fin){

glClear ( GL_COLOR_BUFFER_BIT );
glPointSize(3.0);
glScalef(4.0, 4.0, 2.0);

glBegin(GL_POINTS);
glVertex2i(x_0,y_0);

int vx=(int)fabs(x_fin-x_0);
int vy=(int)fabs(y_fin-y_0);
int dx,dy;
int m = (int)(y_fin-y_0)/(x_fin-x_0);

if(m==1)m++;
if(m==0)m=-1;

if(m>0&&m<1){
if(x_0<x_fin){
dx=1;
dy=m;
}else{
dx=-1;
dy=-m;
}
}
else
if(m>0&&m>1){
if(m>1){
if(x_0<x_fin){
dy=1;
dx=(int)1/m;

}else{
dy=-1;
dx=(int)-1/m;

}

}else

if(m<0&&fabs(m)<1){

if(x_0>x_fin)
{
dx=-1;
dy=-m;

}else
{
dx=1;
dy=-m;
}

}

else{

if(x_0>x_fin){
dy=1;
dx=-1/m;

}
else {
dy=-1;
dx=1/m;

}

}

if(m>0&&m<1){
for(int i=1;i<=vx;i++)
{
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;

}
}
else
if(m>0&&m>1){
for(int i=1;i<=vy;i++){
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;}

}else

if(m<0&&fabs(m)<1){

for(int i=1;i<=vx;i++)
{
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;

}

}

else{

for(int i=1;i<=vy;i++){
glVertex2i(x_0+dx ,y_0+dy );
x_0+=dx;
y_0+=dy;
}
}
}
glEnd();
glFlush();
}

Algoritmo de Bresenham para trazar líneas

Es un algoritmo preciso para la generación de líneas de rastreo 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 pixeles.

 Algoritmo

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.

 

Implementación

Esta es la implementación del algoritmo:

 public void Bresenham(Graphics g,int x0, int y0, int x1, int y1)

{ int x, y, dx, dy, p, incE, incNE, stepx, stepy;

  dx = (x1 - x0);

  dy = (y1 - y0);

 /* determinar que punto usar para empezar, cual para terminar */

  if (dy < 0) { 

    dy = -dy; stepy = -1; 

  } 

  else

    stepy = 1;

  if (dx < 0) {  

    dx = -dx; stepx = -1; 

  } 

  else 

    stepx = 1;

  x = x0;

  y = y0;

  g.drawLine( x0, y0, x0, y0);

 /* se cicla hasta llegar al extremo de la línea */

  if(dx>dy){

    p = 2*dy - dx;

    incE = 2*dy;

    incNE = 2*(dy-dx);

    while (x != x1){

      x = x + stepx;

      if (p < 0){

        p = p + incE;

      }

      else {

        y = y + stepy;

        p = p + incNE;

      }

      g.drawLine( x, y, x, y);

    }

  }

  else{

    p = 2*dx - dy;

    incE = 2*dx;

    incNE = 2*(dx-dy);

    while (y != y1){

      y = y + stepy;

      if (p < 0){

        p = p + incE;

      }

      else {

        x = x + stepx;

        p = p + incNE;

      }

      g.drawLine( x, y, x, y);

    }

  }

 }

 Definicion de circunferencia

Se conoce como circunferencia a la linea cerrada de formato curvo y apariencia plana en la cual los puntos resultan equidistantes del punto central que se localiza en el mismo plano.

 

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 posición 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 simétrica 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