BRESENHAM'S LINE DRAWING ALGORITHM

                               Bresenham’s drawing Algorithm is employed for scan converting a line. it absolutely was created by Bresenham. it's a well-structured method because it involves only integer addition, subtractions, and multiplication operations. These operations may be executed very quickly. So lines may be generated rapidly.

In this manner, the following pixel selected is that the one with the bottom distance from the particular line.

The method works as follows:

Once a pixel in choose at any step
The next pixel is
1. Either the one to its right (lower-bound for the line)
2. One top its right and up (upper-bound for the line)

The Algorithm as follows:

Step1: Start Algorithm

Step2: Declare variable x1,x2,y1,y2,d,i1,i2,dx,dy

Step3: Enter value of x1,y1,x2,y2
                Where x1,y1are coordinates of start line
                And x2,y2 are coordinates of Ending point

Step4: Calculate dx = x2-x1
                Calculate dy = y2-y1
                Calculate i1=2*dy
                Calculate i2=2*(dy-dx)
                Calculate d=i1-dx

Step5: Consider (x, y) as start line and xendas maximum possible value of x.
                If dx < 0
                        Then x = x2
                        y = y2
                          xend=x1
                If dx > 0
                    Then x = x1
                y = y1
                        xend=x2

Step6: Generate point at (x,y)coordinates.

Step7: Check if whole line is generated.
                If x > = xend
                Stop.

Step8: Calculate co-ordinates of the following pixel
                If d < 0
                    Then d = d + i1
                If d ≥ 0
          Then d = d + i2
                Increment y = y + 1

Step9: Increment x = x + 1

Step10: Draw a degree of latest (x, y) coordinates

Step11: move to step 7

Step12: End of Algorithm

Example: Starting and Ending points of the road are (150, 100) and (80, 50). Find intermediate points.

Solution: x1=150
                y1=100
                x2=80
                y2=50
                dx = x2-x1=80-150=70
                dy = y2-y1=50-100=50
                I1=2* ∆y=2*50=100
                I2=2*(∆y-∆x) =2*(50-70) =40
                d = I1-∆x=100-70=30

C Program:

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

#include<math.h>

main()

{

int gd=DETECT,gm;

int x1,y1,x2,y2;

char a[50],b[50];

initgraph(&gd,&gm," ");

printf("\nEnter the starting point");

scanf("%d%d",&x1,&y1);

printf("\nEnter the ending point");

scanf("%d%d",&x2,&y2);

cleardevice();

outtextxy(190,60,"**********BRESENHAM'S LINE DRAWING ALGORITHM**********");

x1+=20;

x2+=20;

y1=470-y1;

y2=470-y2;

line(20,20,20,470);

line(20,470,590,470);

outtextxy(16,15,"^y");

outtextxy(590,468,">x");

bresenham(x1,y1,x2,y2);

getch();

closegraph();

}

bresenham(x1,y1,x2,y2)

{

int i,dx,dy,x,y,c1,c2,xend,yend,xin,yin,p;

dx=abs(x1-x2);

dy=abs(y1-y2);

xend=x2;

yend=y2;

x=x1;

y=y1;

if(x==xend)

xin=0;

if(y==yend)

yin=0;

if(xend<x)

xin=-1;

if(yend<y)

yin=-1;

else

yin=1;

if(dy<dx)

{

p=2*dy-dx;

c1=2*dy;

c2=2*(dy-dx);

for(i=dx;i>0;i--)

{

x=x+xin;

if(p<0)

p+=c1;

else

{

y=y+yin;

p+=c2;

}

putpixel(x,y,WHITE);

}

}

else

{

p=2*dx-dy;

c1=2*dx;

c2=2*(dx-dy);

for(i=dy;i>0;i--)

{

y=y+yin;

if(p<0)

p+=c1;

else

{

x=x+xin;

p+=c2;

}

putpixel(x,y,WHITE);

}

}

}

FOR OUTPUT CLICK HERE!!