L’algorithme de tracé de cercle d'Andres. permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle. Cet algorithme permet de paver entièrement le plan par des cercles concentriques, sans les trous que laisse par exemple l'algorithme de tracé d'arc de cercle de Bresenham.
Principe Andres considère que les cercles discrets de rayon r et de centre sont les ensembles des points vérifiant
(E) :
On procède par itération sur les points. Plaçons-nous dans un octant, par exemple celui juste au-dessus de l'axe des abscisses, et supposons que le point P de coordonnées (x, y) ait déjà été placé. On cherche alors à déterminer s'il faut choisir le point A (x+1,y), le point B (x, y-1) ou le point C (x+1, y-1).
On montre alors que si P vérifie (E), alors seuls A, B ou C peuvent vérifier (E). De plus, A et B s'excluent mutuellement. Enfin, si ni A ni B ne vérifient (E), alors C vérifie (E).
On pose et on montre que l'on doit choisir A si et B si .
En effet, avec ce et pour (les autres cercles s'obtiennent par translation), si P vérifie (E) : si : d'où et . Donc A vérifie (E). si :
et car il s'agit d'expressions entières . Donc B vérifie (E). sinon alors : or (nous sommes sur ) d'où et or car le point de coord. (x=r, y=1) ne vérifie pas (E)donc donc .Donc C vérifie (E).
Algorithme
Cet algorithme décrit le tracé d'un octant, les sept autres s'obtenant par symétrie.
x <- 0 y <- r d <- r - 1 Tant que y>=x TracerPixel(x, y) Si d >= 2x alors d <- d-2x-1 x <- x+1 Sinon Si d < 2(r-y) alors d <- d+2y-1 y <- y-1 Sinon d <- d+2(y-x-1) y <- y-1 x <- x+1 Fin de tant que
Algorithme de tracé du cercle complet
x <- 0 y <- r d <- r - 1 Tant que y>=x tracerPixel( x_centre + x , y_centre + y ) tracerPixel( x_centre + y , y_centre + x ) tracerPixel( x_centre - x , y_centre + y ) tracerPixel( x_centre - y , y_centre + x ) tracerPixel( x_centre + x , y_centre - y ) tracerPixel( x_centre + y , y_centre - x ) tracerPixel( x_centre - x , y_centre - y ) tracerPixel( x_centre - y , y_centre - x ) Si d >= 2x alors d <- d-2x-1 x <- x+1 Sinon Si d < 2(r-y) alors d <- d+2y-1 y <- y-1 Sinon d <- d+2(y-x-1) y <- y-1 x <- x+1 Fin de tant que
Pavage du plan par cercle concentriques En traçant des cercles concentriques, on obtient bien un pavage complet du plan.
Ceci permet notamment de tourner des images avec une moindre déformation.
Exemples d'implémentation En Java /** * Algorithme de tracé de cercle d'Andres */ public static HashSet<int[]> cercle(int x_centre, int y_centre, int r) { HashSet<int[]> pixels = new HashSet<int[]>();
int x = 0; int y = r; int d = r - 1;
while(y >= x)
pixels.add( new int[]{ x_centre + x, y_centre + y }); pixels.add( new int[]{ x_centre + y, y_centre + x }); pixels.add( new int[]{ x_centre - x, y_centre + y }); pixels.add( new int[]{ x_centre - y, y_centre + x }); pixels.add( new int[]{ x_centre + x, y_centre - y }); pixels.add( new int[]{ x_centre + y, y_centre - x }); pixels.add( new int[]{ x_centre - x, y_centre - y }); pixels.add( new int[]{ x_centre - y, y_centre - x });
if (d >= 2*x)
d -= 2*x + 1; x ++;
else if (d < 2 * (r-y))
d += 2*y - 1; y --;
else
d += 2*(y - x - 1); y --; x ++;
return pixels; }
En C# public static List<Point> AndresCircle(int xc, int yc, int r) { List<Point> ret = new List<Point>();
int x = 0; int y = r; int d = r - 1;
while (y >= x)
ret.Add(new Point(xc + x, yc + y)); ret.Add(new Point(xc + y, yc + x)); ret.Add(new Point(xc - x, yc + y)); ret.Add(new Point(xc - y, yc + x)); ret.Add(new Point(xc + x, yc - y)); ret.Add(new Point(xc + y, yc - x)); ret.Add(new Point(xc - x, yc - y)); ret.Add(new Point(xc - y, yc - x));
if (d >= 2 * x)
d -= 2 * x + 1; x++;
else if (d < 2 * (r - y))
d += 2 * y - 1; y--;
else
d += 2 * (y - x - 1); y--; x++;
return ret; }
En MicroLua -- Cercle cercle = function (ecran, x, y, rayon, couleur) --Algorithme de tracé de cercle d'Andres
-- (x;y) représente le point en haut à gauche du carré imaginaire contenant le cercle
x = x+rayon y = y+rayon
local d = rayon-1 local a = rayon - 1 local b = 0 while a>= b do screen.drawPoint(ecran, x + b , y + a, couleur) screen.drawPoint(ecran, x + a , y + b, couleur ) screen.drawPoint(ecran, x - b , y + a, couleur ) screen.drawPoint(ecran, x - a , y + b, couleur ) screen.drawPoint(ecran, x + b , y - a, couleur ) screen.drawPoint(ecran, x + a , y - b, couleur ) screen.drawPoint(ecran, x - b , y - a, couleur ) screen.drawPoint(ecran, x - a , y - b, couleur ) if d >= 2*b then d = d-2*b-1 b = b+1 elseif d < 2*(rayon-a) then d = d+2*a-1 a = a-1 else d = d+2*(a-b-1) a = a-1 b = b+1 end end end
-- Cercle plein cerclePlein = function (ecran, x, y, rayon, couleur) -- Algorithme basé sur le tracé de cercle d'Andres
-- (x;y) représente le point en haut à gauche du carré imaginaire contenant le cercle
x = x+rayon y = y+rayon
local d = rayon-1 local a = rayon - 1 local b = 0 while a>= b do screen.drawLine(ecran, x + b , y - a, x + b , y + a, couleur ) screen.drawLine(ecran, x + a , y - b, x + a , y + b, couleur ) screen.drawLine(ecran, x - b , y - a, x - b , y + a, couleur ) screen.drawLine(ecran, x - a , y - b, x - a , y + b, couleur ) if d >= 2*b then d = d-2*b-1 b = b+1 elseif d < 2*(rayon-a) then d = d+2*a-1 a = a-1 else d = d+2*(a-b-1) a = a-1 b = b+1 end end end
En Bash #!/bin/bash -f # Algorithme de tracé de cercle dû à Éric Andres function circle () { # x, y, rayon, couleur
r=$3 x=$1 y=$2
d=$(($r-1)) a=$(($r-1)) b=0
tput setaf $4 while test $a -ge $b ; do tput cup $(($y+$b)) $(($x+$a)); echo "@"; tput cup $(($y+$a)) $(($x+$b)); echo "@"; tput cup $(($y-$b)) $(($x+$a)); echo "@"; tput cup $(($y-$a)) $(($x+$b)); echo "@"; tput cup $(($y+$b)) $(($x-$a)); echo "@"; tput cup $(($y+$a)) $(($x-$b)); echo "@"; tput cup $(($y-$b)) $(($x-$a)); echo "@"; tput cup $(($y-$a)) $(($x-$b)); echo "@"; if test $d -ge $((2*$b)) ; then d=$(($d-2*$b-1)) b=$(($b+1)) elif test $d -lt $((2*($r-$a))); then d=$(($d+2*$a-1)) a=$(($a-1)) else d=$(($d+2*($a-$b-1))) a=$(($a-1)) b=$(($b+1)) fi done }
clear
# Cercle centré sur le centre de l'écran xc=$(($(tput cols)/2)) yc=$(($(tput lines)/2)) # Nombre de couleurs disponibles dans le terminal nc=$(tput colors)
# Tracé de cercles concentriques montrant le parfait remplissage for i in $(seq 1 $(($yc-1))) ; do circle $xc $yc $i $(($RANDOM%$nc)) done
tput cup $(tput lines) 0 tput oc
Notes et références
Andres (Tracé de cercle) Catégorie:Cercle