Šis algoritmas naudojamas nuskaitymui konvertuojant eilutę. Jį sukūrė Bresenhamas. Tai efektyvus metodas, nes jis apima tik sveikųjų skaičių sudėjimo, atimties ir daugybos operacijas. Šios operacijos gali būti atliekamos labai greitai, todėl greitai galima sukurti linijas.

Taikant šį metodą, kitas pasirenkamas taškas, turintis mažiausią atstumą nuo tikrosios linijos.

Metodas veikia taip:

Tarkime, pikselis P₁'(x₁', ir₁'), tada pasirinkite tolesnius pikselius, kai dirbame nuo gegužės iki nakties, po vieną pikselio padėtį horizontalia kryptimi link P₂'(x₂', ir₂').

Kai tik pikselis, pasirinkite bet kuriuo žingsniu

Kitas pikselis yra

1. Dešinėje esanti (apatinė eilutės riba)
2. Vienas viršuje yra dešinėn ir aukštyn (viršutinė eilutės riba)

Liniją geriausiai apytiksliai nustato tie pikseliai, kurie mažiausią atstumą nukrenta nuo kelio tarp P₁', P₂“.

Norėdami pasirinkti kitą tarp apatinio taško S ir viršutinio pikselio T.
Jei pasirinktas S
Mes turime x_aš+1=x_i+1 ir y_aš+1=y_i
Jei pasirinktas T
Mes turime x_aš+1=x_i+1 ir y_aš+1=y_i+1

Tiesės, esančios x = x, tikrosios y koordinatės_aš+1yra
y=mx_aš+1+b

Atstumas nuo S iki tikrosios linijos y kryptimi
s = y-y_i

Atstumas nuo T iki tikrosios linijos y kryptimi
t = (y_i+1)-y

Dabar apsvarstykite skirtumą tarp šių dviejų atstumo verčių
s - t

Kada (s-t)<0 ⟹ s < t< p>

Artimiausias pikselis yra S

Kai (s-t) ≧0 ⟹ s

Artimiausias pikselis yra T

Šis skirtumas yra
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Pakeičiant m ir įvedant sprendimo kintamąjį
d_i=△x (s-t)
d_i=△x (2 (x_i+1)+2b-2m_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

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

Galime parašyti sprendimo kintamąjį d_aš+1už kitą slydimą
d_aš+1=2△y.x_aš+1-2△x.y_aš+1+c
d_aš+1-d_i=2△y.(x_aš+1-x_i)- 2△x(y_aš+1- ir_i)

Kadangi x_(i+1)=x_i+1, turime
d_aš+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_aš+1- ir_i)

Ypatingi atvejai

Jei pasirinktas pikselis yra viršutiniame pikselyje T (t. y. d_i≧0)⟹ ir_aš+1=y_i+1
d_aš+1=d_i+2△y-2△x

Jei pasirinktas pikselis yra apatiniame pikselyje T (t. y. d_i<0)⟹ y_{i+1=yi
daš+1=di+2△m}

Galiausiai apskaičiuojame d₁
d₁=△x[2m(x₁+1)+2b-2m₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

Nuo mx₁+b-y_i=0 ir m = , mes turime
d₁=2△y-△x

Privalumas:

1. Ji apima tik sveikųjų skaičių aritmetiką, todėl ji yra paprasta.

2. Taip išvengiama pasikartojančių taškų generavimo.

3. Jis gali būti įgyvendintas naudojant techninę įrangą, nes nenaudoja daugybos ir dalybos.

4. Jis yra greitesnis, palyginti su DDA (skaitmeniniu diferencialiniu analizatoriumi), nes neapima slankiojo kablelio skaičiavimų, tokių kaip DDA algoritmas.

Trūkumas:

1. Šis algoritmas skirtas tik pagrindiniam linijų braižymui Inicijuoti nėra Bresenhamo linijų algoritmo dalis. Taigi, norėdami nubrėžti lygias linijas, turėtumėte pažvelgti į kitą algoritmą.

Bresenhamo linijos algoritmas:

1 žingsnis: Pradėti algoritmą

kino aktorė Kajal

2 žingsnis: Deklaruoti kintamąjį x₁,x₂, ir₁, ir₂,d,i₁,t.y₂,dx,dy

3 veiksmas: Įveskite x reikšmę₁, ir₁,x₂, ir₂
Kur x₁, ir₁yra pradinio taško koordinatės
Ir x₂, ir₂yra pabaigos taško koordinatės

4 veiksmas: Apskaičiuokite dx = x₂-x₁
Apskaičiuokite dy = y₂- ir₁
Apskaičiuokite i₁=2*tu
Apskaičiuokite i₂=2*(dy-dx)
Apskaičiuokite d=i₁-dx

5 veiksmas: Apsvarstykite (x, y) kaip pradžios tašką ir x_galaskaip didžiausia galima x reikšmė.
Jei dx<0
Tada x = x₂
y = y₂
x_galas=x₁
Jei dx > 0
Tada x = x₁
y = y₁
x_galas=x₂

6 veiksmas: Sukurkite tašką (x,y) koordinatėse.

7 veiksmas: Patikrinkite, ar sugeneruota visa eilutė.
Jei x > = x_galas
Sustabdyti.

8 veiksmas: Apskaičiuokite kito pikselio koordinates
Jei d<0
Tada d = d + i₁
Jei d ≧ 0
Tada d = d + i₂
Padidinkite y = y + 1

9 veiksmas: Padidinkite x = x + 1

10 veiksmas: Nubrėžkite naujausių (x, y) koordinačių tašką

11 veiksmas: Eikite į 7 veiksmą

12 veiksmas: Algoritmo pabaiga

Pavyzdys: Linijos pradžios ir pabaigos padėtis yra (1, 1) ir (8, 5). Raskite tarpinius taškus.

Sprendimas: x₁=1
ir₁=1
x₂=8
ir₂=5
dx = x₂-x₁=8-1=7
tu=y₂- ir₁=5-1=4
aš₁=2* ∆y=2*4=8
aš₂=2*(∆y-∆x)=2*(4-7)=-6
d = I₁-∆x=8-7=1

Programa, skirta įgyvendinti Bresenhamo linijų braižymo algoritmą:

 #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; } 

Išvestis:

Atskirkite DDA algoritmą nuo Bresenhamo linijos algoritmo: