Ilustración para rastrear las 8 octavas en el algoritmo de línea de Bresenham

Posted on by Rudeus Greyrat

Prerrequisito: Algoritmo de generación de líneas de Bresenham

En este artículo, entenderemos cómo se usa el algoritmo de línea de Bresenham para encontrar todas las octavas.

Para comprender el algoritmo, se considera solo el caso en el que las coordenadas de los dos puntos  P 0 (x 0 , y 0 ) y P 1 (x 1 , y 1 ) son tales que  x 0 < x 1 e  y 0 < y 1 . La tarea es encontrar todos los puntos intermedios necesarios para dibujar una línea  P 0 (x 0 , y 0 ) y P 1 (x 1 , y 1 ) en la pantalla de píxeles de la computadora.

A continuación se muestra el algoritmo utilizado en el algoritmo de línea de Bresenham:

plotLine(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    DE = 2*dy
    DNE = 2(dy - dx)
    y = y0
    x = x0
    plot(x, y)
    while (x < x1)
        if D > 0
            D = D + DNE
            y = y + 1
        else
               D = D + DE
        end if
        x = x + 1
        plot(x, y)
    end while

Los siguientes son los cambios que se deben hacer para trazar una línea en otras octavas:

  • Octava 1: Ninguna.
  • Octava 2: Cambia los roles de x e y.
  • Octava 3: Cambia los roles de x e y; Utilice la regla (8).
  • Octava 4: Dibujar de P1 a P0; Utilice la regla (8).
  • Octava 5: Dibuja de P1 a P0.
  • Octava 6: Dibujar de P1 a P0; Utilice la regla (2).
  • Octava 7: Cambia los roles de x e y; Utilice la regla (4).
  • Octava 8: Usa y = y – 1.

A continuación se muestra la ilustración de la primera octava:

P0 = (5, 8) y P1 = (9, 11)
dx = x1 – x0 = 9 – 5 = 4
dy = y1 – y0 = 11 – 8 = 3
D = 2*dy – dx = 2(3) – 4 = 2
DE = 2*dy = 2*3 = 6
DNE = 2(dy – dx) = 2(3 – 4) = -2

Inicialmente, trace (x 0 , y 0 ) que es (5, 8)

  • parcela(5, 8)
  • D = 2 -> NE está seleccionado -> plot(6, 9) -> D = 2 + DNE = 2 – 2 = 0.
  • D = 0 -> E está seleccionado -> plot(7, 9) -> D = 2 + DE = 0 + 6 = 6.
  • D = 6 -> NE está seleccionado -> plot(8, 10) -> D = 6+ DNE = 6 – 2 = 4.
  • D = 4 -> NE está seleccionado -> plot(9, 11) -> D = 4 + DNE = 4 – 2 = 2.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (5, 8), (6, 9), (7, 9), (8, 10), (9, 11).

A continuación se muestra la ilustración de la segunda octava:

P0 = (2, 6) y P1 = (5, 15)

=> Realice los siguientes pasos para la tercera octava:

  • Cambiar los roles de x e y significa intercambiar (x0, y0) e intercambiar (x1, y1) y mientras trazamos tenemos que trazar (y, x)
  • Los nuevos puntos se convierten en P0 = (6, 2) y P1 = (15, 5)

dx = x1 – x0 = 15 – 6 = 9
dy = y1 – y0 = 5 – 2 = 3
D = 2*dy – dx = 2(3) – 9 = 6 – 9 = -3
DE = 2*dy = 2 *3 = 6
DNE = 2(dy – dx) = 2(3 – 9) = -12

Inicialmente, tenemos que graficar (y 0 , x 0 ) que es (2, 6)

  • Parcela (2, 6).
  • D = -3 -> E está seleccionado -> plot(2, 7) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> Se selecciona NE -> plot(3, 8).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E está seleccionado -> plot(3, 9) -> D = -9 + DE = -9 + 6 = -3.
  • D = -3 -> E está seleccionado -> plot(3, 10) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> Se selecciona NE -> plot(4, 11).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E está seleccionado -> plot(4, 12) -> D = -9 + DE = -9 + 6 = -3.
  • D = -3 -> E está seleccionado -> plot(4, 13) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> Se selecciona NE -> plot(5, 14).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E está seleccionado -> plot(5, 15) -> D = -9 + DE = -9 + 6 = -3.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (2, 6), (2, 7), (3, 8), (3, 9), (3, 10), (4, 11), (4, 12), (4, 13) ), (5, 14), (5, 15).

A continuación se muestra la ilustración para la tercera octava:

P0 = (-2, 4) y P1 = (-6, 12)

