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

Иллюстрация результата работы алгоритма

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

Алгоритм

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

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

$y - y_0 = \frac{y_1-y_0}{x_1-x_0}(x-x_0).$

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

$y = \frac{y_1-y_0}{x_1-x_0}(x-x_0) + y_0.$

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

$s = \frac{y_1-y_0}{x_1-x_0},$

которое можно вычислить заранее. Более того, на каждом шаге мы делаем одно из двух: либо сохраняем тот же 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) {
    const int deltaX = abs(x2 - x1);
    const int deltaY = abs(y2 - y1);
    const int signX = x1 < x2 ? 1 : -1;
    const int signY = y1 < y2 ? 1 : -1;
    //
    int error = deltaX - deltaY;
    //
    setPixel(x2, y2);
    while(x1 != x2 || y1 != y2) {
        setPixel(x1, y1);
        const 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;

Реализация на PascalABC

procedure drawLine(x1, y1, x2, y2: integer);
var
  currentX, currentY: integer;
  errorX, errorY: integer;
  d, dx, dy, incX, incY: integer;
begin
  dx := x2 - x1;
  dy := y2 - y1;
  errorX := 0;
  errorY := 0;
 
  if(dx > 0) then incX := 1
    else if(dx = 0) then incX := 0
      else incX := -1;
 
  if(dy > 0) then incY := 1
    else if(dy = 0) then incY := 0
      else incY := -1;
 
  dx := abs(dx);
  dy := abs(dy);
 
  if(dy > dx) then d := dy
    else d := dx;
 
  currentX := x1;
  currentY := y1;
  SetPixel(currentX, currentY, 0);
  while((currentX <> x2) OR (currentY <> y2)) do
  begin
    errorX := errorX + dx;
    errorY := errorY + dy;
    if(errorX >= d) then
    begin
         errorX := errorX - d;
         currentX := currentX + incX;
    end;
    if(errorY >= d) then
    begin
         errorY := errorY - d;
         currentY := currentY + incY;
    end;
    SetPixel(currentX, currentY, 0);
  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;

Для TurboPascal

procedure BrezenCircle(x0, y0, r: integer);
 var
 x, y: integer;
 dv, dd, dh: integer;
 procedure sim(x, y: integer); {построить 4 симметричные точки}
  begin
    putpixel(x0+x, y0+y, 0); {верхняя правая четверть}
    putpixel(x0+x, y0-y, 0); {нижняя правая четверть}
    putpixel(x0-x, y0+y, 0); {верхняя левая четверть}
    putpixel(x0-x, y0-y, 0); {нижняя левая четверть}
  end;
begin
  x:=0;
  y:=r;
  while((y>=0)or(x<r)) do {обход идет по верхней правой четверти}
    begin
     sim(x,y);
     dv:=abs(r*r - x*x - (y-1)*(y-1)); {сдвиг на 1 вниз}
     dh:=abs(r*r - (x+1)*(x+1) - y*y); {сдвиг на 1 вправо}
     dd:=abs(r*r - (x+1)*(x+1) - (y-1)*(y-1)); {сдвиг на 1 по диагонали вправо и вниз}
     if(dv<dh) then {если сдвиг вниз ближе к радиусу круга}
      begin
        dec(y);
        if(dd<dv) then inc(x); {если сдвиг по диагонали ближе к радиусу круга}
      end
     else {если сдвиг вправо ближе к радиусу круга}
      begin
        inc(x);
        if(dd<dh) then dec(y); {если сдвиг по диагонали ближе к радиусу круга}
      end;
    end;
end;

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

/* Вспомогательная функция, печатает точки, определяющие окружность */
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);
}

Реализация для Turbo Assembler

.model  tiny
.stack  100h
.data
        eror dw ?
        x dw ?
        y dw ?
        x0 dw ?
        y0 dw ?
        delta dw ?
        radius dw ?
.code
 
Plot proc
        mov Ah, 0Ch             ;Функция отрисовки точки
        mov al, 6               ;Цвет
        int 10h                 ;Нарисовать точку
        ret
Plot endp
 
drawCircle proc
        mov x, 0
        mov ax, radius
        mov y, ax
        mov delta, 2
        mov ax, 2
        mov dx, 0
        imul y
        sub delta, ax
        mov eror, 0
        jmp ccicle
finally: ret
ccicle:
        mov ax, y
        cmp ax, 0
        jl  finally
        mov cx, x0
        add cx, x
        mov dx, y0
        add dx, y
        call Plot
        mov cx, x0
        add cx, x
        mov dx, y0
        sub dx, y
        call Plot
        mov cx, x0
        sub cx, x
        mov dx, y0
        add dx, y
        call Plot
        mov cx, x0
        sub cx, x
        mov dx, y0
        sub dx, y
        call Plot
        mov ax, delta
        mov eror, ax
        mov ax, y
        add eror, ax
        mov ax, eror
        mov dx, 0
        mov bx, 2
        imul bx
        sub ax, 1
        mov eror, ax
        cmp delta, 0
        jg sstep
        je sstep
        cmp eror, 0
        jg  sstep
        inc x
        mov ax, 2
        mov dx, 0
        imul x
        add ax, 1
        add delta, ax
        jmp ccicle
sstep:
        mov ax, delta
        sub ax, x
        mov bx, 2
        mov dx, 0
        imul bx
        sub ax, 1
        mov eror, ax
        cmp delta, 0
        jg tstep
        cmp eror, 0
        jg tstep
        inc x
        mov ax, x
        sub ax, y
        mov bx, 2
        mov dx, 0
        imul bx
        add delta, ax
        dec y
        jmp ccicle
tstep:
        dec y
        mov ax, 2
        mov dx, 0
        imul y
        mov bx, 1
        sub bx, ax
        add delta, bx
        jmp ccicle
drawCircle endp
 
start:
        mov ax, @data
        mov ds, ax
        mov Ah, 0
        mov Al, 4
        int 10h    ;Включение видеорежима VGA
        mov radius, 20    ;Радиус нашего круга.
        mov x0, 80    ;Номер строки, в котором будет находится центр круга
        mov y0, 80    ;Номер столбца, в котором будет находится центр круга
        call DrawCircle
        mov ah, 1    ;Функция захвата кода клавиши (идентична getch из "с")
        int 21h
        mov ah, 4Ch
        int 21h
end     start

Литература

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

См. также

• Алгоритмы построения отрезка
• Алгоритм Ву
• Алгоритм DDA-линии