При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксель. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. Так если одна из координат в процессе работы изменяется на 1, то изменение другой может быть различным (0 или 1) и зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Это расстояние называют ошибкой. Суть работы алгоритма заключается в проверке знака ошибки. Рассмотрим построение отрезка в первом октанте (угловой коэффициент в диапазоне от 0 до 1). Из Рис.4 видно, что если угловой коэффициент (?=? y/? x) отрезка из т.(0,0) > 1/2, то точка его пересечения с прямой х=1 будет ближе к прямой y=1, чем y=0. Т.о. для построения очередной точки лучше использовать т.(1,1), чем (1,0). Если ?<1/2, то наоборот. Если ?=1/2 то выбор падает на т.(1,1).
Некоторые отрезки не проходят точно через точки растра (например, на Рис. 5 показана ситуация, когда пересекаются три пикселя, или дискретные пиксели). В этом случае также вычисляется результирующая ошибка (исходная e = -1/2): ? рез=? исх+ ?. Если значение отрицательно, то отрезок пройдет ниже середины пикселя (координата Y не меняется), а если >0, то выше (координата Y увеличится). Алгоритм Брезенхема для разложения отрезка в растр можно на псевдокоде описать так:
Предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
Integer — функция преобразования в целое
x, y, ? x, ? y — целые
e — вещественное
инициализация переменных
x = x1, y = y1, ? x = x2 — x1, ?y = y2 — y1
инициализация e с поправкой на половину пиксела
e = ? y/? x — 1/2
начало основного цикла
for I = 1 to ? x
Plot (x, y)
while (e ? 0)
y = y + 1
e = e — 1
end while
x = x + 1
e = e + ? y/? x
next I
finish
Примечание! В данном способе имеются неудобства (арифметика с плавающей точкой и операции деления) при вычислении углового коэффициента и оценке ошибки. Поэтому в 1965 году Брезенхемом предложен простой алгоритм, использующий целочисленную арифметику. Суть в следующем.
Для увеличения быстродействия сначала произведем преобразование:
= 2?е??x. Затем подставим его в алгоритм для первого октанта (рассмотренный ранее):
. . .
инициализируем с поправкой на половину пикселя
= 2 * ? y — ? x
начало основного цикла
for I = 1 to ? x
Plot (x, y)
while ( ? 0)
y = y + 1
= — 2 * ? x
end while
x = x + 1
= + 2 * ? y
next I
finish
Модифицируем алгоритм для обработки отрезка в любом октанте. Определим номер квадранта (где находится отрезок) и угловой коэффициент. Если последний > 1, то y изменяется на 1. Критерий ошибки Брезенхема используется для установления x. Величина (1 или -1) определится номером квадранта.