Algorytm liniowy Bresenhama
Algorytm ten służy do skanowania konwertującego linię. Został opracowany przez Bresenhama. Jest to skuteczna metoda, ponieważ obejmuje tylko dodawanie, odejmowanie i mnożenie liczb całkowitych. Operacje te można wykonać bardzo szybko, dzięki czemu można szybko wygenerować linie.
W tej metodzie kolejnym wybranym pikselem jest ten, który ma najmniejszą odległość od linii prawdziwej.
Metoda działa w następujący sposób:
Załóżmy, że piksel P 1 '(X 1 ',I 1 '), następnie zaznaczaj kolejne piksele w miarę jak pracujemy do nocy, po jednym pikselu na raz w kierunku poziomym w stronę P 2 '(X 2 ',I 2 ').
Po wybraniu piksela w dowolnym kroku
Następny piksel to
- Albo ten po prawej stronie (dolna granica linii)
- Jeden u góry w prawo i w górę (górna granica linii)
Linię najlepiej przybliżają te piksele, które znajdują się w najmniejszej odległości od ścieżki pomiędzy P 1 ',P 2 '.
Aby wybrać następny pomiędzy dolnym pikselem S i górnym pikselem T.
Jeśli wybrano S
Mamy x ja+1 =x I +1 i y ja+1 = y I
Jeśli wybrano T
Mamy x ja+1 =x I +1 i y ja+1 = y I +1
Rzeczywiste współrzędne y linii w punkcie x = x ja+1 Jest
y=mx ja+1 +b
Odległość od S do rzeczywistej linii w kierunku y
s = y-y I
Odległość od T do rzeczywistej linii w kierunku y
t = (y I +1) -y
Rozważmy teraz różnicę między tymi dwiema wartościami odległości
s - t
Kiedy (s-t) <0 ⟹ s < t < p>
Najbliższy piksel to S
Kiedy (s-t) ≧0 ⟹ s Najbliższy piksel to T Ta różnica jest Zastępując m przez Gdzie c= 2△y+△x (2b-1) Możemy zapisać zmienną decyzyjną d ja+1 na następną wpadkę Ponieważ x_(i+1)=x I +1, mamy Specjalne przypadki Jeśli wybrany piksel znajduje się na górnym pikselu T (tzn I ≧0)⟹ i ja+1 = y I +1 Jeśli wybrany piksel znajduje się na dolnym pikselu T (tzn I <0)⟹ y i+1=y I Na koniec obliczamy d 1 Od mx 1 +b-y I =0 i m = 1. Dotyczy tylko arytmetyki liczb całkowitych, więc jest proste. 2. Pozwala uniknąć generowania duplikatów punktów. 3. Można go zaimplementować przy użyciu sprzętu, ponieważ nie używa mnożenia i dzielenia. 4. Jest szybszy w porównaniu do DDA (Digital Differential Analyzer), ponieważ nie obejmuje obliczeń zmiennoprzecinkowych, takich jak algorytm DDA. 1. Algorytm ten jest przeznaczony wyłącznie do podstawowego rysowania linii. Inicjowanie nie jest częścią algorytmu linii Bresenhama. Aby więc rysować gładkie linie, powinieneś przyjrzeć się innemu algorytmowi. Krok 1: Uruchom algorytm Krok 2: Zadeklaruj zmienną x 1 ,X 2 ,I 1 ,I 2 ,d,tj 1 ,I 2 ,dx,dy Krok 3: Wprowadź wartość x 1 ,I 1 ,X 2 ,I 2 Krok 4: Oblicz dx = x 2 -X 1 Krok 5: Rozważ (x, y) jako punkt wyjścia i x koniec jako maksymalna możliwa wartość x. Krok 6: Generuj punkt we współrzędnych (x, y). Krok 7: Sprawdź, czy została wygenerowana cała linia. Krok 8: Oblicz współrzędne następnego piksela Krok 9: Przyrost x = x + 1 Krok 10: Narysuj punkt o ostatnich współrzędnych (x, y). Krok 11: Przejdź do kroku 7 Krok 12: Koniec algorytmu Przykład: Pozycje początkowe i końcowe linii to (1, 1) i (8, 5). Znajdź punkty pośrednie. Rozwiązanie: X 1 =1 Wyjście:
s-t = (y-yi)-[(yi+1)-y]
= 2 lata - 2 lata -1 
i wprowadzenie zmiennej decyzyjnej
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
D ja+1 =2△y.x ja+1 -2△x.y ja+1 +c
D ja+1 -D I =2△y.(x ja+1 -X I )- 2△x(y ja+1 -I I )
D ja+1 +d I =2△y.(x I +1-x I )- 2△x(y ja+1 -I I )
D ja+1 =d I +2△y-2△x
D ja+1 =d I +2△y
D 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
D 1 =△x[2(mx 1 +b-y 1 )+2m-1] , mamy
D 1 =2△y-△x Korzyść:
Niekorzyść:
Algorytm liniowy Bresenhama:
Gdzie x 1 ,I 1 są współrzędnymi punktu początkowego
I x 2 ,I 2 są współrzędnymi punktu końcowego
Oblicz dy = y 2 -I 1
Oblicz I 1 =2*ty
Oblicz I 2 =2*(dy-dx)
Oblicz d=i 1 -dx
Jeśli dx <0
Wtedy x = x 2
y = y 2
X koniec =x 1
Jeśli dx > 0
Wtedy x = x 1
y = y 1
X koniec =x 2
Jeśli x > = x koniec
Zatrzymywać się.
Jeśli d <0
Wtedy d = d + ja 1
Jeśli d ≧ 0
Wtedy d = d + ja 2
Przyrost y = y + 1
I 1 =1
X 2 =8
I 2 =5
dx=x 2 -X 1 =8-1=7
ty=y 2 -I 1 =5-1=4
I 1 =2* ∆y=2*4=8
I 2 =2*(∆y-∆x)=2*(4-7)=-6
d = ja 1 -∆x=8-7=1
X I d=d+ja 1 lub ja 2 1 1 d+ja 2 =1+(-6)=-5 2 2 d+ja 1 =-5+8=3 3 2 d+ja 2 =3+(-6)=-3 4 3 d+ja 1 =-3+8=5 5 3 d+ja 2 =5+(-6)=-1 6 4 d+ja 1 =-1+8=7 7 4 d+ja 2 =7+(-6)=1 8 5 Program implementujący algorytm rysowania linii Bresenhama:
#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; } 
Rozróżnij algorytm DDA od algorytmu liniowego Bresenhama:
Algorytm DDA Algorytm liniowy Bresenhama 1. Algorytm DDA wykorzystuje liczbę zmiennoprzecinkową, czyli arytmetykę rzeczywistą. 1. Algorytm liniowy Bresenhama wykorzystuje punkt stały, tj. arytmetykę liczb całkowitych 2. Algorytmy DDA w swoim działaniu wykorzystują mnożenie i dzielenie 2. Algorytm liniowy Bresenhama wykorzystuje w swojej operacji jedynie odejmowanie i dodawanie 3. Algorytm DDA jest wolniejszy niż algorytm liniowy Bresenhama w rysowaniu linii, ponieważ wykorzystuje rzeczywistą arytmetykę (operacja zmiennoprzecinkowa) 3. Algorytm Bresenhama jest szybszy niż algorytm DDA, ponieważ w obliczeniach uwzględnia jedynie dodawanie i odejmowanie oraz wykorzystuje wyłącznie arytmetykę liczb całkowitych. 4. Algorytm DDA nie jest dokładny i skuteczny w porównaniu z algorytmem liniowym Bresenhama. 4. Algorytm liniowy Bresenhama jest dokładniejszy i wydajniejszy w przypadku algorytmu DDA. 5. Algorytm DDA może rysować koła i krzywe, ale nie jest dokładny jak algorytm liniowy Bresenhama 5. Algorytm liniowy Bresenhama umożliwia rysowanie okręgów i krzywych z większą dokładnością niż algorytm DDA.
