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₁, y₁) and (x₂, y₂)
2. Calculate constants:
Δx=x₂ – x₁
Δy=y₂ – y₁
2Δy
2Δy-Δx
3. Assign the value to the starting parameter :
k=0
P₀=2Δy-Δx
4. Plot the pixel at (x₁, y₁)
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.