Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем
или .
Решение представляется в виде:
, ,
где и - концы разлагаемого отрезка,
- начальное значение для очередного шага вдоль отрезка.
Этот метод, используемый для разложения отрезков в растр, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо 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 от нового значения у}