Algorithme de droite

Pour tracer des droites avec peu de ressource

Pour tracer des droites avec peu de ressource

Mai 2001

Durant mes études... j'ai travaillé sur un jeu de puissance 4 en assembleur, à cette occasion, j'ai eu à trouver une technique de tracé de droite et de cercle en minimisant les calculs.

J'ai découvert plus tard que cet algorithme avait déjà un nom. C'est celui de leur inventeur originel : Jack E. Bresenham

Vous trouverez ici ma forme de cet algorithme de tracé de droite.

Schéma

Point 1 (`X_(1)`, `Y_(1)`) : en bas à gauche
Point 2 (`X_(2)`, `Y_(2)`) : en haut à droite
`Deltax = X_(2) - X_(1)` : écart des abscisses
`Deltay = Y_(2) - Y_(1)` : écart des ordonnées

L'idée

La droite `(D2)` est la droite théorique tracée entre le point de départ et le point d'arrivée
La droite `(D1)` est la droite parallèle à `(D)` mais passant par le centre de `A`
La droite `(D2)` est la droite parallèle à `(D)` mais passant par le centre de `B`
L'idée est de choisir le point suivant pour lequel l'écart cumulé sera minimal.

Petits calculs

Equation de la droite `(D)` :
`y = a*x + b` avec `a = (Deltay)/(Deltax)` et `b = Y_(1) - (Deltay)/(Deltax)*X_(1)`
d'où `(E) : y = (Deltay)/(Deltax)*x + b`

Equation de la droite `(D1)` :
`y' = a*x' + b'` avec `a = (Deltay)/(Deltax)` et `b' = b + Delta_(1)` et `y' = y + 1` et `x' = x + 1`
d'où `(E_(1)) : y + 1 = (Deltay)/(Deltax)*(x + 1) + b + Delta_(1)`
`(E_(1) - E) : 1 = (Deltay)/(Deltax) + Delta_(1) => Delta_(1) = 1 - (Deltay)/(Deltax)`

Equation de la droite `(D2)` :
`y' = a*x' + b'` avec `a = (Deltay)/(Deltax)` et `b' = b + Delta_(2)` et `y' = y` et `x' = x + 1`
d'où `(E_(2)) : y = (Deltay)/(Deltax)*(x + 1) + b + Delta_(2)`
`(E_(2) - E) : 0 = (Deltay)/(Deltax) + Delta_(2) => Delta_(2) = - (Deltay)/(Deltax)`

Comme ce qui nous intéresse ce n'est pas la valeur même mais l'ordre de grandeur de `Delta_(1)` par rapport à `Delta_(2)`, on les multiplie par `Deltax` :
`Delta'_(1) = Deltax - Deltay`
`Delta'_(2) = - Deltay`

Comme ce n'est pas forcément pratique de comparer des valeurs absolues dans l'algorithme, on ne va pas comparer `|Delta'_(1)|` avec `|Delta'_(2)|` mais plutôt `|Delta'_(2)| - |Delta'_(1)|` avec `0` d'où l'expression `2 * DeltaY - DeltaX` et les suivantes que vous allez voir ci-dessous.

Algorithme

Cet algorithme a comme syntaxe une syntaxe très basique.
A vous de la traduire dans le language qu'il vous plaira.

Dans cet algorithme je ne me limite pas au premier quadrant comme vu ci-dessus pour exprimer les formules.

`X = X_(1)`
`Y = Y_(1)`
`DeltaX = |X_(2) - X_(1)|`
`DeltaY = |Y_(2) - Y_(1)|`
Affiche_Pixel(`X`, `Y`)

1er quadrant

Si `X_(1) <= X_(2)` et `Y_(1) <= Y_(2)` Alors # en dessous 1ere bissectrice
Si `X_(2) - X_(1) >= Y_(2) - Y_(1)` Alors `Delta = 2 * DeltaY - DeltaX`
Tant que `X <> X_(2)`
`X = X + 1`
Si `Delta > 0` Alors
`Y = Y + 1`
`Delta = Delta - 2 * DeltaX` `Delta = Delta + 2 * DeltaY`
Affiche_Pixel(`X`, `Y`) # au dessus 1ere bissectrice
Sinon `Delta = 2 * DeltaX - DeltaY`
Tant que `Y <> Y_(2)`
`Y = Y + 1`
Si `Delta > 0` Alors
`X = X + 1`
`Delta = Delta - 2 * DeltaY` `Delta = Delta + 2 * DeltaX`
Affiche_Pixel(`X`, `Y`)

2ème quadrant

Si `X_(1) > X_(2)` et `Y_(1) < Y_(2)` Alors
# en dessous 2e bissectrice
Si `X_(1) - X_(2) >= Y_(2) - Y_(1)` Alors
`Delta = 2 * DeltaY - DeltaX`
Tant que `X <> X_(2)`
`X = X - 1`
Si `Delta > 0` Alors
`Y = Y + 1`
`Delta = Delta - 2 * DeltaX`
 `Delta = Delta + 2 * DeltaY`
Affiche_Pixel(`X`, `Y`)
 # au dessus 2e bissectrice
Sinon
`Delta = 2 * DeltaX - DeltaY`
Tant que `Y <> Y_(2)`
`Y = Y + 1`
Si `Delta > 0` Alors
`X = X - 1`
`Delta = Delta - 2 * DeltaY`
 `Delta = Delta + 2 * DeltaX`
Affiche_Pixel(`X`, `Y`)

3ème quadrant

Si `X_(1) >= X_(2)` et `Y_(1) >= Y_(2)` Alors
# en dessous 3e bissectrice
Si `X_(1) - X_(2) >= Y_(1) - Y_(2)` Alors
`Delta = 2 * DeltaY - DeltaX`
Tant que `X <> X_(2)`
`X = X - 1`
Si `Delta > 0` Alors
`Y = Y - 1`
`Delta = Delta - 2 * DeltaX`
 `Delta = Delta + 2 * DeltaY`
Affiche_Pixel(`X`, `Y`)
 # au dessus 3e bissectrice
Sinon
`Delta = 2 * DeltaX - DeltaY`
Tant que `Y <> Y_(2)`
`Y = Y - 1`
Si `Delta > 0` Alors
`X = X - 1`
`Delta = Delta - 2 * DeltaY`
 `Delta = Delta + 2 * DeltaX`
Affiche_Pixel(`X`, `Y`)

4ème quadrant

Si `X_(1) < X_(2)` et `Y_(1) > Y_(2)` Alors
# en dessous 4e bissectrice
Si `X_(2) - X_(1) >= Y_(1) - Y_(2)` Alors
`Delta = 2 * DeltaY - DeltaX`
Tant que `X <> X_(2)`
`X = X + 1`
Si `Delta > 0` Alors
`Y = Y - 1`
`Delta = Delta - 2 * DeltaX`
 `Delta = Delta + 2 * DeltaY`
Affiche_Pixel(`X`, `Y`)
 # au dessus 4e bissectrice
Sinon
`Delta = 2 * DeltaX - DeltaY`
Tant que `Y <> Y_(2)`
`Y = Y - 1`
Si `Delta > 0` Alors.
`X = X + 1`
`Delta = Delta - 2 * DeltaY`
 `Delta = Delta + 2 * DeltaX`
Affiche_Pixel(`X`, `Y`)