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

2025-10-31T09:20:05Z

85.172.12.58: /* Литература */

[[Файл:LineBresenham.gif|thumb|336px|Демонстрация работы алгоритма]]
'''Алгоритм Брезенхе́ма''' ({{lang-en|Bresenham's line algorithm}}) — [[алгоритм]], определяющий, какие точки [[Алгоритмы построения отрезка|двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками]]. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения кривых 2-го порядка.{{Нет АИ|25|9|2023}} Это один из старейших алгоритмов в [[машинная графика|машинной графике]] — он был разработан [[Брезенхэм, Джек Элтон|Джеком Элтоном Брезенхэмом]] в компании [[IBM]] в 1962 году.

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

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

: <math>y - y_0 = \frac{y_1-y_0}{x_1-x_0}(x-x_0).</math>

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

: <math>y = \frac{y_1-y_0}{x_1-x_0}(x-x_0) + y_0.</math>

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

: <math>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. В реализации алгоритма, приведённой ниже, <code>plot(x,y)</code> рисует точку, а <code>abs</code> возвращает [[Абсолютная величина|абсолютную величину]] числа:
'''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

Проблема такого подхода в том, что с вещественными величинами, такими как <code>error</code> и <code>deltaerr</code>, компьютеры работают относительно медленно. Кроме того, при вычислениях с плавающей точкой из-за ограничений, связанных с представлением вещественных чисел, невозможно получить точные значения при делении. Это приводит к тому, что в процессе вычислений происходит накопление ошибки и может привести к нежелательным результатам. По этим причинам лучше работать только с целыми числами. Это можно сделать, если умножить все используемые вещественные величины на (<code>deltax + 1)</code>. Получаем следующий код:

'''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'', обменом координат начала отрезка с координатами конца.

== Рисование окружностей ==
Также существует алгоритм Брезенхема для рисования окружностей. По методу построения он похож на рисование линии. В этом алгоритме строится дуга окружности для первого квадранта, а координаты точек окружности для остальных квадрантов получаются симметрично. На каждом шаге алгоритма рассматриваются три пикселя, и из них выбирается наиболее подходящий путём сравнения расстояний от центра до выбранного пикселя с радиусом окружности.

[[Файл:CircleBresenham.gif|справа|Разложение окружности в растр|обрамить]]
// этот алгоритм рисует смежные пиксели,
// 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;
}

== Литература ==
* {{книга
| автор = Роджерс Д.
| заглавие = Алгоритмические основы машинной графики
| ссылка = https://archive.org/details/libgen_00155582
| год = 1989
| издательство = Мир
| место = М.
| страницы = [https://archive.org/details/libgen_00155582/page/n446 54]-63
|isbn = 5-03-000476-9
}}
* {{книга
| автор = Шмидт Г.
| заглавие = "Си" для профессиональных программистов
| год = 1989
| место = М.
| ref = Шмидт
}}

== См. также ==
{{wikibooks|Алгоритмы_компьютерной_графики}}
* [[Алгоритмы построения отрезка]]
* [[Алгоритм Ву]]
* [[Алгоритм DDA-линии]]

[[Категория:Геометрические алгоритмы]]

wiki12 - Вклад [ru]

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