Реферат: Сравнительные характеристики трёх наиболее эффективных алгоритмов рисования отрезка

Sign - функция, возвращающая -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно

аппроксимируем длину отрезка

if abs(x2 - x1) >= abs(y2 - y1) then

Длина = abs(x2 - x1) else

Длина = abs(y2 - y1) end

полагаем большее из приращений x или y равными единице растра

x = (x2 - x1) // Длина

y = (y2 - y1) // Длина

округляем величины, а не отбрасываем дробную часть

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

x = x1 + 0.5 * Sign(x)

y = y1 + 0.5 * Sign(y)

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

i =1

while (i <= Длина)

вывод точки PutPixel (Integer(x), Integer(y))

x = x + x

y = y + y

i = i + 1

end

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

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

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

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

равного 1/2, нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1, 1).

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

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