Geometría

Algoritmos geométricos

Algoritmo de Bresenham

Ejemplo de aplicación del algoritmo de Bresenham.

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 pixel.

El algoritmo sería el siguiente:

Si 0<|m|<1 almacena="" capturan="" de="" e="" el="" en="" extremo="" extremos="" izquierdo="" l="" la="" los="" nea="" se="" style="line-height: 1em;" sub="" x="" y="">0

,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 razamos="" style="line-height: 1em;" sub="" 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.

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.drawCircle( 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);
    }















Algoritmo de Bresenham

El algoritmo busca cual de dos píxeles es el que esta mas cerca según la trayectoria de la línea. Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1. Las posiciones de píxel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.




1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

2. Se traza el primer punto (x0, y0).

3. Se calculan las constantes Dy, Dx, 2Dy, 2Dy-2Dx, y se obtiene el valor inicial para el parámetro de decisión como p0 = 2 Dy - Dx.

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 Dy. De otro modo, el siguiente punto en trazarse es (xk+1, yk+1) y pk +1 = pk + 2 Dy - 2Dx.

5. Se repite el paso 4 otras Dx veces.




void LineBres(Graphics g, int x0, int y0, int x1, int y1){

  int x, y, dx, dy, xend, p, incE, incNE;

  dx = abs(x1 - x0);

  dy = abs(y1 - y0);

  p = 2*dy - dx;

  incE = 2*dy;

  incNE = 2*(dy-dx);

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

  if (x0 > x1) {

    x = x1;

    y = y1;

    xend = x0;

  }

  else {

    x = x0;

    y = y0;

    xend = x1;

  }

  g.drawLine( x0, y0, x0, y0);/* se cicla hasta llegar al extremo de la línea */

  while (x <= xend){

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

    x = x + 1;

    if (p < 0)

      p = p + incE

    else {

      y = y + 1;

      p = p + incNE;

    }

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

}



El algoritmo de Bresenham se generaliza para líneas con una pendiente arbitraria al considerar la simetría entre los diversos octantes y cuadrantes del plano de xy. Para una línea con una pendiente m > 1, intercambiamos las funciones de las direcciones de x y y, o sea, pasamos a lo largo de y en pasos unitarios y calculamos los valores sucesivos de x que se aproximan mas a la trayectoria de la línea. Asimismo, podemos revisar el programa para trazar píxeles iniciando desde cualquier extremo.




El programa resultante es el siguiente:




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( x0, y0, x0, y0);    }
  }
  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( x0, y0, x0, y0);










Algoritmo de Bresenham para trazar líneas.






Es un algoritmo creado para dibujar rectas en los dispositivos de graficos rasterizados, como por ejemplo un monitor de computadora, que determina que pixeles se rellenaran, en funcion de la inclinacion del angulo de la recta a dibujar.

Es un algoritmo preciso para la generacion de lineas de rastreo que convierte mediante rastreo las lineas al utilizar solo calculos 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 las columnas de pixel.



















Es considerado uno de los algoritmos más efectivos para dibujar líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente pixel a dibujar en la generación de una línea, se describe a continuación:

1.- Punto inicial  P1(Xinicial,Yinicial).
2.- Se desplaza una columna (incrementando la posición en X)
3.- Se traza el pixel cuyo valor de Y de la línea de rastreo se aproxima más a la trayectoria de la línea. Se capturan los dos extremos de la línea  P1(Xinicial,Yinicial) y P2(Xfinal,Yfinal)
4.- Se dibuja el primer pixel correspondiente al extremo izquierdo de la línea(P1)
5.- Se calculan los parámetros que permitien decidir cuál será el proximo pixel a dibujar (DeltaX, DeltaY y ConstanteP).
6.- Dependiendo del valor que tome el Parámetro ConstanteP se evalúa y determina la coordenada a dibujar que puede ser: 
       1.- (X+1,Y) para ConstanteP < 0
       2.- Sino (X+1,Y+1)
El proceso anterior debe repetirse 4DeltaX veces.








Algoritmo.





Leer Coordenadas P1(Xinicial, Yinicial)
Leer Coordenadas P2(Xfinal, Yfinal)
Asignar a  DeltaX el ABS( Xfinal - Xinicial)
Asignar a  DeltaY el ABS( Yfinal -Yinicial)
Asignar a ConstanteP  el resultado de 2*DeltaY - DeltaX
Si Xinicial > Xfinal
Asignar Xfinal a X
Asignar Yfinal a Y
Asignar Xinicial a Ultimo
De lo contrario
Asignar Xinicial a X
Asignar Yinicial a Y
Asignar a Xfinal a Ultimo
Iluminar pixel en coordenada X,Y
Hacer mientras X
Asignar X + 1 a X
Si ConstanteP < 0 
Asignar  ConstanteP + 2 *DeltaY a ConstanteP
De lo contrario
Asignar Y+1 a Y
Asignar a ConstanteP el resultado de ConstanteP+2 *(DeltaY-DeltaX)
Iluminar pixel en coordenada X,Y
Fin de Algoritmo (Bresenham)

Ejemplo.

#include 
#include 
#include 
#include 
void BRESENHAM      (int Bx1, int By1, int Bx2, int By2)
{
   float e,ax,ay,temp;
   int s1,s2,intercambio,i,x,y;
   x=Bx1;
   y=By1;
   ax=abs(Bx2-Bx1);
   ay=abs(By2-By1);
   s1=signo(Bx2-Bx1);
   s2=signo(By2-By1);
   if(ay>ax)
   {
      temp=ax;
      ax=ay;
      ay=temp;
      intercambio=1;
   }
   else
   {
       intercambio=0;
   }
   e=2*ay-ax;
   for(i=1;i<=ax;i++)
   {
      putpixel((319+x),(239-y),4);
      if(e>=0)
      {
         if (intercambio==1)
         {
             x=x+s1;
         }
         else
         {
             y=y+s2;
         }
            e=e-(2*ax);
      }
      if (intercambio==1)
      {
          y=y+s2;
      }
      else
      {
          x=x+s1;
      }
      e=e+2*ay;
   }
}

int signo(int num)
{
    int resultado;
    if(num<0 span="">
       resultado=-1;
   if(num>0)
       resultado=1;
   if(num==0)
       resultado=0;
   return(resultado);