Tracé d'un cercle

Je vous présente ici 5 algorithmes de tracé de cercles utilisant des entiers.

 Algorithme d'Eric Andres

Principe : Eric Andres intègre les coordonnées du centre dans l'équation du cercle : r2=x2+y2 devient r2=(x-x0)2+(y-y0)2. On choisit le pixel suivant parmi les 3 pixels (x+1,y), (x+1,y+1) et (x,y+1), en évaluant leur distance du cercle discret. Pour chaque pixel on a une distance d = r - √(x2 - y2). Il considère en outre que les points de ce cercle dont l'épaisseur physique est de 1 pixel sont situés dans l'intervale r-0.5 ≤ pixel < r+0.5. La vérification de l'appartenance du point est alors (r-½)2 ≤ (x-x0)2+(y-y0)2 < (r+½)2.

Le génie consiste ici à poser d = r2 + r - x2 - y2 - 1 et de montrer qu'on choisit :

  1. (x+1,y) si d ≥ 2x
  2. (x,y+1) si d < 2(r - y)
  3. sinon (x+1,y+1) quand 2x > d ≥ 2(r - y) 

Tous les points entiers (pixels) du plan appartiennent à au moins 1 cercle d'Eric Andres de rayon entier (c'est le cas aussi pour ceux de Pierre Audibert et Nicolas Rey).

Implémentation

DrawCircleAndres

Algorithme de Bresenham pour le tracé de cercle

Principe : Comme dans son algorithme de tracé de segment Jack Bresenham part du principe qu'on doit choisir entre 2 pixels en fonctions de sa distance au cercle de rayon R+½. On parcout un octant en X et on décrémente Y quand le point passe dans ce cercle. L'optimisation de cet algorithme passe par un développement de (x+1,y-0.5) multiplié par 4. On peut de plus intégrer le choix du pixel dans l'équation (voir Wiki).

Implémentation

DrawCircleBresenham

Implémentation optimale en intégrant le choix du pixel dans l'équation

DrawCircleOptimalBresenham

Algorithme de Pierre Audibert

Principe : Pierre Audibert est parti du théorème de Pythagore en développant et factorisant les incrémentations de (x-x0) et (y-y0). voir Tracé d'un cercle quelconque.

Implémentation

DrawCirclePierreAudibert

Algorithme de Nicolas Rey

Principe : J'ai utilisé une propriété intéressante des carrés. Tout nombre entier au carré est une somme de nombres impairs consécutifs, ce qui permet d'incrémenter un carré sans passer par une multiplication. Mon algorythme n'utilise donc que des additions et des soustractions dans la boucle principale.

Implémentation

DrawCircleNicolasRey

Pythagore

Je le met à titre indicatif puisque tous les algorythmes cités ici utilisent ce célèbre théorème.

Implémentation

DrawCirclePythagore

Comments est propulsé par CComment