3.2. Цифровой дифференциальный анализатор
Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем
или 
.
Решение представляется в виде:
, 
,
где
и
- концы разлагаемого отрезка,
- начальное значение
для очередного шага вдоль отрезка.
Этот метод, используемый для разложения отрезков в растр, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо x, либо y (большее из приращений) выбирается в качестве единицы растра.
Рассмотрим пример процедуры, реализующий алгоритм ЦДА:
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 угла вещественное число.
Более применим алгоритм Брезенхема.
3.3. Алгоритм Брезенхема
Данный алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо 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
3.4. Целочисленный алгоритм Брезенхема
Алгоритм Брезенхема в том виде, как он представлен выше, требует использования арифметики с плавающей точкой и деления (для вычисления углового коэффициента и оценки ошибки). Известно, что операции с вещественными числами осуществляются гораздо медленнее, чем с целыми. Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. С этой целью в алгоритме переменные e и d умножаются на целое число 2n. Таким образом, изменив масштаб переменных и внеся корректировки в неравенства, получим целочисленную версию алгоритма Брезенхема:
x:=x1; y:=y1; n:=x2-x1; m:=y2-y1; dx:=2m; dy:= 2n; e:=0;
for i:=1 to n do
begin
x:=x+1; e:=e+dx
if e>n then
begin
y:=y+1; e:=e-dy
end;
PutPixel (x,y)
end