Общий алгоритм Брезенхема

Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величины x. Выбор постоянно изменяющейся (на +1 или -1) координаты зависит от квадранта (рис. 15.1).

Обобщенный целочисленный алгоритм Брезенхема квадрантов

Предполагается, что концы отрезка (x₁, y₁) и (x₂, y₂) не совпадают
все переменные считаются целыми
функция Sign возвращает -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно
инициализация переменных
x = x₁
y = y₁
Dx = abs(x₂ - x₁)
Dy = abs(y₂ - y₁)
s₁ = Sign(x₂ - x₁)
s₂ = Sign(y₂ - y₁)
обмен значений Dx и Dy в зависимости от углового коэффициента наклона отрезка
if Dy > Dx then
    Врем = Dx
    Dx = Dy
    Dy = Врем
    Обмен = 1
else
    Обмен = 0
end if
инициализация e' с поправкой на половину пиксела
e' = 2 * Dy - Dx
основной цикл
for i = 1 to Dx
    Plot (x, y)
    while (e' >= 0)
        if Обмен = 1 then
        x = x + s₁
    else
        y = y + s₂
    end if
    e' = e' - 2 * Dx
    end while
    if Обмен = 1 then
        y = y + s₂
    else
        x = x + s₁
    end if
    e' = e' + 2 * Dy
next i
finish

Пример. Для иллюстрации общего алгоритма Брезенхема рассмотрим отрезок из точки (0, 0) в точку (-8, -4).

Начальные установки:
x = 0
y = 0
Dx = 8
Dy = 4
s₁ = -1
s₂ = -1
Обмен = 0
e = 0

Пошаговое выполнение основного цикла показано в таблице.

На рис. 15.2 продемонстрирован результат.