Let us understand how DDA Algorithm works by taking some examples and solving them too. Just keep in mind two things one, Y=mx+b is the line equation. Second, If m is less than one increase X and calculate Y. If m is more than 1 then increase Y and calculate X. DDA Algorithm is explained by taking some examples.
Remember the steps:
- If slope (m) is less than 1 (m<1) then increment x as x1+1 and calculate y as y1=y1+m
- If slope (m) is greater than 1 (m>1) then increment y as y1+1 and calculate x1=x1+1/m
- If slope is equal to 1 (m=1) then increment both x and y. x1=x1+1 , y1=y1+1.
DDA- Digital Differential Analyser – The Algorithm
S-1: Lets take the starting points of line as (x1,y1) and ending points as (x2,y2)
S-2: m=(y2-y1)/(x2-x1)
S-3: If slope (m) is less than 1 (m<1) then increment x as x1+1 and calculate y as y1=y1+m
S-4: If slope (m) is greater than 1 (m>1) then increment y as y1+1 and calculate x1=x1+1/m
S-5 : If slope is equal to 1 (m=1) then increment both x and y. x1=x1+1 , y1=y1+1
S-6 : Repeat the steps till end of line (x2,y2) is reached.
—————————————————————–
Problem Statement
Draw a line from (1,1) to (8,7) using DDA and BLA algorithms.
DDA- Digital Differential Analyser
This case is for slope (m) less than 1. Slope (m) =(7-1)/(8-1) = 6/7 .
S-1: x1=1; y1=1; x2=8; y2=7.
S-2: m=(7-1)/(8-1) = 6/7 which is less than 1.
S-3: As m (6/7) is less than 1 therefore x is increased and y is calculated.
S-4 : The step will be x1=x1+1 and y1= y1+6/7
S-5 : The points genrated would be x1=1+1 and Y1=1+(5/7) => 1+0.9=>1.9=> approx 2. So X 1=2 and Y1= ~2
| S.No. | X1 | Y1 | Pixel Plotted |
| 1 | 2 | 2 | 2,2 |
| 2 | 3 | 2+6/7 = 2.9 | 3,3 |
| 3 | 4 | 2.9 + 6/7 = 3.8 | 4,4 |
| 4 | 5 |
3.8 + 6/7 = 4.7 |
5,5 |
| 5 | 6 | 4.7 + 6/7 = 5.6 | 6,6 |
| 6 | 7 | 5.6 + 6/7 = 7.0 | 7,7 |
The algorithm will stop here as the x value has reached 7.
—————————————————————–
Lets take another example.
Draw a line using DDA Algorithm from (0,0) to (4,6)
This case is for slope (m) greater than 1. Slope (m) =(6-0)/(4-0) = 6/4 .
S-1: x1=0; y1=0; x2=4; y2=6
S-2: m=(6-0)/(4-0) = 6/4 which is more than 1.
S-3: As m (6/4) is greater than 1 therefore y is increased and x is calculated.
S-4 : Now increase the value of y and calculate value of x.
- To calculate x, take line equation and find x , x2=x1+1/m
- The step will be y1=y1+1 and x1 =x1+1/( 6/4) , After Simplification, Every time y1=y1+1 and x1=x1+4/6
| Step | Y1 | X1 | Pixel Plotted |
| 1 | 0 | 0 | (0,0) |
| 2 | 1 | x1= (0)+4/6=0.67 =1 | (1,1) |
| 3 | 2 | 0.67+4/6 = 1.34 | (1,2) |
| 4 | 3 | 1.34+4/6=2.01 | (2,3) |
| 5 | 4 | 2.01+4/6= 2.68 | (3,4) |
| 6 | 5 | 2.68+4/6=3.35 | (3,5) |
| 7 | 6 | 3.35+4/6=4.02 | (4,6) |
The algorithm will stop here because the Y and X values have reached the End point (4,6).
Example -3: Draw a line from (0,0) to (7,7) using DDA Algorithm
This case is for slope (m) equals 1. Slope (m) =(7-0)/(7-0) = 7/7 .
S-1: x1=0; y1=0; x2=7; y2=7.
S-2: m=(7-0)/(7-0) = 7/7 which is equal to 1.
S-3: As m equals to 1 (m=1) therefore x will be increased by 1 and y will be incremented by m.
S-4 : The step will be x1=x1+1 and y1= y1+1. This would be a 45 degree line where x and y both have equal incremented value.
S-5 : The points generated would be x1=1+1 and Y1=1+(1) => So X 1=2 and Y1= 2
| S.No. | X1 | Y1 | Pixel Plotted |
| 1 | 2 | 2 | 2,2 |
| 2 | 3 | 2+1 = 3 | 3,3 |
| 3 | 4 | 3 + 1 = 4 | 4,4 |
| 4 | 5 | 4 + 1 =5 | 5,5 |
| 5 | 6 | 5 + 1 =6 | 6,6 |
| 6 | 7 | 6 + 1 = 7.0 | 7,7 |
The algorithm will stop here as the x and y values have reached 7. This would be a straight line dividing the first quadrant in two equal halves.
Example -4
Use DDA Algorithm to draw a line from (2,3) to (9,8).
S-1: x1=2, y1=3 and x2=9 , y2=8.
S-2: Calculate Slope m = (8-3)/(9-2) = 5/7, which is less than 1.
S-3: Since m is less than one that means we would increase x and calculate y.
S-4: So new x would be equal to old x plus 1 🙂 and calculate y as new y = old y +m(slope). — Easy to understand, We mean the following
x1=x1+1 and y1=y1+(5/7)
| S.No. | X1 | Y1 | Pixel Plotted |
| 1 | 2 | 3 | 2,3 |
| 2 | 3 | 3+5/7 => 26/7 => 26/7=>3.71 | 3,4 |
| 3 | 4 | 3.71 + 5/7 = 4.42 | 4,4 |
| 4 | 5 | 4.42 + 5/7 =5 .13 | 5,5 |
| 5 | 6 | 5.13 + 5/7 =5.84 | 6,6 |
| 6 | 7 | 5.84 + 5/7 = 6.55 | 7,7 |
| 7 | 8 | 6.55+5/7=7.26 | 8,7 |
| 8 | 9 | 7.26+5/7=7.97 | 9,8 |
The algorithm would stop here as we have reached the end point of the line (9,8)