Bresenham’s Line Algorithm
Bresenham’s Line algorithm determines the point of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points.
This algorithm only performs integer arithmetic and the line can be generated quickly.
Steps in Bresenham’s Line Algorithm
step 1: Input the two-line endpoints.
start coordinate = (x0, y0)
end coordinate = (xn, yn)
step2: plot the point.
Calculate ∆x and ∆y
∆x = xn-x0
∆y = yn-y0
Step3: Calculate the decision parameter. (It is used to find an exact point to draw a line)
pk = 2∆y-∆x
Step 4: suppose the current point (xk, yk), the next point (xk+1, yk+1) find the next point depending on the value of the decision parameter.
Starting at k=0, perform the following test
Case 1:
pk<0
pk+1 = pk + 2∆y
xk+1 = xk +1
yk+1 = yk
Case 2:
Pk>=0
pk+1 = pk + 2∆y — 2∆x
xk+1 = xk +1
yk+1 = yk + 1
Step 5: repeat step 4 (∆x-1) times. (That mean until endpoint reached)
Example
Let’s plot the line from (9, 18) to (14, 22)
Step1:
Start coordinate (x0, y0) = (9, 18)
End coordinate (xn, yn) = (14, 22)
Step2:
∆x = xn — x0
∆x = 14–9 = 5
∆y = yn — y0
∆y = 22–18 = 4
2∆y = 4*2 = 8
Step3:
pk = 2∆y — ∆x
pk = 8–5 = 3
Step4:
pk = 3
pk>0
pk+1 = pk + 2∆y — 2∆x
pk+1 = 3 + 8–2*5 = 1
xk+1 = xk +1 = 9 + 1 = 10
yk+1 = yk + 1 = 18 + 1 = 19
pk = 1
pk >0
pk+1 = pk + 2∆y — 2∆x
pk+1 = 1 + 8–2*5 = -1
xk+1 = xk +1 = 10 + 1 = 11
yk+1 = yk + 1 = 19 + 1 = 20
pk = -1
pk+1 = pk + 2∆y
pk = -1 + 8 = 7
xk+1 = xk +1 = 11+1 = 12
yk+1 = yk = 20
Like this find pk and repeat step4 (∆x-1) times.
Then draw a Line
Advantages
- A fast incremental algorithm (compared to DDA).
- use only integer calculations.
- can be implemented using hardware. (Because it does not use multiplication and division)
So guys this is Bresenham’s Line Drawing Algorithm. Try out the example. Hope you guys enjoy that article and get knowledge. Thank you for reading my article.