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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Иллюстрация результата работы алгоритма

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

Алгоритм[править | править вики-текст]

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

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

y - y_0 = \frac{y_1-y_0}{x_1-x_0}(x-x_0).

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

y = \frac{y_1-y_0}{x_1-x_0}(x-x_0) + y_0.

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

s = \frac{y_1-y_0}{x_1-x_0},

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же 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
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if error >= 0.5
             y := y - 1
             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
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if 2 * error >= deltax
             y := y - 1
             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
       error = 2 * (delta - x) - 1
       if ((delta > 0) && (error > 0))
           delta += 1 - 2 * --y
           continue
       x++
       delta += 2 * (x - y)
       y--

Литература[править | править вики-текст]

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

См. также[править | править вики-текст]