Алгоритм Brezenhema. 
Алгоритм Брезенхема

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

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

Рис. 1. Основная идея алгоритма Брезенхема

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

Рис. 2. График погрешности в алгоритме Брезенхема

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

е = -1 / 2 +3 / 8 = -1 / 8.

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

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

Приведем алгоритм Брезенхема для первого октанта, т. е. для случая 0 Ј Dy Ј Dx.

Алгоритм Брезенхема разложения в растр отрезка для первого октанта предполагается, что концы отрезка (x1, y1) и (x2, y2) не совпадают.

Integer — функция преобразования в целое х, у, Dx, Dy — целые е — настоящее инициализация переменных х = x1.

у = y 1.

Dx = x2-x1.

Dy = y2-y1.

Инициализация с поправкой на половину пиксела е = Dy/Dx-½.

начало основного цикла для г = 1, чтобы Dx.

участок (х, у) в то время как (е => 0).

у = у +1.

е = е-1.

конец в то время как х = х +1.

е = е + Dy / Dx.

Затем я отделка Блок-схема алгоритма на рис. 3. Пример приведен ниже.

Пример 1. Алгоритм Брезенхема.

Рассмотрим отрезок, проведенный из точки (0,0) в точку (5,5). Расписание отрезка в растр по алгоритму Брезенхема приводит к такому результату:

начальные установки х = 0.

у = 0.

Dx = 5.

Два = 5.

= 1−½ = ½.

Результаты работы пошагового цикла.

Рис. 3. Алгоритмы Блок-схема Brezenhema

Результат показан на рис. 4 совпадает с ожидаемым. Заметим, что точка растра с координатами (5,5) не активизирована. Эту точку можно активировать путем изменения цикла for-next на 0 to Dx. Активация точки (0,0) можно устранить, если поставить оператор Plot непосредственно перед строкой next i.

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