Общий алгоритм Брезенхема

Общий алгоритм Брезенхема - student2.ru

Чтобы реализация алгоритма Брезенхема была полной необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделатть, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициепт. Когда абсолютная величина углового коэффициента больше 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 в зависимости от углового коэффициента наклона отрезка

ify < 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

Общий алгоритм Брезенхема - student2.ru

Рис.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
Общий алгоритм Брезенхема - student2.ru

Рис.4.2. Результат работы обобщенного алгоритма Брезенхема в третьем квадранте.

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

В следующем разделе рассматривается алгоритм Брезенхема для генерации окружности.

Наши рекомендации