34. Целочисленный алгоритм Брезенхема

Алгоритм Брезенхэ́ма — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в графике. Алгоритм выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо y (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (на 0 или 1) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние мы назовем ошибкой.

Алгоритм Брезенхема, работающий с действительными величинами, можно записать в следующем виде:

1. Ввод исходных данных X_н,Y_н,X_к,Y_к.

2. Проверка вырожденности отрезка. Если отрезок вырожденный, то высвечивается точка и осуществляется переход к п.10.

3. Вычисление приращений dX:=X_к-X_н и dY:=Y_к-Y_н.

4. Вычисление шага изменения каждой координаты пиксела: S_X:=sign(dX), S_Y:=sign(dY).

5. Вычисление модулей приращения координат: dX:=dX, dY:=dY

6. Обмен значений dX и dY в зависимости от углового коэффициента наклона отрезка:

если dY > dX, то выполнить Temp:=dX, dX:=dY, dY:=Temp, flag:=1; иначе flag:=0 (flag - флаг, определяющий факт обмена местами координат).

7. Инициализация начального значения ошибки:

f:= dY/dX -0,5 (для целочисленного алгоритма: f_ц=2dY-dX)

8. Инициализация начальных значений координат текущего пиксела: X:=X_н, Y:=Y_н

9. Цикл - пока Х X_к делать:

9.1. Высвечивание точки с координатами (X,Y).

9.2. Вычисление координат и корректировка ошибки для следующего пиксела:

Если f0, то если flag:=1, то X:=X+S_X иначе Y:=Y+S_Y; корректировка ошибки f:=f-1 (f_ц=f_ц-2dX)

Если f<0, то если flag:=1, то Y:=Y+S_Y иначе X:=X+S_X.

9.3. Вычисление ошибки f:=f+ dY/dX (f_ц=f_ц+2dY).

10. Конец.

Алгоритм Брезенхема требует использования арифметики с плавающей точкой и деления (для вычисления углового коэффициента и оценки ошибки). Быстродействие алгоритма можно увеличить, если использовать только целочисленную арифметику и исключить деление. Для этого выражение, например f = m - 0.5, запишем в виде: f = dY/dX-1/2 и, умножив обе части этого равенства на 2dX, получим:

2dXf = 2dY - dX.

Обозначив f_ц=2dXf, окончательно получим:

f_ц = 2dY - dX

(В соответствии с этим выражением должно вычисляться теперь начальное значение ошибки в п.7).

Тогда подсчет нового значения ошибки в п.9 "действительного" алгоритма будет производиться по формулам:

f_ц = f_ц + 2dY и f_ц = f_ц - 2dX.