Realice los siguientes pasos para la tercera octava:

  • Cambiar los roles de x e y = intercambiar (x0, y0) e intercambiar (x1, y1) y mientras trazamos tenemos que trazar (y, x)
  • Use y = y – 1 = tenemos que usar y = y – 1 en lugar de y = y + 1 y dy = -dy.
  • Los nuevos puntos se convierten en P0 = (4, -2) y P1 = (12, -6)

dx = x1 – x0 = 12 – 4 = 8
dy = y1 – y0 = -6 – (-2) = -4

Tenemos que hacer dy = -dy. Por lo tanto, dy = +4

D = 2*dy – dx = 2(4) – 8 = 8 – 8 = 0
DE = 2*dy = 2*4 = 8
DNE = 2(dy – dx) = 2(4 – 8) = -8

Inicialmente, tenemos que graficar (y 0 , x 0 ) que es (-2, 4)

  • Parcela (-2, 4).
  • D = 0 -> E está seleccionado -> plot(-2, 5) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> Se selecciona NE -> plot(-3, 6).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E está seleccionado -> plot(-3, 7) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> Se selecciona NE -> plot(-4, 8).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E está seleccionado -> plot(-4, 9) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> Se selecciona NE -> plot(-5, 10).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E está seleccionado -> plot(-5, 11) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> Se selecciona NE -> plot(-6, 12).-> D = 8 + DNE = 8 + -8 = 0.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (-2, 4), (-2, 5), (-3, 6), (-3, 7), (-4, 8), (-4, 9), (-5, 10), (-5, 11), (-6, 12).

A continuación se muestra la ilustración de la cuarta octava:

P0 = (-2, 1) y P1 = (-6, 3)

Realice los siguientes pasos para la cuarta octava:

  • Dibujar de P1 a P0 = intercambiar (P0, P1).
  • Use y = y – 1 = tenemos que usar y = y – 1 en lugar de y = y + 1 y dy = -dy.
  • Los nuevos puntos se convierten en P0 = (-6, 3) y P1 = (-2, 1) */

dx = x1 – x0 = -2 – (-6) = 4
dy = y1 – y0 = 1 – 3 = -2

Tenemos que hacer dy = -dy. Por lo tanto, dy = +2

D = 2*dy – dx = 2(2) – 4 = 4 – 4 = 0
DE = 2*dy = 2*2 = 4
DNE = 2(dy – dx) = 2(2 – 4) = -4

Inicialmente, tenemos que graficar (x0, y0) que es (-6, 3)

  • Parcela (-6, 3).
  • D = 0 -> E está seleccionado -> plot(-5, 3) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> Se selecciona NE -> plot(-4, 2).-> D = 4 + DNE = 4 + -4 = 0.
  • D = 0 -> E está seleccionado -> plot(-3, 2) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> Se selecciona NE -> plot(-2, 1).-> D = 4 + DNE = 4 + -4 = 0.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (-6, 3), (-5, 3), (-4, 2), (-3, 2), (-2, 1).

A continuación se muestra la ilustración de la quinta octava:

P0 = (-3, -1) y P1 = (-9, -3)

Realice los siguientes pasos para la quinta octava:

  • Dibujar de P1 a P0 = intercambiar (P0, P1).
  • Los nuevos puntos se convierten en P0 = (-9, -3) y P1 = (-3, -1)

dx = x1 – x0 = -3 – (-9) = 6
dy = y1 – y0 = -1 – (-3) = 2
D = 2*dy – dx = 2(2) – 6 = 4 – 6 = – 2
DE = 2*dy = 2*2 = 4
DNE = 2(dy – dx) = 2(2 – 6) = -8

Inicialmente, tenemos que graficar (x0, y0) que es (-9, -3)

  • Parcela(-9, -3).
  • D = -2 -> E está seleccionado -> plot(-8, -3) -> D = -2 + DE = -2 + 4 = 2.
  • D = 2 -> Se selecciona NE -> plot(-7, -2).-> D = 2 + DNE = 2 + -8 = -6.
  • D = -6 -> E está seleccionado -> plot(-6, -2) -> D = -6 + DE = -6 + 4 = -2.
  • D = -2 -> E está seleccionado -> plot(-5, -2) -> D = -2 + DE = -2 + 4 = 2.
  • D = 2 -> Se selecciona NE -> plot(-4, -1).-> D = 2 + DNE = 2 + -8 = -6.
  • D = -6 -> E está seleccionado -> plot(-3, -1) -> D = -6 + DE = -6 + 4 = -2.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (-9, -3), (-8, -3), (-7, -2), (-6, -2), (-5, -2), (-4, -1 ), (-3, -1).

