13,143,774 members (29,936 online)
alternative version

#### Stats

63.8K views
7 bookmarked
Posted 3 Mar 2012

# Implementation of the DDA line drawing algorithm

, 16 Apr 2012
 Rate this:
Introducing an implementation of the DDA algorithm in J2ME.

Figure 1

## Introduction

The DDA_Final application is capable of drawing lines between two points specified on the screen by the user. The user can navigate the cursor on the mobile screen by RIGHT, LEFT, UP, and DOWN keys and specify the end points by pressing the FIRE button. A line will be drawn on the screen when both start and end points will be specified. The program was tested on Sun WTK 2.5.2_01 emulator and Nokia 5130XpressMusic Handset.

The reason for implementing the algorithm in J2ME is that the reader gets a glimpse of how the real display devices work. To fully understand the topic, a little knowledge of computer graphics primitives like pixels and raster display devices is necessary. As the code is written in J2ME, a little knowledge of J2ME will be helpful.

## Background

Digital Differential Analyzer or simply abbreviated as DDA line drawing algorithm is used for drawing lines in raster graphics devices. In this algorithm, the starting and end position of the line has to be supplied.

The intermediary pixel positions will be calculated by the linear interpolation of variables over an interval between the start and end points. The algorithm is as follows:

Let the start and end point of the line be (x1, y1) and (x2, y2), respectively. So slope, m= (y2-y1)/(x2-x1). Depending on the value of m and the Quadrant to which (x, y) belongs, intermediary pixel positions have to be calculated as follows:

The positions have to be calculated as follows:

 Quadrant m<=1 m>1 First x=x+1 y=y + m x=x+1/m y=y+1 Second x=x-1 y=y + m x=x+1/m y=y+1 Third x=x-1 y=y-m x=x-1/m y=y-1 Fourth x=x+1 y=y + m x=x-1/m y=y-1 Table-1

Here the values of x and y are approximated to the nearest integer value as the pixel position cannot be a floating point number.

This was the theoretical approach towards the algorithm where a point can lie in any of the four quadrants virtually. Practically this is not possible as the pixel position cannot be negative in physical display devices. In physical display devices we have only the 1st quadrant of the Cartesian axis system where both x and y are positive or equal to zero and can assume integer values. At the time of implementing the algorithm for physical display devices, we only have to program for the first quadrant.

Another point to be noted here is that the orientation of physical display devices is different from the geometrical Cartesian axis.

Figure 2

In the real co-ordinate system for the first quadrant, the x value increases in right direction and y-value increases towards up continuously. In the physical display device coordinate system, the origin is the top left corner pixel. It means that the top left corner pixel will have a coordinate value (0, 0). The x co-ordinate value will increase in the right direction pixel wise and the y co-ordinate value will increase in the downward direction pixel wise. It may be noted that the bottom-right corner pixel will have the highest co-ordinate value in the display device.

For a clear visualization, the screen co-ordinate can be viewed as the reflected version of the geometrical first quadrant where the reflection is done by the line y=0.

## Using the Code

A total of five classes are used in the whole program:

```Main.java
GUI.java
Cursor.java
DDAEngine.java
DDA.java```

Main.java and GUI.java are used to create the Graphical User Interface and Command Actions. Cursor.java defines the navigable cursor which is used to select the start and end points. The J2ME `Sprite` class is used to create the animation.

In DDAEngine.java, the instance for the `Cursor` is created:

```private Cursor c;
. . . . . . . .
public DDAEngine(. . . .){
c=new Cursor(CURSOR_IMAGE,CURSOR_WIDTH,CURSOR_HEIGHT);
c.setRefPixelPosition(height/2, width/2);
this.append(c);
}```

The cursor can be navigated throughout the view port using the RIGHT, LEFT, UP, and DOWN keys:

```if ((keyState & gui.RIGHT_PRESSED) != 0){
c.moveRight(width);
}

if ((keyState & gui.LEFT_PRESSED) != 0){
c.moveLeft();
}

if ((keyState & gui.UP_PRESSED) != 0){
c.moveUp();
}

if ((keyState & gui.DOWN_PRESSED) != 0){
c.moveDown(height);
}```

The cursor on pressing the FIRE button selects the start and end points, respectively:

```/*s1 and s2 indicates wheather the points are selected or not.
These are Boolean variables.After selecting the first point
the s1 is set to true and on next FIRE press the control goes
to the 2nd if() statement.*/

if ((keyState & gui.FIRE_PRESSED) != 0){
if(!s1){
x1=c.getRefPixelX();  //x co-ordinate of the start point
y1=c.getRefPixelY();  //y co-ordinate of the start point
s1=true;              // s1 is set to true as first point is chosen
hit=false;
. . . . . . . ..
}
if( hit & !s2 ){
x2=c.getRefPixelX();      //x co-ordinate of the end point
y2=c.getRefPixelY();      //y co-ordinate of the end point
s2=true;                   // s2 is set to true as end point is chosen

. . . . . . . . . .
}
}
if(s1){
hit=true;
}```

When we have both the points selected, the DDA algorithm is invoked from the DDAEngine.java class which is implemented in the DDA.java class.

```if(s1 & s2){
dda=new DDA(x1,y1,x2,y2);
}```

In the DDA.java class, we have the `drawLine()` method which calculates the intermediary pixel positions between (x1, y1) and (x2, y2). Here at the 1st place we calculate the differences between the x and y coordinates of the start and end points:

```void drawLine(. .. . ){
dx=(double)(x2-x1);
dy=(double)(y2-y1);
. . . . . . . ..
}```

Next we have to check if slope <= 1 or slope > 1:

```void drawLine(. .. . ){
. . . . . . . ..
len=Math.abs(dx);
if(Math.abs(dy)>Math.abs(dx))len=Math.abs(dy);
. . . . . . . . .
}```

We can model the algorithm in such a way that it works for lines having slope = 90 degrees. The slope of a line is 90 degree means the x co-ordinates of the start and end points are equal. This can be modeled as:

```void drawLine(. .. . ){
. . . . . . . ..
if((x1==x2)&& dy<0)len=dy;
. . . . . . . . .
}```

Next select the raster unit, i.e., compute the x-increment and y-increment:

```void drawLine(. .. . ){
. . . . . . . ..
xinc=dx/len;            //x-increment
yinc=dy/len;            //y-increment
if((x1==x2)&& dy<0)yinc=Math.abs(dy)/len; //y-increment for line having slope = 90 degree
. . . . . . . . .
}```

Here one point to be noted is that either `xinc` or `yinc` will be one because `len` is either (x2-x1) or (y2-y1).

Thus the incremental value for x or y will be one.

Next, calculate and plot the intermediary points by executing a loop:

```void drawLine(. .. . ){
. . . . . . . ..
fx=(double)x1;
fy=(double)y1;
double i=1;

if(x1!=x2){
while(i<=len){
g.setColor(200,0,0);
g.drawLine((int)Math.floor(fx),(int)Math.floor(fy),
(int)Math.floor(fx),(int)Math.floor(fy));
fx=fx+xinc;
fy=fy+yinc;
i=i+1;
}
}
else if(x1==x2){
i=(double)y1;
while(i!=(double)y2){
g.setColor(200,0,0);
g.drawLine((int)Math.floor(fx),(int)Math.floor(fy),
(int)Math.floor(fx),(int)Math.floor(fy));
fx=fx+xinc;
fy=fy+yinc;
i=i+yinc;
}
}
. . . . . . . . .
}```

The whole project is composed using NetBeans IDE 6.9.1. On successful execution, the user will get a star like cursor on the screen like in Figure 3.

Figure: 3

This cursor can be navigated by pressing the RIGHT, LEFT, UP, and DOWN Keys. On pressing Fire the points will be specified on the screen with a pink star as shown in Figure 4.

Figure 4

In figure 4, the start point is specified. On specifying the end point, the line will be drawn as shown in Figure 1. The start and end co-ordinates will also be shown.

## Points of Interest

With this program, the difference between geometric and screen coordinates becomes visible to the programmer. Also, this gives a taste to the reader of how simple graphical contents can be created for real devices.

## About the Author

 IERCEM Institute of Information Techology India
No Biography provided

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 Needs more work sorry Garth J Lancaster29-Feb-12 23:23 Garth J Lancaster 29-Feb-12 23:23
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Sep-17 16:05 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.