===== Algorithmes de tracer de cercles =====

Pour l'étude, on considère la partie dans le deuxième octant((pour avoir 1 pixel par colonne)) (x>0, y>x) d'un cercle de rayon R et centre (0,0). x<sup>2</sup> + y<sup>2</sup> =  R<sup>2</sup>.

Deux approches se présente :
  * Calculs flottants : pour <jsm>x=0,1,\ldots\quad</jsm> y=arrondi(sqrt{R*R - x*x)
  * Algorithme de Bresenham (analogue de son algorithme pour les segments) : incrémentale, arithmétique entière.

==== Algorithme de Bresenham ====

=== Principe ===

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 <jsm>S: (\left(x_c+1,y_c\right), T : \left(x_c +1, y_c -1\right)</jsm>. 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:
  * <jsm>D\left(S\right) = \left(x_c + 1\right)^2 + \left(y_c \right)^2 - R^2 </jsm>
  * <jsm>D\left(T\right) = \left(x_c + 1\right)^2 + \left(y_c -1\right)^2 - R^2 </jsm>

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 =<jsm>\left(x_c +1, y_c -1\right)</jsm> et sinon choisir S =<jsm>\left(x_c +1, y_c \right)</jsm> .

=== Algorithme ===

  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;
         }
      }

=== évolution de "d" ===

Pour un point donné, la somme 
  * <jsm>D(S)+D(T)=(x+1)^2 + y^2-R^2 + (x+1)^2 + (y-1)^2 - R^2</jsm>
    * <jsm> =2x^2 +2x +2y^2 -2y + 2 - 2R^2</jsm>
  * Si le successeur au même niveau est choisi (choix S, y ne change pas) sa prochaine valeur sera 
    * <jsm>(x+2)^2 + y^2-R^2 + (x+2)^2 + (y-1)^2 - R^2</jsm>
  * si S est choisi, l'incrément de ''d'' sera
    * <jsm> \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) </jsm>
    * <jsm>= 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 </jsm>
  * sinon, si  T est choisi, le successeur baisse de niveau et la valeur sera
    * <jsm>(x+2)^2 + (y-1)^2-R^2 + (x+2)^2 + (y-2)^2 - R^2</jsm>
  * si T est choisi, l'incrément de ''d'' sera
    * <jsm> \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)</jsm>
    * <jsm> =2\left[(x+2)^2 - (x+1)^2\right] + (y-2)^2 -y^2 = 4x+6-4y+4=4\left(x-y\right)+10 </jsm>


=== Remarque ===

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

=== reste à faire ===

  * 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

==== Cercle arithmétique ====

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

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

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

=== Principe ===

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
       }
     }

==== Exemples des Deux ====

=== Bresenham ===

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

^ R ^ d ^ x ^ y ^ allumer ^  traiter d ^ traiter y ^ traiter x ^
^ 1 | 3-2=1 | 0 | 1 | (0,1) | 1+4*(0-1)+10 |  - 1 | + 1 |
|  | 7 | 1 | 0 | rien: x>y |  |  |  |
^ 2 | 3-4=-1 | 0 | 2 | (0,2) | -1+4*0+6 | -0 | +1 |
|   | 5  | 1  | 2  | (1,2 )  | 5 +4(1-2)+10 | -1 | +1 |
|  | 11 | 2  | 1  | rien: x>y |  |  |  |
^ 3 | -3 | 0 | 3  | (0,3) | -3+4*0+6 | -0  | + 1  |
|  | 3  |  1  |  3  | (1,3)  | 3+4*(1-3)+10  |  -1  | +1  |
|  | 5  |  2  |  2  | (2,2)  |  5 + 4*(2-2)+10 | -1 | + 1 |
|  | 15 | 3  |  1  | rien : x>y |  |  |  |
^ 4 | -5  |  0  |  4  |  (0,4) | -5+4*0+6  | -0  | +1 |
|   | 1  |  1  |  4  |  (1,4)  | 1 +4*(1-4)+10 | -1 | +1 |
|   | -1  | 2  |  3  |  (2,3)  | -1+4*2+6  | -0 | +1  |
|  | 13  |  3  |  3  |  (3,3)  | 13 +4(3-3)+10 | -1 | +1 |
|  | 23  |  4  |  2  |  rien : x>y |  |  |  |


=== arithmétiques ===

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

^ R ^ d ^ x ^ y ^ allumer ^  d >= 2*x ^ d<2*(R-y) ^ traiter d ^ traiter y ^ traiter x ^
^ 1 | 0 | 0 | 1 |  (0,1)  | oui  |  ---  | d=d-2x-1 | -0- | x<- x+1  |
|  | -1 | 1 | 1 |  (1,1)  | non  | oui | d <- d+2x-1 | y <- y-1 | -0- |
|  | 0 | 1 | 0  | rien : x>y  | |||||
^ 2  | 1  | 0  |  2  |  (0,2)  | oui  |   | d<-d-2x-1 | -0- | x <- x+1 |
|   | 0 | 1  | 2  |  (1,2)  | non | non | d <- d-2*(y-x-1) | y<-y-1 | x<- x+1 |
|   | 0 | 2 | 1 | rien : x>y | |||||
^ 3 |  2  | 0  |  3  |  (0,3)  | oui  |    | d <- 2 -2*0 - 1 | -0- | x <- x+1 |
|   |  1  | 1  |  3  |  (1,3)  | non  |  non | d <- d-2*(y-x-1) | y<-y-1 | x<- x+1 |
|   |  -1  |  2  |  2  |  (2,2)  | oui  |    | d <- d -2x-1 | -0- | x <- x+1 |
|   |  -6  |  3  |  2  | rien : x>y  | |||||
^ 4 |  3  |  0  |  4  |  (0,4)  | oui  |  | d <- d-2*x -1 |  -0-  | x <- x+1 |
|   |  2  |  1  |  4  |  (1,4)  | oui  |  | d <- d-2*x -1 |  -0-  | x <- x+1 |
|   |  -1  |  2  |  4  |  (2,4)  | non | oui | d <- d+2x-1 | y <- y-1 | -0- |
|   |  2  |  2 |  3  |  (2,3)  |  non  | non | d <- d+2x-1 | y <- y-1 | x <- x+1 |
|   |  5  |  3  |  2  | rien: x>y  | |||||