\magnification=1000
\input math

\grostitre{Cercle d'Andres et application aux rotations discr�tes.}
\bigskip
\questiontitre{Les m�thodes classiques de trac� de cercles discrets.}
Le probl�me pos� est d'approcher le trac� d'un cercle de centre � 
coordonn�es enti�res et de rayon entier par celui d'une s�rie de points 
� coordonn�es enti�res (les pixels de l'�cran). 
On souhaite que ce trac� soit le plus 
fid�le possible (en un sens � pr�ciser) et qu'il donne une courbe au moins 
$8$-connexe, c'est-�-dire que pour chaque point du cercle discret, deux de 
ses $8$ voisins au moins appartiennent �galement au cercle.
Rappelons ici bri�vement les m�thodes par DDA (Differential Digital Analyser) 
et de Br�senham. \par
On s'int�resse (� une translation pr�s) au trac� d'un cercle de centre $O$~. 
Soit $r$ son rayon (entier). 
Les deux m�thodes proc�dent par trac� d'un octant (celui correspondant 
� $x\geq 0~,~y\geq 0~,~y\geq x$~) puis 
par sym�tries, et sont incr�mentales � partir du point $(0,r)$~. 
En effet, dans le premier octant, la tangente au cercle est de pente en 
valeur absolue $\leq 1$~, si bien qu'on progresse de mani�re connexe le 
long du cercle en faisant progresser l'abscisse de $1$~. La question 
revient donc � d�terminer � quelles abscisses il faut faire d�cro�tre 
$y$ de $1$~. 
\par
\hskip4truecm\hbox{\special{em\DP graph c_a1.pcx}}
\vskip 4truecm

\sousquestion M�thode par analyse diff�rentielle discr�te (DDA);\par
Ici on trace en respectant au mieux l'�quation diff�rentielle
$$x.dx+y.dy=0~~.$$
En fait, $dx=1$ est constant, et les $|dy|$ s'accumulent jusqu'� atteindre 
et d�passer, au choix, $1$ ou $1/2$~. Cela donne plusieurs algorithmes 
possibles, sur le mod�le suivant:
\cleartabs
\+\qquad \qquad &let &cercle$\_$dda r x0 y0 = \cr
\+              &    &let x = ref 0 and y = ref r \cr
\+(* 1 *)       &    &and d= ref (-r) \cr
\+              &    &in \cr
\+              &    &while &(!x)$<=$(!y) do \cr
\+              &    &      &point (!x+x0) (!y+y0);\cr
\+              &    &      &point (!y+x0) (!x+y0);\cr
\+              &    &      &x$:=$(!x)+1;\cr
\+(* 2 *)       &    &      &d$:=$(!d)+2*(!x);\cr
\+(* 3 *)       &    &      &if &(!d)$>=$0 then \cr 
\+              &    &      &   &begin\cr 
\+              &    &      &   &\quad y$:=$(!y)-1;\cr
\+(* 4 *)       &    &      &   &\quad d$:=$(!d)-2*(!y); \cr 
\+              &    &      &   &end;\cr
\+              &    &      &   &\qquad done;;\cr            
La variable $d$ initialis�e ligne (* 1 *) accumule les $2*x$~. Quand elle 
d�passe la valeur $0$~, c'est que $|dy|$ d�passe la valeur $1/2$~; on fait 
alors comme si $dy$ valait $-1$~, \cad qu'on 
d�cr�mente $y$ de $1$ et $d$ de $-2*y$ (ligne (* 4 *)) de mani�re � 
respecter l'in�quation $d=\Sum (2x.dx +2y.dy)\leq 0$~. \par
Les variantes concernent la ligne (* 3 *) o� on peut mettre (!d)$>$0~ 
� la place de (!d)$>=$0~, 
et les lignes (* 2 *), (*~4~*) qu'on peut remplacer respectivement 
par 
\+(* 2 *)       &    & ...  &d$:=$(!d)+(!x);\cr
\+(* 4 *)       &    & ...  &   &\quad d$:=$(!d)-(!y); \cr 
Les quatre quarts de cercle obtenus sont montr�s en figure 1.
\sousquestion La M�thode de Br�senham.\par
La m�thode pr�c�dente offre peu de justifications th�oriques, de plus, 
quelle variante choisir? Son int�r�t est qu'elle peut se g�n�raliser au 
trac� d'autres courbes alg�briques, des coniques par exemple. \par
Avec la m�thode de Br�senham, on a une justification th�orique: 
on choisit � chaque �tape, entre les points $(x,y)$ et $(x,y-1)$ 
celui qui est le plus proche du point th�orique $(x,\sqrt{r^2-x^2})$~. 
Or, 
$$\eqalign{
y-\sqrt{r^2-x^2}\leq \sqrt{r^2-x^2}-(y-1)
&\equ 1+4(x^2+y^2-y-r^2)\leq 0~~.}$$
Le choix se fait donc au moyen de la {\it variable de d�cision} 
$d=1+4(x^2+y^2-y-r^2)$~. Cette variable se calcule de fa�on incr�mentale 
� partir de sa valeur initiale $1-4r$~, d'o� l'algorithme suivant:
\cleartabs
\+\qquad \qquad &let &cercle$\_$bres r x0 y0 = \cr
\+              &    &let x = ref 0 and y = ref r \cr
\+              &    &and d= ref (1-4*r) \cr
\+              &    &in \cr
\+(* 1 *)       &    &while &(!x)$<=$(!y) do \cr
\+(* a *)       &    &      &point (!x+x0) (!y+y0);\cr
\+(* b *)       &    &      &point (!y+x0) (!x+y0);\cr
\+              &    &      &x$:=$(!x)+1;\cr
\+              &    &      &d$:=$(!d)+8*(!x)-4;\cr
\+(* 2 *)       &    &      &if &(!d)$>$0 then \cr 
\+              &    &      &   &begin\cr 
\+              &    &      &   &\quad d$:=$(!d)-8*(!y)+8; \cr 
\+              &    &      &   &\quad y$:=$(!y)-1;\cr
\+              &    &      &   &end;\cr
\+              &    &      &   &\qquad done;;\cr            
A la ligne (* 2 *) on peut remplacer $d>0$ par $d\geq 0$ ce qui change le 
choix et fait pr�f�rer $y-1$ � $y$ en cas d'�quidistance des 
deux points $(x,y)$ et $(x,y-1)$ au point th�orique. Cela n'a aucune 
influence si le centre est � coordonn�es enti�res, mais peut en avoir si le 
centre est � coordonn�es demi-enti�res.\par
On montre en Figure 1. diff�rents cercles obtenus par DDA et par la m�thode 
de Br�senham. Les cercles de Br�senham de droite sont obtenus par une 
modification
de l'algorithme expliqu�e plus loin.

\hskip4truecm\hbox{\special{em\DP graph c_dda_br.pcx}}
\nopage
\vfill\eject
\footline={\centerline{\it - \folio { -}}}
{\sl Remarques}: \par
\quad -~On voit (cas des cercles de Br�senham de rayons $4$ et $11$~) que, 
dans le programme pr�c�dent,
le test ligne (* 1 *) n'est pas le meilleur possible, car 
il met parfois un point $(x,x)$ sur le cercle alors que le point 
$(x-1,x)$ y est d�j�, ce qui rajoute une ``pointe'' peu esth�tique. On corrige 
ce d�faut en permutant, dans la boucle $while$~, l'affichage (lignes (* a*) 
et (* b *)) avec les lignes suivantes de calcul des nouveaux $x,y,d$~, 
en rajoutant 
cet affichage avant la boucle $while$~, et en rempla�cant le test de la ligne 
(* 1 *) par \quad $(* 1' *)\qquad while (!x)+1\leq (!y)-1 $~.\par
\quad -~Un logiciel comme Paint Shop Pro par exemple, ou $wcaml74$~, 
utilise Br�senham comme routine de trac� de cercles.
\par
\hbox{\hskip 4truecm\special{em\DP graph c_a3.pcx}}
\vskip 4truecm

\questiontitre{Le cercle d'Andres.}
Le d�faut des cercles pr�c�dents est qu'ils oublient des points: il y a 
environ $10\%$ de trous, \cad de points n'appartenant � aucun cercle discret 
de centre entier donn�. En revanche, tout point $(x,y)$ est dans une 
couronne $r-\Frac{1}{2}\leq \sqrt{x^2+y^2}<r+\Frac{1}{2}$ lorsque $r$ 
d�crit $\N$~. D'o� l'id�e de la d�finition suivante
\sousquestion {\sl D�finition}:\par
Le cercle discret d'Andres de centre $(x_0,y_0)$ et de rayon $r$ est 
l'ensemble des points $(x,y)\in\Z^2$ v�rifiant les in�quations 
diophantiennes:
$$(A)\qquad \(r-\Frac{1}{2}\)^2\leq (x-x_0)^2+(y-y_0)^2
< \(r+\Frac{1}{2}\)^2~~.$$
Deux remarques � propos de cette d�finition:\par
\def\[{\bigm[}
\quad - tout d'abord, on peut �videmment remplacer les intervalles 
$\[r-\Frac{1}{2},r+\Frac{1}{2}\[$ par tout ensemble d'intervalles de 
longueur $1$ contig�s, en particulier les $[r,r+1[$ (on obtient ainsi les 
cercles dits ``na�fs'');\par
\quad - le centre $(x_0,y_0)$ d'un tel cercle est � coordonn�es enti�res 
ou demi-enti�res. On verra en effet que les propri�t�s sont fondamentalement 
les m�mes pour les deux types de centres, de plus prendre un centre de 
coordonn�es $(1/2,1/2)$ par exemple donne une plus grande sym�trie au cercle 
et simplifie les algorithmes (par exemple, le nombre total de points d'un 
cercle est toujours exactement $4$ fois celui d'un quadrant). 

\sousquestion {\sl Propri�t�s des cercles d'Andres.}\par
{\sl Proposition:\par
Le cercle d'Andres est $8$-connexe et les points du cercle peuvent �tre 
tous parcourus dans un ordre canonique, donn� par un algorithme de type 
incr�mental.}
\par
Pour d�montrer cette proposition, pla�ons-nous en un point $(x,y)\in 
\N^2$ du cercle, et cherchons � d�terminer ses voisins �ventuels � droite 
et en-dessous, suivant la figure ci-dessous:
\par
\hbox{\hskip 4truecm\special{em\DP graph c_a2.pcx}}
\vskip 4.5truecm
{\bf Lemmes:}\par
1. Si $(x,y)$ v�rifie $(A)$~, ni $(x+1,y+1)$ ni $(x-1,y-1)$  
ne v�rifient $(A)$~(i.e. les cas $(d)$ et $(e)$ sont exclus).\par
2. Si $(x+1,y)$ v�rifie $(A)$~, $(x,y-1)$ ne le v�rifie pas, et 
r�ciproquement (i.e. les cas $(a)$ et $(b)$ s'excluent mutuellement).\par
3. Pour $y\geq 1$~, si ni $(x+1,y)$ ni $(x,y-1)$ ne v�rifient $(A)$~, alors 
$(x+1,y-1)$ v�rifie $(A)$ 
(i.e. les cas $non~(a)$ et $non~(b)$ impliquent le cas $(c)$~).

%\vfill\eject
\bigskip
{\sl D�monstrations:} 
\par Les d�monstrations de ces trois lemmes se font dans le cas 
$x_0=y_0=0$ et reposent toutes sur 
le fait qu'on a alors $x+y\geq \sqrt{x^2+y^2}\geq (r-\Frac{1}{2})$~. \par
Pour le lemme 1~,on voit facilement que 
$$x^2+y^2\geq \(r-\Frac{1}{2}\)^2\Impl 
(x+1)^2+(y+1)^2 > \(r+\Frac{1}{2}\)^2~~,$$
d'o� on d�duit que si $(x,y)$ v�rifie $(A)$, il est impossible que 
$(x-1,y-1)$ v�rifie $(A)$ aussi. \par
D�monstration du lemme 2~:\par
Supposons (absurde) � la fois $(a)$ et $(b)$~. On aurait alors:
$$\(r-\Frac{1}{2}\)^2\leq x^2+(y-1)^2~~{\rm et}~~ 
(x+1)^2+y^2< \(r+\Frac{1}{2}\)^2~~,$$
d'o�, successivement:
$$\eqalign{
\qquad &r^2-r+\Frac{1}{4} < r^2+r+\Frac{1}{4}-2y-2x\cr
\Impl  &x+y < r \cr
\Impl  &\sqrt{x^2+y^2}\leq x+y\leq r-1\qquad
\hbox{\rm (on est avec des entiers).}\cr}$$
Or ceci contredit le fait que $(x,y)$ v�rifie $(A)$~, cqfd.
Enfin, pour le lemme 3~: \par
L'hypoth�se est que $(x+1)^2+y^2\geq \(r+\Frac{1}{2}\)$ et 
$x^2+(y-1)^2<\(r-\Frac{1}{2}\)^2$~. On en d�duit:
$$\eqalign{
\(r+\Frac{1}{2}\)^2-2y+1\leq (x+1)^2+(y-1)^2 &<\(r-\Frac{1}{2}\)^2+2x+1\cr
\equ\(r-\Frac{1}{2}\)^2+2(r-y)\leq (x+1)^2+(y-1)^2 
&<\(r+\Frac{1}{2}\)^2+2(x-r)+1~~.\cr}$$
Or, les �quations $(A)$ impliquent que $x\leq r$ n�cessairement, mais si 
$x=r$~, on voit de plus que $(x,y-1)$ v�rifie $(A)$ aussi, or c'est exclu 
par hypoth�se. On a donc $x<r$ et comme de m�me $r-y\geq 0$~, on en d�duit que 
$$\(r-\Frac{1}{2}\)^2 <(x+1)^2+(y-1)^2 \leq \(r+\Frac{1}{2}\)^2~~,~cqfd.$$

On d�duit de ces trois lemmes que l'algorithme initialisant $(x,y)$ � 
$(x_0,r+y_0)$ et faisant progresser le point $(x,y)$ du cercle d'Andres 
suivant les cas (exclusifs) $(a)$ ou $(b)$ quand c'est possible, sinon 
suivant le cas $(c)$~, et ceci tant que $y$ reste $\geq 0$~, 
fait parcourir � $(x,y)$ {\it tous} les points du cercle d'Andres situ�s 
dans le premier quadrant. Ceci se d�montre par invaraint de boucle en 
utilisant la relation d'ordre partiel sur les couples 
$$(x_1,y_1) \prec (x_2,y_2)\equ x_1 < x_2 ~ou~ (x_1=x_2~et~y_1\geq y_2)~~.$$ 
En effet, raisonnons dans le cas du centre $(0,0)$~. 
Pour $x=0$~, $(0,r)$ est le seul point du cercle situ� dans le premier 
quadrant et $\prec (0,r)$~(clair sur $(A)$ o� $x=0$~). 
Supposons que l'algorithme ait trac�, 
jusqu'au point $(x,y)$~, tous les points $\prec (x,y)$ appartenant au 
cercle d'Andres et situ�s dans le premier quadrant. Le point $(x',y')$ 
suivant choisi par l'algorithme poss�de, vu les $3$ lemmes, aussi cette 
propri�t�: si c'est le point choisi par $(b)$ c'est �vident puisque les 
points pr�c�dents $(x',y')$ par $\prec$ sont les pr�d�cesseurs de 
$(x,y)$ et $(x,y)$ lui-m�me; si c'est le point choisi par $(a)$~, comme 
le point correspondant � $(e)$ n'est pas sur le cercle, et donc tous ceux qui 
sont au-dessus a fortiori non plus, de m�me que le point choisi par $(b)$ 
(lemme 2) et a fortiori tous les points en-dessous, c'est encore vrai; 
enfin, si c'est le point choisi par $(c)$~, comme ne sont pas sur le cercle 
les points correspondant 
� $(a)$~, et a fortiori tous ceux qui sont au-dessus, ni ceux correspondant 
� $(b)$ et a fortiori tous ceux qui sont en-dessous, c'est toujours vrai. 
Or, l'algorithme finit n�cessairement par atteindre le cas $y=0~,~x=r$~, 
puisque le choix $(a)$ ne peut �tre effectu� au plus que $r$ fois et que 
pour les autres choix, possibles tant que $y\geq 1$~, $y$ diminue de $1$~. 
Ceci ach�ve de d�montrer notre proposition. 
\bigskip

Donnons pour terminer l'algorithme de parcours du cercle d'Andres en $CAML$~. 
La condition pour le choix $(a)$ s'�crit:
$$(x+1)^2+y2<\(r+\Frac{1}{2}\)^2\equ r^2+r-x^2-y^2-1 \geq  2x$$
(on tient compte du $1/4$ en autorisant l'�galit�, puisqu'on est avec des 
entiers), et celle pour le choix $(b)$ est 
$$x^2+(y-1)^2\geq \(r-\Frac{1}{2}\)^2\equ r^2+r-x^2-y^2-1< 2(r-y)~~,$$
(ici on peut ne plus tenir compte du $1/4$~). \par
Comme le cas $(c)$ est choisi automatiquement quand les cas $(a)$ et $(b)$ 
font d�faut, on voit que tout peut se faire � l'aide de la seule 
variable de contr�le $d=r^2+r-x^2-y^2-1$~. De plus, celle-ci se calcule 
par incr�mentation au fur et � mesure � partir de sa valeur initiale 
$d=r-1$~. \par
Algorithme: (* parcours du quart de cercle d'Andres de centre 
$(x_0,y_0)\in\Z^2$~*)
\cleartabs
\+\qquad \qquad &let &cercle$\_$a r x0 y0 = \cr
\+              &    &let x = ref 0 and y = ref r \cr
\+              &    &and d= ref (r-1) \cr
\+              &    &in \cr
\+              &    &while &0$<=$(!y) do \cr
\+              &    &      &point (!x+x0) (!y+y0);\cr
\+(* (a) *)     &    &      &if &(!d)$>=$2*x \cr  
\+              &    &      &   &then \cr
\+              &    &      &   &\qquad (d$:=$(!d)-2*(!x)-1; \cr 
\+              &    &      &   &\qquad ~x$:=$(!x)+1)\cr
\+              &    &      &   &else \cr
\+(* (b) *)     &    &      &   &if &(!d)$<$2*(r-y) \cr  
\+              &    &      &   &   &then \cr
\+              &    &      &   &   &\qquad (d$:=$(!d)+2*(!y)-1; \cr 
\+              &    &      &   &   &\qquad ~y$:=$(!y)-1)\cr
\+(* (c) *)     &    &      &   &   &else \cr
\+              &    &      &   &   &\qquad (d$:=$(!d)+2*((!y)-(!x)-1); \cr 
\+              &    &      &   &   &\qquad ~x$:=$(!x)+1;\cr
\+              &    &      &   &   &\qquad ~y$:=$(!y)-1)\cr
\+              &    &      &   &\qquad done;;\cr            

\bigskip

{\sl Remarque:} On ne peut prolonger cette approche de mani�re naturelle 
pour les ellipses. En effet, soit $a$ et $b$ les deux demi-axes (entiers)
d'une ellipse, et posons $a=\Frac{p}{q}.b$~, o� $\Frac{p}{q}\geq 1$ est 
une fraction irr�ductible. L'�quation de l'ellipse se ram�ne �:
$$q^2x^2+p^2y^2=q^2a^2=p^2b^2~~.$$
Si, par analogie avec les cercles on pose comme �quations de l'ellipse 
discr�te  
$$q^2\(a-\Frac{1}{2}\)^2\leq q^2x^2+p^2y^2<q^2\(a+\Frac{1}{2}\)^2~~(1)
\quad ou\quad 
p^2\(b-\Frac{1}{2}\)^2\leq q^2x^2+p^2y^2<p^2\(b+\Frac{1}{2}\)^2~~(2)~~,$$
alors ou bien l'ellipse est non connexe (�quation $(1)$~) ou bien il y a 
trop de points sur l'ellipse si bien que la propri�t� 
d'ordre naturel sur les points n'est plus satisfaite (�quation $(2)$~).
\par
Par exemple, pour $a=30,b=20$ on trouvera les ensembles de points suivants:
\par
\setbox20=\vtop{\hsize=80truemm \leftskip=0mm \rightskip=0mm
\special{em\DP graph ellipsea.pcx}
\vskip 3.5truecm
\qquad Equation $(1)$ }
\setbox22=\vtop{\hsize=80truemm \leftskip=0mm \rightskip=0mm
\special{em\DP graph ellipseb.pcx}
\vskip 3.5truecm
\qquad Equation $(2)$}
\hfill\hbox{\box20\qquad\box22}\hfill
\bigskip

\sousquestion Cercles de centre demi-entier.\par
On s'int�ressera ici aux cercles de centre $(1/2,1/2)$~, les autres cas �tant 
similaires. L'�quation est donc:
$$(A')\qquad \(r-\Frac{1}{2}\)^2\leq \(x-\Frac{1}{2}\)^2 + 
\(y-\Frac{1}{2}\)^2 < \(r+\Frac{1}{2}\)^2~~.$$
On laisse au lecteur la d�monstration d'une proposition 
strictement analogue au cas pr�c�dent, justifiant le trac� de tous les 
points entiers v�rifiant $(A')$ au moyen d'un algorithme incr�mental. 
\par
Soit $(x,y)$ un point v�rifiant $(A')$~: le choix du point suivant 
$(x+1,y)$ $(a)$ se fait si 
$$\(x+1-\Frac{1}{2}\)^2 + \(y-\Frac{1}{2}\)^2 < \(r+\Frac{1}{2}\)^2
\equ r^2+r-x^2-y^2+x+y > 2x~~,$$
le choix du point suivant $(x,y-1)$ $(b)$ se fait si 
$$\(x-\Frac{1}{2}\)^2 + \(y-1-\Frac{1}{2}\)^2 \geq \(r-\Frac{1}{2}\)^2
\equ r^2+r-x^2-y^2+x+y \leq 2(r+1-y)~~,$$
et sinon on choisit le point suivant $(x+1,y-1)$ $(c)$~. On remarque � ce 
moment que la variable de d�cision $d=r^2+r-x^2-y^2+x+y$ est toujours paire 
et doit se comparer � des nombres pairs, donc on peut simplifier les tests 
par $2$~. Finalement, l'algorithme est le suivant:\par
Algorithme: (* parcours du quart de cercle d'Andres de centre 
$(x_0+1/2,y_0+1/2)~,~(x_0,y_0)\in\Z^2$~*)
\cleartabs
\+\qquad \qquad &let &cercle$\_$a r x0 y0 = \cr
\+              &    &let x = ref 0 and y = ref r \cr
\+              &    &and d= ref r \cr
\+              &    &in \cr
\+              &    &while &$0<=$(!y) do \cr
\+              &    &      &point (!x+x0) (!y+y0);\cr
\+(* (a) *)     &    &      &if &(!d)$>$x \cr  
\+              &    &      &   &then \cr
\+              &    &      &   &\qquad (d$:=$(!d)-(!x); \cr 
\+              &    &      &   &\qquad ~x$:=$(!x)+1)\cr
\+              &    &      &   &else \cr
\+(* (b) *)     &    &      &   &if &(!d)$<=$r+1-y \cr  
\+              &    &      &   &   &then \cr
\+              &    &      &   &   &\qquad (d$:=$(!d)+(!y)-1; \cr 
\+              &    &      &   &   &\qquad ~y$:=$(!y)-1)\cr
\+(* (c) *)     &    &      &   &   &else \cr
\+              &    &      &   &   &\qquad (d$:=$(!d)+(!y)-(!x)-1; \cr 
\+              &    &      &   &   &\qquad ~x$:=$(!x)+1;\cr
\+              &    &      &   &   &\qquad ~y$:=$(!y)-1)\cr
\+              &    &      &   &\qquad done;;\cr            

\questiontitre{Applications aux rotations discr�tes.}
\sousquestion G�n�ralit�s.\par

Les propri�t�s pr�c�dentes du cercle d'Andres permettent de d�finir des 
coordonn�es polaires discr�tes. En effet, tout point appartient � un cercle 
de centre $O(0,0)$ et un seul, et sur ce cercle, on dipose d'un sens de 
parcours permettant de num�roter un � un tous les pixels. Dans cette optique, 
on d�finit la longueur d'un cercle comme le nombre de points le composant, 
et l'angle polaire comme le quotient entier entre le nombre de points � 
parcourir depuis le point sur l'axe polaire et la longueur du cercle. \par
Mais des difficult�s aparaissent: d'une part, la longueur n'est pas donn�e 
par une fonction simple du rayon, mais doit �tre calcul�e algorithmiquement. 
On s'aper�oit � cette occasion que le quotient de la longueur sur le rayon 
oscille entre $6.07$ et $6.50$ pour des rayons de l'ordre de $200$~. Mais 
de plus, la progression d'un point le long d'un cercle ne se fait pas � 
la m�me vitesse angulaire d'un cercle � l'autre, et pire, ne se 
fait pas m�me � vitesse angulaire constante sur un m�me cercle. 
On peut s'en douter � l'aspect 
tant�t lisse, tant�t ``fripp�'' des arcs de cercles, mais aussi en 
repr�sentant l'ensemble des points ayant m�me angle polaire. Sur la planche 
$1$ (fichier image ``arcs3030.pcx'') on a repr�sent� des points d'angle 
polaire correspondant � $30\up{o}$~, 
puis les points d'angles polaires d�cal�s de $30\up{o}$ par rapport � 
ceux-ci (l'axe polaire �tant l'axe vertical). On voit que les droites 
discr�tes obtenues ne sont m�me pas $8$-connexes!
\par
\hbox{\hskip 4truecm\special{em\DP graph arcs3030.pcx}}
\vskip 4.5truecm
Quant � l'additivit� des angles, elle est mise en d�faut uniquement � 
cause de l'approximation dans le quotient entier par la longueur. Parfois, 
cela se passe bien, comme en t�moigne la planche 2 (``arcs3060.pcx'') o� 
on retrouve l'axe horizontal apr�s une rotation de $30\up{o}+60\up{o}$~. 
\par
\hbox{\hskip 4truecm\special{em\DP graph arcs3060.pcx}}
\vskip 4.5truecm

\sousquestion Impl�mentation d'une rotation discr�te.\par
Malgr� ces inconv�nients (pr�)visibles, nous avons impl�ment� voir une 
rotation discr�te d'images en $CAML$~. Pour cela, nous nous sommes servis 
de l'algorithme de parcours pr�c�dent pour des cercles de centre � 
coordonn�es demi-enti�res, et nous en avons fait une fonction 
$$pix\_suiv~:~int~ -\!>~ int~ -\!>~ int~ ref~ -\!> int~ -\!> ~int~ *~ int~~,$$
o� $pix\_suiv~x~y~d~r$ donne le pixel suivant $(x,y)$ sur le cercle 
de centre $(1/2,1/2)$ de rayon $r$ tout en modifiant la variable 
de d�cision $d$ correspondante. \par
La rotation elle-m�me se fait alors par parcours simultan�s et d�cal�s 
d'un angle polaire constant 
de $2$ cercles de m�me rayon croissant, l'un dans l'image de d�part, 
l'autre dans l'image � obtenir par rotation, et en recopiant les couleurs 
d'une image � l'autre.\par
\bigskip

Le r�sultat est visible aux planches $3$ et $4$~. En planche $3$, on a fait 
subir � l'image une rotation de $135\up{o}$~, et en planche $4$ on a rajout� 
une rotation de $225\up{o}$~: l� encore on remarque une non-additivit� 
des arcs discrets. \par
\hbox{\qquad\special{em\DP graph vis135.pcx}}
\vfill\eject
\null
\hbox{\qquad\special{em\DP graph vis_360.pcx}}
\vskip 12truecm
Certes, l'image est d�form�e, 
mais tout de m�me reconnaissable, et de plus celle-ci est obtenue sans 
perte d'informations. Avec un logiciel comme Paint Shop Pro, si on tourne 
une image de $135\up{o}$ puis de $225\up{o}$ on obtient une image qui n'est 
plus identique � l'image de d�part, mais ayant subie un l�ger lissage 
(cf comparaison � l'�cran des images ``vis\_p0.pcx'' et ``vis\_p360.pcx'').

\vfill
\troiset 
\end
