Bresenham’s Line Drawing Algorithm
1. Input line endpoints, (x1, y1) and (x2, y2)
2. Calculate constants:
∆x = x2 – x1
∆y = y2 – y1
2∆y
2∆y – ∆x
3. Assign value to the starting parameters:
k=0
P0 = 2∆y – ∆x
4. Plot the pixel at (x1, y1)
5. For each integer x-coordinate, xk, along the line
if Pk < 0 plot pixel at (xk + 1, yk)
Pk+1 = Pk + 2∆y (note that 2∆y is a pre-computed constant)
else plot pixel at (xk + 1, yk + 1)
Pk+1 = Pk + 2∆y – 2∆x (note that 2∆y – 2∆x is a pre-computed constant)
increment k
while xk < x2
Problem
A line has a starting point (20, 10) and ending point (30, 18). Apply the Bresenham’s Line Drawing
algorithm to plot a line.
Solution
We have two coordinates,
Starting Point = (x1, y1) = (20, 10)
Ending Point = (x2, y2) = (30, 18)
First, we calculate ∆x, ∆y, 2∆y and 2∆y – ∆x
∆x = x2 – x1 = 30 – 20 = 10
∆y = y2 – y1 =18 – 10 = 8
2∆y = 2 x 8 = 16
2∆y – ∆x = (2 x 8) – 10 = 16 – 10 = 6
Now, we are going to calculate the decision parameter at k = 0
P0 = 2∆y – ∆x = 16 – 10 = 6
Pk Pk+1 xk+1 yk+1
20 10
Pk+1 = Pk + 2∆y – 2∆x
6 21 11
= 6 + 16 – 20 = 2
Pk+1 = Pk + 2∆y – 2∆x
2 22 12
= 2 + 16 – 20 = -2
Pk+1 = Pk + 2∆y
-2 23 12
= -2 + 16 = 14
Pk+1 = Pk + 2∆y – 2∆x
14 24 13
= 14 + 16 – 20 = 10
Pk+1 = Pk + 2∆y – 2∆x
10 25 14
= 10 + 16 – 20 = 6
Pk+1 = Pk + 2∆y – 2∆x
6 26 15
= 6 + 16 – 20 = 2
Pk+1 = Pk + 2∆y – 2∆x
2 27 16
= 2 + 16 – 20 = -2
Pk+1 = Pk + 2∆y
-2 28 16
= -2 + 16 = 14
Pk+1 = Pk + 2∆y – 2∆x
14 29 17
= 14 + 16 – 20 = 10
Pk+1 = Pk + 2∆y – 2∆x
10 30 18
= 10 + 16 – 20 = 6
