Обобщенный целочисленный алгоритм Брезенхема квадрантов

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

Целочисленный алгоритм Брезенхема для первого октанта

Целочисленный алгоритм Брезенхема

Алгоритм Брезенхема в том виде, как он представлен выше, требует использования арифметики с плавающей точкой и деления (для вычисления углового коэффициента и оценки ошибки). Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. Так как важен лишь знак ошибки, то простое преобразование

e'= 2еDх

превратит предыдущий алгорим в целочисленный и позволит эффективно реализовать его на аппаратном или микропрограммном уровне. Модифицированный целочисленный алгоритм для первого октанта, т. е. для 0<=Dy<=Dx таков:

предполагается, что концы отрезка (х1, у1) и (х2, у2) не совпадают и все переменные - целые

х = х1

у=у1

Dх = у2 - х1

Dу = у2 - х1

инициализируем е' с поправкой на половину пиксела

e' = 2*Dy - Dx

начало основного цикла

for i = 1 to Dх

Plot (x,y)

while (e' > 0)

у = у + 1

e' = e' - 2 *Dx

end while

x = x + 1

e' = e' + 2 * Dу

next i

finish

Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, у постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины х. Выбор постоянно изменяющейся (на +1 или -1) координаты зависит от квадранта.

Предполагается:

· концы отрезка (х1, у1) и (х2, у2) не совпадают;

· все переменные считаются целыми;

· функция Sign возвращает -1,0, 1 для отрицательного, нулевого и положительного аргумента соответственно.

инициализация переменных: х=х1 у=у1 Dх = abs (х2 - х1) Dу = abs (у2 - у1) s1 = Sign (х2 - х1) s2 = Sign (у2 - у1) обмен значений х и у в зависимости от углового коэффициента наклона отрезка: if Dу > Dх then Врем = Dх Dх = Dу Dу = Врем Обмен =1 else Обмен = 0 end if

Разбор случаев для обобщённого алгоритма Брезенхема.

инициализация е' с поправкой на половину пиксела:

e' = 2 * Dу - Dх

основной цикл:

for i = 1 to Dх

Plot(x, у)

while (e' >= 0)

If Обмен = 1 then

x = x + s1

else

y = y + s2

end if

e' = e' - 2 * Dх

end while

If Обмен = l then

у = у + s2

else

x = x + s1

end if

e' = e' + 2* Dy

next i

finish