Алгоритмы растеризации Алгоритмы Брезенхема рисования отрезка и окружности

Растровые алгоритмы Алгоритмы растеризации Алгоритмы перевода графических примитивов в растровую форму Алгоритмы заполнения областей и многоугольников Алгоритмы обработки растровых изображений Регулировка яркости и контрастности Масштабирование изображений Геометрические преобразования Алгоритмы фильтрации

Литература Д. Роджерс. Алгоритмические основы машинной графики. – М. Мир, 1989.

4-связность и 8-связность

Алгоритм Брезенхема рисования отрезка Отрезок от A(x a, y a ) до B(x b, y b ) 0 y b - y a x b - x a, k=(y b - y a ) / (x b - x a ) y = y a + k (x – x a ) procedure line(xa,ya,xb,yb:integer); var k,y : double; begin k:=(yb-ya)/(xb-xa); y:=ya; for i:=xa to xb do begin put(x,round(y)); y:=y+k end;

Алгоритм Брезенхема рисования отрезка dy/dx = (S+q)/(r+1) S = dy/dx (r+1) – q T = 1 – S = 1 - dy/dx (r+1) – q S – T = 2 dy/dx (r+1) – 2q -1 dx (S – T) = 2 dy (r+1) – 2q dx – dx d i+1 = d i +2 dy – 2 dx (y i -y i-1 )

Алгоритм Брезенхема рисования отрезка procedure line(xa,ya,xb,yb:integer); var dx,dy,inc1,inc2,d,x,y,xend : integer; begindx:=abs(x2-x1); dy:=abs(y2-y1); d:=2*dy-dx; inc1:= 2*dy; inc2:=2*(dy-dx); if x1>x2 then begin x:=x2; y:=y2; xend:=x1 end else begin x:=x1; y:=y1; xend:=x2 end; put(x,y); while x < xend do begin inc(x); if d < 0 then inc(d,inc1) else begin inc(y); inc(d,inc2); end; put(x,y) end;

Алгоритм Брезенхема рисования окружности procedure circle(x0,y0,r:integer); var d,d1,d2,x,y : integer; begin d:=0; y:=r; for x:=0 to round(r*sqrt(2.0)/2) do begin d1:=d+x+x+1; d2:=d1-y-y+1; if abs(d1) < abs(d2) then begin d:=d1; end else begin d:=d2; dec(y); end; put(x0+x,y0+y);put(x0+y,y0+x);put(x0-x,y0+y);put(x0+y,y0-x); put(x0+x,y0-y);put(x0-y,y0+x);put(x0-x,y0-y);put(x0-y,y0-x); end;