Algorithme de Bresenham

Cette page présente simplement l'algorithme de Bresenham pour Processing. Pour la description précise de cet algorithme allez sur l'Article de Wikipédia.

static final int taille = 20;

void setup() {
  size(800, 800);
  fill(0);
}

void draw() {
  background(255);
  for (int i = 0; i < width; i += taille) {
    line(0, i, width, i);
    line(i, 0, i, height);
  }
  tracerSegment(width / (2 * taille), height / (2 * taille), (int)mouseX / taille, (int)mouseY / taille);
}

void tracerPixel(int x, int y) {
  rect(x * taille, y * taille, taille, taille);
}

void tracerSegment(int x1, int y1, int x2, int y2) {
  int dx, dy;
  dx = x2 - x1;
  if (dx != 0) {
    if (dx > 0) {
      dy = y2 - y1;
      if (dy!= 0) {
        if (dy > 0) {
          // vecteur oblique dans le 1er quadran

          if (dx >= dy) {
            // vecteur diagonal ou oblique proche de l’horizontale, dans le 1er octant
            int e = dx;
            dx = e * 2 ;
            dy = dy * 2 ;  // e est positif
            while (x1 < x2) {
              tracerPixel(x1, y1) ;
              x1++;
              e -= dy;
              if (e <= 0) {
                y1++ ;  // déplacement diagonal
                e += dx ;
              }
            }
          } 
          else {
            // vecteur oblique proche de la verticale, dans le 2nd octant
            int e = dy;
            dy = e * 2;
            dx = dx * 2 ;  // e est positif
            while (y1 < y2) {  // déplacements verticaux
              tracerPixel(x1, y1) ;
              y1++;
              e -= dx;
              if (e <= 0) {
                x1++;  // déplacement diagonal
                e += dy ;
              }
            }
          }
        } 
        else { // dy < 0 (et dx > 0)
          // vecteur oblique dans le 4e cadran

          if (dx >= -dy) {
            // vecteur diagonal ou oblique proche de l’horizontale, dans le 8e octant
            int e = dx;
            dx *= 2 ;
            dy *= 2 ;  // e est positif
            while (x1 < x2) {  // déplacements horizontaux
              tracerPixel(x1, y1) ;
              x1++;
              e += dy;
              if (e <= 0) {
                y1 -= 1 ;  // déplacement diagonal
                e += dx ;
              }
            }
          } 
          else {  // vecteur oblique proche de la verticale, dans le 7e octant
            int e = dy;
            dy *= 2;
            dx *= 2;  // e est négatif
            while (y2 < y1) {  // déplacements verticaux
              tracerPixel(x1, y1);
              y1--;
              e += dx;
              if (e > 0) {
                x1++ ;  // déplacement diagonal
                e += dy;
              }
            }
          }
        }
      } 
      else {  // dy = 0 (et dx > 0)

        // vecteur horizontal vers la droite
        while (x1 < x2) {
          tracerPixel(x1, y1) ;
          x1++;
        }
      }
    } 
    else {  // dx < 0
      dy = y2 - y1;
      if (dy != 0) {
        if (dy > 0) {
          // vecteur oblique dans le 2nd quadran

          if (-dx >= dy) {
            // vecteur diagonal ou oblique proche de l’horizontale, dans le 4e octant
            int e = dx;
            dx *= 2 ;
            dy *= 2 ;  // e est négatif
            while (x1 > x2) {  // déplacements horizontaux
              tracerPixel(x1, y1) ;
              x1--;
              e += dy;
              if (e >= 0) {
                y1++;  // déplacement diagonal
                e +=dx ;
              }
            }
          } 
          else {
            // vecteur oblique proche de la verticale, dans le 3e octant
            int e = dy;
            dy *= 2 ;
            dx *= 2 ;  // e est positif
            while (y1 < y2) {  // déplacements verticaux
              tracerPixel(x1, y1) ;
              y1++;
              e += dx;
              if (e <= 0) {
                x1--;  // déplacement diagonal
                e += dy ;
              }
            }
          }
        } 
        else {  // dy < 0 (et dx < 0)
          // vecteur oblique dans le 3e cadran

          if (dx <= dy) {
            // vecteur diagonal ou oblique proche de l’horizontale, dans le 5e octant
            int e = dx;
            dx *= 2 ;
            dy *= 2 ;  // e est négatif
            while (x1 > x2) {  // déplacements horizontaux
              tracerPixel(x1, y1) ;
              x1--;
              e -= dy;
              if (e >= 0) {
                y1--;  // déplacement diagonal
                e += dx ;
              }
            }
          } 
          else {  // vecteur oblique proche de la verticale, dans le 6e octant
            int e = dy;
            dy *= 2 ;
            dx *= 2 ;  // e est négatif
            while (y1 > y2) {  // déplacements verticaux
              tracerPixel(x1, y1) ;
              y1--;
              e -= dx;
              if (e >= 0) {
                x1--;  // déplacement diagonal
                e += dy ;
              }
            }
          }
        }
      } 
      else {  // dy = 0 (et dx < 0)

        // vecteur horizontal vers la gauche
        while (x1 > x2) {
          tracerPixel(x1, y1) ;
          x1--;
        }
      }
    }
  } 
  else {  // dx = 0
    dy = y2 - y1;
    if (dy != 0) {
      if (dy > 0) {

        // vecteur vertical croissant
        while (y1 < y2) {
          tracerPixel(x1, y1) ;
          y1++;
        }
      } 
      else {  // dy < 0 (et dx = 0)

        // vecteur vertical décroissant
        while (y1 > y2) {
          tracerPixel(x1, y1) ;
          y1--;
        }
      }
    }
  }
  tracerPixel(x2, y2);// n’est pas tracé.
}