Cet algorithme est utilisé pour convertir une ligne par balayage. Il a été développé par Bresenham. Il s’agit d’une méthode efficace car elle implique uniquement des opérations d’addition, de soustraction et de multiplication d’entiers. Ces opérations peuvent être effectuées très rapidement afin que les lignes puissent être générées rapidement.

Dans cette méthode, le prochain pixel sélectionné est celui qui a le moins de distance par rapport à la vraie ligne.

La méthode fonctionne comme suit :

réseaux informatiques

Supposons un pixel P₁'(X₁',et₁'), puis sélectionnez les pixels suivants au fur et à mesure que nous travaillons jusqu'à la nuit, une position de pixel à la fois dans la direction horizontale vers P.₂'(X₂',et₂').

Une fois un pixel entré, choisissez à tout moment

Le pixel suivant est

1. Soit celui à sa droite (borne inférieure de la ligne)
2. Un en haut à droite et en haut (limite supérieure de la ligne)

La ligne est mieux approchée par les pixels qui se trouvent le moins à distance du chemin entre P₁',P₂'.

To choisit le suivant entre le pixel du bas S et le pixel du haut T.
Si S est choisi
Nous avons x_je+1=x_je+1 et y_je+1=oui_je
Si T est choisi
Nous avons x_je+1=x_je+1 et y_je+1=oui_je+1

Les coordonnées y réelles de la ligne à x = x_je+1est
y=mx_je+1+b

La distance de S à la ligne réelle dans la direction y
s = a-y_je

La distance de T à la ligne réelle dans la direction y
t = (y_je+1)-y

Considérons maintenant la différence entre ces 2 valeurs de distance
St

Quand (merde)<0 ⟹ s < t< p>

Le pixel le plus proche est S

Quand (s-t) ≧0 ⟹ s

Le pixel le plus proche est T

Cette différence est
s-t = (y-yi)-[(yi+1)-y]
= 2a - 2yi -1

Remplacer m par et introduction de la variable de décision
d_je=△x (s-t)
d_je=△x (2 (X_je+1)+2b-2a_je-1)
=2△xy_je-2△y-1△x.2b-2y_je△x-△x
d_je=2△y.x_je-2△x.y_je+c

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

On peut écrire la variable de décision d_je+1pour le prochain slip
d_je+1=2△y.x_je+1-2△x.y_je+1+c
d_je+1-d_je=2△y.(x_je+1-X_je)- 2△x(y_je+1-et_je)

Puisque x_(i+1)=x_je+1, nous avons
d_je+1+d_je=2△y.(x_je+1-x_je)- 2△x(y_je+1-et_je)

Cas spéciaux

Si le pixel choisi est au pixel supérieur T (c'est-à-dire d_je≧0)⟹ et_je+1=oui_je+1
d_je+1=d_je+2△y-2△x

Si le pixel choisi se trouve au pixel inférieur T (c'est-à-dire d_je<0)⟹ y_{je+1=yje
dje+1=dje+2△y}

Finalement, on calcule d₁
d₁=△x[2m(x₁+1)+2b-2a₁-1]
d₁=△x[2(mx₁+par-y₁)+2m-1]

Depuis mx₁+par-y_je=0 et m = , nous avons
d₁=2△y-△x

Avantage:

1. Cela implique uniquement de l’arithmétique entière, donc c’est simple.

2. Cela évite la génération de points en double.

3. Il peut être implémenté à l’aide de matériel car il n’utilise ni multiplication ni division.

4. Il est plus rapide que le DDA (Digital Differential Analyser) car il n'implique pas de calculs à virgule flottante comme l'algorithme DDA.

Désavantage:

1. Cet algorithme est destiné uniquement au dessin de lignes de base. L'initialisation ne fait pas partie de l'algorithme de lignes de Bresenham. Donc, pour tracer des lignes douces, vous devriez envisager un algorithme différent.

Algorithme de ligne de Bresenham :

Étape 1: Démarrer l'algorithme

générateur de nombres aléatoires en c

Étape 2: Déclarer la variable x₁,X₂,et₁,et₂,d,je₁,je₂,dx,dy

chaîne ajouter

Étape 3: Entrez la valeur de x₁,et₁,X₂,et₂
Où x₁,et₁sont les coordonnées du point de départ
Et x₂,et₂sont les coordonnées du point final

Étape 4: Calculer dx = x₂-X₁
Calculer dy = y₂-et₁
Calculer je₁=2*tu
Calculer je₂=2*(dy-dx)
Calculer d=i₁-dx

Étape 5 : Considérons (x, y) comme point de départ et x_fincomme valeur maximale possible de x.
Si dx<0
Alors x = x₂
y = y₂
X_fin=x₁
Si dx > 0
Alors x = x₁
y = y₁
X_fin=x₂

Étape 6 : Générez un point aux coordonnées (x, y).

Étape 7 : Vérifiez si la ligne entière est générée.
Si x > = x_fin
Arrêt.

Étape 8 : Calculer les coordonnées du pixel suivant
Si d<0
Alors d = d + je₁
Si d ≧ 0
Alors d = d + je₂
Incrément y = y + 1

Étape 9 : Incrément x = x + 1

Étape 10 : Dessiner un point de dernières coordonnées (x, y)

Étape 11 : Passez à l'étape 7

Étape 12 : Fin de l'algorithme

Exemple: Les positions de début et de fin de la ligne sont (1, 1) et (8, 5). Trouvez des points intermédiaires.

Solution: X₁=1
et₁=1
X₂=8
et₂=5
dx = x₂-X₁=8-1=7
tu=o₂-et₁=5-1=4
je₁=2* ∆y=2*4=8
je₂=2*(∆y-∆x)=2*(4-7)=-6
d = je₁-∆x=8-7=1

Programme pour implémenter l'algorithme de dessin de lignes de Bresenham :

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

Sortir:

Faites la différence entre l'algorithme DDA et l'algorithme de ligne de Bresenham :