Иллюстрация для отслеживания всех 8 октав в линейном алгоритме Брезенхема.

Опубликовано: 23 Сентября, 2022

Предварительное условие: Алгоритм генерации линий Брезенхэма

В этой статье мы поймем, как линейный алгоритм Брезенхема используется для нахождения всех октав.

При понимании алгоритм рассматривает только случай, когда координаты двух точек P 0 (x 0 , y 0 ) и P 1 (x 1 , y 1 ) такие, что x 0 < x 1 и y 0 < y 1 . Задача состоит в том, чтобы найти все промежуточные точки, необходимые для рисования линии P 0 (x 0 , y 0 ) и P 1 (x 1 , y 1 ) на экране компьютера пикселей.

Ниже приведен алгоритм, используемый в линейном алгоритме Брезенхэма:

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

Ниже приведены изменения, которые необходимо сделать, чтобы провести линию в других октавах:

  • Октава 1: Нет.
  • Октава 2: Поменяйте местами x и y.
  • Октава 3: Поменяйте местами x и y; Используйте правило (8).
  • Октава 4: рисовать от P1 до P0; Используйте правило (8).
  • Октава 5: рисуйте от P1 до P0.
  • Октава 6: рисовать от P1 до P0; Используйте правило (2).
  • Октава 7: Поменяйте местами x и y; Используйте правило (4).
  • Октава 8: Используйте y = y – 1.

Ниже приведена иллюстрация для первой октавы:

P0 = (5, 8) and  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

Сначала постройте (x 0 , y 0 ) , который равен (5, 8)

  • сюжет(5, 8)
  • D = 2 -> выбран NE -> plot(6, 9) -> D = 2 + DNE = 2 – 2 = 0.
  • D = 0 -> E выбрано -> plot(7, 9) -> D = 2 + DE = 0 + 6 = 6.
  • D = 6 -> выбран NE -> plot(8, 10) -> D = 6+ DNE = 6 – 2 = 4.
  • D = 4 -> выбран NE -> plot(9, 11) -> D = 4 + DNE = 4 – 2 = 2.
  • x = x1, поэтому выйдите из цикла.

Нанесены точки (5, 8), (6, 9), (7, 9), (8, 10), (9, 11).

Ниже приведена иллюстрация для второй октавы:

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

=> Perform the following steps for the third octave:

  • Switch roles of x and y mean swap(x0, y0) and swap(x1, y1) and while plotting we have to plot(y, x)
  • New points become P0 = (6, 2) and  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

Первоначально мы должны построить (y 0 , x 0 ) , который равен (2, 6)

  • Участок(2, 6).
  • D = -3 -> E выбрано -> plot(2, 7) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> выбран NE -> plot(3, 8).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E выбрано -> plot(3, 9) -> D = -9 + DE = -9 + 6 = -3.
  • D = -3 -> E выбрано -> plot(3, 10) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> выбран NE -> plot(4, 11).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E выбрано -> plot(4, 12) -> D = -9 + DE = -9 + 6 = -3.
  • D = -3 -> E выбрано -> plot(4, 13) -> D = -3 + DE = -3 + 6 = 3.
  • D = 3 -> выбран NE -> plot(5, 14).-> D = 3 + DNE = 3 + -12 = -9.
  • D = -9 -> E выбрано -> plot(5, 15) -> D = -9 + DE = -9 + 6 = -3.
  • x = x1, поэтому выйдите из цикла.

На графике нанесены точки (2, 6), (2, 7), (3, 8), (3, 9), (3, 10), (4, 11), (4, 12), (4, 13). ), (5, 14), (5, 15).

Ниже приведена иллюстрация для третьей октавы:

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

Perform the following steps for the third octave:

  • Switch roles of x and y = swap(x0, y0) and swap(x1, y1) and while plotting we have to plot(y, x)
  • Use y = y – 1 = we have to use y = y – 1 instead of y = y + 1 and dy = -dy.
  • New points become P0 = (4, -2) and  P1 = (12, -6)

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

We have to make dy = -dy. Therefore, 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

Первоначально мы должны построить (y 0 , x 0 ), что равно (-2, 4)

  • Участок (-2, 4).
  • D = 0 -> E выбрано -> plot(-2, 5) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> выбран NE -> plot(-3, 6).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E выбрано -> plot(-3, 7) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> выбран NE -> plot(-4, 8).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E выбрано -> plot(-4, 9) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> выбран NE -> plot(-5, 10).-> D = 8 + DNE = 8 + -8 = 0.
  • D = 0 -> E выбрано -> plot(-5, 11) -> D = 0 + DE = 0 + 8 = 8.
  • D = 8 -> выбран NE -> plot(-6, 12).-> D = 8 + DNE = 8 + -8 = 0.
  • x = x1, поэтому выйдите из цикла.

На графике нанесены точки (-2, 4), (-2, 5), (-3, 6), (-3, 7), (-4, 8), (-4, 9), (-5, 10), (-5, 11), (-6, 12).

Ниже приведена иллюстрация для четвертой октавы:

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

Perform the following steps for the fourth octave:

  • Draw from P1 to P0 = swap(P0, P1).
  • Use y = y – 1 = we have to use y = y – 1 instead of y = y + 1 and dy = -dy.
  • New points become P0 = (-6, 3) and  P1 = (-2, 1) */

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

We have to make dy = -dy. Therefore, 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

Первоначально мы должны построить (x0, y0), что равно (-6, 3)

  • Участок (-6, 3).
  • D = 0 -> E выбрано -> plot(-5, 3) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> выбран NE -> plot(-4, 2).-> D = 4 + DNE = 4 + -4 = 0.
  • D = 0 -> E выбрано -> plot(-3, 2) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> выбран NE -> plot(-2, 1).-> D = 4 + DNE = 4 + -4 = 0.
  • x = x1, поэтому выйдите из цикла.

Нанесенные точки: (-6, 3), (-5, 3), (-4, 2), (-3, 2), (-2, 1).

Ниже приведена иллюстрация для пятой октавы:

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

Perform the following steps for the fifth octave:

  • Draw from P1 to P0 = swap(P0, P1).
  • New points become P0 = (-9, -3) and  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

Первоначально мы должны построить (x0, y0), что равно (-9, -3)

  • Участок (-9, -3).
  • D = -2 -> E выбрано -> plot(-8, -3) -> D = -2 + DE = -2 + 4 = 2.
  • D = 2 -> выбран NE -> plot(-7, -2).-> D = 2 + DNE = 2 + -8 = -6.
  • D = -6 -> E выбрано -> plot(-6, -2) -> D = -6 + DE = -6 + 4 = -2.
  • D = -2 -> E выбрано -> plot(-5, -2) -> D = -2 + DE = -2 + 4 = 2.
  • D = 2 -> выбран NE -> plot(-4, -1).-> D = 2 + DNE = 2 + -8 = -6.
  • D = -6 -> E выбрано -> plot(-3, -1) -> D = -6 + DE = -6 + 4 = -2.
  • x = x1, поэтому выйдите из цикла.

Нанесенные точки: (-9, -3), (-8, -3), (-7, -2), (-6, -2), (-5, -2), (-4, -1) ), (-3, -1).

Ниже приведена иллюстрация для шестой октавы:

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

Perform the following steps for the sixth octave:

  • Draw from P1 to P0 = swap(P0, P1).
  • Switch roles of x and y = swap(x0, y0) and swap(x1, y1) and while plotting we have to plot(y, x).
  • New points become P0 = (-6, -3) and  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

Первоначально мы должны построить (y0, x0), что равно (-3, -6)

  • Участок (-3, -6).
  • D = 0 -> E выбрано -> plot(-3, -5) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> выбран NE -> plot(-2, -4).-> D = 4 + DNE = 4 + -4 = 0.
  • D = 0 -> E выбрано -> plot(-2, -3) -> D = 0 + DE = 0 + 4 = 4.
  • D = 4 -> выбран NE -> plot(-1, -2).-> D = 4 + DNE = 4 + -4 = 0.
  • x = x1, поэтому выйдите из цикла.

Нанесенные точки: (-3, -6), (-3, -5), (-2, -4), (-2, -3), (-1, -2).

Ниже приведена иллюстрация для седьмой октавы:

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

Perform the following steps for the seventh octave:

  • Switch roles of x and y = swap(x0, y0) and swap(x1, y1) and while plotting we have to plot(y, x).
  • Draw from P1 to P0 = swap(P0, P1).
  • Use y = y – 1 = we have to use y = y – 1 instead of y = y + 1 and dy = -dy.
  • New points become P0 = (-10, 4) and  P1 = (-5, 2)

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

We have to make dy = -dy. Therefore, 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

Первоначально мы должны построить (y0, x0), что равно (4, -10)

  • Участок(4, -10).
  • D = -1 -> E выбрано -> plot(4, -9) -> D = -1 + DE = -1 + 4 = 3.
  • D = 3 -> выбран NE -> plot(3, -8).-> D = 3 + DNE = 3 + -6 = -3.
  • D = -3 -> E выбрано -> plot(3, -7) -> D = -3 + DE = -3 + 4 = 1.
  • D = 1 -> выбран NE -> plot(2, -6).-> D = 1 + DNE = 1 + -6 = -5.
  • D = -5 -> E выбрано -> plot(2, -5) -> D = -5 + DE = -5 + 4 = -1.
  • x = x1, поэтому выйдите из цикла.

Нанесенные точки: (-4, 10), (-4, 9), (-3, 8), (-3, 7), (-2, 6), (-2, 5).

Ниже приведена иллюстрация для восьмой октавы:

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

Perform the following steps for the eighth octave:

  • Use y = y – 1 = we have to use y = y – 1 instead of y = y + 1 and dy = -dy.

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

We have to make dy = -dy. Therefore, 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

Первоначально мы должны построить (x 0 , y0), который равен (3, -2)

  • Участок(3, -2).
  • D = 1 -> выбран NE -> plot(4, -3) -> D = 1 + DNE = 1 + (-2) = -1.
  • D = -1 -> E выбрано -> plot(5, -3).-> D = -1 + DE = -1 + 4 = 3.
  • D = 3 -> выбран NE -> plot(6, -4) -> D = 3 + DNE = 3 + -2 = 1.
  • x = x1, поэтому выйдите из цикла.

Нанесены точки (3, -2), (4, -3), (5, -3), (6, -4).