# DDA Line Generation Algorithm

Two of the most popular line generation algorithms are DDA Algorithm and Bresenham Algorithm. The full form of DDA algorithm is Digital Differential Analyser algorithm. To understand it we have to clear about some mathematical terms discussed below.

## Need to know:

Any point ‘P’ in 2D represented as (x, y) where x is termed as abscissa which is distance of the point from origin i.e., (0, 0) in the direction of X-axis and y is termed as ordinate which is distance of the point from origin i.e., (0, 0) in the direction of Y-axis.

Now, if we are given the co-ordinates of end points of a line segment PQ , P(x_{1}, y_{1}) and Q(x_{2}, y_{2}) then the equation of the line is,

\[y-{{y}_{1}}=m(x-{{x}_{1}})\]

Where, m = Slope of the line and it is calculated as,

\[m=\frac{{{y}_{2}}-{{y}_{1}}}{{{x}_{2}}-{{x}_{1}}}\]

\[i.e.,m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}\]

For example, let us find the slope of the line joining the points (2, 3) and (8, 11).

\[m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}=\frac{11-3}{8-2}=\frac{8}{6}=\frac{4}{3}\]

The slope of any particular line is fixed and its does not changes if we calculate it using any two points on the line.

Again, remember

\[\Delta x=dx={{x}_{2}}-{{x}_{1}}\]

\[\Delta y=dy={{y}_{2}}-{{y}_{1}}\]

\[\therefore m=\frac{\Delta y}{\Delta x}=\frac{dy}{dx}\]

Now we are ready to understand DDA algorithm.

It is an incremental conversion method. In this approach next step is calculated using results from the preceding step. Suppose at step k we have calculated (x_{k}, y_{k}) to be a point on the line then the next point (x_{k+1}, y_{k+1}) should satisfy m.

**Case 1:**

If the slope m < 1, we increase the value of x by 1 i.e., dx = 1 and calculate successive y values.

**Case 2:**

If the slope m > 1, we increase the value of y by 1 i.e., dy = 1 and calculate consecutive x values.

**Case 3:**

If the slope m = 1, we increase the value of x and y both by 1.

#### Rule:

m |
x_{k+1 } |
y_{k+1} |

m < 1 | x_{k+1 }= x_{k} + 1 |
y_{k+1}= y_{k} + m |

m > 1 | x_{k+1 }= x_{k} + (1/m) |
y_{k+1}= y_{k} + 1 |

m = 1 | x_{k+1 }= x_{k} + 1 |
y_{k+1}= y_{k} + 1 |

Example 01 |

**Draw line segment from point (2, 4) to (9, 9) using DDA algorithm.**

**Solution:**

We know general equation of line is given by

\[y-{{y}_{1}}=m(x-{{x}_{1}})\]

Where,

\[m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}\]

Given, (x_{start}, y_{start}) → (2, 4) and (x_{end} , y_{end}) → (9, 9)

\[\Rightarrow m=\frac{{{y}_{(end)}}-{{y}_{(start)}}}{{{x}_{(end)}}-{{x}_{(start)}}}=\frac{9-4}{9-2}=\frac{5}{7}<1\]

As 0 < *m* < 1 so according to DDA algorithm case 1.

x_{k+1 }= x_{k} + 1, y_{k+1}= y_{k} + m

**Iteration 1:**

Given, (x_{1}, y_{1}) → (2, 4)

\[\therefore {{x}_{2}}={{x}_{1}}+1=2+1=3\]

\[\therefore {{y}_{2}}={{y}_{1}}+m=4+\frac{5}{7}=\frac{33}{7}\]

Put pixel (x_{2}, round y_{2}, color) i.e., put on (3, 5)

**Iteration 2:**

\[{{x}_{3}}={{x}_{2}}+1=3+1=4\]

\[{{y}_{3}}={{y}_{2}}+m=\frac{33}{7}+\frac{5}{7}=\frac{38}{7}\]

Put pixel (x_{3}, round y_{3}, color) i.e., put on (4, 5)

Similarly go on till (9, 9) is reached.

## DDA Algorithm

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
Procedure DDAL(x0, y0, x1, y1: integer); var: dx, dy, counter: integer; x_inc, y_inc, x, y: real; begin: dx := x1 - x0; dy := y1 – y0 if abs(dx) > abs(dy) then counter := abs(dx); else counter := abs(dy); x_inc := dx/counter; y_inc := dy/counter; x := x0; y := y0; putpixel( round(x), round(y), color); for i:= 0 to counter do begin: x := x + x_inc; y := y + y_inc; putpixel(round(x), round(y), color); end; end;{DDAL} |

## Imlementation of DDA Algorithm in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<stdio.h> #include<graphics.h> //Function for finding absolute value int abs (int n) { return ( (n>0) ? n : ( n * (-1))); } //DDA Function for line generation void DDAL(int X0, int Y0, int X1, int Y1) { // calculate dx & dy int dx = X1 - X0; int dy = Y1 - Y0; // calculate steps required for generating pixels int counter = abs(dx) > abs(dy) ? abs(dx) : abs(dy); // calculate increment in x & y for each steps float X_inc = dx / (float) counter; float Y_inc = dy / (float) counter; // Put pixel for each step float X = X0; float Y = Y0; for (int i = 0; i <= counter; i++) { putpixel (X,Y,RED); // put pixel at (X,Y) X += X_inc; // increment in x at each step Y += Y_inc; // increment in y at each step delay(100); // for visualisation of line generation step by step } } int main() { int gd = DETECT, gm; // Initialize graphics function initgraph (&gd, &gm, ""); int X0, Y0, X1, Y1; printf(“\n Enter the co-ordinate of the starting point: “); scanf(“%d%d”,&X0,Y0); printf(“\n Enter the co-ordinate of the ending point: “); scanf(“%d%d”,&X1,Y1); DDAL(X0, Y0, X1, Y1); return 0; } |