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.

Zeichenfolge enthält Java

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+1Ist
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

Datum in String konvertieren

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+1fü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=yich
Di+1=dich+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.

Java-String-Join

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

Java enthält Teilzeichenfolge

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_Endeals 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

tostring-Methode Java

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: