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₁, y₁) and Q(x₂, y₂) 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:

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₁, y₁) → (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₂, round y₂, 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₃, round y₃, color) i.e., put on (4, 5)

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

DDA Algorithm

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

#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;
}

 ;