Tracer un cercle point à point

Il y a fort fort longtemps ... 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

R : rayon du cercle
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
`DeltaR = Delta_(1)`
`Y = Y + 1`
`X = X - 1`
Sinon
`DeltaR = Delta_(2)`
`Y = Y + 1`
Trace_Pixels(`X`, `Y`)
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
`DeltaR = Delta_(1)`
`Y = Y + 1`
Trace_Pixels(`X`, `Y`)
Trace_Pixels(`Y`, `X`)
`X = X - 1`
Sinon
`DeltaR = Delta_(2)`
`Y = Y + 1`
Trace_Pixels(`X`, `Y`)
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