Алгоритм Брезенхе́ма ( англ. Bresenham's line algorithm ) — алгоритм , определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками . Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка. ^{[ источник не указан 129 дней ]} Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом в компании IBM в 1962 году.

Алгоритм

Отрезок проводится между двумя точками — ${\displaystyle (x_{0},y_{0})}$ и ${\displaystyle (x_{1},y_{1})}$ , где в этих парах указаны столбец и строка соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вправо и вниз, причём горизонтальное расстояние ${\displaystyle x_{1}-x_{0}}$ превосходит вертикальное ${\displaystyle y_{1}-y_{0}}$ , то есть наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждого столбца x между ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ определить, какая строка y ближе всего к линии, и нарисовать точку ${\displaystyle (x,y)}$ .

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

${\displaystyle y-y_{0}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0}).}$

Поскольку мы знаем колонку ${\displaystyle x}$ , то строка ${\displaystyle y}$ получается округлением к целому следующего значения:

${\displaystyle y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}.}$

Однако, вычислять точное значение этого выражения нет необходимости. Достаточно заметить, что ${\displaystyle y}$ уменьшается от ${\displaystyle y_{0}}$ и за каждый шаг мы добавляем к ${\displaystyle x}$ единицу и добавляем к ${\displaystyle y}$ значение наклона (в нашем случае значение наклона будет отрицательным числом):

${\displaystyle s={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},}$

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же 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)

   // этот алгоритм не рисует смежные пиксели
   var x = 0;
   var y = R;
   var delta = 3 - 2 * y;
   while (x <= y) {
       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);
       delta += delta < 0 ? 4 * x + 6 : 4 * (x - y--) + 10;
       ++x;
   }

Литература

• Роджерс Д. . — М. : Мир, 1989. — С. -63. — ISBN 5-03-000476-9 .
• Шилдт Г. "Си" для профессиональных программистов. — М. , 1989.

См. также

• Алгоритмы построения отрезка
• Алгоритм Ву
• Алгоритм DDA-линии