Algorithme de tracé de cercle d'Andres

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 (x0,y0) 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 ait déjà été placé. On cherche alors à déterminer s'il faut choisir le point A, le point B ou le point C.

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 d = r2 + rx2y2 − 1 et on montre que l'on doit choisir A si d > 2x et B si d < 2(ry) .

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+x_centre, y+y_centre )
        tracerPixel( y+x_centre, x+y_centre )
        tracerPixel( -x+x_centre, y+y_centre )
        tracerPixel( -y+x_centre, x+y_centre )
        tracerPixel( x+x_centre, -y+y_centre )
        tracerPixel( y+x_centre, -x+y_centre )
        tracerPixel( -x+x_centre, -y+y_centre )
        tracerPixel( -y+x_centre, -x+y_centre )
        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

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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de tracé de cercle d'Andres de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme De Tracé De Cercle D'Andres — 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… …   Wikipédia en Français

  • Algorithme de trace de cercle d'Andres — Algorithme de tracé de cercle d Andres 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 …   Wikipédia en Français

  • Algorithme de tracé de cercle d'andres — 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… …   Wikipédia en Français

  • Algorithme De Tracé D'arc De Cercle De Bresenham — L’algorithme de tracé d arc de cercle de Bresenham, ou algorithme de tracé d arc de cercle par point milieu (midpoint en anglais) permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle. Sommaire 1… …   Wikipédia en Français

  • Algorithme de trace d'arc de cercle de Bresenham — Algorithme de tracé d arc de cercle de Bresenham L’algorithme de tracé d arc de cercle de Bresenham, ou algorithme de tracé d arc de cercle par point milieu (midpoint en anglais) permet, pour une complexité algorithmique très réduite, de tracer… …   Wikipédia en Français

  • Algorithme de tracé d'arc de cercle de bresenham — L’algorithme de tracé d arc de cercle de Bresenham, ou algorithme de tracé d arc de cercle par point milieu (midpoint en anglais) permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle. Sommaire 1… …   Wikipédia en Français

  • Algorithme de tracé d'arc de cercle de Bresenham — L’algorithme de tracé d arc de cercle de Bresenham, ou algorithme de tracé d arc de cercle par point milieu (midpoint en anglais) permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle. Sommaire 1… …   Wikipédia en Français

  • Cercle — Pour les articles homonymes, voir cercle (homonymie). Un cercle est une courbe plane fermée constituée des points situés à égale distance d un point nommé centre. La valeur de cette distance est appelée rayon du cercle. Celui ci étant infiniment… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”