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