Bresenham decision parameter, negative slope

Case: line from (x0, y0) to (x1, y1), x0 < x1, slope m = Δy/Δx with −1 < m < 0, so x increases by 1 each step and y either stays or decreases by 1.

Let Δx = x1 − x0 > 0 and |Δy| = y0 − y1 > 0. The line equation is y = m·x + b.

Pixel choice

Having plotted (x_k, y_k), the next column is x_k+1. The two candidate pixels are y_k and y_k − 1. The true y at x_k+1 is

y = m(x_k + 1) + b
d1 = y_k − y            (distance to upper pixel y_k)
d2 = y − (y_k − 1)      (distance to lower pixel y_k − 1)
d1 − d2 = 2y_k − 2y − 1
        = 2y_k − 2m(x_k + 1) − 2b − 1

Decision parameter

Multiply by Δx (positive, so the sign is unchanged) and use m = −|Δy|/Δx:

p_k = Δx (d1 − d2)
    = 2Δx·y_k + 2|Δy|(x_k + 1) − 2b·Δx − Δx
    = 2Δx·y_k + 2|Δy|·x_k + c      where c = 2|Δy| − 2bΔx − Δx

• If p_k < 0 then d1 < d2, the upper pixel is nearer: next point (x_k+1, y_k).
• If p_k ≥ 0 then d1 ≥ d2, the lower pixel is nearer: next point (x_k+1, y_k − 1).

Recursive form

p_k+1 − p_k = 2|Δy|(x_k+1 − x_k) + 2Δx(y_k+1 − y_k) = 2|Δy| + 2Δx(y_k+1 − y_k)

• If y_k+1 = y_k: p_k+1 = p_k + 2|Δy|
• If y_k+1 = y_k − 1: p_k+1 = p_k + 2|Δy| − 2Δx

Initial value

At (x0, y0), y0 = m·x0 + b, so 2Δx(y0 − b) = 2Δx·m·x0 = −2|Δy|·x0. Substituting in p_0:

p_0 = 2|Δy| − Δx

Algorithm

1. Plot (x0, y0). p = 2|Δy| − Δx.
2. For x = x0 to x1 − 1:
      if p < 0:  plot (x+1, y);        p = p + 2|Δy|
      else:      y = y − 1; plot (x+1, y);  p = p + 2|Δy| − 2Δx