Digital Differential Analyzer Algorithm (DDA)

By | February 17, 2022
0 Comment

Digital Differential Analyzer Algorithm (DDA)

  • The digital differential analyzer (DDA) is an incremental scan conversion method that is based on calculating either Δx or Δy.
  • This algorithm generates line from their differential equations.
  • The name ‘DDA‘ comes from the mechanical device that is used to solve differential equations by numerical methods. It finds out successive (x, y) values by simultaneously incrementing x and y by small steps proportional to the first derivative of x and y.
  • Given the endpoints (x1, y1) and (x2, y2) of a line segment, we know the slope m is represented as :

m = y2 – y1 / x2 – x1

  • If (xi, yi) and (xi+1, yi+1) are the two consecutive points lying on this line segment, slope m can also be expressed as:

m = yi+1 – yi / xi+1 – xi

Thus, we can say yi+1 – yi = Δy and xi+1 – xi = Δx

∴ m =Δy / Δx

  • In DDA algorithm, the line is sampled at unit interval in one coordinate and corresponding integer value (nearest to the line path) is then calculated for the other coordinate i.e. either Δx = 1 or Δy = 1.

Digital Differential Analyzer (DDA) Algorithm

  • Consider a line with positive slope (i.e. x1 < x2 and y1 < y2). The line processed from left endpoint to the right endpoint.
  • If slope m of a line is less than equal to 1 i.e. | m |≤1 or lΔyl < IΔxl, we sample the line at unit x interval i.e. Δx=1.
  • Therefore, Δy calculated as:

Δy = m . Δx

∴ Δy = m

  • As a result the coordinate values of next point (xi+1, yi+1) calculated as:

xi+1 = xi + Δx

yi+1 = yi + Δy

Substituting Δx = 1 and Δy = m, we get :

xi+1 = xi + 1

yi+1 = yi + m

  • If slope m of a line is greater than 1 i.e. I ml>1 or lΔyl > IΔxl, we sample the line at unit y interval i.e. Δy = 1.
  • Therefore Δx  is calculated as :

Δx = Δy / m

Δx = 1 / m

  • Substituting Δx = 1/m and Δy = 1 in equation, we get:

xi+1 = xi + 1/m

yi+1 = yi + 1

  • Now consider a line with negative slope (i.e. x2 < x1 and y2 < y1). The line processed from right endpoint to left endpoint.
  • If the slope m of line is less than equal to 1 i.e. I m l≤1 then Δx = -1 and Δy = – m

Thus the value of (xi+1, yi+1) are :

xi+1 = xi – 1

yi+1 = yi – m

  • If the slope m of a line is greater than 1 i.e. I m >1 then Δx = -1/m and Δy = 1. The coordinate values of next point are :

xi+1 = xi – 1/m

yi+1 = yi – 1

Advantage of Digital Differential Analyzer Algorithm

  1. Digital Differential Analyzer algorithm is faster than the direct use of line equation as it calculate points on the line without any floating point multiplication.

Disadvantages of DDA algorithm

  1. It is time consuming as it deals with rounding off operation and floating point arithmetic.
  2. It is orientation dependent, because of this the endpoint accuracy is poor.

[su_button url=”https://h-educate.in/wp-content/uploads/2022/02/Digital-Differential-Analyzer-Algorithm.pdf” background=”#0ba600″ color=”#ffffff” size=”10″ wide=”yes”]Download as Pdf[/su_button]

Algorithm for DDA in programming

Given the endpoints of a line segment : (x1, y1) and (x2, y2), the following steps are used to plot a line :

1. Input the two endpoint coordinates (x1, y1) and (x2, y2)

2. Calculate the value of dx and dy :

dx = x2 – x1

dy = y2 – y1

3. Set the running coordinates (x, y) to the starting value (x1, y1).

4. Determine the length of a line.

If abs (dx) ≥ abs (dy) then

set length = abs (dx)

else

set length = abs (dy)

5. Calculate the incremental values in x and y directions as :

Δx = dx / length

Δy = dy / length

6. Plot the point at current (x, y) location.

7. Calculate the Δx and Δy for subsequent points as :

i = 1
while (i ≤ length)
{
Plot (integer (x), integer (y))
x = x + Δx
y = y + Δy
i = i+1
}

Flowchart of Digital Differential Analyzer Algorithm (DDA)

FlowChart of DDA Algorithm

Related posts:-

[su_posts template=”templates/list-loop.php” posts_per_page=”3″ taxonomy=”link_category” tax_operator=”NOT IN” order=”
desc”]