Skip to main content

Bresenham: line (25,20) to (15,10)

Short answer

Start at left point (15,10). dx=10, dy=10, p0=2*10−10=10. Since p remains ≥0, both x and y increment each step. Pixels: (15,10), (16,11), (17,12), (18,13), (19,14), (20,15), (21,16), (22,17), (23,18), (24,19), (25,20).

Explain the Bresenham line drawing algorithm and use this algorithm to draw a line with end points (25,20) and (15,10).

Bresenham's line algorithm

It draws a line using only integer arithmetic. For 0 < m < 1 with the left end point as start:

1. dx = x2 − x1, dy = y2 − y1; plot (x1, y1).
2. p0 = 2dy − dx.
3. For each step, x = x + 1:
     if p < 0: y same;  p = p + 2dy
     else:     y = y + 1; p = p + 2dy − 2dx
     plot (x, y)

For m = 1 the same steps are used; for steeper lines the roles of x and y are interchanged.

Numerical

The end points are (25,20) and (15,10). The line is drawn from left to right, so start at the left point (15,10) and end at (25,20) (the pixel set is the same).

dx = 25 − 15 = 10,  dy = 20 − 10 = 10,  slope m = 1
2dy = 20,  2dy − 2dx = 0
p0 = 2dy − dx = 20 − 10 = 10
kp_k(x_k, y_k)Next
010(15,10)p ≥ 0: (x+1, y+1), p = p + 0
110(16,11)p ≥ 0: (x+1, y+1), p = p + 0
210(17,12)p ≥ 0: (x+1, y+1), p = p + 0
310(18,13)p ≥ 0: (x+1, y+1), p = p + 0
410(19,14)p ≥ 0: (x+1, y+1), p = p + 0
510(20,15)p ≥ 0: (x+1, y+1), p = p + 0
610(21,16)p ≥ 0: (x+1, y+1), p = p + 0
710(22,17)p ≥ 0: (x+1, y+1), p = p + 0
810(23,18)p ≥ 0: (x+1, y+1), p = p + 0
910(24,19)p ≥ 0: (x+1, y+1), p = p + 0
1010(25,20)-

Since p stays 10 (positive), y is increased every time.

Answer: (15,10), (16,11), (17,12), (18,13), (19,14), (20,15), (21,16), (22,17), (23,18), (24,19), (25,20).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Graphics chapter 2 questions →