Derive the expression for Bresenham's Line Drawing algorithm. Trace the points in the line path with starting point (6, 12) and end point (10, 5) using Bresenham's line drawing algorithm.

Derivation (for 0 < m < 1)

For a line from (x₀, y₀) to (x₁, y₁), let Δx = x₁ − x₀ and Δy = y₁ − y₀. We step x by 1 each time and choose between the pixels (xₖ + 1, yₖ) and (xₖ + 1, yₖ + 1).

At x = xₖ + 1 the true line has y = m(xₖ + 1) + b. The distances from it to the two candidate pixels are:

• d₁ = y − yₖ = m(xₖ + 1) + b − yₖ
• d₂ = (yₖ + 1) − y = yₖ + 1 − m(xₖ + 1) − b

d₁ − d₂ = 2m(xₖ + 1) − 2yₖ + 2b − 1

Multiply by Δx (positive), with m = Δy/Δx, to remove fractions. This gives the decision parameter

pₖ = Δx(d₁ − d₂) = 2Δy·xₖ − 2Δx·yₖ + c, where c is a constant.

• If pₖ < 0, the lower pixel is closer: plot (xₖ + 1, yₖ).
• If pₖ ≥ 0, plot (xₖ + 1, yₖ + 1).

Subtracting pₖ from pₖ₊₁ gives pₖ₊₁ = pₖ + 2Δy − 2Δx(yₖ₊₁ − yₖ):

• if pₖ < 0: pₖ₊₁ = pₖ + 2Δy
• if pₖ ≥ 0: pₖ₊₁ = pₖ + 2Δy − 2Δx

The first value is p₀ = 2Δy − Δx. Only integer additions are needed.

Trace: (6, 12) to (10, 5)

Δx = 10 − 6 = 4 and Δy = 5 − 12 = −7, so |m| = 7/4 > 1 and y decreases. For a steep line we swap the roles of x and y: y steps by −1 each time, and x increases by 1 only when the decision parameter says so.

• p₀ = 2|Δx| − |Δy| = 8 − 7 = 1
• If p < 0: x stays the same and p = p + 2|Δx| = p + 8
• If p ≥ 0: x = x + 1 and p = p + 2|Δx| − 2|Δy| = p − 6

Plotted points: (6, 12), (7, 11), (7, 10), (8, 9), (8, 8), (9, 7), (9, 6), (10, 5). The last point is the given end point, which confirms the trace.