Método de cálculo del algoritmo lineal de Bresenham

Línea recta dibujada por el algoritmo de línea recta de Bresenham Supongamos que necesitamos dibujar una línea recta desde este punto (x0, y0) hasta otro punto en la esquina inferior derecha (x1, y1), donde x e y representan sus abscisas y ordenadas respectivamente, x 1- x0 > y1 - y0 Aquí utilizamos el sistema de coordenadas comúnmente utilizado en sistemas informáticos, es decir, el valor de la coordenada X aumenta hacia la derecha a lo largo del eje X y el valor de la coordenada Y aumenta hacia abajo a lo largo del eje Y.

¿Entonces los valores de X e Y aumentan hacia la parte inferior derecha respectivamente, y la distancia horizontal entre los dos puntos es x1? X0, la distancia vertical es y1-y0. Se puede observar que la pendiente de la recta debe estar entre 1 y 0. El propósito de este algoritmo es encontrar la columna Y correspondiente a la fila X entre x0 y x1, obteniendo así un punto de píxel de modo que la posición del punto de píxel sea la más cercana a la línea recta original.

Para una recta formada por (x0, y0) y (x1, y1), la fórmula es la siguiente:

Por lo tanto, para cada punto de x, el valor de y es

Debido a que X e Y son ambos números enteros, pero no cada punto X corresponde a un número entero, no es necesario calcular el valor de Y correspondiente a cada punto y 0, solo necesitamos averiguar cuál El valor hará que Y aumente en 1 cuando X alcance este valor. Si X aún no ha alcanzado este valor, Y permanecerá sin cambios. En cuanto a cómo encontrar el valor de x relevante, depende de la pendiente. El método de cálculo de la pendiente es m = (y1? y0) / (x1? x0). Debido a que este valor no cambia, se puede calcular con anticipación antes de la operación para reducir el número de operaciones.

Para implementar este algoritmo necesitamos calcular el error entre cada píxel y la línea recta. En el ejemplo anterior, el error debería ser la diferencia entre el valor Y del píxel correspondiente en cada punto X y el valor Y real de la línea. Cada vez que el valor de x aumenta en 1, el valor del error aumenta en m. Siempre que el valor del error excede 0,5, la línea recta se acerca al siguiente punto de la imagen, por lo que el valor de y aumenta en 1 y el error. disminuye en 1.

El siguiente pseudocódigo es una expresión simple de este algoritmo (donde plot(x,y) traza los puntos y abs devuelve el valor absoluto). Aunque se utilizan costosas operaciones de punto flotante, es fácil cambiar a operaciones con números enteros (consulte la sección Optimización para obtener más detalles):

Líneas de función (x0, x1, y0, y1)

int deltax := x1 - x0

int deltay := y1 - y0

Error real:= 0

Deltaerr real := deltay/deltax //Asumir deltax ! = 0 (no vertical),

//Nota: Es necesario conservar la parte decimal del resultado de la división.

int y := y0

Para x de x0 a x1

Trazar(x,y)

Error:=Error + error incremental

Si abs (error) ≥ 0,5, entonces

y := y + 1

Error:=error - 1,0