Tento algoritmus se používá pro skenování převodu řádku. Byl vyvinut společností Bresenham. Je to efektivní metoda, protože zahrnuje pouze operace sčítání, odčítání a násobení celých čísel. Tyto operace lze provádět velmi rychle, takže lze rychle generovat čáry.

V této metodě je jako další vybraný pixel ten, který má nejmenší vzdálenost od skutečné čáry.

Metoda funguje následovně:

Předpokládejme pixel P₁'(X₁',a₁'), pak vybírejte následující pixely, jak pracujeme, až do noci, po jednom pixelu ve vodorovném směru směrem k P₂'(X₂',a₂').

Jakmile pixel vstoupíte, vyberte si v libovolném kroku

Další pixel je

1. Buď ten napravo (dolní hranice pro řádek)
2. Jeden nahoře vpravo a nahoru (horní hranice pro řádek)

Čára je nejlépe aproximována těmi pixely, které spadají do nejmenší vzdálenosti od cesty mezi P₁',P₂'.

To vybere další mezi spodním pixelem S a horním pixelem T.
Pokud je zvoleno S
Máme x_i+1=x_i+1 a y_i+1=y_i
Pokud je zvoleno T
Máme x_i+1=x_i+1 a y_i+1=y_i+1

Skutečné souřadnice y přímky v x = x_i+1je
y=mx_i+1+b

Vzdálenost od S ke skutečné přímce ve směru y
s = y-y_i

Vzdálenost od T ke skutečné přímce ve směru y
t = (y_i+1)-y

Nyní zvažte rozdíl mezi těmito 2 hodnotami vzdálenosti
Svatý

Když (s-t)<0 ⟹ s < t< p>

Nejbližší pixel je S

Když (s-t) ≧0 ⟹ s

Nejbližší pixel je T

Tento rozdíl je
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Nahrazení m za a zavedení rozhodovací proměnné
d_i=△x (s-t)
d_i=△x (2 (X_i+1)+2b-2y_i-1)
= 2△xy_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.y_i+c

Kde c= 2△y+△x (2b-1)

Rozhodovací proměnnou d můžeme napsat_i+1na další skluz
d_i+1=2△y.x_i+1-2△x.y_i+1+c
d_i+1-d_i=2△y.(x_i+1-X_i)- 2△x(y_i+1-a_i)

Protože x_(i+1)=x_i+1, máme
d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-a_i)

Speciální případy

Pokud je vybraný pixel na horním pixelu T (tj. d_i≧0)⟹ a_i+1=y_i+1
d_i+1=d_i+2△y-2△x

Pokud je vybraný pixel na spodním pixelu T (tj. d_i<0)⟹ y_{i+1=yi
di+1=di+2△r}

Nakonec vypočítáme d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

Od mx₁+b-y_i=0 a m = , my máme
d₁=2△y-△x

Výhoda:

1. Zahrnuje pouze celočíselnou aritmetiku, takže je jednoduchý.

2. Vyhne se generování duplicitních bodů.

3. Může být implementován pomocí hardwaru, protože nepoužívá násobení a dělení.

4. Je rychlejší ve srovnání s DDA (Digital Differential Analyzer), protože nezahrnuje výpočty s plovoucí desetinnou čárkou jako algoritmus DDA.

Nevýhoda:

1. Tento algoritmus je určen pouze pro základní kreslení čar Inicializace není součástí Bresenhamova liniového algoritmu. Chcete-li tedy nakreslit hladké čáry, měli byste se podívat na jiný algoritmus.

Bresenhamův lineární algoritmus:

Krok 1: Spustit algoritmus

Krok 2: Deklarujte proměnnou x₁,X₂,a₁,a₂,d,i₁,i₂,dx,dy

index java

Krok 3: Zadejte hodnotu x₁,a₁,X₂,a₂
Kde x₁,a₁jsou souřadnice výchozího bodu
A x₂,a₂jsou souřadnice koncového bodu

Krok 4: Vypočítejte dx = x₂-X₁
Vypočítejte dy = y₂-a₁
Vypočítejte i₁= 2*ty
Vypočítejte i₂=2*(dy-dx)
Vypočítejte d=i₁-dx

Krok 5: Uvažujme (x, y) jako výchozí bod a x_konecjako maximální možná hodnota x.
Pokud dx<0
Pak x = x₂
y = y₂
X_konec=x₁
Pokud dx > 0
Pak x = x₁
y = y₁
X_konec=x₂

Krok 6: Vygenerujte bod na souřadnicích (x,y).

Krok 7: Zkontrolujte, zda je generován celý řádek.
Pokud x > = x_konec
Stop.

Krok 8: Vypočítejte souřadnice dalšího pixelu
Pokud d<0
Potom d = d + i₁
Pokud d ≧ 0
Potom d = d + i₂
Přírůstek y = y + 1

Krok 9: Přírůstek x = x + 1

Krok 10: Nakreslete bod nejnovějších (x, y) souřadnic

Krok 11: Přejděte ke kroku 7

Krok 12: Konec algoritmu

Příklad: Počáteční a Koncová pozice řádku jsou (1, 1) a (8, 5). Najděte mezilehlé body.

Řešení: X₁=1
a₁=1
X₂=8
a₂=5
dx = x₂-X₁=8-1=7
ty=y₂-a₁=5-1=4
já₁=2* ∆y=2*4=8
já₂=2*(∆y-∆x)=2*(4-7)=-6
d = I₁-∆x=8-7=1

Program pro implementaci Bresenhamova algoritmu pro kreslení čar:

 #include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 

Výstup:

Rozdíl mezi algoritmem DDA a algoritmem Bresenham's Line: