Algorytm Bresenhama rysowania linii

Algorytm Bresenhama rysujący linię i bazujący na współrzędnych jej początku (x₁,y₁) i końca (x₂,y₂) można podzielić na pięć fragmentów:

1. przygotowanie danych do rysowania,

2. rysowanie linii poziomej,

3. rysowanie linii pionowej,

(1)

4. rysowanie linii, dla której spełniony jest warunek:
   ,

(2)

5. rysowanie linii, dla której spełniony jest warunek:
   .

Każde uruchomienie procedury powoduje narysowanie linii poprzez jeden z fragmentów 2-5. Punkty 2,3 nie wymagają specjalnego wyjaśnienia. Powinien wystarczyć komentarz zamieszczony obok kodu źródłowego. Wyjaśnienia mogą wymagać punkty 4,5. W niniejszej instrukcji szczegółowo zostanie omówiony przypadek 4. Przypadek 5 jest analogiczny do 4. Załóżmy, że na rysunku 1 zaprezentowano w powiększeniu fragment ekranu monitora. Szara siatka reprezentuje układ pikseli. Każdy piksel reprezentowany jest przez kwadrat o boku
2 cm, ograniczony ciągłą linią. Środek każdego piksela wyznacza punkt będący przecięciem linii przerywanych. Przykładowe środki pikseli znaczone na rysunku to punkty: A₀, A_i-1, A_i, B_i-1, B_i, A_n. Zadanie algorytmu to narysowanie linii od piksela A₀ = (x₀, y₀) do piksela
A_n = (x_n, y_n). Na rysunku czerwonym kolorem narysowano linię o początku w punkcie
A₀ = (x₁, y₁) i końcu w punkcie A_n = (x_n, y_n). Linia ta reprezentuje pewien wzorzec do którego powinien dążyć algorytm. Niestety, ze względu na dość duże rozmiary pikseli, w prezentowanym przykładzie, rysowana przez algorytm linia będzie jedynie pewnym „dalece niedoskonałym” przybliżeniem linii czerwonej. Na starcie algorytm zapali piksel A₀ następnie w każdym następnym kroku i będzie zapalał ten piksel spośród A_i i B_i, którego środek znajduje się bliżej czerwonej linii.

Załóżmy, że w kroku i-1 zapalono piksel A_i-1. Na rysunku 1 zapalony piksel wypełniono kolorem szarym.

W kroku i algorytm podejmie decyzję co do wyboru następnego piksela.

Jeżeli d(A_i, L_i) ≤ d(B_i, L_i) to zostanie zapalony piksel A_i. W przeciwnym wypadku tzn.
d(A_i, L_i) > d(B_i, L_i) zostanie zapalony piksel B_i.

Przyjmując odległość euklidesową można napisać:

(3)

Po opuszczeniu modułów i uporządkowaniu mamy:

(4)

Wykorzystując z (4) można napisać następujące równanie:

(5)

Mnożąc obie strony ostatniego równania przez
otrzymujemy:

(6)

Po podstawieniu
otrzymujemy:

Wartość d_i można traktować jako kryterium wyboru punktu w kroku i.

(7)

(8)

(9)

(10)

(11)

(12)

Inaczej formułę (7) można zapisać następująco:

Zwiększając formalnie indeksy o 1 otrzymujemy:

Odejmując od równania (9) równanie (8) otrzymujemy związek między kryteriami wyboru w krokach: i oraz i+1:

Ponieważ
to ostatnie równanie można zapisać prościej:

Na podstawie powyższych rozważań można zapisać sposób postępowania algorytmu w ogólnym przypadku:

1. Jeżeli
   (d(A_i, L_i) > d(B_i, L_i) ) to algorytm wybiera punkt B_i. Wtedy
   . Stąd i z (11) mamy:

2. Jeżeli
   (d(A_i, L_i) ≤ d(B_i, L_i) ) to algorytm wybiera punkt A_i. Wtedy
   . Stąd i z (11) mamy:

(13)

Najpierw algorytm zapala punkt A₀. Następnie przyjmując, że (x₀, y₀) = (0, 0) oraz wykorzystując (8) otrzymujemy kryterium w kroku i = 0:

(14)

Schemat algorytmu w ogólnym przypadku:

Rysunek 1 Ilustracja zasady działania algorytmu Bresenhama.

Teraz algorytm Bresenhama zostanie zaprezentowany na przykładzie zilustrowanym na rysunku 2:

Krok 0:

Zapalenie piksela A₀

Krok 1:

Ponieważ d₁ < 0, to zapalenie piksela A₁.

Krok 2:

Ponieważ d₂ < 0, to zapalenie piksela A₂.

Krok 3:

Ponieważ d₃ < 0, to zapalenie piksela A₃.

Krok 4

Ponieważ d₄ > 0, to zapalenie piksela B₄.

Krok 5:

Ponieważ d₅ < 0, to zapalenie piksela A₅.

Krok 6:

Ponieważ d₆ < 0, to zapalenie piksela A₆.

Krok 7:

Ponieważ d₇ < 0, to zapalenie piksela A₇.

Krok 8:

Ponieważ d₈ < 0, to zapalenie piksela A₈.

Krok 9:

Ponieważ d₉ < 0, to zapalenie piksela A₉.

Krok 10:

Ponieważ d₁₀ < 0, to zapalenie piksela A₁₀.

Krok 11:

Ponieważ d₁₁ < 0, to zapalenie piksela A₁₁.

Krok 12:

Ponieważ d₁₂ > 0, to zapalenie piksela B₁₂.

Krok 13:

Ponieważ d₁₃ > 0, to zapalenie piksela A₁₃.

Krok 14:

Ponieważ d₁₄ > 0, to zapalenie piksela A₁₄.

Krok 15:

Ponieważ d₁₅ > 0, to zapalenie piksela A₁₅.

KONIEC

Rysunek 2 Przykład sposobu działania algorytmu Bresenhama

Krok 0:

Zapalenie piksela (x₀, y₀) i wyliczenie d₁ ze wzoru (14)

Krok i-ty:

Dla kryterium d_i obliczonego w poprzednim kroku

1. Jeżeli d_i >0 to wybór punktu
   i obliczenie
   ze wzoru (12).

2. Jeżeli d_i ≤0 to wybór punktu
   i obliczenie
   ze wzoru (13).

0 1 2 3 4 5 6 7

A_i-1=(x_i-1, y_i-1)

A_i=(x_i-1+1, y_i-1)

A₀=(x₀,y₀)

B_i-1

B_i=(x_i-1+1, y_i-1+1)

L_i-1

0

1

2

A_n=(x_n,y_n)

L_i

A₁

A₂

A₃

A₄

A₀=(x₀,y₀)

A₅

A₆

A₇

A₈

A₉

A₁₀

A₁₁

A₁₂

B₁

B₂

B₃

B₄

A₁₃

A₁₄

A₁₅=(x₁₅,y₁₅)

B₅

B₆

B₇

B₈

B₉

B₁₀

B₁₁

B₁₂

B₁₃

B₁₅

L₁

L₂

L₃

L₄

L₅

L₆

L₇

L₈

L₉

L₁₀

L₁₁

L₁₂

L₁₃

L₁₄

B₁₄

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0

1

2

3

4

5

---