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

Для получения общего алгоритма растровой развертки необходимо избавиться от ограничений, которые мы до сих пор накладывали на расположение отрезка на плоскости, а именно от требования 0< =k< =1.

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

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

Пример процедуры общего алгоритма Брезенхема для восьмисвязной развертки отрезка:

Procedure Line_8 (x1, y1, x2, y2: integer);

Var

x, y, s 1, s2, dx, dy, e, z: integer;

change: boolean;

Begin

x: =xl; y: =y1; dx: =abs(x2-xl); dy: =abs(y2-yl);

s1: =sign(x2-x1); s2: =sign(y2-y1);

if dy> dx then

begin

z: =dx; dx: =dy; dy: =z; change: =false;

end

else change: =false;

e: =2*(dy-dx);

for i: =1 to dx do

begin

PutPixel (x, у, color);

While e> =0 do begin

if change then x: =x+sl else y: =y+s2; e: =se-2*dx

end;

if change then y: ==y+s2 else x: =x+sl;

e: =e+2*dy

end;

PutPixel (x, у, color)

End.

Функция sign возвращает значения -1, 0, +1 для отрицательного, нулевого и положительного аргумента соответственно (реализована не во всех версиях Паскаля).