A continuación se muestra la ilustración de la sexta octava:

P0 = (-1, -2) y P1 = (-3, -6)

Realice los siguientes pasos para la sexta octava:

  • Dibujar de P1 a P0 = intercambiar (P0, P1).
  • Cambie los roles de x e y = swap (x0, y0) y swap (x1, y1) y mientras graficamos tenemos que graficar (y, x).
  • Los nuevos puntos se convierten en P0 = (-6, -3) y P1 = (-2, -1)

dx = x1 – x0 = -2 – (-6) = 4
dy = y1 – y0 = -1 – (-3) = 2
D = 2*dy – dx = 2(2) – 4 = 4 – 4 = 0
DE = 2*dy = 2*2 = 4
DNE = 2(dy – dx) = 2(2 – 4) = -4

Inicialmente, tenemos que graficar (y0, x0) que es (-3, -6)

  • Parcela(-3, -6).
  • D = 0 -> E está seleccionado -> plot(-3, -5) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> Se selecciona NE -> plot(-2, -4).-> D = 4 + DNE = 4 + -4 = 0.
  • D = 0 -> E está seleccionado -> plot(-2, -3) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> Se selecciona NE -> plot(-1, -2).-> D = 4 + DNE = 4 + -4 = 0.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (-3, -6), (-3, -5), (-2, -4), (-2, -3), (-1, -2).

A continuación se muestra la ilustración de la séptima octava:

P0 = (2, -5) y P1 = (4, -10)

Realice los siguientes pasos para la séptima octava:

  • Cambie los roles de x e y = swap (x0, y0) y swap (x1, y1) y mientras graficamos tenemos que graficar (y, x).
  • Dibujar de P1 a P0 = intercambiar (P0, P1).
  • Use y = y – 1 = tenemos que usar y = y – 1 en lugar de y = y + 1 y dy = -dy.
  • Los nuevos puntos se convierten en P0 = (-10, 4) y P1 = (-5, 2)

dx = x1 – x0 = -5 -(-10) = 5
dy = y1 – y0 = 2 – 4 = -2

Tenemos que hacer dy = -dy. Por lo tanto, dy = +2

D = 2*dy – dx = 2(2) – 5 = 4 – 5 = -1
DE = 2*dy = 2(2) = 4
DNE = 2(dy – dx) = 2(2 – 5) = – 6

Inicialmente, tenemos que graficar (y0, x0) que es (4, -10)

  • Parcela(4, -10).
  • D = -1 -> E está seleccionado -> plot(4, -9) -> D = -1 + DE = -1 + 4 = 3.
  • D = 3 -> Se selecciona NE -> plot(3, -8).-> D = 3 + DNE = 3 + -6 = -3.
  • D = -3 -> E está seleccionado -> plot(3, -7) -> D = -3 + DE = -3 + 4 = 1.
  • D = 1 -> Se selecciona NE -> plot(2, -6).-> D = 1 + DNE = 1 + -6 = -5.
  • D = -5 -> E está seleccionado -> plot(2, -5) -> D = -5 + DE = -5 + 4 = -1.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (-4, 10), (-4, 9), (-3, 8), (-3, 7), (-2, 6), (-2, 5).

A continuación se muestra la ilustración de la octava octava:

P0 = (3, -2) y P1 = (6, -4)

Realice los siguientes pasos para la octava octava:

  • Use y = y – 1 = tenemos que usar y = y – 1 en lugar de y = y + 1 y dy = -dy.

dx = x1 – x0 = 6 – 3 = 3
dy = y1 – y0 = -4 – (-2) = -2

Tenemos que hacer dy = -dy. Por lo tanto, dy = +2

D = 2*dy – dx = 2(2) – 3 = 4 – 3 = 1
DE = 2*dy = 2*2 = 4
DNE = 2(dy – dx) = 2(2 – 3) = -2

Inicialmente, tenemos que graficar (x 0 , y0) que es (3, -2)

  • Parcela(3, -2).
  • D = 1 -> NE está seleccionado -> plot(4, -3) -> D = 1 + DNE = 1 + (-2) = -1.
  • D = -1 -> Se selecciona E -> plot(5, -3).-> D = -1 + DE = -1 + 4 = 3.
  • D = 3 -> NE está seleccionado -> plot(6, -4) -> D = 3 + DNE = 3 + -2 = 1.
  • x = x1, así que salga del ciclo while.

Los puntos trazados son (3, -2), (4, -3), (5, -3), (6, -4).

Publicación traducida automáticamente

Artículo escrito por yasaswinipandu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *