Алгоритм был предложен Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году и предназначен для рисования фигур точками на плоскости. Этот алгоритм находит широкое распространение в машинной графике для рисования линий на экране. Алгоритм определяет, какие точки двумерного растра необходимо закрасить.
Графическая интерпретация алгоритма Брезенхема представлена на рисунке.
Для рисования прямых отрезков на плоскости с использованием алгоритма Брезенхема запишем уравнение прямой в общем виде
{\displaystyle{y = k \cdot x + b}}
{\displaystyle{f(x, y) = A \cdot x + B \cdot y + C = 0}},
где коэффициенты {\displaystyle{A}} и {\displaystyle{B}} выражаются через коэффициенты {\displaystyle{k}} и {\displaystyle{b}} уравнения прямой.
Если прямая проходит через две точки с координатами {\displaystyle{(x_1; y_1)}} и {\displaystyle{(x_2; y_2)}}, то коэффициенты уравнения прямой определяются по формулам
{\displaystyle{A = y_2 \ — \ y_1}}
{\displaystyle{B = x_1 \ — \ x_2}}
{\displaystyle{C = y_1 \cdot x_2 \ — \ y_2 \cdot x_1}}
Для любой растровой точки с координатами {\displaystyle{(x_i; y_i)}} значение функция
- {\displaystyle{f(x_i, y_i) = 0}} если точка лежит на прямой
- {\displaystyle{f(x_i, y_i) \gt 0}} если точка лежит ниже прямой
- {\displaystyle{f(x_i, y_i) \lt 0}} если точка лежит выше прямой
где {\displaystyle{i}} – номер отображаемой точки.
Таким образом, одним из методов решения того, какая из точек {\displaystyle{P}} или {\displaystyle{Q}} (см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка {\displaystyle{P-Q}} со значением функции {\displaystyle{f(x,y)}}.
Если значение {\displaystyle{f(x,y)}} лежит ниже средней точки отрезка {\displaystyle{|P-Q|}}, то следующей отображаемой точкой будет точка {\displaystyle{P}}, иначе — точка {\displaystyle{Q}}.
Запишем приращение функции
{\displaystyle{\Delta f = A \cdot \Delta x + B \cdot \Delta y}}
После отображения точки с координатами {\displaystyle{(x_i; y_i)}} принимается решение о следующей отображаемой точке. Для этого сравниваются приращения {\displaystyle{\Delta x}} и {\displaystyle{\Delta y}}, характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1.
Следовательно, когда мы перемещаемся от точки вправо,
{\displaystyle{\Delta f = A}},
когда мы перемещаемся от точки вправо и вниз, то
{\displaystyle{\Delta f = A + B}},
когда мы перемещаемся от точки вниз, то
{\displaystyle{\Delta f = B}}
Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем {\displaystyle{f = 0}}.
От текущей точки можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель.
Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и
{\displaystyle{|A| \lt |B|}}
с каждым шагом осуществляется движение по горизонтали или диагонали.
Если угол наклона больше 45º, с каждым шагом движение осуществляется вертикали или диагонали.
Таким образом, алгоритм рисования наклонного отрезка следующий:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
void Brezenhem(char** z, int x0, int y0, int x1, int y1)
{
int A, B, sign;
A = y1 - y0;
B = x0 - x1;
if (abs(A) > abs(B))
sign = 1;
else
sign = -1;
int signa, signb;
if (A < 0)
signa = -1;
else
signa = 1;
if (B < 0)
signb = -1;
else
signb = 1;
int f = 0;
z[y0][x0] = '*';
int x = x0, y = y0;
if (sign == -1)
{
do {
f += A * signa;
if (f > 0)
{
f -= B * signb;
y += signa;
}
x -= signb;
z[y][x] = '*';
} while (x != x1 || y != y1);
}
else
{
do {
f += B * signb;
if (f > 0) {
f -= A * signa;
x -= signb;
}
y += signa;
z[y][x] = '*';
} while (x != x1 || y != y1);
}
}
int main()
{
const int SIZE = 25; // размер поля
int x1, x2, y1, y2;
char** z;
z = new char* [SIZE];
for (int i = 0; i < SIZE; i++)
{
z[i] = new char[SIZE];
for (int j = 0; j < SIZE; j++)
z[i][j] = '-';
}
cout << "x1 = "; cin >> x1;
cout << "y1 = "; cin >> y1;
cout << "x2 = "; cin >> x2;
cout << "y2 = "; cin >> y2;
Brezenhem(z, x1, y1, x2, y2);
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
cout << z[i][j];
cout << endl;
}
for (int i = 0; i < SIZE; i++)
delete[] z[i];
delete[] z;
cin.get(); cin.get();
return 0;
}
Результат выполнения
Алгоритм Брезенхема также может применяться в задачах управления, например, для регулирования мощности или скорости вращения. При этом горизонтальной осью является ось времени, а заданное значение устанавливает коэффициент угла наклона прямой (но всегда до 45 градусов).
Описание алгоритма не соответствует блок-схеме. Вроде работает, но на блок-схеме координаты отрисовки постоянно пытаются быть выше линии, хотя в описании сказано, что переход на следующую координату происходит только после сравнения отрезка |P-Q|. Потратил кучу времени что бы понять, почему то, что алгоритм рисует не подходит под то, что ожидается в алгоритме Брейзенхейма здорового человека.
Спасибо, Елена, за понятное объяснение и элегантный код, очень всё упаковано, а ведь есть 8 вариантов знаков и отношений модулей A и B.
Теперь критика: На блок-схеме нет модуля в условии A<B. Для рисования качественных линий условия f > 0 недостаточно, надо сравнивать модули ошибки для двух случаев. Т.е. первое ‘f > 0’ заменяется на abs(f) > abs(f-abs(B)), а второе — на abs(f-abs(A)). А так алгоритм «идет» сбоку от идеальной прямой. abs оператор недорогой, любая ардуина потянет. Можно даже (но не в учебной программе) удалить знаки у A & B вначале, после вычисления signa & signb.