Dit algoritme wordt gebruikt voor het scannen van een lijn. Het is ontwikkeld door Bresenham. Het is een efficiënte methode omdat het alleen gaat om optellingen, aftrekkingen en vermenigvuldigingen van gehele getallen. Deze bewerkingen kunnen zeer snel worden uitgevoerd, zodat lijnen snel kunnen worden gegenereerd.

Bij deze methode wordt de volgende pixel geselecteerd die de minste afstand tot de ware lijn heeft.

De methode werkt als volgt:

Stel een pixel P₁'(X₁',En₁'), selecteer vervolgens de volgende pixels terwijl we tot diep in de nacht doorwerken, pixelpositie voor pixel in de horizontale richting richting P₂'(X₂',En₂').

Zodra u bij elke stap een pixel kiest

De volgende pixel is

1. Ofwel degene aan de rechterkant (ondergrens voor de lijn)
2. Eén bovenaan is rechts en omhoog (bovengrens voor de lijn)

De lijn wordt het beste benaderd door de pixels die zich op de kleinste afstand van het pad tussen P bevinden₁',P₂'.

To kiest de volgende tussen de onderste pixel S en de bovenste pixel T.
Als S wordt gekozen
Wij hebben x_ik+1=x_i+1 en j_ik+1=j_i
Als T wordt gekozen
Wij hebben x_ik+1=x_i+1 en j_ik+1=j_i+1

De werkelijke y-coördinaten van de lijn op x = x_ik+1is
y=mx_ik+1+b

De afstand van S tot de werkelijke lijn in de y-richting
s = j-j_i

De afstand van T tot de werkelijke lijn in de y-richting
t = (j_i+1)-j

Beschouw nu het verschil tussen deze 2 afstandswaarden
s - t

tekenreeks en subtekenreeks

Wanneer (s-t)<0 ⟹ s < t< p>

De dichtstbijzijnde pixel is S

Wanneer (s-t) ≧0 ⟹ s

De dichtstbijzijnde pixel is T

Dit verschil is
s-t = (y-yi)-[(yi+1)-y]
= 2j - 2yi -1

Vervang m door en het introduceren van een beslissingsvariabele
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

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

We kunnen de beslissingsvariabele d schrijven_ik+1voor de volgende slip-on
D_ik+1=2△y.x_ik+1-2△x.y_ik+1+c
D_ik+1-D_i=2△j.(x_ik+1-X_i)- 2△x(j_ik+1-En_i)

Omdat x_(i+1)=x_i+1, dat hebben we
D_ik+1+d_i=2△j.(x_i+1-x_i)- 2△x(j_ik+1-En_i)

Speciale gevallen

Als de gekozen pixel zich op de bovenste pixel T bevindt (d.w.z. d_i≧0)⟹ en_ik+1=j_i+1
D_ik+1=d_i+2△y-2△x

Als de gekozen pixel zich op de onderste pixel T bevindt (d.w.z. d_i<0)⟹ y_{ik+1=ji
Dik+1=di+2△j}

Tenslotte berekenen we d₁
D₁=△x[2m(x₁+1)+2b-2y₁-1]
D₁=△x[2(mx₁+b-y₁)+2m-1]

Sinds MX₁+b-y_i=0 en m= , we hebben
D₁=2△y-△x

Voordeel:

1. Het gaat alleen om rekenen met gehele getallen, dus het is eenvoudig.

2. Het vermijdt het genereren van dubbele punten.

3. Het kan worden geïmplementeerd met behulp van hardware, omdat er geen gebruik wordt gemaakt van vermenigvuldigen en delen.

4. Het is sneller in vergelijking met DDA (Digital Differential Analyzer) omdat er geen drijvende-kommaberekeningen nodig zijn, zoals het DDA-algoritme.

Nadeel:

1. Dit algoritme is alleen bedoeld voor het tekenen van basislijnen. Initialiseren maakt geen deel uit van het lijnalgoritme van Bresenham. Om vloeiende lijnen te tekenen, zou je dus naar een ander algoritme moeten kijken.

Het lijnalgoritme van Bresenham:

Stap 1: Begin algoritme

Stap 2: Declareer variabele x₁,X₂,En₁,En₂,d,ik₁,i₂,dx,dy

Stap 3: Voer de waarde van x in₁,En₁,X₂,En₂
Waar x₁,En₁zijn de coördinaten van het startpunt
En x₂,En₂zijn de coördinaten van het eindpunt

Stap 4: Bereken dx = x₂-X₁
Bereken dy = y₂-En₁
Bereken ik₁=2*jij
Bereken ik₂=2*(dy-dx)
Bereken d=i₁-dx

Stap 5: Beschouw (x, y) als uitgangspunt en x_eindeals maximaal mogelijke waarde van x.
Als dx<0
Dan x = x₂
j = j₂
X_einde=x₁
Als dx > 0
Dan x = x₁
j = j₁
X_einde=x₂

Stap6: Genereer een punt op (x,y)coördinaten.

Stap7: Controleer of de hele lijn is gegenereerd.
Als x > = x_einde
Stop.

Stap 8: Bereken de coördinaten van de volgende pixel
Als d<0
Dan d = d + ik₁
Als d ≧ 0
Dan d = d + ik₂
Verhoging y = y + 1

Stap9: Verhogen x = x + 1

Stap 10: Teken een punt met de laatste (x, y)-coördinaten

Stap 11: Ga naar stap 7

Stap 12: Einde van algoritme

Voorbeeld: Begin- en eindpositie van de lijn zijn (1, 1) en (8, 5). Zoek tussenpunten.

Oplossing: X₁=1
En₁=1
X₂=8
En₂=5
dx = x₂-X₁=8-1=7
jij=j₂-En₁=5-1=4
I₁=2* ∆y=2*4=8
I₂=2*(∆y-∆x)=2*(4-7)=-6
d = ik₁-∆x=8-7=1

Programma om het lijntekeningalgoritme van Bresenham te implementeren:

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

Uitgang:

Maak onderscheid tussen het DDA-algoritme en het lijnalgoritme van Bresenham: