5. Алгоритмы Брезенхема разложения отрезков в растр. Простой алгоритм Брезенхема. Целочисленный алгоритм Брезенхема. Общий алгоритм Брезенхема

Работа алгоритма Брезенхема основывается на использовании понятия ошибка.

Ошибкой здесь называется расстояние между действительным положением отрезка и ближайшим пикселом сетки растра, который аппроксимирует отрезок на очередном шаге.

Согласно алгоритму на каждом шаге одна из координат - либо x, либо y (в зависимости от угла наклона отрезка) изменяется на единицу, изменение другой координаты (на ноль или единицу) определяется в процессе работы и зависит от значения ошибки. Таким образом, выбирается пиксел, ближе расположенный к идеальному отрезку. Поскольку при реализации алгоритма на ЭВМ удобнее анализировать не само значение ошибки, а ее знак, то истинное значение ошибки смещается на -0.5.

Простой алгоритм Брезенхема

1. Ввод исходных данных Xн,Yн,Xк,Yк
2. Проверка вырожденности отрезка. Если отрезок вырожденный, то высвечивается точка и осуществляется переход к п.8
3. Вычисление приращений dX=Xк-Xн и dY=Yк-Yн.
4. Вычисление модуля тангенса угла наклона отрезка: m=dY/dX
5. Инициализация начального значения ошибки: f=m-0,5
6. Инициализация начальных значений координат текущего пиксела: X=Xн, Y=Yн
7. Цикл от i=1 до i=dX+1 с шагом 1:
   1. Высвечивание точки с координатами (X,Y)
   2. Если f<0, то
      a) Y++
      b) f--
   3. Вычисление ошибки f=f+m
   4. X++