Алгоритм вывода прямой линии.

→Это растровый алгоритм для отрезка прямой линии.

Предположим, что x₁,x₂;y₁,y₂—координаты концов прямой для вывода линии необходимо запросить в определенный цвет все пиксели вдоль линии. Для того, чтобы закрасить каждый пиксель необходимо знать его координаты. Наиболее просто нарисовать отрезок горизонтальной и вертикальной линии. Вычисления текущих координат пикселей здесь выполняется как приращение по оси Х, до тех пор пока Х, не станет равен Х2; в цикле выполняются простейшие операции над целыми числами (приращение на единицу и сравнение). Поэтому операция рисования отрезка выполняется быстро и просто, вследствие этого эта операция используется как базовая для других операций. (Например, алгоритм заполнения полигонов и т.д.)

→Прямого вычисления координат (для отрезка)

Пусть заданы координаты конечных точек прямой. Найдем координаты точки внутри отрезка.

x =f(y):

x=x₁+(y-y₁)-(x₂-x₁)/ (y₂-y₁);

y=F(x):

x=y₁+(x-x₁)-(y₂-y₁)/ (x₂-x₁)

В зависимости от угла наклона прямой выполняется цикл расчетов координат по оси Х или Y.

Достоинства способа вычисления координат:

1. простота, ясность построения алгоритма.

2. возможность работать с нецелыми значениями координат отрезка.

Недостатки:

1. использование операции с плавающей точкой и целочисленные операции умножения и деления обуславливают малую скорость работы.

2. при вычислительном процессе путем добавления приращения может накапливаться ошибка.

→Инкрементный алгоритм вычисления координат:

О н предложен Брезенхем. Основной целью для разработки таких алгоритмов было построение циклов вычисления координат на основе только целочисленных операций сложения и вычитания, без умножения и деления. Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселей, путем добавления приращения координат. Приращение рассчитываются на основе анализа функции погрешности, в цикле выполняется только целочисленные операции. Это операции сравнения, сложения и вычитания, следовательно, повышения быстродействия, для вычисления любого пикселя, по сравнению с прямым способом вычисления координат; предположим, что есть отрезок с координатами [x₁; y₁] и [x₂;y₂].

dx=x₂-x₁

dy=y₂-y₁

Будем сравнивать:

dx>0 => x+1 dy>0 => y+1

dx=0 => x+0 dy=0 => y+0

dx<0 => x-1 dy<0 => y-1

Этот алгоритм является 8-ми связанным, т.е. пути вычисления приращений координат для перехода к соседним пикселям возможны 8 вариантов.

Существует также 4х связный алгоритм. Он проще, но генерирует менее качественное изображение за большое количество этапов.