HOW TO IMPLEMENT BRESENHAM’S LINE DRAWING ALGORITHM ?

Bresenham’s line drawing algorithm is an accurate and efficient raster line generating algorithm, where only integer calculation is eliminated so fast calculation can be extended to display circles, ellipses and other curves too.
First of all the two end point of a line is taken and slope (m) is calculated. The slope can either be greater than 1 or lesser than 1 (i.e. |m|>1 or |m|<1).
The initial decision parameter which is used to obtain the next point of the line is given by:

                P_k=2∆y-∆x
If the initial decision parameter P_0<0 then next point of choose (i.e. (x_(k+1),y_(k+1))) will be:
x_(k+1)=x_k+1
               y_(k+1)=y_k
And the decision parameter P_(k+1) will be:
P_(k+1)=P_k+2∆y
Else the initial decision parameter P_0>0 then next point of choose (i.e. (x_(k+1),y_(k+1))) will be:
x_(k+1)=x_k+1
              y_(k+1)=y_k+1
And the decision parameter P_(k+1) will be:
P_(k+1)=P_k+2∆y-2∆x

Algorithm:

When |m|>1

Step 1: Read two end points of line (x_1,y_1) and (x_2,y_2)
Step 2: Plot the first point (x_1,y_1)
Step 3: Calculate:
delx=|x_2-x_1 |
dely=|x_2-y_1 |
Initial decision parameter, P_0=2*delx-dely
Step 4: For i= 0 to dely in step 1
If P_0<0, then y_1=y_1+1
Plot (x_1,y_1)
P_0=P_0+2*delx
Else,
x_1=x_1+1
y_1=y_1+1
Plot (x_1,y_1)
P_0=P_0+2*delx – 2*dely
End if
End For
Step 5: End

When |m|<1

Step 1: Read two end points of line (x_1,y_1) and (x_2,y_2)
Step 2: Plot the first point (x_1,y_1)
Step 3: Calculate:
delx=|x_2-x_1 |
dely=|x_2-y_1 |
Initial decision parameter, P_0=2*delx-dely
Step 4: For i= 0 to dely in step 1
If P_0<0, then x_1=x_1+1
Plot (x_1,y_1)
P_0=P_0+2*dely
Else,
x_1=x_1+1
y_1=y_1+1
Plot (x_1,y_1)
P_0=P_0+2*dely – 2*delx
End if
End For
Step 5: End

C++ computer program:

#include <math.h>
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int main(void)
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
initgraph(&gdriver, &gmode, “c:\\turboc3\\bgi”);
int p, i, x1, y1, x2, y2, delx, dely;
printf(“Enter the starting point (x1,y1): \n”);
scanf(“%f%f”,&x1,&y1);
printf(“Enter the end point (x2,y2): \n”);
scanf(“%f%f”,&x2,&y2);
delx = fabs(x2-x1);
dely = fabs(y2-y1);
if(delx>dely)
{
p = (2*dely)- delx;
for(i=0;i<delx;i++)
{
if(p<0)
{
x1++;
putpixel(x1,y1,WHITE);
p += 2*dely;
}
else
{
x1++;
y1++;
putpixel(x1,y1,WHITE);
p=p + (2*dely) – (2*delx);
}
}
}
else
{
p = (2*delx)- dely;
for(i=0;i<delx;i++)
{
if(p<0)
{
y1++;
putpixel(x1,y1,WHITE);
p += 2*delx;
}
else
{
x1++;
y1++;
putpixel(x1,y1,WHITE);
p=p + (2*delx) – (2*dely);
}
}
}
/* read result of initialization */
errorcode = graphresult();
/* clean up */
getch();
closegraph();
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: