Алгоритм Брезенхема для растрового представления отрезка. Особенность модифицированного алгоритма Брезенхема.


При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксель. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. Так если одна из координат в процессе работы изменяется на 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) определится номером квадранта.