Bresenham decision parameter, |m| > 1

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

Let Δx = x1 − x0 and |Δy| = y0 − y1, with |Δy| > Δx. The line is y = m·x + b, or x = (y − b)/m, with m = −|Δy|/Δx.

Pixel choice

After plotting (x_k, y_k), the next row is y_k − 1. The candidates are x_k and x_k + 1. The true x at this row is x = (y_k − 1 − b)/m.

d1 = x − x_k           (distance to left pixel)
d2 = (x_k + 1) − x     (distance to right pixel)
d1 − d2 = 2x − 2x_k − 1 = 2(y_k − 1 − b)/m − 2x_k − 1

Since 1/m = −Δx/|Δy|, multiplying by |Δy| (positive) gives the decision parameter:

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

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

Recursive form

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

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

Initial value

At (x0, y0) b = y0 − m·x0 = y0 + (|Δy|/Δx)x0, so −2Δx(y0 − 1 − b) = 2Δx + 2|Δy|x0. Then

p_0 = 2Δx + 2|Δy|x0 − 2|Δy|x0 − |Δy| = 2Δx − |Δy|

Algorithm

Plot (x0, y0); p = 2Δx − |Δy|
Repeat |Δy| times:
    y = y − 1
    if p < 0:  p = p + 2Δx
    else:      x = x + 1;  p = p + 2Δx − 2|Δy|
    plot (x, y)