Skip to main content

Bresenham: line (20,10) to (30,18)

Short answer

dx=10, dy=8, p0=6. If p<0 y unchanged and p+=16; else y incremented and p-=4. Pixels: (20,10), (21,11), (22,12), (23,12), (24,13), (25,14), (26,15), (27,16), (28,16), (29,17), (30,18).

Digitize the line with end points A(20,10) and B(30,18) using Bresenham's algorithm.

Given: A(20,10), B(30,18). Slope is 0 < m = 8/10 < 1, so x is incremented by 1 at each step.

dx = 30 − 20 = 10,   dy = 18 − 10 = 8
2dy = 16,   2dy − 2dx = 16 − 20 = −4
p0 = 2dy − dx = 16 − 10 = 6

Rule: if p_k < 0: next point (x+1, y), p_k+1 = p_k + 2dy = p_k + 16. If p_k ≥ 0: next point (x+1, y+1), p_k+1 = p_k + 2dy − 2dx = p_k − 4.

kp_k(x_k, y_k)Next pointp_k+1
06(20,10)(21,11)2
12(21,11)(22,12)-2
2-2(22,12)(23,12)14
314(23,12)(24,13)10
410(24,13)(25,14)6
56(25,14)(26,15)2
62(26,15)(27,16)-2
7-2(27,16)(28,16)14
814(28,16)(29,17)10
910(29,17)(30,18)6
106(30,18)--

Pixels plotted:

(20,10) (21,11) (22,12) (23,12) (24,13) (25,14)
(26,15) (27,16) (28,16) (29,17) (30,18)

Answer: the 11 pixels above, from (20,10) to (30,18).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Graphics chapter 2 questions →