Алгоритм Брезенхэма
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.
Алгоритм
Отрезок проводится между двумя точками — [math]\displaystyle{ (x_0, y_0) }[/math] и [math]\displaystyle{ (x_1, y_1) }[/math], где в этих парах указаны столбец и строка соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вправо и вниз, причём горизонтальное расстояние [math]\displaystyle{ x_1 - x_0 }[/math] превосходит вертикальное [math]\displaystyle{ y_1 - y_0 }[/math], то есть наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждого столбца x между [math]\displaystyle{ x_0 }[/math] и [math]\displaystyle{ x_1 }[/math] определить, какая строка y ближе всего к линии, и нарисовать точку [math]\displaystyle{ (x, y) }[/math].
Общая формула линии между двумя точками:
- [math]\displaystyle{ y - y_0 = \frac{y_1-y_0}{x_1-x_0}(x-x_0). }[/math]
Поскольку мы знаем колонку [math]\displaystyle{ x }[/math], то строка [math]\displaystyle{ y }[/math] получается округлением к целому следующего значения:
- [math]\displaystyle{ y = \frac{y_1-y_0}{x_1-x_0}(x-x_0) + y_0. }[/math]
Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что [math]\displaystyle{ y }[/math] уменьшается от [math]\displaystyle{ y_0 }[/math] и за каждый шаг мы добавляем к [math]\displaystyle{ x }[/math] единицу и добавляем к [math]\displaystyle{ y }[/math] значение наклона (в нашем случае значение наклона будет отрицательным числом):
- [math]\displaystyle{ s = \frac{y_1-y_0}{x_1-x_0}, }[/math]
которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же y, либо уменьшаем его на 1.
Что из этих двух выбрать — можно решить, отслеживая значение ошибки, которое означает — вертикальное расстояние между текущим значением y и точным значением y для текущего x. Всякий раз, когда мы увеличиваем x, мы увеличиваем значение ошибки на величину наклона s, приведённую выше. Если ошибка превысила 1.0, линия стала ближе к следующему y, поэтому мы увеличиваем y на 1.0, одновременно уменьшая значение ошибки на 1.0. В реализации алгоритма, приведённой ниже, plot(x,y) рисует точку, а abs возвращает абсолютную величину числа:
function line(int x0, int x1, int y0, int y1)
int deltax := abs(x1 - x0)
int deltay := abs(y1 - y0)
real error := 0
real deltaerr := (deltay + 1) / (deltax + 1)
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 >= 1.0
y := y + diry
error := error - 1.0
Проблема такого подхода — в том, что с вещественными величинами, такими как error и deltaerr, компьютеры работают относительно медленно. Кроме того, при вычислениях с плавающей точкой из-за ограничений, связанных с представлением вещественных чисел, невозможно получить точные значения при делении. Это приводит к тому, что в процессе вычислений происходит накопление ошибки и может привести к нежелательным результатам. По этим причинам лучше работать только с целыми числами. Это можно сделать, если умножить все используемые вещественные величины на (deltax + 1). Получаем следующий код:
function line(int x0, int x1, int y0, int y1)
int deltax := abs(x1 - x0)
int deltay := abs(y1 - y0)
int error := 0
int deltaerr := (deltay + 1)
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 >= (deltax + 1)
y := y + diry
error := error - (deltax + 1)
Необходимость прибавлять единицу к deltax и deltay вызвана тем, что функция должна строить линию от точки (x0, y0) до точки (x1, y1) включительно! Теперь мы можем быстро рисовать линии, направленные вправо-вниз с величиной наклона меньше 1. Осталось распространить алгоритм на рисование во всех направлениях. Это достигается за счёт зеркальных отражений, то есть заменой знака (шаг в 1 заменяется на −1), обменом переменных x и y, обменом координат начала отрезка с координатами конца.
Рисование окружностей
Также существует алгоритм Брезенхема для рисования окружностей. По методу построения он похож на рисование линии. В этом алгоритме строится дуга окружности для первого квадранта, а координаты точек окружности для остальных квадрантов получаются симметрично. На каждом шаге алгоритма рассматриваются три пикселя, и из них выбирается наиболее подходящий путём сравнения расстояний от центра до выбранного пикселя с радиусом окружности.
// R - радиус, X1, Y1 - координаты центра
int x := 0
int y := R
int delta := 1 - 2 * R
int error := 0
while (y >= x)
drawpixel(X1 + x, Y1 + y)
drawpixel(X1 + x, Y1 - y)
drawpixel(X1 - x, Y1 + y)
drawpixel(X1 - x, Y1 - y)
drawpixel(X1 + y, Y1 + x)
drawpixel(X1 + y, Y1 - x)
drawpixel(X1 - y, Y1 + x)
drawpixel(X1 - y, Y1 - x)
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)
Литература
- Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — С. 54-63. — ISBN 5-03-000476-9.
- Шилдт Г. "Си" для профессиональных программистов. — М., 1989.