Bresenham Line Drawing Algorithm

What is Bresenham Line Drawing Algorithm?

The Bresenham line drawing algorithm determines the points of the N-dimensional raster selected to generate the close approximation to the straight line between the two coordinates or points. In the Bresenham line drawing algorithm, the integer is only for addition, subtraction, and multiplication.

The operation in the Bresenham line drawing algorithm is performed quickly so the line can be generated quickly. Suppose the line equation is y = mx + c. If the slope(m) value is 1, both the coordinate incremented, but if the slope value is less than 1, then the y coordinate may or may not be incremented. The Bresenham line drawing algorithm is used where the slope value is not equal to one.

Download Formulas for GATE Computer Science Engineering - Discrete Mathematics

Bresenham Line Drawing Algorithm Derivation

The Bresenham line drawing algorithm takes four integer values that are x₁, y₁, x₂, and y₂. The Bresenham line drawing algorithm given below is for the slope value less than one that is as follows:

Algorithm_bresenham(x₁, y₁, x₂, y₂)

{

x= x₁;

y=y₁;

dx = x₂ – x₂;

dy = y₂ – y₁;

p = 2dx = dy;

while(x <= x₂)

{

putpixel(x,y);

x++;

if(p<0)

p=p+2dx;

else

p=p + 2dy – 2dx;

y++;

}

}

Need of Bresenham Line Drawing Algorithm

The Bresenham line drawing algorithm is needed to overcome the problem of floating points in the DDA (Digital Differential Analyzer) that is for the DDA algorithms, the equations are:

• For X-axis Δx = x₂ – x₁
• For Y-axis Δy = y₂ – y₁

Step = max(Δx, Δy)

X_inc = Δx/step

Y_inc = Δy/step

As in the above equation, the division operation is used, which returns the float value. The float takes more time for addition, subtraction, and multiplication than an integer. Therefore, the Bresenham line drawing algorithm is used to overcome the floating-point problem.

Advantages of the Bresenham Line Drawing Algorithm

The advantage of the Bresenham line drawing Algorithm is that the Bresenham line drawing algorithm is easy to implement. It is very fast to execute but less than the DDA(Digital Differential Analyzer) algorithm and incremental.

The points generated by the Bresenham line drawing algorithm are more correct or accurate than DDA(Digital Differential Analyzer) Algorithm. The Bresenham line drawing algorithm uses fixed points or coordinates only.

Download Formulas for GATE Computer Science Engineering - Algorithms

How is the Decision Parameter Calculated in the Bresenham Line Drawing Algorithm?

The decision parameter calculated in the Bresenham line drawing algorithm for slope |m|>1 is as follows:

1. Input two endpoints or coordinates of the line (x₁,y₁) and (x₂,y₂).

2. The first point (x₁,y₁) is plotted on the graph or screen.

3. Now calculate the difference in X and Y coordinates, that is: dx =|x₂ – x₁| dy = |y₂ – y₁ |

4. The initial decision parameter will be calculated as aa:  p = 2*dx – dy.

5. For I = 0 to dy in step 1.

If p < 0 then

the Y coordinate incremented as y₁ = y₁ + 1 and then plot(x₁,y₁).

Calculate new decision parameter as p = p + 2dx.

Else

the X coordinate incremented as x₁ = x₁ + 1

the Y coordinate incremented as y₁ = y₁ + 1

and then plot(x₁, y₁)

Calculate new decision parameter as p = p + 2dx – 2*dy

6. END