Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

general
communitycreator

What is the Digital Differential Analyzer algorithm?

Vijay Vardhan Koka

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The Digital Difference Analyzer (DDA) algorithm is used to draw lines on a screen in an incrementally. The algorithm is called the Digital Difference Analyzer because it interpolates points based on the difference between the start and end points. The algorithm itself is very easy to understand and implement.

Algorithm

1. Start
2. Get the ends points of the line (x1, y1) and (x2, y2).
3. Calculate,
             dx = x2 - x1
             dy = y2 - y1

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

4. len = abs(dx) > abs(dy) ? abs(dx):abs(dy)

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

5. Calculate,
             xinc = dx / len
             yinc = dy / len

Now, all that’s left is to create a loop to interpolate 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 color at the coordinates (x, y).

6.
    x = x1
    y = y1
    loop while x < x2:
         setpixel(x, y)
         x += xinc
         y += yinc
7. End

This algorithm can be implemented using multiple languages and libraries. Some I would recommend are:

  • pygame (Python)
  • SDL/SFML/SDL_BGI (C/C++)

RELATED TAGS

general
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring