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 2 (, ) : en haut à droite
: écart des abscisses
: écart des ordonnées
L'idée
La droite est la droite parallèle à mais passant par le centre de
La droite est la droite parallèle à mais passant par le centre de
L'idée est de choisir le point suivant pour lequel l'écart cumulé sera minimal.
Petits calculs
Equation de la droite :
avec et
d'où
Equation de la droite :
avec et et et
d'où
Equation de la droite :
avec et et
et
d'où
Comme ce qui nous intéresse ce n'est pas la valeur même mais l'ordre de grandeur de par rapport à
, on les multiplie par :
Comme ce n'est pas forcément pratique de comparer des valeurs absolues dans l'algorithme, on ne va pas comparer avec mais plutôt avec d'où l'expression 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.
Affiche_Pixel(, )
1er quadrant
Si et Alors
# en dessous 1ere bissectrice
Si Alors
# au dessus 1ere bissectrice
Tant que
Si Alors
Affiche_Pixel(, )
Sinon
Tant que
Si Alors
Affiche_Pixel(, )
2ème quadrant
Si et Alors
# en dessous 2e bissectrice
Si Alors
# au dessus 2e bissectrice
Tant que
Si Alors
Affiche_Pixel(, )
Sinon
Tant que
Si Alors
Affiche_Pixel(, )
3ème quadrant
Si et Alors
# en dessous 3e bissectrice
Si Alors
# au dessus 3e bissectrice
Tant que
Si Alors
Affiche_Pixel(, )
Sinon
Tant que
Si Alors
Affiche_Pixel(, )
4ème quadrant
Si et Alors
# en dessous 4e bissectrice
Si Alors
# au dessus 4e bissectrice
Tant que
Si Alors
Affiche_Pixel(, )
Sinon
Tant que
Si Alors.
Affiche_Pixel(, )