DDA (Digital Differential Analyser) Line Drawing Algorithm

The DDA algorithm is a very simple and efficient algorithm for generating straight lines on a digital display device.

However, it may produce errors due to rounding, and it may not be as accurate as other line-drawing algorithms such as the Bresenham’s line algorithm.

The algorithm starts at one end of the line and calculates the coordinates of each point along the line by adding the incremental changes to the previous point.

Digital Differential Analyser algorithm to perform rasterization on polygons, lines, and triangles.

Digital Differential Analyser algorithm is also known as an incremental method of scan conversion.

In this algorithm, we can perform the calculation in a step by step manner. We use the previous step result in the next step.

As we know the general equation of the straight line is:

y = mx + c

Here, m is the slope of (x1, y1) and (x2, y2).

dx = x2-x1

dy = y2-y1

m = dy/dx

Now, we consider one (start) point (xi, yi) and (xi+1, yi+1) as the next point.

Here i is starting value for x and y coordinator

Then the slope

m = (yi+1 — yi) / (xi+1 — xi)

Now, we have to find the slope between the starting point and ending point.

Algorithm DDA Line Drawing

Step 1: Start.

Step 2: Consider the two end points of line (x1, y1) and (x2, y2)

Step 3: Calculate,

dx = x2-x1

dy = y2-y1

m = dy/dx

The length of the line, or rather the number of iterations, is determined by the absolute values of dx and dy.

Step 4: Len = absolute (dx) > absolute (dy)?

absolute (dx): absolute (dy)

Now, to add lines, we have to find the incremental factors for the x and y-axis. We do this by dividing dx and dy with len.

Step 5: Calculate,

xinc = dx / Len

yinc = dy / Len

Now create a loop to add the values. To plot these values, we are assuming two variables, xi and yi. Here, assume we have a function setpixel(int x, int y), such that it plots a point of our chosen colour at the coordinates (x and y).

Step 6:

x = x1

y = y1

loop while x < x2:

setpixel(x, y)

x += xinc

y += yinc

Step 7: End

DDA algorithm is a simple and efficient algorithm for generating straight lines on a digital display device.

Its simplicity, efficiency, versatility, and accuracy make it a popular choice for line drawing in computer graphics.

But it has some limitations and is not always the optimal choice for all applications.

DDA algorithm to draw a line in Python Program:

import matplotlib.pyplot as plt

def DDA(x1, y1, x2, y2):

dx = x2 — x1

dy = y2 — y1

steps = abs(dx) if abs(dx) > abs(dy) else abs(dy)

xinc = dx / steps

yinc = dy / steps

x = x1

y = y1

points = [(round(x), round(y))]

for i in range(steps):

x += xinc

y += yinc

points.append((round(x), round(y)))

return points

points = DDA(1, 2, 7, 8)

x, y = zip(*points)

’’’ Python's zip() function is defined as zip(*iterables) . The function takes in iterables as arguments and returns an iterator. This iterator generates a series of tuples containing elements from each iterable. zip() can accept any type of iterable, such as files, lists, tuples, dictionaries, sets, and so on. ’’’

plt.plot(x, y, marker=’o’)

plt.show()

OUT PUT

DDA algorithm to draw a line in C Program also

#include <graphics.h>

#include <stdio.h>

#include <math.h>

#include <dos.h>

void main( )

{

float x,y,x1,y1,x2,y2,dx,dy,step;

int i,gd=DETECT,gm;

initgraph(&gd,&gm,”c:\\turboc3\\bgi”);

printf(“Enter the value of x1 and y1 : “);

scanf(“%f%f”,&x1,&y1);

printf(“Enter the value of x2 and y2: “);

scanf(“%f%f”,&x2,&y2);

dx=abs(x2-x1);

dy=abs(y2-y1);

if(dx>=dy)

step=dx;

else

step=dy;

dx=dx/step;

dy=dy/step;

x=x1;

y=y1;

i=1;

while(i<=step)

{

putpixel(x,y,5);