Алгоритм Брезенхема

Цифровой дифференциальный анализатор

Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем

или .

Решение представляется в виде:

, ,

где и - концы разлагаемого отрезка,

- начальное значение для очередного шага вдоль отрезка.

Этот метод, используемый для разложения отрезков в растр, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо Dx, либо Dy (большее из приращений) выбирается в качестве единицы растра.

Рассмотрим пример процедуры, реализующий алгоритм ЦДА:

Procedure Line

(x1,y1{начальная точка};

x2,y2{конечная точка};

x: integer);

Var

dy, dx, y, m: real;

Begin

if x1<> x2 then

begin

dy:= y2-y1;

dx:= x2-x1;

m:=dy/dx;

y:= y1;

for x:= x1 to x2 do

begin

PutPixel (x, raund(y));

y:=y+m {у увеличиваем на величину тангенса угла наклона m}

end

end {если отрезок на самом деле точка, изображаем ее, в противном случае - ошибка}

else

if y1=y2 then PutPixel (x1,y1)

else

{writeln ('Ошибка')}

End.

Трудности применения процедуры Line состоят в том, что округление y до целого значения требует времени и, кроме того, y и m должны быть вещественными переменными, т.к. tg угла вещественное число.

Более применим алгоритм Брезенхема.

Данный алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависимости от значения углового коэффициента) - изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние называется ошибкой.

Алгоритм построен так, что требуется проверить лишь знак этой ошибки. Из рис. 2 можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем ½, то его пересечение с прямой х=1 будет расположено ближе к прямой y=1, чем к прямой y=0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше ½, то верно обратное. Для углового коэффициента, равного ½, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).

Рассмотрим фрагмент программы реализующей простой алгоритм Брезенхема:

x:=x1; y:=y1; n:=x2-x1; m:=y2-y1; d:=m/n; e:=0;

for i:=1 to n do

begin {шаг по оси абсцисс и вычисление отклонения}

x:=x+1; e:=e+d;

if e>0.5 then {если отклонение по оси ординат от текущего значения у превосходит ½, то необходимо увеличить у на единицу и скорректировать отклонение e от нового значения у}

begin

y:=y+1; e:=e-1

end;

PutPixel (x,y)

end