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

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+1 voor 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=j i
D ik+1 =d i +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 _einde als 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: