DDA Algorithm
Consider one point of the line as (X0, Y0) and the second point of the line as (X1, Y1).
// calculate dx , dy
dx = X1 – X0;
dy = Y1 – Y0;// Depending upon absolute value of dx & dy
// choose number of steps to put pixel as// steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy)
steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);// calculate increment in x & y for each steps
Xinc = dx / (float) steps;
Yinc = dy / (float) steps;// Put pixel for each step
X = X0;
Y = Y0;for (int i = 0; i <= steps; i++)
{
putpixel (round(X),round(Y),WHITE);
X += Xinc;
Y += Yinc;
}
Below is the implementation of the above approach:
C
// C program for DDA line generation #include <graphics.h> #include <math.h> #include <stdio.h> // Function for finding absolute value int abs(int n) { return ((n > 0) ? n : (n * (-1))); } // DDA Function for line generation void DDA(int X0, int Y0, int X1, int Y1) { // calculate dx & dy int dx = X1 - X0; int dy = Y1 - Y0; // calculate steps required for generating pixels int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy); // calculate increment in x & y for each steps float Xinc = dx / (float)steps; float Yinc = dy / (float)steps; // Put pixel for each step float X = X0; float Y = Y0; for (int i = 0; i <= steps; i++) { putpixel(round(X), round(Y), RED); // put pixel at (X,Y) X += Xinc; // increment in x at each step Y += Yinc; // increment in y at each step delay(100); // for visualization of line- // generation step by step } } // Driver program int main() { int gd = DETECT, gm; // Initialize graphics function initgraph(&gd, &gm, ""); int X0 = 2, Y0 = 2, X1 = 14, Y1 = 16; // Function call DDA(2, 2, 14, 16); return 0; } |
C++
// C++ program for DDA line generation #include <bits/stdc++.h> using namespace std; // function for rounding off the pixels int round(float n) { if (n - (int)n < 0.5) return (int)n; return (int)(n + 1); } // Function for line generation void DDALine(int x0, int y0, int x1, int y1) { // Calculate dx and dy int dx = x1 - x0; int dy = y1 - y0; int step; // If dx > dy we will take step as dx // else we will take step as dy to draw the complete // line if (abs(dx) > abs(dy)) step = abs(dx); else step = abs(dy); // Calculate x-increment and y-increment for each step float x_incr = (float)dx / step; float y_incr = (float)dy / step; // Take the initial points as x and y float x = x0; float y = y0; for (int i = 0; i < step; i++) { // putpixel(round(x), round(y), WHITE); cout << round(x) << " " << round(y) << "\n"; x += x_incr; y += y_incr; // delay(10); } } // Driver code int main() { int x0 = 200, y0 = 180, x1 = 180, y1 = 160; // Function call DDALine(x0, y0, x1, y1); return 0; } // all functions regarding to graphichs.h are commented out // contributed by hopelessalexander |
Java
// Java Code for DDA line generation public class Solution { // function for rounding off the pixels public static int round(float n) { if (n - (int) n < 0.5) return (int) n; return (int) (n + 1); } // Function for line generation public static void DDALine(int x0, int y0, int x1, int y1) { // Calculate dx and dy int dx = x1 - x0; int dy = y1 - y0; int step; // If dx > dy we will take step as dx // else we will take step as dy to draw the complete // line if (Math.abs(dx) > Math.abs(dy)) step = Math.abs(dx); else step = Math.abs(dy); // Calculate x-increment and y-increment for each step float x_incr = (float) dx / step; float y_incr = (float) dy / step; // Take the initial points as x and y float x = x0; float y = y0; for (int i = 0; i < step; i++) { // putpixel(round(x), round(y), WHITE); System.out.println(round(x) + " " + round(y)); x += x_incr; y += y_incr; // delay(10); } } // Driver code public static void main(String[] args) { int x0 = 200, y0 = 180, x1 = 180, y1 = 160; // Function call DDALine(x0, y0, x1, y1); } } // This code is contributed by ishankhandelwals. |
Python3
# Python program for DDA line generation from matplotlib import pyplot as plt # DDA Function for line generation def DDA(x0, y0, x1, y1): # find absolute differences dx = abs(x0 - x1) dy = abs(y0 - y1) # find maximum difference steps = max(dx, dy) # calculate the increment in x and y xinc = dx/steps yinc = dy/steps # start with 1st point x = float(x0) y = float(y0) # make a list for coordinates x_coorinates = [] y_coorinates = [] for i in range(steps): # append the x,y coordinates in respective list x_coorinates.append(x) y_coorinates.append(y) # increment the values x = x + xinc y = y + yinc # plot the line with coordinates list plt.plot(x_coorinates, y_coorinates, marker="o", markersize=1, markerfacecolor="green") plt.show() # Driver code if __name__ == "__main__": # coordinates of 1st point x0, y0 = 20, 20 # coordinates of 2nd point x1, y1 = 60, 50 # Function call DDA(x0, y0, x1, y1) # This code is contributed by 111arpit1 |
C#
// C# code for DDA line generation using System; public class Solution { // function for rounding off the pixels public static int Round(float n) { if (n - (int)n < 0.5) return (int)n; return (int)(n + 1); } // Function for line generation public static void DDALine(int x0, int y0, int x1, int y1) { // Calculate dx and dy int dx = x1 - x0; int dy = y1 - y0; int step; // If dx > dy we will take step as dx // else we will take step as dy to draw the complete // line if (Math.Abs(dx) > Math.Abs(dy)) step = Math.Abs(dx); else step = Math.Abs(dy); // Calculate x-increment and y-increment for each // step float x_incr = (float)dx / step; float y_incr = (float)dy / step; // Take the initial points as x and y float x = x0; float y = y0; for (int i = 0; i < step; i++) { // putpixel(round(x), round(y), WHITE); Console.WriteLine(Round(x) + " " + Round(y)); x += x_incr; y += y_incr; // delay(10); } } // Driver code public static void Main(string[] args) { int x0 = 200, y0 = 180, x1 = 180, y1 = 160; // Function call DDALine(x0, y0, x1, y1); } } // This code is contributed by ishankhandelwals |
Javascript
// JS program for DDA Line generation function round(n) { if (n - Math.floor(n) < 0.5) return Math.floor(n); return Math.floor(n + 1); }; function DDALine(x0, y0, x1, y1) { let dx = x1 - x0; let dy = y1 - y0; let step; if (Math.abs(dx) > Math.abs(dy)) step = Math.abs(dx); else step = Math.abs(dy); let x_incr = (dx / step); let y_incr = (dy / step); let x = x0; let y = y0; for (let i = 0; i < step; i++) { console.log(round(x) + " " + round(y)); x += x_incr; y += y_incr; } }; let x0 = 200, y0 = 180, x1 = 180, y1 = 160; DDALine(x0, y0, x1, y1); // This code is contributed by ishankhandelwals. |
Output:
200 180 199 179 198 178 197 177 196 176 195 175 194 174 193 173 192 172 191 171 190 170 189 169 188 168 187 167 186 166 185 165 184 164 183 163 182 162 181 161
DDA Line generation Algorithm in Computer Graphics
Introduction :
DDA (Digital Differential Analyzer) is a line drawing algorithm used in computer graphics to generate a line segment between two specified endpoints. It is a simple and efficient algorithm that works by using the incremental difference between the x-coordinates and y-coordinates of the two endpoints to plot the line.
The steps involved in DDA line generation algorithm are:
- Input the two endpoints of the line segment, (x1,y1) and (x2,y2).
- Calculate the difference between the x-coordinates and y-coordinates of the endpoints as dx and dy respectively.
- Calculate the slope of the line as m = dy/dx.
- Set the initial point of the line as (x1,y1).
- Loop through the x-coordinates of the line, incrementing by one each time, and calculate the corresponding y-coordinate using the equation y = y1 + m(x – x1).
- Plot the pixel at the calculated (x,y) coordinate.
- Repeat steps 5 and 6 until the endpoint (x2,y2) is reached.
DDA algorithm is relatively easy to implement and is computationally efficient, making it suitable for real-time applications. However, it has some limitations, such as the inability to handle vertical lines and the need for floating-point arithmetic, which can be slow on some systems. Nonetheless, it remains a popular choice for generating lines in computer graphics.
In any 2-Dimensional plane, if we connect two points (x0, y0) and (x1, y1), we get a line segment. But in the case of computer graphics, we can not directly join any two coordinate points, for that, we should calculate intermediate points’ coordinates and put a pixel for each intermediate point, of the desired color with the help of functions like putpixel(x, y, K) in C, where (x,y) is our co-ordinate and K denotes some color.
Examples:
Input: For line segment between (2, 2) and (6, 6) :
Output: we need (3, 3) (4, 4) and (5, 5) as our intermediate points.Input: For line segment between (0, 2) and (0, 6) :
Output: we need (0, 3) (0, 4) and (0, 5) as our intermediate points.
For using graphics functions, our system output screen is treated as a coordinate system where the coordinate of the top-left corner is (0, 0) and as we move down our y-ordinate increases, and as we move right our x-ordinate increases for any point (x, y). Now, for generating any line segment we need intermediate points and for calculating them we can use a basic algorithm called DDA(Digital differential analyzer) line generating algorithm.