Уроки онлайн
Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) кооординаты зависит от квадранта (рис.4.1.). Общий алгоритм может быть оформлен в следующем виде:
Обобщенный целочисленный алгоритм Брезенхема квадрантов
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
все переменные считаются целыми
Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно
инициализация переменных
x = x1
y = y1
Dx = abs(x2 - x1)
Dy = abs(y2 - y1)
s1 = Sign(x2 - x1)
s2 = Sign(y2 - y1)
обмен значений Dx и Dy в зависимости от углового коэффициента наклона отрезка
if Dy < Dx then
Врем = Dx
Dx = Dy
Dy = Врем
Обмен = 1
else
Обмен = 0
end if
инициализация e с поправкой на половину пиксела
e = 2*Dy - Dx
основной цикл
for i = 1 to Dx
Plot(x,y)
while(e =>0)
if Обмен = 1 then
x = x + s1
else
y = y + s2
end if
e = e - 2*Dx
end while
if Обмен = 1 then
y = y + s2
else
x = x + s1
end if
e = e + 2*Dy
next i
finish
![]() |
Рис.4.1. Разбор случаев для обобщенного алгоритма Брезенхема.
Пример 4.1. обобщенный алгоритм Брезенхема.
Для иллюсрации рассмотрим отрезок из точки (0,0) в точку (-8, -4).
начальные установки
x = 0
y = 0
Dx = 8
Dy = 4
s1 = -1
s2 = -1
Обмен = 0
е = 0
результаты работы пошагового цикла
i | Plot | е | x | y |
0 | 0 | 0 | ||
1 | (0,0) | |||
-16 | 0 | -1 | ||
-8 | -1 | -1 | ||
2 | (-1,-1) | |||
0 | -2 | -1 | ||
3 | (-2,-1) | |||
-16 | -2 | -2 | ||
-8 | -3 | -2 | ||
4 | (-3,2) | |||
0 | -4 | -2 | ||
5 | (-4,2) | |||
-16 | -4 | -3 | ||
-8 | -5 | -3 | ||
6 | (-5,-3) | |||
0 | -6 | -3 | ||
7 | (-6,-3) | |||
-16 | -6 | -4 | ||
-8 | -7 | -4 | ||
8 | (-7,-4) | |||
0 | -8 | -4 |
![]() |
Рис.4.2. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.
На рис. 4.2 продемонстрирован результат. Сравнение с рис. 2.2 показывает, что результаты работы двух алгоритмов отличаются.
В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.
Алгоритм Брезенхема для генерации окружности.