Инкрементные алгоритмы. Алгоритм Брезенхэма вывода прямой линии

Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселов путем добавления приращений координат. Приращения рассчитываются на основе анализа функции погрешности. В цикле выполняются только целочисленные операции сравнения и сложения/вычитания. Достигается повышение быстродействия для вычисления каждого пиксела по сравнению с прямым способом.

Алгоритм Брезенхэма – это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками.

Следует выбрать, восьмисвязный или же четырёхсвязный алгоритм использовать.

Смысл алгоритма состоит в том, что мы выбираем, какую точку закрасить по соседству с той, в которой сейчас стоит перо на основании ошибки. Например, если «ошибка» по x составила больше 0.5, то мы прибавляем (или же вычитаем) значение x на 1, то есть перемещаем перо или влево, или вправо.

Один из вариантов алгоритма Брезенхэма:

xerr:=0; yerr:=0;

dx:=x2-x1; dy:=y2-y1;

Если dx>0, то incX:=1;

dx=0, то incX:=0;

dx<0, то incX:=-1;

Если dy>0, то incY:=1;

dy=0, то incY:=0;

dy<0, то incY:=-1;

dx:=|dx|; dy:=|dy|;

Если dx>dy, то d:=dx иначе d:=dy;

x:=x1; y:=y1;

Закрасить пиксел с координатами (x, y);

Выполнить d раз цикл:

xerr:=xerr+dx;

yerr:=yerr+dy;

Если xerr>=d, то xerr:=xerr-d, x:=x+incX;

Если yerr>=d, то yerr:=yerr-d, y:=y+incY;

Закрасить пиксел с координатами (x, y).

Брезенхэм предложил подход [54, 55], позволяющий разрабатывать так называемые инкрементные алгоритмы растеризации. Основной целью для разра­ботки таких алгоритмов было построение циклов вычисления координат на основе только целочисленных операций сложения/вычитания без использо­вания умножения и деления. Уже известны инкрементные алгоритмы не только для отрезков прямых, но и для кривых линий [33, 55].

Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселов путем добавления приращений координат. Приращения рассчитываются на основе анализа функции погрешности. В цикле выполняются только целочисленные операции сравнения и сложе­ния/вычитания. Достигается повышение быстродействия для вычислений каждого пиксела по сравнению с прямым способом. Один из вариантов алго­ритма Брезенхэма:

Рассмотрим пример работы приведенного выше алгоритма Брезенхэма для отрезка (х1у1 - х2у2) = (2,3 - 8,6). Этот алгоритм восьмисвязный, то есть при вычислении приращений координат для перехода к соседнему пикселу возможны восемь случаев (рис. 3.3).

Известны также четырехсвязные алгоритмы (рис. 3.4).

Четырехсвязные алгоритмы проще, но они генерируют менее качественное

изображение линий за большее количество тактов роботы. Для приведенного

примера четырехсвязный алгоритм работает 10 тактов, а восьмисвязный —

только 7.