All rights are reserved by Niteesh Kumar.. Theme images by Storman. Powered by Blogger.

Followers

Total Pageviews

Blog Archive

Follow by Email

Translate

Sunday, 5 February 2017

DDA algorithm for line generation

DDA algorithm is the basic algorithm for line drawing.In this method, we start from the starting point and then on each step a fixed increment is added to the current point to get the next point on the line.We repeat these steps till the end of the line.

Let us suppose (x1,y1) and (x2,y2) are the end points of the line and the equation of the line is y=mx+c.

                 slope of the line=(y2-y1)/(x2-x1)
                 suppose dx=(x2-x1) and dy=(y2-y1)
                 dx=dy/m    and     dy=m*dx
dx and dy will be the values for incrementing x and y values of current point.so-

                         Xi+1 =Xi + dy/m
                         Yi+1 =Yi + m*dx

DDA Algorithm- 

  • Read the points (x1,y1) and (x2,y2)
  • approximate the length of line i.e. if
                 if(abs(x2-x1)>abs(y2-y1))
                         length=abs(x2-x1)
                else
                         length=abs(y2-y1)
  •  Select the raster unit dx and dy
       dx=(x2-x1)/length   and   dy=(y2-y1)/length
  • Round the value rather than truncating, make use of SIGN function so as to enable line drawing in any quadrant 
                     SIGN(x) can have (-1,0,1) 
                     X=x1+0.5*SIGN(dx); 
                     Y=y1+0.5*SIGN(dy);
     (x1,y1) will be initial coordinates.
  • now plot the points and i=1
               while(i<=length)
                      {
                               plot(int(x),int(y));
                               Xi+1 =Xi + dx;
                               Yi+1 =Yi + dy;
                                i=i+1;               
                      } 
  •   stop

Advantage of DDA algorithm-

The only advantage of DDA algorithm is that it is the simplest algorithm for line drawing.  


Drawbacks of DDA algorithm-

  1. While plotting we are taking either abs(y2-y1) or abs(x2-x1) as length which makes this orientation dependent, so it may posible that end point 

DDA algorithm in c-

#include<stdio.h>
#include<math.h>
#include<graphics.h>
//structure for two end points
struct point{
 int x,y;
}a,b;
int main()
{
 int dx,dy,delx,dely,len,i,gd,gm;
 printf("enter two pair of points\n");
 scanf("%d %d",&a.x,&a.y);
 scanf("%d %d",&b.x,&b.y);
 dx=abs(b.x-a.x);
 dy=abs(b.y-a.y);
 if(dx>dy)
  len=dx;
 else
  len=dy;
 delx=dx/len;
 dely=dy/len;
 i=1;
 initgraph(&gd,&gm,"");
 if(len<0)
 len=-len;
 while(i<=len)
 {
  putpixel(a.x,a.y,RED);
  a.x=a.x+delx;
  a.y=a.y+dely;
  i++;
  delay(10);
 }
 getchar();
 closegraph();
 return 0;
}
 

OUTPUT-

  • To execute the program save the file given above with .c extension i.e. (dda.c)
  • open your terminal and type gcc dda.c -lgraph and click enter button
  • run ./a.out and see the output 
  • output given below is for end points (10,10) and (100,100)

DDA algorithm
 

0 on: "DDA algorithm for line generation"