Algoritmo de generación de línea DDA en gráficos por computadora

En cualquier plano bidimensional, si conectamos dos puntos (x0, y0) y (x1, y1), obtenemos un segmento de línea. Pero en el caso de los gráficos por computadora, no podemos unir directamente dos puntos de coordenadas cualquiera, para eso, debemos calcular las coordenadas de los puntos intermedios y poner un píxel para cada punto intermedio, del color deseado con la ayuda de funciones como putpixel(x , y, K) en C , donde (x,y) es nuestra coordenada y K denota algún color.
Ejemplos: 
 

Input: For line segment between (2, 2) and (6, 6) :
we need (3, 3) (4, 4) and (5, 5) as our intermediate
points.

Input: For line segment between (0, 2) and (0, 6) :
we need (0, 3) (0, 4) and (0, 5) as our intermediate
points.

Para usar funciones gráficas, la pantalla de salida de nuestro sistema se trata como un sistema de coordenadas en el que la coordenada de la esquina superior izquierda es (0, 0) y, a medida que avanzamos hacia abajo, nuestra ordenada y aumenta, y a medida que avanzamos hacia la derecha, nuestra ordenada x aumenta para cualquier punto (x, y). 
Ahora, para generar cualquier segmento de línea necesitamos puntos intermedios y para calcularlos podemos usar un algoritmo básico llamado algoritmo de generación de línea DDA (analizador diferencial digital) .
 

// C program for DDA line generation
#include<stdio.h>
#include<graphics.h>
#include<math.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;
    DDA(2, 2, 14, 16);
    return 0;
}

# 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()
 
 
if __name__ == "__main__":
   
    # coordinates of 1st point
    x0, y0 =  20, 20
 
    # coordinates of 2nd point
    x1, y1 = 60, 50
    DDA(x0, y0, x1, y1)
 
    # This code is contributed by 111arpit1

#include <iostream>
//#include<graphics.h>
//#include<time.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 function
int main() {
    //initwindow(3000,1000);
    int x0 = 200, y0 = 180, x1 = 180, y1 = 160;
     
    DDALine(x0, y0, x1, y1);
    //getch();
    //closegraph();
   
    return 0;
}
 
//all functions regarding to graphichs.h are commented out
//contributed by hopelessalexander