Bresenham’s line drawing algorithm in C-Language:
For Slope<1
Bresenhams line drawing algorithm removes disadvantages of DDA algorithm. this algorithm uses integer calculation instead of floating-point calculation to reduce complexity and time consumption. In bresenhams algorithm pixel which is nearer to line will be displayed as a part of line based on distance from center of pixel and actual line.
From above diagram, equation of line at point (y, xa+1) is y=m.(xa+1)+c. we will calculate distance D1 and distance D2 to check which pixel is nearer to line .
D1=y-ya
D1= m.(xa+1)+c-ya -------------------------------------------------(1)
D2=ya+1 -y
D2= ya+1 - m.(xa+1)+c -------------------------------------------------(2)
We will decide nearer pixel based on D1-D2 and multiplied by dx for integer calculation as a decision parameter.
Pa= dx*(D1-D2)
Pa= 2.dy.xa -2.dx. ya +b where b=2.dy+dx.(2c-1) , dx=x2-x1 and dy=y2-y2..……(3)
At next step decision parameter will be
Pa+1 = 2.dy.xa+1 -2.dx. ya+1 +b --------------------------(4)
We will find relation between current decision parameter and next decision parameter by subtracting Pa from Pa+1.
Pa+1- Pa = (2.dy.xa+1 -2.dx. ya+1 +b) – (2.dy.xa -2.dx. ya +b)
Pa+1 = Pa+ 2.dy -2.dx(ya+1 - ya) -----------------------------(5)
Initial decision parameter calculated at (x0,y0) is
P0=2.dy-dx.
Steps:
1.Accept line endpoints A(x1,y1) and B(x2,y2) as input.
2.Calculate dx=x2-x1,dy=y2-y1,2dx,2dy
3.Calculate initial decision parameter p0=2dy-dx
4.If pk<0:
x1=x1+1,
y1=y1 and
pk+1=pk+2dx
else:
x1=x1+1,
y1=y1+1 and
pk+1=pk+2dx-2dy
5 . Repeat step 4 dx times
6. Plot all pixels and Stop
Program:
#include<stdio.h>
#include<graphics.h>
#include<math.h>
#include<conio.h>
void main()
{
int gd=DETECT,gm;
int x1,y1,x2,y2,dx,dy,p,i;
initgraph(&gd,&gm,"c:\\turboc3\\bgi");
printf("Enter x1");
scanf("%d",&x1);
printf("Enter y1");
scanf("%d",&y1);
printf("Enter x2");
scanf("%d",&x2);
printf("Enter y2");
scanf("%d",&y2);
dx=(x2-x1);
dy=(y2-y1);
p=2*dy-dx;
putpixel(x1,y1,3);
for(i=0;i<=dx;i++)
{
if(p<0)
{
x1=x1+1;
y1=y1;
p=p+2*dy;
}
else
{
x1=x1+1;
y1=y1+1;
p=p+2*dy-2*dx;
}
putpixel(x1,y1,3);
}
getch();
}
Output:
