Растровое представление отрезка. Алгоритм Брезенхейма

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(xa, ya) и B(xb, yb). Для простоты будем считать, что

0 ≤ yb – ya ≤ xb – xa . Тогда отрезок описывается уравнением:

y = ya + Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (x–xa), x Є [xa, xb] или y = kx + b.

Отсюда получаем простейший алгоритм растрового представления отрезка:

private void MyLine(int xa, int ya, int xb, int yb, Color color)

{

double k = ((double)(yb - ya)) / (xb - xa);

double b = ya - k * xa;

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

for (int x = xa; x <= xb; x++){

bmp.SetPixel(x, (int) (k*x + b), color);}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

Вычислений значений функции y = kx + b можно избежать, используя в цикле рекуррентные соотношения, так как при изменении x на 1 значение y меняется на k:

private void MyLineN(int xa, int ya, int xb, int yb, Color color)

{

double k = ((double)(yb - ya)) / (xb - xa);

double y = ya;

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

for (int x = xa; x <= xb; x++, y+= k){

bmp.SetPixel(x, (int)y, color);}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

Приведенные простейшие пошаговые алгоритмы построения отрезка имеют ряд недостатков:

1. Выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;

2. На каждом шаге выполняется операция округления, что также снижает быстродействие.

Эти недостатки устранены в следующем алгоритме Брезенхейма.

Как и в предыдущем случае, будем считать, что тангенс угла наклона отрезка принимает значение в диапазоне от 0 до 1. Рассмотрим i-й шаг алгоритма (рис. 4.3). На этом этапе пиксель Pi-1 уже найден как ближайший к реальному отрезку. Требуется определить, какой из пикселей (Ti или Si) будет установлен следующим.

Pi-1= (r, q) = (xi-1, yi-1)
Si = (r+1, q)
Ti = (r+1,q+1)
S
T
y=x Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru

Рис. 4.3. i-й шаг алгоритма Брезенхейма

В алгоритме используется управляющая переменная di, которая на каждом шаге пропорциональна разности между S и T. Если S < T, то Si ближе к отрезку, иначе выбирается Ti.

Пусть изображаемый отрезок проходит из точки (x1, y1) в точку (x2, y2). Исходя из начальных условий, точка (x1, y1) ближе к началу координат. Тогда перенесем оба конца отрезка с помощью преобразования T(­­­­­­–x1, –y1), так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x2– x1, dy = y2 – y1 (рис. 4.4).

y
q
r
r+1
Pi-1
S
T
x
dy

Рис. 4.4. Вид отрезка после переноса в начало координат

Уравнение прямой в этом случае будет иметь вид:

y=x Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru .

Обозначим координаты точки Pi-1после переноса через (r, q). Тогда Si = (r+1, q) и Ti = (r+1, q+1).

Из подобия треугольников на рис. 4.4 можно записать, что

Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru = Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru .

Выразим S:

S = Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (r + 1) – q.

T можно представить как T = 1 – S. Используем предыдущую формулу

T = 1 – S = 1 – Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (r + 1) – q.

Найдем разницу S – T:

S – T = Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (r + 1) – q – 1 + Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (r + 1) – q = 2 Растровое представление отрезка. Алгоритм Брезенхейма - student2.ru (r + 1) – 2 q – 1.

Помножим левую и правую часть на dx:

dx (S – T) = 2 dy (r + 1) – 2 q dx – dx = 2(r dy – q dx) + 2 dy – dx.

Величина dx положительная, поэтомунеравенство dx (S – T) < 0 можно использовать в качестве проверки при выборе Si. Обозначим di = dx (S – T), тогда

di = 2(r dy – q dx) + 2 dy – dx.

Поскольку r = xi-1 и q = yi-1, то

di = 2 xi-1 dy –2 yi-1 dx + 2 dy – dx.

Прибавляя 1 к каждому индексу найдем di+1:

di+1= 2 xi dy –2 yi dx + 2 dy – dx.

Вычитая di из di+1получим

di+1 – di = 2 dy (xi – xi-1) – 2 dx (yi – yi-1).

Известно, что xi – xi-1 = 1, тогда

di+1– di = 2 dy – 2 dx (yi – yi-1).

Отсюда выразим di+1:

di+1 = di + 2 dy – 2 dx (yi – yi-1).

Таким образом, получили итеративную формулу вычисления управляющего коэффициента di+1 по предыдущему значению di. С помощью управляющего коэффициента выбирается следующий пиксель – Si или Ti.

Если di ≥ 0, тогда выбирается Ti и yi = yi1 + 1, di+1 = di +2 (dy – dx). Если di < 0, тогда выбирается Si и yi = yi1 и di+1 = di +2 dy.

Начальные значения d1 с учетом того, что (x0, y0) = (0, 0),

d1= 2 dy – dx.

Преимуществом алгоритма является то, что для работы алгоритма требуются минимальные арифметические возможности: сложение, вычитание и сдвиг влево для умножения на 2.

Реализация этого алгоритма выглядит следующим образом:

private void BLine(int x1, int y1, int x2, int y2, Color color)

{

int dx, dy, inc1, inc2, d, x, y, Xend;

dx = Math.Abs(x2 - x1);

dy = Math.Abs(y2 - y1);

d = (dy << 1) - dx;

inc1 = dy << 1;

inc2 = (dy - dx) << 1;

if (x1 > x2)

{

x = x2;

y = y2;

Xend = x1;

}

else

{

x = x1;

y = y1;

Xend = x2;

};

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width,

this.ClientSize.Height);

bmp.SetPixel(x, y, color);

while (x < Xend)

{

x++;

if (d < 0) d = d + inc1;

else {y++; d = d + inc2;};

bmp.SetPixel(x, y, color);

}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

Если dy > dx, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.

Наши рекомендации