Иллюстрация для отслеживания всех 8 октав в линейном алгоритме Брезенхема.
Предварительное условие: Алгоритм генерации линий Брезенхэма
В этой статье мы поймем, как линейный алгоритм Брезенхема используется для нахождения всех октав.
При понимании алгоритм рассматривает только случай, когда координаты двух точек 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) = -4We 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 = -2We 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 = -2We 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) = -2We 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).