Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.
Отрезок проводится между двумя точками — и , где в этих парах указаны столбец и строка соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вправо и вниз, причём горизонтальное расстояние превосходит вертикальное , то есть наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждого столбца x между и определить, какая строка y ближе всего к линии, и нарисовать точку .
Общая формула линии между двумя точками:
Поскольку мы знаем колонку , то строка получается округлением к целому следующего значения:
Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что уменьшается от и за каждый шаг мы добавляем к единицу и добавляем к значение наклона (в нашем случае значение наклона будет отрицательным числом):
которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же y, либо уменьшаем его на 1.
Что из этих двух выбрать — можно решить, отслеживая значение ошибки, которое означает — вертикальное расстояние между текущим значением y и точным значением y для текущего x. Всякий раз, когда мы увеличиваем x, мы увеличиваем значение ошибки на величину наклона s, приведённую выше. Если ошибка превысила 0.5, линия стала ближе к следующему y, поэтому мы уменьшаем y на единицу, одновременно уменьшая значение ошибки на 1. В реализации алгоритма, приведённой ниже, plot(x,y)
рисует точку, а abs
возвращает абсолютную величину числа:
function line(x0, x1, y0, y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) real error := 0 real deltaerr := deltay / deltax int y := y0 int diry := y1 - y0 if diry > 0 diry = 1 if diry < 0 diry = -1 for x from x0 to x1 plot(x,y) error := error + deltaerr if error >= 0.5 y := y + diry error := error - 1.0
Проблема такого подхода — в том, что с вещественными величинами, такими как error
и deltaerr
, компьютеры работают относительно медленно. Кроме того, при вычислениях с плавающей точкой может накапливаться ошибка. По этим причинам лучше работать только с целыми числами. Это можно сделать, если умножить все используемые вещественные величины на deltax
. Единственная проблема — с константой 0.5 — но в данном случае достаточно умножить обе части неравенства на 2. Получаем следующий код:
function line(x0, x1, y0, y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) int error := 0 int deltaerr := deltay int y := y0 int diry := y1 - y0 if diry > 0 diry = 1 if diry < 0 diry = -1 for x from x0 to x1 plot(x,y) error := error + deltaerr if 2 * error >= deltax y := y + diry error := error - deltax
Умножение на 2 для целых чисел, представленных в дополнительном коде, можно реализовать битовым сдвигом влево. Однако, если число отрицательное, представленное в прямом либо обратном кодах, возможно возникновение искажений результата. В частности, в случае прямого кода, при сдвиге может быть обнулён бит знака. При представлении отрицательного числа в обратном коде, при битовом сдвиге влево, станут равны нулю все младшие биты результата, что приведёт к его уменьшению (т.е. к увеличению абсолютного значения), относительно ожидаемого.
Теперь мы можем быстро рисовать линии, направленные вправо-вниз с величиной наклона меньше 1. Осталось распространить алгоритм на рисование во всех направлениях. Это достигается за счёт зеркальных отражений, то есть заменой знака (шаг в 1 заменяется на −1), обменом переменных x и y, обменом координат начала отрезка с координатами конца.
Также существует алгоритм Брезенхэма для рисования окружностей. По методу построения он похож на рисование линии. В этом алгоритме строится дуга окружности для первого квадранта, а координаты точек окружности для остальных квадрантов получаются симметрично. На каждом шаге алгоритма рассматриваются три пикселя, и из них выбирается наиболее подходящий путём сравнения расстояний от центра до выбранного пикселя с радиусом окружности.
// R - радиус, X1, Y1 - координаты центра int x := 0 int y := R int delta := 1 - 2 * R int error := 0 while (y >= 0) drawpixel(X1 + x, Y1 + y) drawpixel(X1 + x, Y1 - y) drawpixel(X1 - x, Y1 + y) drawpixel(X1 - x, Y1 - y) error = 2 * (delta + y) - 1 if ((delta < 0) && (error <= 0)) delta += 2 * ++x + 1 continue if ((delta > 0) && (error > 0)) delta -= 2 * --y + 1 continue delta += 2 * (++x - y--)
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .