Реализации алгоритмов/Алгоритм Брезенхэма
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки n-мерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками.
Существует обобщение алгоритма Брезенхэма для построения окружностей.
Рисование линий[править]
Реализация на Verilog[править]
`define IDLE 0
`define LINEY 1
`define LINEX 2
`define ERRORX 3
`define ERRORY 4
module Bresenham ( clk, rst, DRAW, X0, Y0, X1, Y1, X, Y, WE, DONE );
input clk;
input rst;
input DRAW;
input [31:0] X0;
input [31:0] Y0;
input [31:0] X1;
input [31:0] Y1;
output [31:0] X;
output [31:0] Y;
output WE;
output DONE;
reg [2:0] state;
reg we;
integer x1, x2, y1, y2;
integer error;
integer dX;
integer dY;
wire signed [31:0] signY = y2 > y1 ? 1 : -1;
always @(posedge clk or posedge rst)
if (rst) begin
x1 <= 0;
x2 <= 0;
y1 <= 0;
y2 <= 0;
we <= 0;
error <= 0;
state <= 0;
end else
case (state)
`IDLE :
begin
we <= 0;
if (DRAW) begin
x1 <= X0;
y1 <= Y0;
x2 <= X1;
y2 <= Y1;
dX = X1 > X0 ? X1 - X0 : X0 - X1;
dY = Y1 > Y0 ? Y1 - Y0 : Y0 - Y1;
error <= dX - dY;
state <= {1'b0, !(dX == 0), !(dY == 0)};
end
end
`ERRORX :
begin
we <= 0;
if (error <<< 1 > -dY) begin error <= error - dY; x1 <= x1 + 1'b1; end
state <= `ERRORY;
end
`ERRORY :
begin
we <= 1;
if (error <<< 1 < dX) begin error <= error + dX; y1 <= y1 + signY; end
state <= {1'b0, !(x1 == x2), !(y1 == y2)};
end
`LINEX :
begin
we <= 1;
x1 <= x1 + 1'b1;
if (x1 == (x2 - 1)) state <= `IDLE;
end
`LINEY :
begin
we <= 1;
y1 <= y1 + signY;
if (y1 == (y2 - signY)) state <= `IDLE;
end
endcase
assign X = x1;
assign Y = y1;
assign WE = we;
assign DONE = state == `IDLE;
endmodule
Реализация на 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);
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);
}
}
Реализация на Python3[править]
""" Имплементация алгоритма на языке Python(перевод с Java)
setPixel(x,y) - функция закрашивает пиксель, с координатами x и y"""
def draw_line(self, x1=0, y1=0, x2=0, y2=0):
dx = x2 - x1
dy = y2 - y1
sign_x = 1 if dx>0 else -1 if dx<0 else 0
sign_y = 1 if dy>0 else -1 if dy<0 else 0
if dx < 0: dx = -dx
if dy < 0: dy = -dy
if dx > dy:
pdx, pdy = sign_x, 0
es, el = dy, dx
else:
pdx, pdy = 0, sign_y
es, el = dx, dy
x, y = x1, y1
error, t = el/2, 0
setPixel(x, y)
while t < el:
error -= es
if error < 0:
error += el
x += sign_x
y += sign_y
else:
x += pdx
y += pdy
t += 1
setPixel(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;
примечание[1]
Реализация на 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 := 1 - 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 = 1 - 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;
}
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 := (1 - 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;
Для Python[править]
def draw_circle(x, y, r):
disp_x = x
disp_y = y
x = 0
y = r
delta = (1-2*r)
error = 0
while y >= 0:
setPixel(disp_x + x, disp_y + y)
setPixel(disp_x + x, disp_y - y)
setPixel(disp_x - x, disp_y + y)
setPixel(disp_x - x, disp_y - y)
error = 2 * (delta + y) - 1
if ((delta < 0) and (error <=0)):
x+=1
delta = delta + (2*x+1)
continue
error = 2 * (delta - x) - 1
if ((delta > 0) and (error > 0)):
y -= 1
delta = delta + (1 - 2 * y)
continue
x += 1
delta = delta + (2 * (x - y))
y -= 1
Модифицированный пример из книги Г.Шилдта «Си для профессиональных программистов» [2][править]
/* Вспомогательная функция, печатает точки, определяющие окружность */
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
Visual Basic[править]
Private Sub BresLine(InitialX As Long, InitialY As Long, FinalX As Long, FinalY As Long)
Dim Steep As Boolean
Dim DeltaX As Long, DeltaY As Long, Delta As Long
Dim StepX As Long, StepY As Long
Dim Coord As Long
Steep = False
DeltaX = Abs(FinalX - InitialX)
If (FinalX - InitialX) > 0 Then
StepX = 1
Else
StepX = -1
End If
DeltaY = Abs(FinalY - InitialY)
If (FinalY - InitialY) > 0 Then
StepY = 1
Else
StepY = -1
End If
If DeltaY > DeltaX Then
Steep = True
Swap InitialX, InitialY
Swap DeltaX, DeltaY
Swap StepX, StepY
End If
Delta = (DeltaY * 2) - DeltaX
For Coord = 0 To DeltaX
If Steep Then
Me.PSet (InitialY, InitialX)
Else
Me.PSet (InitialX, InitialY)
End If
While Delta >= 0
InitialY = InitialY + StepY
Delta = Delta - (DeltaX * 2)
Wend
InitialX = InitialX + StepX
Delta = Delta + (DeltaY * 2)
Next Coord
Me.PSet (FinalX, FinalY)
End Sub
C++ для 3D-растра[править]
Алгоритм Брезенхэма для построения трёхмерных точек линии (x1, y1, z1) — (x2, y2, z2).[4]
void Bresenham3D(int x1, int y1, int z1, const int x2, const int y2, const int z2, WorldMap *output, int symbol){
int i, dx, dy, dz, l, m, n, x_inc, y_inc, z_inc, err_1, err_2, dx2, dy2, dz2;
int point[3];
point[0] = x1;
point[1] = y1;
point[2] = z1;
dx = x2 - x1;
dy = y2 - y1;
dz = z2 - z1;
x_inc = (dx < 0) ? -1 : 1;
l = abs(dx);
y_inc = (dy < 0) ? -1 : 1;
m = abs(dy);
z_inc = (dz < 0) ? -1 : 1;
n = abs(dz);
dx2 = l << 1;
dy2 = m << 1;
dz2 = n << 1;
if ((l >= m) && (l >= n)) {
err_1 = dy2 - l;
err_2 = dz2 - l;
for (i = 0; i < l; i++) {
output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
if (err_1 > 0) {
point[1] += y_inc;
err_1 -= dx2;
}
if (err_2 > 0) {
point[2] += z_inc;
err_2 -= dx2;
}
err_1 += dy2;
err_2 += dz2;
point[0] += x_inc;
}
} else if ((m >= l) && (m >= n)) {
err_1 = dx2 - m;
err_2 = dz2 - m;
for (i = 0; i < m; i++) {
output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
if (err_1 > 0) {
point[0] += x_inc;
err_1 -= dy2;
}
if (err_2 > 0) {
point[2] += z_inc;
err_2 -= dy2;
}
err_1 += dx2;
err_2 += dz2;
point[1] += y_inc;
}
} else {
err_1 = dy2 - n;
err_2 = dx2 - n;
for (i = 0; i < n; i++) {
output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
if (err_1 > 0) {
point[1] += y_inc;
err_1 -= dz2;
}
if (err_2 > 0) {
point[0] += x_inc;
err_2 -= dz2;
}
err_1 += dy2;
err_2 += dx2;
point[2] += z_inc;
}
}
output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
}
Примечания[править]
- ↑ переменная DX взята не удачно при написании фрагмента на асм’е среда плохо переварит
- ↑ Шилдт, 1989
- ↑ Encyclopedia > Bresenham’s line algorithm Visual basic code Bresenham’s line algorithm for Microsoft Visual Basic 6.0. Implementation by Robert Lee <rlee0001@maine.rr.com> July, 2002 Public Domain
- ↑ C++ Bresenham 3d Line Drawing Algorithm A slightly modified version of the source found at http://www.ict.griffith.edu.au/anthony/info/graphics/bresenham.procs Provided by Anthony Thyssen, though he does not take credit for the original implementation It is highly likely that the original Author was Bob Pendelton, as referenced here ftp://ftp.isc.org/pub/usenet/comp.sources.unix/volume26/line3d line3d was dervied from DigitalLine.c published as "Digital Line Drawing" by Paul Heckbert from "Graphics Gems", Academic Press, 1990 3D modifications by Bob Pendleton. The original source code was in the public domain, the author of the 3D version places his modifications in the public domain as well.