Cercle d’Andres et rotations discrètes.

1) Les tracés classiques. La méthode DDA. Les cercles de Brésenham.

2) Les cercles d’Andres. Propriétés. Tracé algorithmique.

3) Application aux rotations.

Cercles par DDA.

Equation :

x.dx + y.dy = 0

Algorithme :

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

Cercles de Brésenham.

Variable de décision :

d = 1 + 4(x^{2} + y^{2} − y − r^{2})

Algorithme :

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

Les cercles d’Andres.

Définition mathématique :

(r−\frac{1}{2})^{2} ≤ (x−x_{0})^{2}+(y−y_{0})^{2} < (r+\frac{1}{2})^{2}

centre : (x_{0}, y_{0}) entier ou demi-entier. rayon : r toujours entier.

Propriétés :

- le cercle est 8-connexe ;

- tout point entier appartient à un et un seul cercle de centre donné ;

- les points peuvent être tracés algorithmiquement en suivant un ordre naturel, total.

Démonstration :

Brésenham et DDA : cas b) et c) seuls Andres : cas a) et b) s’excluent

si ni a) ni b) alors c)

Variable de décision :

d = (1/2).(r^{2} + r − x^{2} − y^{2} + x + y) 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) else 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)

done ; ;