Bresenhams Linienalgorithmus
Dieser Algorithmus wird für die Scankonvertierung einer Linie verwendet. Es wurde von Bresenham entwickelt. Es handelt sich um eine effiziente Methode, da sie nur ganzzahlige Additions-, Subtraktions- und Multiplikationsoperationen umfasst. Diese Vorgänge können sehr schnell ausgeführt werden, sodass Linien schnell generiert werden können.
Bei dieser Methode wird als nächstes dasjenige Pixel ausgewählt, das den geringsten Abstand von der wahren Linie hat.
Die Methode funktioniert wie folgt:
Nehmen Sie ein Pixel P an 1 '(X 1 ',Und 1 '), wählen Sie dann die nachfolgenden Pixel aus, während wir uns bis zur Nacht vorarbeiten, eine Pixelposition nach der anderen in horizontaler Richtung in Richtung P 2 '(X 2 ',Und 2 ').
Wählen Sie bei jedem Schritt einmal ein Pixel aus
Das nächste Pixel ist
- Entweder der rechts daneben (untere Grenze für die Linie)
- Einer oben rechts und oben (obere Grenze für die Linie)
Die Linie wird am besten durch die Pixel angenähert, die am wenigsten vom Pfad zwischen P entfernt sind 1 ',P 2 '.
Um das nächste zwischen dem unteren Pixel S und dem oberen Pixel T auszuwählen.
Wenn S gewählt wird
Wir haben x i+1 =x ich +1 und y i+1 =y ich
Wenn T gewählt wird
Wir haben x i+1 =x ich +1 und y i+1 =y ich +1
Die tatsächlichen y-Koordinaten der Linie bei x = x i+1 Ist
y=mx i+1 +b
Der Abstand von S zur tatsächlichen Linie in y-Richtung
s = y-y ich
Der Abstand von T zur tatsächlichen Linie in y-Richtung
t = (y ich +1)-y
Betrachten Sie nun den Unterschied zwischen diesen beiden Abstandswerten
s - t
Wann (s-t) <0 ⟹ s < t < p>
Das nächstgelegene Pixel ist S
Wenn (s-t) ≧0 ⟹ s Das nächstgelegene Pixel ist T Dieser Unterschied ist Ersetzen von m durch Wobei c= 2△y+△x (2b-1) Wir können die Entscheidungsvariable d schreiben i+1 für den nächsten Slip-On Da x_(i+1)=x ich +1, das haben wir Sonderfälle Wenn das ausgewählte Pixel das oberste Pixel T ist (d. h. d ich ≧0)⟹ und i+1 =y ich +1 Wenn das ausgewählte Pixel das untere Pixel T ist (d. h. d ich <0)⟹ y i+1=y ich Abschließend berechnen wir d 1 Da mx 1 +b-y ich =0 und m = 1. Da es sich nur um Ganzzahlarithmetik handelt, ist es einfach. 2. Es vermeidet die Generierung doppelter Punkte. 3. Es kann mit Hardware implementiert werden, da keine Multiplikation und Division verwendet wird. 4. Im Vergleich zu DDA (Digital Differential Analyzer) ist es schneller, da keine Gleitkommaberechnungen wie der DDA-Algorithmus erforderlich sind. 1. Dieser Algorithmus ist nur für das einfache Zeichnen von Linien gedacht. Die Initialisierung ist nicht Teil des Linienalgorithmus von Bresenham. Um glatte Linien zu zeichnen, sollten Sie sich also einen anderen Algorithmus ansehen. Schritt 1: Algorithmus starten Schritt 2: Variable x deklarieren 1 ,X 2 ,Und 1 ,Und 2 ,d,i 1 ,ich 2 ,dx,dy Schritt 3: Geben Sie den Wert von x ein 1 ,Und 1 ,X 2 ,Und 2 Schritt 4: Berechnen Sie dx = x 2 -X 1 Schritt 5: Betrachten Sie (x, y) als Ausgangspunkt und x Ende als maximal möglicher Wert von x. Schritt 6: Punkt an (x,y)-Koordinaten generieren. Schritt 7: Überprüfen Sie, ob eine ganze Zeile generiert wird. Schritt 8: Berechnen Sie die Koordinaten des nächsten Pixels Schritt 9: Erhöhe x = x + 1 Schritt 10: Zeichnen Sie einen Punkt mit den neuesten (x, y)-Koordinaten Schritt 11: Gehen Sie zu Schritt 7 Schritt 12: Ende des Algorithmus Beispiel: Start- und Endposition der Linie sind (1, 1) und (8, 5). Finden Sie Zwischenpunkte. Lösung: X 1 =1 Ausgabe:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
und Einführung einer Entscheidungsvariablen
D ich =△x (s-t)
D ich =△x (2 (X ich +1)+2b-2y ich -1)
=2△xy ich -2△y-1△x.2b-2y ich △x-△x
D ich =2△y.x ich -2△x.y ich +c
D i+1 =2△y.x i+1 -2△x.y i+1 +c
D i+1 -D ich =2△y.(x i+1 -X ich )- 2△x(y i+1 -Und ich )
D i+1 +d ich =2△y.(x ich +1-x ich )- 2△x(y i+1 -Und ich )
D i+1 =d ich +2△y-2△x
D i+1 =d ich +2△y
D 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
D 1 =△x[2(mx 1 +b-y 1 )+2m-1] , wir haben
D 1 =2△y-△x Vorteil:
Nachteil:
Bresenhams Linienalgorithmus:
Wo x 1 ,Und 1 sind Koordinaten des Startpunkts
Und x 2 ,Und 2 sind Koordinaten des Endpunkts
Berechnen Sie dy = y 2 -Und 1
Berechnen Sie i 1 =2*du
Berechnen Sie i 2 =2*(dy-dx)
Berechnen Sie d=i 1 -dx
Wenn dx <0
Dann ist x = x 2
y = y 2
X Ende =x 1
Wenn dx > 0
Dann ist x = x 1
y = y 1
X Ende =x 2
Wenn x > = x Ende
Stoppen.
Wenn d <0
Dann ist d = d + i 1
Wenn d ≧ 0
Dann ist d = d + i 2
Erhöhe y = y + 1
Und 1 =1
X 2 =8
Und 2 =5
dx= x 2 -X 1 =8-1=7
du=y 2 -Und 1 =5-1=4
ICH 1 =2* ∆y=2*4=8
ICH 2 =2*(∆y-∆x)=2*(4-7)=-6
d = I 1 -∆x=8-7=1
X Und d=d+I 1 oder ich 2 1 1 d+I 2 =1+(-6)=-5 2 2 d+I 1 =-5+8=3 3 2 d+I 2 =3+(-6)=-3 4 3 d+I 1 =-3+8=5 5 3 d+I 2 =5+(-6)=-1 6 4 d+I 1 =-1+8=7 7 4 d+I 2 =7+(-6)=1 8 5 Programm zur Implementierung des Bresenham-Linienzeichnungsalgorithmus:
#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; } 
Unterscheiden Sie zwischen dem DDA-Algorithmus und dem Bresenham-Linien-Algorithmus:
DDA-Algorithmus Bresenhams Linienalgorithmus 1. Der DDA-Algorithmus verwendet Gleitkommazahlen, d. h. reelle Arithmetik. 1. Bresenhams Linienalgorithmus verwendet Festkomma-Arithmetik, d. h. Ganzzahlarithmetik 2. DDA-Algorithmen verwenden Multiplikation und Division für ihre Operation 2. Bresenhams Linienalgorithmus verwendet bei seiner Operation nur Subtraktion und Addition 3. Der DDA-Algorithmus ist beim Zeichnen von Linien langsamer als der Bresenham-Linienalgorithmus, da er echte Arithmetik (Gleitkommaoperation) verwendet. 3. Der Bresenham-Algorithmus ist schneller als der DDA-Algorithmus, da er in seiner Berechnung nur Addition und Subtraktion umfasst und nur Ganzzahlarithmetik verwendet. 4. Der DDA-Algorithmus ist nicht genau und effizient wie der Linienalgorithmus von Bresenham. 4. Der Linienalgorithmus von Bresenham ist im Vergleich zum DDA-Algorithmus genauer und effizienter. Der 5.DDA-Algorithmus kann Kreise und Kurven zeichnen, ist jedoch nicht so genau wie der Linienalgorithmus von Bresenham 5. Der Linienalgorithmus von Bresenham kann Kreise und Kurven genauer zeichnen als der DDA-Algorithmus.
