Algorithme de tracé de cercle d'Andres

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

(E) : ${\displaystyle (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).

Schéma de la situation

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

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

• si ${\displaystyle 2x\leq d}$ :
  • ${\displaystyle x\geq 1\implies x^{2}\geq x}$ d'où ${\displaystyle (r-1/2)^{2}\leq x^{2}+y^{2}\leq (x+1)^{2}+y^{2}}$
  • et ${\displaystyle 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 ${\displaystyle d<2(r-y)}$ :
  • ${\displaystyle 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 ${\displaystyle 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
    ${\displaystyle (r-1/2)^{2}\leq r^{2}-r+1\leq x^{2}+(y-1)^{2}}$.
    Donc B vérifie (E).
• sinon alors ${\displaystyle 2x>d\geq 2(r-y)}$ :
  • ${\displaystyle 2x>d\implies (x+1)^{2}+y^{2}>r^{2}+r\implies (x+1)^{2}+(y-1)^{2}>r^{2}+r-2y+1}$ or ${\displaystyle x^{2}+y^{2}\leq (r+1/2)^{2}\implies y^{2}\leq (r+1/2)^{2}\implies y\leq r}$ (nous sommes sur ${\displaystyle \mathbb {N} }$) d'où ${\displaystyle 2x>d\implies (x+1)^{2}+(y-1)^{2}>r^{2}-r+1>(r-1/2)^{2}}$
  • et ${\displaystyle 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 ${\displaystyle y\geq 1\implies x<r}$ car le point de coord. (x=r, y=1) ne vérifie pas (E)
    donc ${\displaystyle 2r>2x\implies 2r\geq 2x+1\implies 2r+1/4>2x+1}$
    donc ${\displaystyle 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).

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 les cercles d'Andres 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.