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

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

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

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

y - y_0 = ((y_1-y_0)/(x_1-x_0))*(x-x_0).