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 ₁ '(X ₁ ',Und ₁ '), 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 ₂ '(X ₂ ',Und ₂ ').

Wählen Sie bei jedem Schritt einmal ein Pixel aus

Das nächste Pixel ist

1. Entweder der rechts daneben (untere Grenze für die Linie)
2. 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 ₁ ',P ₂ '.

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
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Ersetzen von m durch 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

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

Wir können die Entscheidungsvariable d schreiben _i+1 für den nächsten Slip-On
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 )

Da x_(i+1)=x _ich +1, das haben wir
D _i+1 +d _ich =2△y.(x _ich +1-x _ich )- 2△x(y _i+1 -Und _ich )

Sonderfälle

Wenn das ausgewählte Pixel das oberste Pixel T ist (d. h. d _ich ≧0)⟹ und _i+1 =y _ich +1
D _i+1 =d _ich +2△y-2△x

Wenn das ausgewählte Pixel das untere Pixel T ist (d. h. d _ich <0)⟹ y _{i+1=y ich
D i+1 =d ich +2△y}

Abschließend berechnen wir d ₁
D ₁ =△x[2m(x ₁ +1)+2b-2y ₁ -1]
D ₁ =△x[2(mx ₁ +b-y ₁ )+2m-1]

Da mx ₁ +b-y _ich =0 und m = , wir haben
D ₁ =2△y-△x

Vorteil:

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.

Nachteil:

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.

Bresenhams Linienalgorithmus:

Schritt 1: Algorithmus starten

Schritt 2: Variable x deklarieren ₁ ,X ₂ ,Und ₁ ,Und ₂ ,d,i ₁ ,ich ₂ ,dx,dy

Schritt 3: Geben Sie den Wert von x ein ₁ ,Und ₁ ,X ₂ ,Und ₂
Wo x ₁ ,Und ₁ sind Koordinaten des Startpunkts
Und x ₂ ,Und ₂ sind Koordinaten des Endpunkts

Schritt 4: Berechnen Sie dx = x ₂ -X ₁
Berechnen Sie dy = y ₂ -Und ₁
Berechnen Sie i ₁ =2*du
Berechnen Sie i ₂ =2*(dy-dx)
Berechnen Sie d=i ₁ -dx

Schritt 5: Betrachten Sie (x, y) als Ausgangspunkt und x _Ende als maximal möglicher Wert von x.
Wenn dx <0
Dann ist x = x ₂
y = y ₂
X _Ende =x ₁
Wenn dx > 0
Dann ist x = x ₁
y = y ₁
X _Ende =x ₂

Schritt 6: Punkt an (x,y)-Koordinaten generieren.

Schritt 7: Überprüfen Sie, ob eine ganze Zeile generiert wird.
Wenn x > = x _Ende
Stoppen.

Schritt 8: Berechnen Sie die Koordinaten des nächsten Pixels
Wenn d <0
Dann ist d = d + i ₁
Wenn d ≧ 0
Dann ist d = d + i ₂
Erhöhe y = y + 1

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
Und ₁ =1
X ₂ =8
Und ₂ =5
dx= x ₂ -X ₁ =8-1=7
du=y ₂ -Und ₁ =5-1=4
ICH ₁ =2* ∆y=2*4=8
ICH ₂ =2*(∆y-∆x)=2*(4-7)=-6
d = I ₁ -∆x=8-7=1

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

Ausgabe:

Unterscheiden Sie zwischen dem DDA-Algorithmus und dem Bresenham-Linien-Algorithmus: