Алгоритм Брезенхема был предложен Джеком Е. Брезенхэмом (Jack E. Bresenham) в 1962 году и предназначен для рисования фигур точками на плоскости. Этот алгоритм находит широкое распространение в машинной графике для рисования линий на экране. Алгоритм определяет, какие точки двумерного растра необходимо закрасить.
Графическая интерпретация алгоритма Брезенхема представлена на рисунке.
Для рисования прямых отрезков на плоскости с использованием алгоритма Брезенхема запишем уравнение прямой в общем виде
y=kx+b
или
f(x,y)=Ax+By+C=0
где коэффициенты A и B выражаются через коэффициенты k и b уравнения прямой. Если прямая проходит через две точки с координатами (x1;y1) и (x2;y2), то коэффициенты уравнения прямой определяются по формулам
A=y2-y1
B=x1-x2
C=y1∙x2-y2∙x1
Для любой растровой точки с координатами (xi;yi) значение функция
- f(xi,yi)=0 если точка лежит на прямой
- f(xi,yi)>0 если точка лежит ниже прямой
- f(xi,yi) где i – номер отображаемой точки.
Таким образом, одним из методов решения того, какая из точек P или Q (см. рисунок) будет отображена на следующем шаге, является сравнение середины отрезка |P-Q| со значением функции f(x,y). Если значение f(x,y) лежит ниже средней точки отрезка |P-Q|, то следующей отображаемой точкой будет точка P, иначе — точка Q.
Запишем приращение функции
∆f=A∆x+B∆y
После отображения точки с координатами (xi,yi) принимается решение о следующей отображаемой точке. Для этого сравниваются приращения Δx и Δy, характеризующие наличие или отсутствие перемещения по соответствующей координате. Эти приращения могут принимать значения 0 или 1. Следовательно, когда мы перемещаемся от точки вправо,
∆f=A,
когда мы перемещаемся от точки вправо и вниз, то
∆f=A+B,
когда мы перемещаемся от точки вниз, то
∆f=B
Нам известны координаты начала отрезка, то есть точки, заведомо лежащей на искомой прямой. Ставим туда первую точку и принимаем f = 0. От текущей точки можно сделать два шага — либо по вертикали (по горизонтали), либо по диагонали на один пиксель.
Направление движения по вертикали или горизонтали определяется коэффициентом угла наклона. В случае если угол наклона меньше 45º, и
|A|<|B|
с каждым шагом осуществляется движение по горизонтали или диагонали.
Если угол наклона больше 45º, с каждым шагом движение осуществляется вертикали или диагонали.
Таким образом, алгоритм рисования наклонного отрезка следующий:
Реализация на C++
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
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;
}
cin.get(); cin.get();
return 0;
}
Результат выполнения
Алгоритм Брезенхема также может применяться в задачах управления, например, для регулирования мощности или скорости вращения. При этом горизонтальной осью является ось времени, а заданное значение устанавливает коэффициент угла наклона прямой.
Назад: Алгоритмизация
Комментариев к записи: 5