Este algoritmo se utiliza para escanear y convertir una línea. Fue desarrollado por Bresenham. Es un método eficiente porque implica únicamente operaciones de suma, resta y multiplicación de números enteros. Estas operaciones se pueden realizar muy rápidamente, por lo que las líneas se pueden generar rápidamente.

En este método, el siguiente píxel seleccionado es el que tiene la menor distancia desde la línea verdadera.

El método funciona de la siguiente manera:

Supongamos un píxel P₁'(X₁',y₁'), luego seleccione los píxeles siguientes a medida que avanzamos hacia la noche, una posición de píxel a la vez en la dirección horizontal hacia P₂'(X₂',y₂').

Una vez que haya un píxel, elija en cualquier paso.

El siguiente píxel es

1. O el que está a su derecha (límite inferior de la línea)
2. Uno arriba a la derecha y arriba (límite superior de la línea)

La línea se aproxima mejor mediante aquellos píxeles que se encuentran a la menor distancia del camino entre P₁',PAG₂'.

Para elegir el siguiente entre el píxel inferior S y el píxel superior T.
Si se elige S
tenemos x_yo+1=x_i+1 y y_yo+1=y_i
Si se elige T
tenemos x_yo+1=x_i+1 y y_yo+1=y_i+1

Las coordenadas y reales de la línea en x = x_yo+1es
y=mx_yo+1+b

La distancia desde S hasta la línea real en la dirección y.
s = y-y_i

La distancia de T a la línea real en la dirección y.
t = (y_i+1)-y

Ahora considere la diferencia entre estos 2 valores de distancia.
calle

cuando (st)<0 ⟹ s < t< p>

El píxel más cercano es S

Cuando (s-t) ≧0 ⟹ s

El píxel más cercano es T

Esta diferencia es
s-t = (y-yi)-[(yi+1)-y]
= 2 años - 2 años -1

Sustituyendo m por e introduciendo la variable de decisión
d_i=△x (st)
d_i=△x (2 (X_i+1)+2b-2a_i-1)
=2△xy_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.y_i+c

Donde c= 2△y+△x (2b-1)

Podemos escribir la variable de decisión d_yo+1para el próximo deslizamiento
d_yo+1=2△y.x_yo+1-2△x.y_yo+1+c
d_yo+1-d_i=2△y.(x_yo+1-X_i)- 2△x(y_yo+1-y_i)

monitor de tubo de rayos catódicos

Dado que x_(i+1)=x_i+1, tenemos
d_yo+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_yo+1-y_i)

Casos especiales

Si el píxel elegido está en el píxel superior T (es decir, d_i≧0)⟹ y_yo+1=y_i+1
d_yo+1=d_i+2△y-2△x

Si el píxel elegido está en el píxel inferior T (es decir, d_i<0)⟹ y_{i+1=yi
dyo+1=di+2△y}

Finalmente calculamos d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

desde mx₁+b-y_i=0 y m = , tenemos
d₁=2△y-△x

Ventaja:

1. Sólo implica aritmética de números enteros, por lo que es simple.

2. Evita la generación de puntos duplicados.

3. Se puede implementar mediante hardware porque no utiliza multiplicación ni división.

4. Es más rápido en comparación con DDA (Analizador Diferencial Digital) porque no implica cálculos de punto flotante como el algoritmo DDA.

Desventaja:

1. Este algoritmo está destinado únicamente al dibujo de líneas básicas. La inicialización no forma parte del algoritmo de líneas de Bresenham. Entonces, para dibujar líneas suaves, deberías buscar un algoritmo diferente.

Algoritmo de línea de Bresenham:

Paso 1: Iniciar algoritmo

novios y dfs

Paso 2: Declarar variable x₁,X₂,y₁,y₂,d,yo₁,i₂,dx,dy

Paso 3: Introduzca el valor de x₁,y₁,X₂,y₂
donde x₁,y₁son las coordenadas del punto de partida
yx₂,y₂son coordenadas del punto final

Etapa 4: Calcular dx = x₂-X₁
Calcular dy = y₂-y₁
calcular yo₁=2*tú
calcular yo₂=2*(dy-dx)
Calcular d=i₁-dx

Paso 5: Considere (x, y) como punto de partida y x_fincomo valor máximo posible de x.
si dx<0
Entonces x = x₂
y = y₂
X_fin=x₁
Si dx > 0
Entonces x = x₁
y = y₁
X_fin=x₂

Paso 6: Generar punto en coordenadas (x,y).

Paso 7: Compruebe si se genera la línea completa.
Si x > = x_fin
Detener.

Paso 8: Calcular las coordenadas del siguiente píxel.
si d<0
Entonces d = d + i₁
Si d ≧ 0
Entonces d = d + i₂
Increment y = y + 1

Paso 9: Incremento x = x + 1

Paso 10: Dibuja un punto de las últimas coordenadas (x, y)

Paso 11: Ir al paso 7

Paso 12: Fin del algoritmo

Ejemplo: Las posiciones inicial y final de la línea son (1, 1) y (8, 5). Encuentra puntos intermedios.

Solución: X₁=1
y₁=1
X₂=8
y₂=5
dx=x₂-X₁=8-1=7
tu=y₂-y₁=5-1=4
I₁=2* ∆y=2*4=8
I₂=2*(∆y-∆x)=2*(4-7)=-6
re = yo₁-∆x=8-7=1

Programa para implementar el Algoritmo de Dibujo Lineal de Bresenham:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 

Producción:

Diferenciar entre el algoritmo DDA y el algoritmo lineal de Bresenham: