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 cercle.
Schéma
On suppose le Centre du cercle en (0, 0)
Point Rose (R, 0) : point de départ de l'algorithme
L'idée
L'idée est que les points suivent le chemin qui est le plus prêt possible du cercle donc ce qui peut être
traduit par :
=> le cercle est le chemin de pixels pour lequel l'écart avec le rayon est minimal
Tout se passe donc par rapport au rayon.
Petits calculs
Equation du cercle dans le cas parfait :
`R^2 = x^2 + y^2`
Equation du cercle dans le cas A ou `x' = x - 1` et `y' = y + 1` (cf point A sur graphe) :
`R'^2 = x'^2 + y'^2`
`R'^2 = (x-1)^2 + (y+1)^2`
`R'^2 = x^2 - 2x + 1 + y^2 + 2y +1`
`R'^2 = x^2 + y^2 + 2y - 2x + 2`
`R'^2 = R^2 + 2y - 2x + 2`
`R'^2 = R^2 + DeltaR` avec `DeltaR = 2y - 2x + 2`
Equation du cercle dans le cas B ou `x' = x` et `y' = y + 1` (cf point B sur graphe) :
`R'^2 = x'^2 + y'^2`
`R'^2 = x^2 + (y+1)^2`
`R'^2 = x^2 + y^2 + 2y +1`
`R'^2 = R^2 + 2y +1`
`R'^2 = R^2 + DeltaR` avec `DeltaR = 2y +1`
Remarque :
On se limite qu'aux cas A et B car on arrêtera l'algorithme à `x = y` étant donné que pour les autres
points, il suffit de les représenter par symétries.
Conclusion :
On a les deux expressions possibles de `DeltaR`.
Pour tracer le cercle il suffit d'itérer cela en choisissant à chaque fois le `DeltaR` le plus petit.
Algorithme
Cet algorithme a comme syntaxe une syntaxe très basique.
A vous de la traduire dans le language qu'il vous plaira.
Algorithme pour que le cercle puisse être colorié par un programme de coloriage à 4 voisins :
Début
`R =` rayon du cercle
`DeltaR = 0`
`X = R`
`Y = 0`
Trace_Pixels(`R`, `0`)
Trace_Pixels(`0`, `R`)
Tant que `X > Y` faire
`Delta_(1) = DeltaR + 2Y - 2X + 2`
`Delta_(2) = DeltaR + 2Y + 1`
Si `|Delta_(1)| < |Delta_(2)|`
Alors
Trace_Pixels(`X`, `Y`)
`DeltaR = Delta_(1)`
Sinon
`Y = Y + 1`
`X = X - 1`
`DeltaR = Delta_(2)`
`Y = Y + 1`
Trace_Pixels(`Y`, `X`)
Fin
Cet algorithme présente un problème dans le cas où vous voudriez effectuer un coloriage du cercle avec un algorithme à 8 voisins car le cercle n'arrêterait pas le coloriage.
Algorithme pour que le cercle puisse être colorié par un programme de coloriage à 8 voisins :
Début
`R =` rayon du cercle
`DeltaR = 0`
`X = R`
`Y = 0`
Trace_Pixels(`R`, `0`)
Trace_Pixels(`0`, `R`)
Tant que `X > Y` faire
`Delta_(1) = DeltaR + 2Y - 2X + 2`
`Delta_(2) = DeltaR + 2Y + 1`
Si `|Delta_(1)| < |Delta_(2)|`
Alors
Trace_Pixels(`X`, `Y`)
`DeltaR = Delta_(1)`
Sinon
`Y = Y + 1`
Trace_Pixels(`X`, `Y`)
Trace_Pixels(`Y`, `X`)
`X = X - 1`
`DeltaR = Delta_(2)`
`Y = Y + 1`
Trace_Pixels(`Y`, `X`)
Fin
La différence avec l'algorithme précédent est le tracé de pixels supplémentaires au milieu de la boucle.
Sous-Programme Trace_Pixels(X, Y)
Début
`X_(0) =` abscisse du centre
`Y_(0) =` ordonnée du centre
Affiche_Pixel(`X_(0) + X`, `Y_(0) + Y`)
Affiche_Pixel(`X_(0) + X`, `Y_(0) - Y`)
Affiche_Pixel(`X_(0) - X`, `Y_(0) + Y`)
Affiche_Pixel(`X_(0) - X`, `Y_(0) - Y`)
Fin