The Bresenham algorithm is another incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at each step choose between two different y coordinates.
For example, as shown in the following illustration, from position (2, 3) you need to choose between (3, 3) and (3, 4). You would like the point that is closer to the original line.
At sample positionthe vertical separations from the mathematical line are labelled as and .
From the above illustration, the y coordinate on the mathematical line atis −
Y = m(+1) + b
So,and are given as follows −
You can use these to make a simple decision about which pixel is closer to the mathematical line. This simple decision is based on the difference between the two pixel positions.
Let us substitute m with dy/dx where dx and dy are the differences between the end-points.
So, a decision parameterfor the kth step along a line is given by −
The sign of the decision parameteris the same as that of .
Ifis negative, then choose the lower pixel, otherwise choose the upper pixel.
Remember, the coordinate changes occur along the x axis in unit steps, so you can do everything with integer calculations. At step k+1, the decision parameter is given as −
Subtractingfrom this we get −
But,is the same as . So −
Where,is either 0 or 1 depending on the sign of .
The first decision parameteris evaluated at is given as −
Now, keeping in mind all the above points and calculations, here is the Bresenham algorithm for slope m < 1 −
Step 1 − Input the two end-points of line, storing the left end-point in.
Step 2 − Plot the point.
Step 3 − Calculate the constants dx, dy, 2dy, and (2dy – 2dx) and get the first value for the decision parameter as −
Step 4 − At eachalong the line, starting at k = 0, perform the following test −
If< 0, the next point to plot is and
Step 5 − Repeat step 4 (dx – 1) times.
For m > 1, find out whether you need to increment x while incrementing y each time.
After solving, the equation for decision parameterwill be very similar, just the x and y in the equation gets interchanged.
know more at : https://www.tutorialspoint.com