Алгоритм Брезенхема. 
Компьютерная графика

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

Алгоритм построен так, что требуется проверить лишь знак этой ошибки. На рисунке 5 это иллюстрируется для отрезка в первом октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от 0 до 1. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше, чем ½, то пересечение с прямой x = 1 будет расположено ближе к прямой y = 1, чем к прямой y = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше ½, то верно обратное. Для углового коэффициента, равного ½, нет какого либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).

Не все отрезки проходят через точки растра. Подобная ситуация иллюстрируется на рисунке 6, где отрезок с тангенсом угла наклона 3/8 сначала походит через точку растра (0,0) и последовательно пересекает три пикселя. Также иллюстрируется вычисление ошибки при представлении отрезка дискретными пикселями.

Так как желательно проверять только знак ошибки, то она первоначально устанавливается равной -½. Таким образом, если угловой коэффициент отрезка больше или равен ½, то величина ошибки в следующей точке растра с координатами (1,0) может быть вычислена как e = e + m, где m — угловой коэффициент. В нашем случае при начальном значении ошибки -½: e = ½ + 3/8 = -1/8.

Так как е отрицательно, отрезок пройдет ниже середины пиксела. Следовательно, пиксел на том же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому у не увеличивается. Аналогично вычисляем ошибку e = -1/8 + 3/8 = ј в следующей точке растра (2,0). Теперь е положительно, значит отрезок пройдет выше средней точки. Растровый элемент (2,1) со следующей по величине координатой у лучше аппроксимирует положение отрезка. Следовательно у увеличивается на 1. Прежде чем рассматривать следующий пиксел, необходимо откорректировать ошибку вычитанием из нее 1. Имеем e = ¼ — 1 = -¾.

Заметим, что пересечение вертикальной прямой x = 2 с заданным отрезком лежит на ¼ ниже прямой у = 1. Если же перенести отрезок ½ вниз, мы получим как раз величину -¾. Продолжение вычислений для следующего пиксела дает e = -¾ + 3/8 = -3/8.

Так как e отрицательно, то y не увеличивается. Из всего сказанного следует, что ошибка — это интервал, отсекаемый по оси y рассматриваемым отрезком в каждом растровом элементе (относительно -½).

Парабола

Для реализации параболы в растровом виде используется алгоритм Брезенхема в координатах.

• 1) Задаются стартовые данные. X, Y=0 — основание параболы. Д=0 коэффициент ошибки. Н=20 высота параболы. I=0 порядковый номер для сохранения координаты точки в матрицу.
• 2) Запускается цикл обсчета точек.

Точка правой ветви:

Точка левой ветви:

Логические условия:

В зависимости от выполнение 1 из 2 логических условий идет пересчет следующей пары точек и коэффициента ошибки. График растровой параболы отображен на рисунке 7.

Гипербола

Для отображения гиперболы в растровой графике используем алгоритм Брезенхема:

• 1) Задаем начальные данные (). Х0 и У0 кардинаты фокуса. А, В растояние от фокуса до вершин дуг гиперблы.
• 2) Абсчет стартовых араметров:

3) Запускаем цикл:. В котором обсчитываем точки гиперболы:; ;;. Делаем проверку по 2 логическим условиям в зависимости от рзультата делаем дальнейший обсчет:

Изображение гиперболы в растровой графике приведено на рисунке 8.