Solution de l'exercice 1

Soit (x0,y0) approximation, la courbe intersecte nécessairement la « croix » de taille 1 centrée en (x0,y0). On utilise facilement l'interprétation géométrique pour montrer que toute intersection de la courbe avec la barre horizontale entraîne l'intersection avec la barre verticale.

Soit donc le point (x₀,y₀) approximation, par le résultat précédent la courbe intersecte le segment unité centré en (x₀,y₀). On suppose que x₀+1 appartient au domaine de f. Par hypothèse la courbe intersecte le segment unité centré en (x₀,y₀), et l'axe vertical x = x₀+1 au point (x₀+1, f(x₀+1)).

D'après l'interprétation géométrique, on voit que l'intersection avec la verticale x = x₀+1 se situe nécessairement dans l'un des deux segments unité centrés en (x₀+1, y₀) ou (x₀+1, y₀-1) (soit y0-3/2 ≤ f(x₀+1) ≤ y₀+1/2 en formules).
On devra donc allumer l'un des point (x₀+1, y₀) ou (x₀+1, y₀-1), pour savoir lequel il suffit de savoir si la courbe passe au dessus ou au dessus de leur milieu, (x₀+1, y₀-1/2). En règle générale on comparera f(x₀+1) et y₀-1/2.
Dans le cas du cercle de rayon R centré à l'origine.
- Le domaine est limité au huitième de cercle compris entre le nord et le nord-est.
- Un premier point est connu : le point (0,R).
- Le test de choix entre (x₀+1,y₀) et (x₀+1,y₀-1) repose sur la position du point (x₀+1,y₀-1/2) soit sur le signe de
  
  d = (x₀+1)² + (y₀-
  
  1
  
  2
  ) - R²
  Si d est positive alors le point suivant est (x₀+1,y₀-1), sinon c'est (x₀+1,y₀).

static void cercle(int r) { int x = 0 ; int y = r ; while (x <= y) { pxl(x,y) ; double d = (x+1)*(x+1) + (y-0.5)*(y-0.5) - r*r ; x++ ; if (d > 0) { y-- ; } } }

On notera que l'on évite la question de la limitation du domaine vers la droite. En effet, les raisonnements du 1. ne sont certainement pas tous valables pour le dernier point affiché.

Pour éviter les multiplications il faut calculer incrémentalement la quantité d. Initialement on a d = 1² + (R-1/2)² -R² = 1+1/4 - R. On remarque ensuite qu'augmenter x de 1 revient à augmenter d de 2x + 3 et que diminuer y de 1 revient à diminuer y de 2y-2. En effet on a d'une part ((x+1)+1)² - (x+1)² = (2x + 3)(2-1) et ((y-1)-1/2)² - (y-1/2)² = (2y-2) (-3/2+1/2).

Par ailleurs pour x et y entiers, e = d-1/4 est entier et les signes de d et e sont identiques. La nullité de e entraînant d = 1/4> 0. (C'est-à-dire que le cas e = 0 est en fait d > 0). On peut donc recoder la méthode cercle ainsi :

static void cercle(int r) { int x = 0 ; int y = r ; int e = 1-r ; while (x <= y) { pxl(x,y) ; if (e >= 0) { y-- ; e -= 2*y ; } x++ ; e += 2*x+1 ; } }

Le cas délicat concerne bien évidemment le dernier point gris (vers la droite) et en particulier les points allumes avec x₀ = y₀. Les rayons 3, 6, 7 et 10 montrent que l'on doit les allumer au moins quand le mouvement qui y aboutit est sud-est. Les rayons 4 et 11 encourageraient plutôt de les oublier.

Enfin tous ces exemples semblent montrer que procéder à la marche du roi pour x₀ ≤ y₀ produit bien une approximation de Freeman, mais il faut le montrer !

On considère d'abord le cas où le dernier point allumé est de la forme (x₀, x₀+1). Par hypothèse le point (x₀+1, x₀+1) n'est pas allumé. Et donc le point milieu (x₀+1, x₀ + 1/2) est au dessus du cercle. Par symétrie selon la diagonale, le point (x₀+1/2, x₀ + 1) est également au dessus du cercle et le point (x₀+1, x₀+1) ne doit pas être allumé.
(Les deux points milieu sont en noir, le dernier de la marche est en gris, et le point allumé par symétrie est en blanc.) Le dessin illustre le cas où le dernier point de la marche est au dessus de l'arc, mais le raisonnement ne fait pas intervenir cette hypothèse.

Supposons maintenant que le dernier point allumé est sur la diagonale, c'est-à-dire qu'il est de la forme (x₀, x₀). On considère alors deux sous-cas.
- Si le dernier mouvement est vers l'est, alors le point milieu (x₀, x₀-1/2) est situé à l'intérieur du cercle (ou sous l'arc). On distingue alors encore deux sous-cas.
  - Si (x₀,x₀) est en dehors du cercle alors le cercle intersecte le demi-segment unité vertical inférieur centré en (x₀,x₀) et ce point doit être allumé.
    Il s'agit du cas disgracieux obtenu par exemple pour R=4 et R=11.
  - Sinon, nous savons par ailleurs que l'arc passe à une distance verticale inférieure à 1/2 de l'avant dernier point (x₀-1,x₀). En appliquant l'interprétation géométrique vers la droite au point de passage de l'arc par l'axe vertical x=x₀-1 on voit que l'arc coupera l'axe x = x₀ sous l'ordonnée x₀+1/2.
    Ce cas me semble d'ailleurs impossible avec R entier. En effet, x₀ est ici la partie entière de 2^-1/2 R, on a donc 2 x₀² < R². Par ailleurs, on a (x₀-1)² + (x₀+1/2) ≥ R² et donc x₀ ≤ 2 x₀² - R² + 5/4, soit encore x₀ < 5/4 et donc x₀ = 1. Soit finalement R = 1 ou R = 2 qui ne correspondent pas à la configuration (voir la figure 1). De fait cette configuration survient pour R compris entre 2^1/2 et 3/2.
- Si le dernier mouvement est vers le sud-est, alors le point milieu (x₀, x₀+1/2) est situé à l'extérieur du cercle.
  - Si le point (x₀,x₀) est à l'intérieur, on peut conclure directement.
  - Sinon, l'arc intersecte nécessairement l'axe x=x₀-1 au dessus du point (x₀-1,x₀+1/2) et on peut conclure par l'interprétation géométrique vers la droite à partir de ce point d'intersection et jusqu'à l'axe y=x₀.
De façon générale, si (x,y) est un point de la marche du roi pour le cercle de rayon R centré sur l'origine, il faut allumer les huit points (x_c+x, y_c+y), (x_c-y, y_c+x), (x_c-x, y_c-y), (x_c+y, y_c-x) (correspondant au point de la marche translaté et à trois rotation d'un quart de tour) et (x_c+y, y_c+x), (x_c-x, y_c+y), (x_c-y. x_c-x), (x_c+x, y_c-y) (le symétrique selon la diagonale et trois rotation d'un quart de tour).

Toutefois, il faut éviter la deuxième série de points dans les cas x=0 et x=y.

On notera bien que c'est la conservation de l'approximation de Freeman par toutes ces isométries qui garantit que nous construisons bien une approximation de Freeman du cercle de rayon R centré en (x_c, y_c).