Algoritmos en rectas

La computación gráfica es el campo de la informática visual, donde podemos utilizar computadoras y así generar imágenes visuales y espaciales del mundo real o no tan reales. También se puede definir como el arte que transmite información usando imágenes que son generadas mediante la computación esto logra ser una herramientas importantes como lo es en ingeniería de sistemas utilizando algoritmos de implementación en rectas.

En este artículo se hablará sobre algunos algoritmos de implementación en rectas pero esto comienza entendiendo como los gráficos por computador se emplean en una gran variedad de aplicaciones, como en interfaces gráficas de usuario, tipografía digital, aplicaciones médicas y juegos de vídeo, entre otras. El tipo de gráfico, se usan algoritmos especializados que permiten ventajas con respecto al resultado que se desea obtener, en el presente caso se mencionan los algoritmos que son utilizados para imágenes rasterizadas, las cuales permiten mostrar transiciones suaves de colores y sombras.

Algoritmos de implementación en rectas, dibujar líneas rectas

Este algoritmo nos indica como una línea recta que en realidad se refiere a un segmento de línea. Debemos conocer la posición de los dos puntos finales de un segmento de línea, mostrar este segmento de línea en una pantalla rasterizada es el objetivo de la rasterización de línea recta. El algoritmo puede lograr una rasterización directa, pero uno de los problemas es que la eficiencia no es alta. La ecuación utilizada al recorrer x para calcular y tiene una multiplicación (k * x), y esto afectará en gran medida la eficiencia de representación. Para ver una explicación completa pueden ingresar al siguiente video Video explicativo.

Algoritmos de implementación en rectas , algoritmo DDA (Analizador diferencial digital)

Podemos decir que el analizador diferenciador digital (DDA – Digital Differential Analyzer) es un algoritmo que tiene una implementación digital de un analizador diferencial. Es el hardware o el software usado para la interpolación lineal de variables sobre un intervalo entre principio y punto final. Los DDA se usan para la rasterización de líneas, triángulos y polígonos. En su realización más simple, el algoritmo DDA interpola valores en el intervalo calculando para cada x las ecuaciones.

El objetivo es unir los dos puntos para obtener una recta (línea), este concepto abstracto es fácilmente entendible por los humanos, pero una máquina no entiende de conceptos, es aquí donde entra el algoritmo DDA, que se encarga de generar una sucesión de puntos finita que le brinda a la máquina las instrucciones para “dibujar” la respectiva línea.

DDA es usado principalmente porque calcula la “posición” de la siguiente coordenada X y Y a nivel de píxel, una vez se alcanza el punto final, se forma la imagen “recta” que es interpretada por nuestro cerebro como una línea. Para ver una explicación completa pueden ingresar al siguiente video Video explicativo.

En su realización más simple, el algoritmo DDA interpola valores en el intervalo calculando para cada x las ecuaciones.

x = x+1/m, y = y + m, donde  ?x = x – x, ?y = y – y y m = ?y/?x

?x = x – x y ?y = y – y y m = ?y/?x

Es necesario definir 2 puntos los cuales están compuestos cada uno por 2 valores, que llevados al plano cartesiano corresponden a X y Y, visto en una imagen de papel nuestro X es el ancho y Y es el alto, con respecto a un punto de referencia se ubican ambos puntos.

Algoritmos de implementación en rectas , algoritmo de Bresenham

El algoritmo de Bresenham es construir el centro de píxeles como una línea de cuadrícula virtual, calcular el punto de intersección de la línea recta y cada línea de cuadrícula vertical en el orden del punto inicial de la línea recta hasta el punto final, y luego determinar el punto más cercano de esta columna de píxeles en la columna de píxeles de acuerdo con el signo del término de error Píxeles. Es un algoritmo preciso para la generación de líneas de rastreo que convierte mediante rastreo las líneas, al utilizar solo cálculos incrementales con enteros que se pueden adaptar para desplegar circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican las columnas de pixel. Para ver una explicación completa pueden ingresar al siguiente video Video explicativo.

