Реализации алгоритмов/Алгоритм Брезенхэма: различия между версиями
Содержимое удалено Содержимое добавлено
Oleg4280 (обсуждение | вклад) убрал ]] |
РоманСузи (обсуждение | вклад) перенесено из истории правок на w:Алгоритм Брезенхэма, oldid=62474043 |
||
Строка 1:
{{wikipedia|Алгоритм Брезенхэма}}
'''Алгоритм Брезенхе́ма''' ({{lang-en|Bresenham's line algorithm}})
== Рисование линий ==
=== Реализация на C++ ===
<source lang="cpp">
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;
}
}
}
</source>
=== Реализация на Java ===
<source lang="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);
}
}
</source>
=== Реализация на Object Pascal ===
<source lang="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;
</source>
примечание<ref>переменная DX взята не удачно при написании фрагмента на [[Ассемблерная вставка|асм’е]] среда плохо переварит</ref>
=== Реализация на PascalABC ===
<source lang="pascal">
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;
</source>
== Рисование окружностей ==
Также существует алгоритм Брезенхэма для рисования окружностей. По методу построения он похож на рисование линии. В этом алгоритме строится дуга окружности для первого квадранта, а координаты точек окружности для остальных квадрантов получаются симметрично. На каждом шаге алгоритма рассматриваются три пикселя, и из них выбирается наиболее подходящий путём сравнения расстояний от центра до выбранного пикселя с радиусом окружности.
// 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++ ===
<source lang="cpp">
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;
}
error = 2 * (delta - x) - 1;
if(delta > 0 && error > 0) {
--y;
delta += 1 - 2 * y;
continue;
}
++x;
delta += 2 * (x - y);
--y;
}
}
</source>
=== Для Delphi 7 ===
<source lang="pascal">
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;
</source>
=== Для TurboPascal ===
<source lang="pascal">
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;
</source>
=== Модифицированный пример из книги Г.Шилдта «Си для профессиональных программистов» {{sfn|Шилдт|1989}} ===
<source lang="c">
/* Вспомогательная функция, печатает точки, определяющие окружность */
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);
}
</source>
== Реализация для Turbo Assembler ==
<source lang="asm">
.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
</source>
-----------
== Visual Basic ==
<ref>[http://encyclopedia.kids.net.au/page/br/Bresenham%27s_line_algorithm_Visual_basic_code Encyclopedia >
<source lang="qbasic">
Private Sub BresLine(InitialX As Long, InitialY As Long, FinalX As Long, FinalY As Long)
Строка 51 ⟶ 579 :
== C++ для 3D-растра ==
Алгоритм Брезенхэма для построения трёхмерных точек линии (x1, y1, z1)
A slightly modified version of the source found at
http://www.ict.griffith.edu.au/anthony/info/graphics/bresenham.procs
| |||