# Bresenham’s Line Algorithm

__Bresenham’s Line Algorithm:__

Bresenham’s Line Algorithm was developed by **Bresenham**. It is more accurate and efficient compared to the DDA algorithm because it cleverly avoids the “Round” function and it scans and converts lines using only incremental integer calculation.

This algorithm samples a line by incrementing by one unit either x or y depending on the slope of the line and then selects the pixel lying at least a distance from the true line path at each sampling position.

To illustrate Bresenham’s approach, let us consider a line (L) with a positive slope of less than 1. So, the line will be sampled at unit intervals in the X-direction. Assuming we have already determined that the pixel at (x_{k}, y_{k}) is to be displayed, we next need to decide which pixel to plot at the next sampling position at x_{k}+1 grid line.

1. Input two line endpoints (x

_{1}, y_{1}) and (x_{2}, y_{2})

2. Calculate constants:

Δx=x_{2}– x_{1}

Δy=y_{2}– y_{1}

2Δy

2Δy-Δx

3. Assign the value to the starting parameter :

k=0

P_{0}=2Δy-Δx

4. Plot the pixel at (x_{1}, y_{1})

5. For each integer X Co-ordinate, X_{k}along the line.

if P_{k}<0, the next point to plot is (x_{k}+1, y_{k})

P_{k+1}=P_{k}+2Δy

else

the next point to plot is (x_{k}+1, y_{k}+1)

P_{k+1}=P_{k}+2Δy-2Δx

6. Repeat Step 5 Δx lines.