Tutorials

Digital Differential Analyzer (DDA) Line Drawing Algorithm

Papri Ghosh
19 Feb 2017
Read Time : 15 Minutes
Digital Differential Analyzer (DDA) Line Drawing Algorithm

Digital Differential Analyzer (DDA) is a scan conversion line algorithm where a line is to be plotted on any graphical devices based on its two end points. The equation of line is: y = mx + c (Eq.1) where m = dx/dy. Different types of the line are already discussed (Click Here to view). Here we discuss how to plot a line on a Raster Device following the DDA Algorithm.

Case-I: Line Type-IV

Let us consider (XK, YK) as the initial point and the next point is to be calculated in the Type-IV line. Two candidate points are there: (XK+1, YK) and (XK+1, YK+1).  So the goal is to achieve whether the value of YK+1 = YK or YK+1.

For the initial point and next probable point we can rewrite the Eq.1 as follows:

YK = m XK + c   ...   (Eq.2)

YK+1 = m XK+1 + c   ...   (Eq.3)

For Line Type-IV we know,

XK+1 = XK + 1   ...   (Eq.4)

Putting the value of Eq.4 in Eq.3 we get,

YK+1    

=   m (XK + 1) + c

=   mXK + m + c

=   m x {(YK - c)/m} + m + c    (Put the value of XK from Eq.2)

=   YK – c + m + c

=   YK + m 

So, YK + 1 = YK + m   ...   (Eq.5)

Case-2: Line Type-V

Let us consider (XK, YK) as the initial point and the next point is to be calculated in the Type-V line. Two candidate points are there: (XK, YK+1) and (XK+1, YK+1).  So the goal is to achieve whether the value of XK+1 = XK or XK+1.

For the initial point and next probable point we can rewrite the Eq.1 as follows:

YK = m XK + c   ...   (Eq.2)

YK+1 = m XK+1 + c   ...   (Eq.3)

For Line Type-V we know,

YK+1 = YK + 1   ...   (Eq.6)

Putting the value of Eq.6 in Eq.3 we get,

YK+1   =   m XK+1 + c

m XK+1   =   YK+1- c

m XK+1   =   m XK + c + 1 – c    (Put the value of YK from Eq.2)

m XK+1   =   m XK + 1

So we can say that,

XK+1    =    XK + 1/m   ...   (Eq.7)

Case-III: Line Type-VI

Let us consider (XK, YK) as the initial point and the next point is to be calculated in the Type-IV line. Two candidate points are there: (XK+1, YK) and (XK+1, YK-1).  So the goal is to achieve whether the value of YK+1 = YK or YK-1.

For the initial point and next probable point we can rewrite the Eq.1 as follows:

YK = m XK + c   ...   (Eq.2)

YK+1 = m XK+1 + c   ...   (Eq.3)

For Line Type-VI we know,

XK+1 = XK + 1   ...   (Eq.8)

Putting the value of Eq.8 in Eq.3 we get,

YK+1    

=   m (XK + 1) + c

=   mXK + m + c

=   m x {(YK - c)/m} + m + c    (Put the value of XK from Eq.2)

=   YK – c + m + c

=   YK + m

So, YK+1   =   YK + m   ...   (Eq.9)

There is no structural difference between Eq.9 with Eq.5 except the value of m is negative in the Eq.9. So similarly if we generate Eq.10 for Line Type-VII, then also we will get the similar line as Eq.7.

Algorithm: DDA

Input:  x1, y1, x2, y2

Output: Plot the line

Variable Used: m, x, y

Steps:

1.    m=( y2-y1 )/(x2-x1);

2.    plot(x1,y1);

3.    if(mod(m)>1)

a.    y=y1;

b.    for(x=x1+1; x<=x2; x++)

i.    y=y+m;

ii.    plot(x,y)

4.    else if(mod(m)<1)

a.    x=x1;

b.    for(y=y1; y<=y1; y++)

i.    x=x+1/m;

ii.    plot(x,y);

Follow us on Facebook_Page, Youtube_Channel and Join us on Facebook_Group

Authored By Papri Ghosh

She is a co-founder of "Day On My Plate". Furthermore she is an academician in Dept. of Computer Science & Engineering. She likes to voyage all over the world in search of unrevealed experiences. She is passionate in reading novels and writing articles. Hope you all are enjoying her articles.

Basics Time Complexity Analysis Motivation of Design and Analysis of Algorithm To study the PN junction diode characteristics under Forward bias conditions To study the input and output characteristics of a BJT in Common Emitter configuration