% Latex 2e
%Luminy 98: Cercle discret d' Andres et rotations discrètes.
\documentclass{slides}
\usepackage{fr}

\begin{document}
\begin{center}
\underbar{Cercle d'Andres et rotations discrètes.}
\end{center}
\par
{\bf\Large 1)~Les tracés classiques.}\par
{\Large La méthode DDA.}\par
{\Large Les cercles de Brésenham.}\par
\bigskip
{\bf\Large 2)~Les cercles d'Andres.}\par
{\Large Propriétés.}\par
{\Large Tracé algorithmique.}\par
{\bf\Large 3)~Application aux rotations.}
\newpage

\begin{center}
\underbar{Cercles par DDA.}
\end{center}
Equation: 
$$x.dx+y.dy=0$$
Algorithme:\par
\begin{tabbing}
\large
let \=cercle$\_$dda r x0 y0 = \\
\+\>  let x = ref 0 and y = ref r \\
      and d= ref (-r)  \\
      in  \\
      while \=(!x)$<=$(!y) do \\
\+\>          point (!x+x0) (!y+y0); \\
              point (!y+x0) (!x+y0);  \\
              x$:=$(!x)+1; \\
              d$:=$(!d)+2*(!x);\\
              if \=(!d)$>=$0 then \\
\+\>               begin \\
                   ~~~\=y$:=$(!y)-1;\\
\+\>                    d$:=$(!d)-2*(!y); \\
\<                 end;\\
                      \qquad\qquad done;;\\
\end{tabbing}

\newpage

\begin{center}
\underbar{Cercles de Brésenham.}
\end{center}
Variable de décision: 
$$d=1+4(x^2+y^2-y-r^2)$$
Algorithme:\par
\begin{tabbing}
\large
let \=cercle$\_$bres r x0 y0 = \\
\+\>  let x = ref 0 and y = ref r \\
      and d= ref (1-4*r)  \\
      in  \\
      while \=(!x)$<=$(!y) do \\
\+\>          point (!x+x0) (!y+y0); \\
              point (!y+x0) (!x+y0);  \\
              x$:=$(!x)+1; \\
              d$:=$(!d)+8*(!x)-4;\\
              if \=(!d)$>$0 then \\
\+\>               begin \\
                   ~~~\=d$:=$(!d)-8*(!y)+8;\\
\+\>                    y$:=$(!y)-1; \\
\<                 end;\\
                      \qquad\qquad done;;\\
\end{tabbing}

\newpage


\begin{center}
\underbar{Les cercles d'Andres.}
\end{center}

{\Large Définition mathématique:}
\large
$$(r-\frac{1}{2})^2\leq (x-x_0)^2+(y-y_0)^2<(r+\frac{1}{2})^2$$
centre: $(x_0,y_0)$ entier ou demi-entier.
\newline
rayon: $r$ toujours entier.
\par
{\Large Propriétés:}
\newline
\quad -~le cercle est $8$-connexe;
\newline
\quad -~tout point entier appartient à un et un seul
cercle de centre donné;
\newline
\quad -~les points peuvent être tracés
algorithmiquement en suivant un ordre naturel, total.
\newpage
{\Large Démonstration:}\par
\hbox{\qquad\special{isoscale c_a2.pcx,13cm 13cm}}
\vskip 10truecm
Brésenham et DDA: cas b) et c) seuls
\newline
Andres: cas a) et b) s'excluent
\newline
\hphantom{Andres: }si ni a) ni b) alors c)
\newline
Variable de décision:
$$d = (1/2).(r^2+r-x^2-y^2+x+y)$$
\newpage
\begin{tabbing}
\large
let\= ~cercle$\_$a\_demi r x0 y0 = \\
\+\>  let x = ref 0 and y = ref r \\
      and\= ~d= ref r in \\
      while 0$<=$(!y) do \\
\+\>          point (!x+x0) (!y+y0); \\
              if\= ~(!d)$>$(!x) then\\
\+\>               (d$:=$(!d)-(!x);x$:=$(!x)+1) \\
              el\=se if (!d)$<=$r+1-(!y) then \\
\+\>               (d$:=$(!d)+(!y)-1;y$:=$(!y)-1) \\
                   else\= \\
\+\>                   (d$:=$(!d)+(!y)-(!x)-1;\\
                        ~x$:=$(!x)+1; \\
                        ~y$:=$(!y)-1) \\
                       \qquad\qquad done;;\\
\end{tabbing}




\end{document}
