DDA Line Algorithm

The two endpoints of a line segment are specified at positions (x1, y1) and (x2, y2). Determine the slope m and y-intercept b with the following calculations.

m = (y2 - y1) / (x2 - x1)
m = Dy / Dx                    ...(2)
b = y1 - m * x1                ...(3)

From the slope equation, the x interval is:

m = Dy / Dx
Dx = Dy / m                    ...(5)

Line DDA Algorithm

The digital differential analyzer (DDA) is a scan-conversion line algorithm based on the Dx calculation. The line is sampled at unit intervals in one coordinate, and the nearest integer value is chosen for the other coordinate.

Consider first a line with a positive slope.

Step 1 — slope ≤ 1

If the slope is less than or equal to 1, use unit x intervals (Dx = 1) and compute each successive y value:

Dx = 1
m = Dy / Dx
m = (y2 - y1) / 1
m = (yk+1 - yk) / 1
yk+1 = yk + m                  ...(6)

• subscript k starts at 1 for the first point and increments until the end point is reached
• m is any real number between 0 and 1
• calculated y values must be rounded to the nearest integer

Step 2 — slope > 1

If the slope is greater than 1, use unit y intervals (Dy = 1) and compute each successive x value:

Dy = 1
m = Dy / Dx
m = 1 / (x2 - x1)
m = 1 / (xk+1 - xk)
xk+1 = xk + (1 / m)            ...(7)

Equations (6) and (7) process the line from the left endpoint to the right endpoint.

Step 3 — reverse processing

If processing starts at the right endpoint:

Dx = -1
m = Dy / Dx
m = (y2 - y1) / -1
yk+1 = yk - m                  ...(8)

Step 4 — negative slope

For negative slope with Dy = -1:

Dy = -1
m = Dy / Dx
m = -1 / (x2 - x1)
m = -1 / (xk+1 - xk)
xk+1 = xk + (1 / m)            ...(9)

Equations (6) and (9) calculate pixel positions along a line with a negative slope.

Advantage

• Faster method for calculating pixel positions than the equation Y = mx + b

Disadvantage

• Floating-point increments accumulate rounding error and still require significant computation time

C Programming Code for line-drawing algorithm

void linedda(int xa, int ya, int xb, int yb)
{
    int dx = xb - xa, dy = yb - ya, steps, k;
    float xincrement, yincrement, x = xa, y = ya;

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

    xincrement = dx / (float)steps;
    yincrement = dy / (float)steps;
    putpixel(round(x), round(y), 2);

    for (k = 0; k < steps; k++) {
        x += xincrement;
        y += yincrement;
        putpixel(round(x), round(y), 2);
    }
}

Sample Output

xa,ya=>(2,2)
xb,yb=>(8,10)
dx=6
dy=8
xincrement=6/8=0.75
yincrement=8/8=1
1) for(k=0;k<8;k++)
xincrement=0.75+0.75=1.50
yincrement=1+1=2
1=>(2,2)
2) for(k=1;k<8;k++)
xincrement=1.50+0.75=2.25
yincrement=2+1=3
2=>(3,3)
it will be incremented upto the final end point is reached.