Pour l'étude, on considère la partie dans le deuxième octant¹⁾ (x>0, y>x) d'un cercle de rayon R et centre (0,0). x² + y² = R².

Deux approches se présente :

• Calculs flottants : pour x=0,1,\ldots\quad y=arrondi(sqrt{R*R - x*x)
• Algorithme de Bresenham (analogue de son algorithme pour les segments) : incrémentale, arithmétique entière.

A chaque étape, le pixel à choisir dans la colonne suivante sera soit au même niveau, soit un cran plus bas, car dans cet octant la tangente varie de pente 0 à pente -1, pas plus. Soient S: (\left(x_c+1,y_c\right), T : \left(x_c +1, y_c -1\right). La distance algébrique de chacun de ces points au cercle indique si le point est à l'intérieur (valeur négative) ou extérieur (valeur positive) et se calcule:

• D\left(S\right) = \left(x_c + 1\right)^2 + \left(y_c \right)^2 - R^2
• D\left(T\right) = \left(x_c + 1\right)^2 + \left(y_c -1\right)^2 - R^2

De trois choses l'une : * si les deux points sont à l'intérieur (si S l'est, T le sera) indiqué par deux valeurs négatives, on choisit S (le point au dessus est plus proche du cercle dans cette région). La somme D(S)+D(T) < 0.

• si les deux points sont à l'extérieur (si T l'est, S aussi) indiqué par deux valeurs positives, on choisit T. La somme D(S) + D(T) > 0
• si S est à l'extérieur et T à l'intérieur, on compare leurs distances on faisant leur somme.
  • Somme D(S) + D(T) > 0 ⇒ S est plus loin, on choisit T;
  • Somme D(S) + D(T) < 0 ⇒ T est plus loin, on choisit S;
  • Somme D(S) + D(T) = 0 ⇒ on choisit S (aussi).

Donc, en générale, D(S) + D(T) > 0 ⇒ choisir T =\left(x_c +1, y_c -1\right) et sinon choisir S =\left(x_c +1, y_c \right) .

cercle (R, couleur)
  {
    x=0; y=R; d=3 - 2*R;
    tant que (x =< y) faire
      { affichePixel(x,y, couleur);
        si (d < 0) alors d = d + 4*x + 6   /* S est choisi */
        sinon {d = d + 4*(x-y) +10; y=y-1;}
        x=x+1;
       }
    }

Pour un point donné, la somme

• D(S)+D(T)=(x+1)^2 + y^2-R^2 + (x+1)^2 + (y-1)^2 - R^2
  • =2x^2 +2x +2y^2 -2y + 2 - 2R^2
• Si le successeur au même niveau est choisi (choix S, y ne change pas) sa prochaine valeur sera
  • (x+2)^2 + y^2-R^2 + (x+2)^2 + (y-1)^2 - R^2
• si S est choisi, l'incrément de d sera
  • \Delta_{S} = 2(x+2)^2 + y^2 + (y-1)^2 - 2R^2- \left(2(x+1)^2 + y^2 + (y-1)^2 -2 R^2\right)
  • = 2\left[ \left(x+2\right)^2 - \left(x+1\right)^2\right] = 2\left[ x^2 +4x +4 - x^2 + 2x +1\right]= 4x +6
• sinon, si T est choisi, le successeur baisse de niveau et la valeur sera
  • (x+2)^2 + (y-1)^2-R^2 + (x+2)^2 + (y-2)^2 - R^2
• si T est choisi, l'incrément de d sera
  • \Delta_{T} =2(x+2)^2 + (y-1)^2 + (y-2)^2 - 2R^2 - \left( 2 (x+1)^2 + y^2 + (y-1)^2 - 2R^2\right)
  • =2\left[(x+2)^2 - (x+1)^2\right] + (y-2)^2 -y^2 = 4x+6-4y+4=4\left(x-y\right)+10

Il existe des points n'appartenant à aucun cercle de Bresenham.

• généralisation à tout cercle (autre centre, R pas forcément entier, autres octants)
• calculer l'incrément de manière incrémental avec des constantes

Un invention récente, de Eric Andrès, 1992.

Un cercle arithmétique C de rayon R entré en O passe par \left(x,y\right) \Leftrightarrow \left(R-\frac{1}{2}\right) \leq x^2 + y^2 \lt \left( R -\frac{1}{2}\right)

Tout point entier appartient à un cercle arithmétique de rayon R, et un seul.

Même contexte qu'avant (deuxième octant, etc.). Le prochain pixel est choisi parmi 3 candidats au lieu de deux (et on peut afficher deux pixels dans une colonne) avec deux règles:

• on n'aura pas à la fois (x, y-1) et (x+1, y) sur le cercle
• si ni (x, y-1) ni (x+1, y) n'est sur le cercle, (x+1, y-1) y est

cercle (x0, y0, couleur)
  {
    x=0; y=R; d=R-1;
    tantque (x =< y) faire
    {  affichePixel(x,y,couleur);
       si (d >= 2*x) alors {d=d-2x-1; x=x+1;}  // a
       sinon
         si (d < 2*(R-y)) alors {d=d+2*x -1; y=y-1;}  // b
         sinon {d=d-2*(y-x-1); x=x+1; y=y-1;}  // c
     }
   }

attention ce tableau n'a pas été vérifié !

attention ce tableau n'a pas été vérifié !