Write Bresenham's line algorithm

Bresenham's line algorithm draws a line between (x1, y1) and (x2, y2) using only integer arithmetic. At each step the pixel closest to the true line is chosen using a decision parameter.

Algorithm for 0 < m < 1 (x1 < x2)

1. Input end points (x1, y1) and (x2, y2).
2. dx = x2 − x1,  dy = y2 − y1.
3. Plot the first point (x1, y1). x = x1, y = y1.
4. p0 = 2·dy − dx
5. For each x from x1 to x2 − 1:
      if p < 0:
          x = x + 1;  plot (x, y);   p = p + 2·dy
      else:
          x = x + 1;  y = y + 1;  plot (x, y);   p = p + 2·dy − 2·dx
6. Stop.

Derivation of the parameter

For the next x_k+1, the candidates are y_k and y_k+1. With d1 and d2 the distances of the true y from them, the decision parameter is p_k = dx(d1 − d2) = 2·dy·x_k − 2·dx·y_k + c. If p_k < 0 the lower pixel y_k is closer, else y_k+1 is closer. Successive values: p_k+1 = p_k + 2dy (y same) or p_k + 2dy − 2dx (y+1), and p_0 = 2dy − dx.

Program in C

void bresenham(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1;
    int p = 2*dy - dx;
    int x = x1, y = y1;
    putpixel(x, y, WHITE);
    while (x < x2) {
        x++;
        if (p < 0) {
            p += 2*dy;
        } else {
            y++;
            p += 2*dy - 2*dx;
        }
        putpixel(x, y, WHITE);
    }
}

For other slopes the same idea is used by swapping the roles of x and y (m > 1), and changing the sign of the y-step (negative slope).