Loading
View RSS Feed

Raks' Blog

How To Implement Bresenhamís Line Drawing Algorithm In C?

Rating: 7 votes, 2.14 average.
The Bresenhamís algorithm offers the following four advantages over the other line drawing algorithms:

1) It involves simple addition and does not perform any multiplication or division. As a result, it consumes less time and memory during execution.

2) It involves simple integer arithmetic and not real or floating-point arithmetic.

3) Its calculations use simple constants instead of complex first- or second-order equations.

To draw a line between two endpoints, the Bresenhamís algorithm evaluates all the intermediate points nearest the line, instead of simply rounding the attained value. Following Figure shows a line drawn up to the point (xn, yn), with the next point (xn+1, yn+1) yet to be evaluated:

Click image for larger version. 

Name:	Bresenham's Line Drawing Algorithm.jpg 
Views:	10678 
Size:	15.4 KB 
ID:	206
This figure shows the line drawn up to the point (xn, yn). The next point is decided between (xn+1, yn) and (xn+1, yn+1).

After plotting the current point, the Bresenhamís algorithm calculates the value of the successive point. In Figure after you plot (xn, yn), the next point chosen is (xn+1, yn) and (xn+1, yn+1), whichever is nearest to the line. The next point is determined by checking if the midpoint D, whose value is (xn+1, yn+1/2), lies above or below the line. If D lies above the line, as it does in above Figure, the point (xn+1, yn) is closest to the line; if D lies below the line, (xn+1, yn+1) is closest to the line. For example, the equation of the line for the function g(x, y) is:


g(x, y) = Lx + My + N ....(1)
A point (xk, yk) lies on the line if g(xk, yk) = 0, below the line if g(xk, yk) > 0, and above the line if g(xk, yk) < 0. These relationships enable you to decide the position of point D and to select the next point to be plotted.

The equation of the line in the slope-intercept form is:

y = m x + c
= (Δy/Δx) x + c.
=> Δx . y = Δy . x + Δx . c

As a result, g(x, y) = Δy . x - Δx . y + Δx . c = 0. ....(2)
To evaluate the values of L, M, and N in equation (1), compare the equation with equation (2). As a result,


L = Δy, M = - Δx and N = Δx.c
To draw a line using Bresenhamís algorithm:

1) Enter the values of the two endpoints of the line, (x1, y1) and (x2, y2).
2) Calculate Δx and Δy from these endpoints.
3) To determine the next pixel, check whether the sign of g(D) is plus or minus. You can determine this using the value of g(xn+1, yn+1/2) denoted by pn:

pn = g(xn+1, yn+1/2)
= L (xn+1) + M (yn+ 1/2) + N.
4) Choose the next pixel depending on the value of pn. If pn < 0, choose pixel (xn+1, yn); if > 0, choose pixel (xn+1, yn+1); and if pn = 0, choose either pixel.

5) If you choose pixel (xn+1, yn), determine the next pixel from the sign of (xn+2, yn+ 1/2) ded by pn+1:

pn+1 = g(xn+2, yn+1/2)
= L (xn+2) + M (yn+1/2) + N

The increment in p is Δp1 = pn+1 - pn = L = Δy.
If you choose pixel (xn+1, yn+1), determine the next pixel from the sign of (xn+2, yn+ 3/2) denoted by pn+1:

pn+1 = g(xn+2, yn+3/2)
= L (xn+2) + M (yn+3/2) + N

The increment in p is, Δp2 = pn+1 - pn = L + M = Δy - Δx.
6) To draw the line, first calculate p0. The first pixel is (x1, y1) and the first midpoint D is at (x1+1, y1+ 1/2):

=> p0 = g(x1+1, y1+ 1/2)
= L (x1 + 1) + M (y1 + Ĺ) + N
= L x1 + M y1 + N + L + M / 2
= g(x1, y1) + L + M / 2

Because (x1, y1) is a point on the line, as a result, g(x1, y1) = 0:


=> p0 = L + M / 2 = Δy - Δx/ 2.
7) Multiply p0, p1 and p2 by 2 to remove the fraction. In all subsequent calculations for the Bresenhamís algorithm, you need only their sign. To remove the fraction:

