Algorithme de tracé de cercle d'Andres

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (mars 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

L’algorithme de tracé de cercle d'Andres^[1] 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[modifier | modifier le code]

Andres considère que les cercles discrets de rayon r et de centre $(x_{0},y_{0})$ sont les ensembles des points vérifiant

(E) : $(r-1/2)^{2}\leq (x-x_{0})^{2}+(y-y_{0})^{2}<(r+1/2)^{2}$

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 $d=r^{2}+r-x^{2}-y^{2}-1$ et on montre que l'on doit choisir A si $d\geq 2x$ et B si $d<2(r-y)$ .

En effet, avec ce $d$ et pour $(x_{0},y_{0})=(0,0)$ (les autres cercles s'obtiennent par translation), si P vérifie (E) :

si $2x\leq d$ $2x\leq d$ :
- $x\geq 1\implies x^{2}\geq x$ d'où $(r-1/2)^{2}\leq x^{2}+y^{2}\leq (x+1)^{2}+y^{2}$
- et $2x\leq d\implies x^{2}+2x+1+y^{2}\leq r^{2}+r\implies (x+1)^{2}+y^{2}<r^{2}+r+1/4=(r+1/2)^{2}$ .
  Donc A vérifie (E).
si $d<2(r-y)$ $d<2(r-y)$ :
- $y\geq 1\implies (y-1)^{2}\leq y^{2}\implies x^{2}+(y-1)^{2}\leq x^{2}+y^{2}\leq (r+1/2)^{2}$
- et $d<2(r-y)\implies r^{2}+r<2r-2y+x^{2}+y^{2}+1\implies r^{2}-r<x^{2}+(y-1)^{2}\implies r^{2}-r+1\leq x^{2}+(y-1)^{2}$ car il s'agit d'expressions entières
  $(r-1/2)^{2}\leq r^{2}-r+1\leq x^{2}+(y-1)^{2}$ .
  Donc B vérifie (E).
sinon alors $2x>d\geq 2(r-y)$ $2x>d\geq 2(r-y)$ :
- $2x>d\implies (x+1)^{2}+y^{2}>r^{2}+r\implies (x+1)^{2}+(y-1)^{2}>r^{2}+r-2y+1$ or $x^{2}+y^{2}\leq (r+1/2)^{2}\implies y^{2}\leq (r+1/2)^{2}\implies y\leq r$ (nous sommes sur $\mathbb {N}$ ) d'où $2x>d\implies (x+1)^{2}+(y-1)^{2}>r^{2}-r+1>(r-1/2)^{2}$
- et $d\geq 2(r-y)\implies r^{2}+r\geq 2r-2y+x^{2}+y^{2}+1\implies r^{2}-r\geq x^{2}+(y-1)^{2}\implies r^{2}-r+2x+1\geq (x+1)^{2}+(y-1)^{2}$
  or $y\geq 1\implies x<r$ car le point de coord. (x=r, y=1) ne vérifie pas (E)
  donc $2r>2x\implies 2r\geq 2x+1\implies 2r+1/4>2x+1$
  donc $r^{2}-r+2r+1/4>r^{2}-r+2x+1\geq (x+1)^{2}+(y-1)^{2}\implies (r+1/2)^{2}>(x+1)^{2}+(y-1)^{2}$ .
  Donc C vérifie (E).

Algorithme[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

En Java[modifier | modifier le code]

/**
  * 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#[modifier | modifier le code]

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[modifier | modifier le code]

-- 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[modifier | modifier le code]

#!/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[modifier | modifier le code]

↑ Eric Andres, « Discrete circles, rings and spheres », Computers & Graphics, vol. 18, n^o 5,‎ 1^er septembre 1994, p. 695–706 (ISSN 0097-8493, DOI 10.1016/0097-8493(94)90164-3, lire en ligne, consulté le 15 février 2016).

[1] Eric Andres, « Discrete circles, rings and spheres », Computers & Graphics, vol. 18, n^o 5,‎ 1^er septembre 1994, p. 695–706 (ISSN 0097-8493, DOI 10.1016/0097-8493(94)90164-3, lire en ligne, consulté le 15 février 2016).

[1]