DDA Algorithm-
DDA Algorithm is the simplest line drawing algorithm.
Given the starting and ending coordinates of a line,
DDA Algorithm attempts to generate the points between the starting and ending coordinates.
Procedure-
Given-
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using DDA Algorithm involves the following steps-
Step-01:
Calculate ΔX, ΔY and M from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
M = ΔY / ΔX
Step-02:
Find the number of steps or points in between the starting and ending coordinates.
if (absolute (ΔX) > absolute (ΔY))
Steps = absolute (ΔX);
else
Steps = absolute (ΔY);
Step-03:
Suppose the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1).
Find the next point by following the below three cases-
Step-04:
Keep repeating Step-03 until the end point is reached or the number of generated new points
(including the starting and ending points) equals to the steps count
PRACTICE PROBLEMS BASED ON DDA ALGORITHM-
Problem-01:
Calculate the points between the starting point (5, 6) and ending point (8, 12).
Solution-
Given-
Starting coordinates = (X0, Y0) = (5, 6)
Ending coordinates = (Xn, Yn) = (8, 12)
Step-01:
Calculate ΔX, ΔY and M from the given input.
ΔX = Xn – X0 = 8 – 5 = 3
ΔY =Yn – Y0 = 12 – 6 = 6
M = ΔY / ΔX = 6 / 3 = 2
Step-02:
Calculate the number of steps.
As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6
Step-03:
As M > 1, so case-03 is satisfied.
Now, Step-03 is executed until Step-04 is satisfied.
Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1)
5 6 5.5 7 (6, 7)
6 8 (6, 8)
6.5 9 (7, 9)
7 10 (7, 10)
7.5 11 (8, 11)
8 12 (8, 12)
Bresenham Line Drawing Algorithm-
Given the starting and ending coordinates of a line,
Bresenham Line Drawing Algorithm attempts to generate the points between the starting and ending
coordinates.
Procedure-
Given-
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using Bresenham Line Drawing Algorithm involves the following steps-
Step-01:
Calculate ΔX and ΔY from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
Step-02:
Calculate the decision parameter P k.
It is calculated as-
Pk = 2ΔY – ΔX
Step-03:
Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).
Find the next point depending on the value of decision parameter P k.
Follow the below two cases-
Step-04:
Keep repeating Step-03 until the end point is reached or number of iterations equals to (ΔX-1) times.
PRACTICE PROBLEMS BASED ON BRESENHAM LINE DRAWING ALGORITHM-
Problem-01:
Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).
Solution-
Given-
Starting coordinates = (X0, Y0) = (9, 18)
Ending coordinates = (Xn, Yn) = (14, 22)
Step-01:
Calculate ΔX and ΔY from the given input.
ΔX = Xn – X0 = 14 – 9 = 5
ΔY =Yn – Y0 = 22 – 18 = 4
Step-02:
Calculate the decision parameter.
Pk
= 2ΔY – ΔX
=2x4–5
=3
So, decision parameter Pk = 3
Step-03:
As Pk >= 0, so case-02 is satisfied.
Thus,
Pk+1 = Pk + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
Xk+1 = Xk + 1 = 9 + 1 = 10
Yk+1 = Yk + 1 = 18 + 1 = 19
Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 4 times.
(Number of iterations = ΔX – 1 = 5 – 1 = 4)
Pk Pk+1 Xk+1 Yk+1
9 18
3 1 10 19
1 -1 11 20
-1 7 12 20
7 5 13 21
5 3 14 22
Mid Point Line Drawing Algorithm-
Given the starting and ending coordinates of a line,
Mid-Point Line Drawing Algorithm attempts to generate the points between the starting and ending
coordinates.
Procedure-
Given-
Starting coordinates = (X0, Y0)
Ending coordinates = (Xn, Yn)
The points generation using Mid Point Line Drawing Algorithm involves the following steps-
Step-01:
Calculate ΔX and ΔY from the given input.
These parameters are calculated as-
ΔX = Xn – X0
ΔY =Yn – Y0
Step-02:
Calculate the value of initial decision parameter and ΔD.
These parameters are calculated as-
Dinitial = 2ΔY – ΔX
ΔD = 2(ΔY – ΔX)
Step-03:
The decision whether to increment X or Y coordinate depends upon the flowing values of D initial.
Follow the below two cases-
Step-04:
Keep repeating Step-03 until the end point is reached.
For each Dnew value, follow the above cases to find the next coordinates.
PRACTICE PROBLEMS BASED ON MID POINT LINE DRAWING ALGORITHM-
Problem-01:
Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).
Solution-
Given-
Starting coordinates = (X0, Y0) = (20, 10)
Ending coordinates = (Xn, Yn) = (30, 18)
Step-01:
Calculate ΔX and ΔY from the given input.
ΔX = Xn – X0 = 30 – 20 = 10
ΔY =Yn – Y0 = 18 – 10 = 8
Step-02:
Calculate Dinitial and ΔD as-
Dinitial = 2ΔY – ΔX = 2 x 8 – 10 = 6
ΔD = 2(ΔY – ΔX) = 2 x (8 – 10) = -4
Step-03:
As Dinitial >= 0, so case-02 is satisfied.
Thus,
Xk+1 = Xk + 1 = 20 + 1 = 21
Yk+1 = Yk + 1 = 10 + 1 = 11
Dnew = Dinitial + ΔD = 6 + (-4) = 2
Similarly, Step-03 is executed until the end point is reached.
Dinitial Dnew Xk+1 Yk+1
20 10
6 2 21 11
2 -2 22 12
-2 14 23 12
14 10 24 13
10 6 25 14
6 2 26 15
2 -2 27 16
-2 14 28 16
14 10 29 17
10 30 18