p0 = 2 . Δy - Δx,
Δp1 = 2 . Δy,
and Δp2 = 2 ( Δy - Δx)
8) To draw a line, start with (x1, y1) and initialize p to 0. After plotting the pixel (x1, y1), increment the value of p by p0. For subsequent pixels, check the value of p. If p < 0, choose (xn+1, yn) as the next pixel and increment p by Δp1. If p > 0, choose pixel (xn+1, yn+1) and increment p by Δp2. If p = 0, choose either. Plot the subsequent pixels until you reach (x2, y2).

Following Example shows how to draw a line with 0 <= slope <= 1, using the Bresenhamís algorithm:


Code:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<graphics.h>

void draw_line(float,float,float,float);

main()
{
 int driver,mode;
 float x1,y1,x2,y2;

 clrscr();
 printf("Enter the two endpoints of the line:");
 printf("\nx1 =");
 scanf("%f",&x1);
 printf("y1 =");
 scanf("%f",&y1);
 printf("x2 =");
 scanf("%f",&x2);
 printf("y2 =");
 scanf("%f",&y2);

 clrscr();

 driver = DETECT;
 initgraph(&driver,&mode,"\\tc\\bgi");     \\path of bgi can be different in your case

 draw_line(x1,y1,x2,y2);

 getch();
 closegraph();
}

void draw_line(float x1,float y1,float x2,float y2)
{
 float dy,dx;
 float x,y;
 float p,p0,dp1,dp2;

 dy = y2-y1;
 dx = x2-x1;

 p0 = 2 * (dy - dx);
 dp1 = 2 * dy;
 dp2 = 2 * (dy - dx);

 putpixel(x1,y1,EGA_WHITE);
 p = p0;

 for(x=x1+1,y=y1;x<x2;x++)
    {
     if(p < 0)
     {
      p = p+dp1;
      putpixel(x,y,EGA_WHITE);
     }
     else
     {
      p = p+dp2;
      y++;
      putpixel(x,y,EGA_WHITE);
     }
     }
}
The example above uses the Turbo C as the compiler.

Submit "How To Implement Bresenhamís Line Drawing Algorithm In C?" to Digg Submit "How To Implement Bresenhamís Line Drawing Algorithm In C?" to del.icio.us Submit "How To Implement Bresenhamís Line Drawing Algorithm In C?" to StumbleUpon Submit "How To Implement Bresenhamís Line Drawing Algorithm In C?" to Google

Updated 05-18-2011 at 05:08 AM by Harsh

Categories
C C++

Comments

  1. shivani2806's Avatar
    this is not my ans
    i want when slope>1
  2. Harsh's Avatar
    Please refer to the following code:-

    Code:
    /*BRESENHAM LINE DRAWING ALGORITHM*/
    #include <stdio.h>
    #include <graphics.h>
    #include <math.h>
    
    void main ( )
    {
       int gdriver = DETECT, gmode, errorcode;
    
    int dx, dy, x, y, x1, y1, x2, y2, xend, p;
    initgraph( &gdriver, &gmode, "d:\\tc30\\bgi" );
       printf( "Enter end points : " );
       scanf( "%d %d %d %d", &x1, &y1, &x2, &y2 );
       dx = x1 - x2;
       dy = y1 - y2;
       p = 2 * dy - dx;
       if ( x1 > x2 )
       {
    	x = x2;
    	y = y2;
    	xend=x1;
       }
       else
       {
    	x = x1;
    	y = y1;
    	xend = x2;
       }
       putpixel ( x, y, 2 );
       while ( x < xend )
       {
    	if ( p < 0 )
    	{
    		x = x + 1;
    		p = p + 2 * dx;
    	}
    	else
    	{
    		y = y + 1;
    		p = p + 2 * dy - 2 * dx;
    	}
    	putpixel ( x, y, 2 );
    
    	}
    	getch();
    }
  3. Unregistered's Avatar
    Same as the title suggests. May I use the snippet for my application?



Disclaimer: Users of techforum4u.com are responsible for ensuring that any material they post (article, blog posts, images or other mulitimedia content) does not violate or infringe upon the copyright, patent, trademark, or any personal or proprietary rights of any third party, and is posted with the permission of the owner of such rights.Anyone who violates these rules may have their access privileges removed without warning.