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

Алгоритм Брезенхе́ма— это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхэмом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.

Алгоритм

Отрезок проводится между двумя точками — и , где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние превосходит вертикальное , то есть наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между и , определить, какая строка y ближе всего к линии, и нарисовать точку .

Общая формула линии между двумя точками:

Поскольку мы знаем колонку , то строка получается округлением к целому следующего значения:

Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что растёт от и за каждый шаг мы добавляем к единицу и добавляем к значение наклона

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же y, либо увеличиваем его на 1.