Introducción al algoritmo de dibujo lineal

En este artículo, veremos un esquema del Algoritmo de dibujo lineal. El dibujo lineal en la computadora significa que la pantalla de la computadora se divide en dos filas y columnas. Esas filas y columnas también se conocen como píxeles. En caso de que tengamos que dibujar una línea en la computadora, antes que nada, necesitamos saber en qué píxeles deben estar. Una línea es una parte de una línea recta que se extiende en la dirección opuesta indefinidamente. La línea está definida por dos puntos finales. Su densidad debe estar separada de la longitud de la línea.
La fórmula para una intercepción de línea de la pendiente: Y = mx + b
En esta fórmula, m es una línea de la pendiente y b es la intersección de y en la línea. En las posiciones (x1, y1) y (x2, y2), se especifican dos puntos finales para el segmento de línea.

El valor de la pendiente myb se puede determinar en consecuencia
• m = y2 - y1 / x2 - x1
• es decir, M = Δy / Δx

Ejemplo:

Los puntos finales de línea son (0, 0) y (4, 12). Trace el resultado para calcular cada valor de y como los pasos x de 0 a 4.

Solución:

Entonces tenemos una fórmula de ecuación de línea: Y = mx + b
• m = y2 - y1 / x2 - x1
• m = 12 - 0/4 - 0
• m = 3
La intersección y b se encuentra entonces vinculando y1 y x1 a la fórmula y = 3 x + b, 0 = 3 (0) + b. Por lo tanto, b = 0, entonces la fórmula de línea y = 3x.
El objetivo es determinar la próxima ubicación x, y lo más rápido posible por la anterior.

Tipos de algoritmo de dibujo lineal

A continuación se presentan los tipos de algoritmo:

1. Algoritmo diferencial digital (DDA)

Un método de conversión incremental es un Algoritmo DDA y también lo llamamos Algoritmo Diferencial Digital (DDA). Este enfoque se caracteriza por el uso de los resultados de la etapa anterior en cada cálculo.

Veamos los ejemplos que se dan a continuación:

Ejemplo 1

La línea de punto final son (x1, y1) y (x2, y2)

  • dx = x2 - x1
  • dy = y2 - y1

entonces, ahora determinaremos la longitud de la línea si abs (dx)> = abs (dy) luego length = abs (dx) else length = abs (dy)

  • Δx = dx / longitud
  • Δy = dy / length
  • X = x1
  • Y = y1

Setpixel (redondo (x), redondo (y));

  • i = 1

mientras (i <= longitud)

  • x = x + Δx;
  • y = y + Δy;

setpixel (redondo (x), redondo (y));
i = i + 1
terminar mientras

Ejemplo # 2

Una línea de puntos finales (5, 4) y (6, 9) se puede convertir con el DDA.

Solución:
• dx = x2 - x1
• dx = 6 - 5 = 1
• dy = y2 - y1
• dy = 9 - 4

dy = 5
Como, dx <dy entonces,
• longitud = y2 - y1 = 5
• dx = (x2 - x1) / longitud = 1/5 = 0.2
• dy = (y2- y1) / longitud = 5/5 = 1
x1 y1 x2 y2 L dx dy ixy

Resultado:

X1

Y1

X2

Y2

L

Dx

Dy

yo

X

Y

Resultado

3

2

4 4

7 7

5 5

.2

1

0 0

3.5

5.5

3.5, 5.5

1

3.9

1, 5

3.9, 1.5

2

4.9

3.5

4.9, 3.5

3

5.1

7.5

5.1, 7.5

4 4

3.7

4.5 4.5

3.7, 4.5

5 5

4.5 4.5

7.5

4.5, 7.5

Limitación del algoritmo DDA

  • La aritmética para puntos flotantes y de redondeo son procedimientos que requieren mucho tiempo.
  • Un error de redondeo puede conducir a una distancia desde la verdadera ruta del segmento de línea larga por la ubicación del píxel medido.

2. El algoritmo de la línea Bresenham

El algoritmo de conversión de escaneo es el algoritmo de Bresenham. Este algoritmo ofrece la principal ventaja de usar solo cálculos enteros.

1. Puntos finales de la fila y almacenar el punto final izquierdo en (x1, y1)
2. Para el parámetro de decisión, obtener el primer valor Δx, es decir, Dx, Δy, es decir, Dy, 2 Δy y 2 Δx.
3. Inicializar el inicio
4. Inicialice i = 1 como contador,
De lo contrario, el siguiente punto para trazar es (xk + 1, yk + 1) y repita el paso 4 (Δx - 1) veces.
Ajustamiento
Para m> 1, podemos decir si aumentamos x cada vez que aumentamos y.
Después de que se resuelva la variable de decisión pk, la fórmula es muy similar, solo se reemplazarán las x e y de la ecuación.

Resumen del algoritmo de línea de Bresenham

Estas son las siguientes ventajas del algoritmo de línea de Bresenham:
• Un algoritmo incremental rápido.
• Esto usa solo cálculos enteros.
DDA tiene los siguientes problemas en comparación con el algoritmo DDA:
• La línea pixelada puede estar distante de la acumulación esperada de errores de redondeo.
• Se requiere tiempo para operaciones de redondeo y aritmética de puntos flotantes.

Artículos recomendados

Esta ha sido una guía para el Algoritmo de dibujo lineal. Aquí discutimos qué es el algoritmo de dibujo lineal junto con los diversos ejemplos. También puede consultar los siguientes artículos para obtener más información:

  1. Algoritmos de aprendizaje automático
  2. Algoritmo SVM
  3. Regresión lineal simple
  4. Regresión multivariante
  5. Comparación principal de regresión lineal versus regresión logística

Categoría:

Big Data