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

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

Отрезок проводится между двумя точками — (x0,y0) и (x1,y1), где в этих парах указаны колонка и строка, соответственно, номера которых растут вправо и вниз. Сначала мы будем предполагать, что наша линия идёт вниз и вправо, причём горизонтальное расстояние x1 − x0 превосходит вертикальное y1 − y0, т.е. наклон линии от горизонтали — менее 45°. Наша цель состоит в том, чтобы для каждой колонки x между x0 и x1, определить, какая строка y ближе всего к линии, и нарисовать точку (x,y).

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

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

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

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же 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, обменом координат начала отрезка с координатами конца.

Рисование линий:

Реализация на C++:

void drawLine(int x1, int y1, int x2, int y2)

{

int deltaX = abs(x2 - x1);

int deltaY = abs(y2 - y1);

int signX = x1 < x2 ? 1 : -1;

int signY = y1 < y2 ? 1 : -1;

int error = deltaX - deltaY;

for (;;)

{

setPixel(x1, y1);

if(x1 == x2 && y1 == y2)

break;

int error2 = error * 2;

if(error2 > -deltaY)

{

error -= deltaY;

x1 += signX;

}

if(error2 < deltaX)

{

error += deltaX;

y1 += signY;

}

}

}

Реализация на Java:

// Этот код "рисует" все 9 видов отрезков. Наклонные (из начала в конец и из конца в начало каждый), вертикальный и горизонтальный - тоже из начала в конец и из конца в начало, и точку.

private int sign (int x) {

return (x > 0) ? 1 : (x < 0) ? -1 : 0;

//возвращает 0, если аргумент (x) равен нулю; -1, если x < 0 и 1, если x > 0.

}

public void drawBresenhamLine (int xstart, int ystart, int xend, int yend, Graphics g)

/**

* xstart, ystart - начало;

* xend, yend - конец;

* "g.drawLine (x, y, x, y);" используем в качестве "setPixel (x, y);"

* Можно писать что-нибудь вроде g.fillRect (x, y, 1, 1);

*/

{

int x, y, dx, dy, incx, incy, pdx, pdy, es, el, err;

dx = xend - xstart;//проекция на ось икс

dy = yend - ystart;//проекция на ось игрек

incx = sign(dx);

/*

* Определяем, в какую сторону нужно будет сдвигаться. Если dx < 0, т.е. отрезок идёт

* справа налево по иксу, то incx будет равен -1.

* Это будет использоваться в цикле постороения.

*/

incy = sign(dy);

/*

* Аналогично. Если рисуем отрезок снизу вверх -

* это будет отрицательный сдвиг для y (иначе - положительный).

*/

if (dx < 0) dx = -dx;//далее мы будем сравнивать: "if (dx < dy)"

if (dy < 0) dy = -dy;//поэтому необходимо сделать dx = |dx|; dy = |dy|

//эти две строчки можно записать и так: dx = Math.abs(dx); dy = Math.abs(dy);

if (dx > dy)

//определяем наклон отрезка:

{

/*

* Если dx > dy, то значит отрезок "вытянут" вдоль оси икс, т.е. он скорее длинный, чем высокий.

* Значит в цикле нужно будет идти по икс (строчка el = dx;), значит "протягивать" прямую по иксу

* надо в соответствии с тем, слева направо и справа налево она идёт (pdx = incx;), при этом

* по y сдвиг такой отсутствует.

*/

pdx = incx; pdy = 0;

es = dy; el = dx;

}

else//случай, когда прямая скорее "высокая", чем длинная, т.е. вытянута по оси y

{

pdx = 0; pdy = incy;

es = dx; el = dy;//тогда в цикле будем двигаться по y

}

x = xstart;

y = ystart;

err = el/2;

g.drawLine (x, y, x, y);//ставим первую точку

//все последующие точки возможно надо сдвигать, поэтому первую ставим вне цикла

for (int t = 0; t < el; t++)//идём по всем точкам, начиная со второй и до последней

{

err -= es;

if (err < 0)

{

err += el;

x += incx;//сдвинуть прямую (сместить вверх или вниз, если цикл проходит по иксам)

y += incy;//или сместить влево-вправо, если цикл проходит по y

}

else

{

x += pdx;//продолжить тянуть прямую дальше, т.е. сдвинуть влево или вправо, если

y += pdy;//цикл идёт по иксу; сдвинуть вверх или вниз, если по y

}

g.drawLine (x, y, x, y);

}

}

[править]Реализация на Object Pascal

Procedure Swap(var x,y:Integer);

var t:Integer;

begin

t:=x;x:=y;y:=t;

end;

Procedure Line(Canvas: TCanvas; x1,y1,x2,y2:integer);

var dx,dy,i,sx,sy,check,e,x,y:integer;

begin

dx:=abs(x1-x2);

dy:=abs(y1-y2);

sx:=Sign(x2-x1);

sy:=Sign(y2-y1);

x:=x1;

y:=y1;

check:=0;

if dy>dx then begin

Swap(dx,dy);

check:=1;

end;

e:= 2*dy - dx;

for i:=0 to dx do begin

Canvas.Pixels[x,y]:=clBlack;

if e>=0 then begin

if check=1 then inc(x,sx) else inc(y,sy);

dec(e,2*dx);

end;

if check=1 then inc(y,sy) else inc(x,sx);

inc(e,2*dy);

end;

end;

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

// R - радиус, X1, Y1 - координаты центра

int x := 0

int y := R

int delta := 2 - 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--

Для C++

void drawCircle(int x0, int y0, int radius) {

int x = 0;

int y = radius;

int delta = 2 - 2 * radius;

int error = 0;

while(y >= 0) {

setPixel(x0 + x, y0 + y);

setPixel(x0 + x, y0 - y);

setPixel(x0 - x, y0 + y);

setPixel(x0 - x, y0 - y);

error = 2 * (delta + y) - 1;

if(delta < 0 && error <= 0) {

++x;

delta += 2 * x + 1;

continue;

}

error = 2 * (delta - x) - 1;

if(delta > 0 && error > 0) {

--y;

delta += 1 - 2 * y;

continue;

}

++x;

delta += 2 * (x - y);

--y;

}

}

Для Delphi 7

Edit1: TEdit;

Edit2: TEdit;

Button1: TButton;

Edit3: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

{ Объявляем процедуру "DrawCircle", реализующая

алгоритм Брезенхема для рисования окружности }

procedure DrawCircle(x1, y1, R : Integer);

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.DrawCircle(x1, y1, R : Integer);

var x,y,error,delta : integer;

begin

InvalidateRect(0, nil, true); //Очистка Canvas, необходимая для затирания созданных кругов

x := 0;

y := R;

delta := (2 - 2 * R);

error := 0;

while y >= 0 do

begin

Canvas.Pixels[X1 + x,Y1 + y] := clBlack;

Canvas.Pixels[X1 + x,Y1 - y] := clBlack;

Canvas.Pixels[X1 - x,Y1 + y] := clBlack;

Canvas.Pixels[X1 - x,Y1 - y] := clBlack;

error := 2 * (delta + y) - 1;

if ((delta < 0) and (error <= 0)) then

begin

inc(x);

delta := delta + (2 * x + 1);

continue;

end;

error := 2 * (delta - x) - 1;

if ((delta > 0) and (error > 0)) then

begin

dec(y);

delta := delta + (1 - 2 * y);

continue;

end;

inc(x);

delta := delta + (2 * (x - y));

dec(y);

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

{ Здесь получаем необходимые данные из Edit-ов, содержащих информацию

для построения окружности по алгоритму Брезенхема, а именно координаты

центра окружности и радиус, реализуем их в процедуру DrawCircle }

DrawCircle(StrToInt(Edit1.Text),StrToInt(Edit2.Text), StrToInt(Edit3.Text));

end;

Модифицированный пример из книги Г.Шилдта "Си для профессиональных программистов" [1]

/* Вспомогательная функция, печатает точки, определяющие окружность */

void plot_circle(int x, int y, int x_center, int y_center, int color_code)

{

mempoint(x_center+x,y_center+y,color_code);

mempoint(x_center+x,y_center-y,color_code);

mempoint(x_center-x,y_center+y,color_code);

mempoint(x_center-x,y_center-y,color_code);

}

/* Вычерчивание окружности с использованием алгоритма Брезенхама */

void circle(int x_center, int y_center, int radius, int color_code)

{

int x,y,delta;

x = 0;

y = radius;

delta=3-2*radius;

while(x<y) {

plot_circle(x,y,x_center,y_center,color_code);

plot_circle(y,x,x_center,y_center,color_code);

if (delta<0)

delta+=4*x+6;

else {

delta+=4*(x-y)+10;

y--;

}

x++;

}

if(x==y) plot_circle(x,y,x_center,y_center,color_code);

}

Лит.: Роджерс Д. Алгоритмические основы машинной графики — М.: Мир, 1989. — С. 512. Шилдт Г. "Си" для профессиональных программистов — М., 1989.