Este algoritmo es uno de los más efectivos para dibujar líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente píxel a dibujar en la generación de una línea, se describe a continuación:

1. Dependiendo del valor que tome el Parámetro Constante P se evalúa y determina la coordenada a dibujar.
2. Calcular los parámetros que permiten decidir cuál será el próximo pixel a dibujar (Delta X, Delta Y y Constante P).
3. Dibujar el primer píxel correspondiente al extremo izquierdo de la línea (P1).
4. Trazar el píxel cuyo valor de Y de la línea de rastreo se aproxima más a la trayectoria de la línea. Se capturan los dos extremos de la línea  P1(Xo, Yo) y P2(Xf, Yf).
5.  Se desplaza una columna (incrementando la posición en X).
6. Punto inicial  P1(Xo, Yf).

Diferencias entre los Algoritmos DDA y Bresenham

• El algoritmo de DDA usa multiplicación y división de ecuaciones, pero el algoritmo de Bresenham solo usa resta y suma.
• El algoritmo de Bresenham es mucho más preciso y eficiente que DDA.
• DDA usa puntos flotantes mientras que el algoritmo de Bresenham usa puntos fijos.
• El algoritmo de Bresenham puede dibujar círculos y curvas con mucha más precisión que DDA.
• DDA redondea las coordenadas al entero más cercano, pero el algoritmo de Bresenham no lo hace.
• DDA usa multiplicación y división de ecuaciones, pero el algoritmo de Bresenham solo usa resta y suma.

Autor: Julieth Paola Pachón López

Editor: Carlos Felipe Pinzón Romero

Código: UCCG – 9.2

Universidad: Universidad Central

Fuentes:

Informática. (2020, 18 noviembre). Algoritmo Básico para Dibujar Rectas [Vídeo]. YouTube. https://www.youtube.com/watch?v=5gcAKpEaMt8

Diferencia entre DDA y algoritmo de Bresenham. (s.f.). STREPHONSAYS
https://es.strephonsays.com/dda-and-vs-bresenham-algorithm-5881

Guerra Crespo, H. [ profesorCrespo]. (2020, 7 noviembre). Algoritmo recta algoritmo bresenham, analisis primera parte [Vídeo]. YouTube. 
https://www.youtube.com/watch?v=hN1QiMYnzJA

Torres, G., Curiel, A., Monroy, J. (s.f.). GRAFICACIÓN Apuntes Digitales. CIDECAME. http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro23/232_algoritmo_dda.html

Adlab13.  (2016). Algoritmo de Bresenham. GRAFICA2016A. 
http://quegrande.org/apuntes/EI/OPT/GC/teoria/00-01/apuntes_completos.pdf

Duque, E. [Edwin Duque]. (2019, 1 febrero). Algoritmo para trazado de linea por computador Bresenham [Vídeo]. YouTube. 
https://www.youtube.com/watch?v=2_BCYD_FwII

Algoritmo de Bresenham. (2020, 12 de Febrero). en Sitio Web de Héctor E. Medellín Anaya. http://galia.fc.uaslp.mx/~medellin/Applets/LineasRectas/Recta.htm

Torres, G., Curiel, A., Monroy, J. (s.f.). GRAFICACIÓN Apuntes Digitales. CIDECAME.
https://programmerclick.com/article/7758561825/

Torres, G., Curiel, A., Monroy, J. (s.f.). GRAFICACIÓN Apuntes Digitales. CIDECAME. 
https://programmerclick.com/article/6348855911/

Saenz Marin, F. (2013, 5 marzo). Dibujo de líneas rectas [Imagen]. Algoritmo básico incremental. 
http://saenz-marin-gr.blogspot.com/2013/03/lineas-rectas.html

Problemática del trazado de las líneas rectas. (2021, 1 julio). [Imagen]. https://es.wikipedia.org/wiki/Algoritmo_de_Bresenham

Algoritmo de Línea DDA. (2018, 13 febrero). [Imagen]. Algoritmo de Línea DDA. https://2018graficacion.wordpress.com/2018/02/09/algoritmo-de-linea-dda/