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

Хотя данный алгоритм первоначально был разработан для цифровых графических построителей, он в равной степени подходит для растровых устройств.

Алгоритм выбирает оптимальные растры из координат для построения отрезка. В процессе работы одна из координат либо X, либо Y, в зависимости от углового коэффициента изменяется на 1, изменение другой координаты равно нулю или единице. Это зависит от расстояния действий положения отрезков, ближайшим координатам сетки.

Алгоритм построен так, что требуется только проверить знак ошибки. Проиллюстрируем на рисунке для отрезка, лежащего в диапазоне от 0 до 1.

≤ ≤ 1

Ошибка = ошибка + .

На рисунке можно увидеть, что угловой коэффициент из точки (0.0) > 1/2.

Приведём алгоритм для первого октанта.

х, y, , Δу – целые

е – вещественное

1) инициализация переменных

х = х₁

у = у₁

Δх = х₂-х₁

Δу = у₂-у₁

е = Δу*Δх-1/2

2) начало основного цикла

for i:=1 to Δx

plot (x,y)

while (e>0)

y = y+1;

e = e-1;

and while

x = x+1

e = e+

end;

Обобщённый целочисленный алгоритм

Предполагается, что концы отрезка не совпадают и все переменные считаются целыми. Функция sign возвращает -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно.

Инициализация переменных:

х = х1

у = у1

Δх = abs (x₂-x₁)

Δy = abs (y₂-y₁)

S1 = sign (x₂-x₁)

S2 = sign (y₂-y₂)

Обмен значений Δх и Δу в зависимости от углового коэффициента наклона отрезка.

if Δy > Δx then

временная = Δx

Δх = Δу

Δу = временная