Algorithme de tracé d'arc de cercle de Bresenham

Un article de Wikipédia, l'encyclopédie libre.

L’algorithme de tracé d'arc de cercle de Jack E. Bresenham permet, pour une complexité algorithmique très réduite, de tracer des cercles en image matricielle.

Sommaire 1 Explication de l'algorithme de base dans le premier octant 1.1 Un huitième suffit 1.2 L'algorithme de base 1.3 Optimisation de l'algorithme 2 Algorithme optimisé 3 Remarques sur la méthode de Bresenham 3.1 La faible complexité 3.2 Extensions 3.3 Limites de la méthode

[modifier] Explication de l'algorithme de base dans le premier octant

[modifier] Un huitième suffit

Tout d'abord, on peut remarquer que sur une grille de pixels, il existe quatre axes de symétrie au cercle, deux suivant les axes de la matrice, et deux représentant les bissectrices du repère centré sur le cercle. Ainsi, ayant calculé un arc d'un secteur du repère délimité par les axes de symétrie, il suffit d'exploiter la symétrie pour positionner les sept autres pixels.

[modifier] L'algorithme de base

Pour les raisons de symétrie expliquées précédemment, l'algorithme expliqué sera limité au deuxième octant (d'angle compris entre et ) puis généralisé ensuite. L'algorithme partira donc du point le plus haut du cercle, et descendra jusqu'à la première bissectrice.

Ce tracé procède par itération, chaque itération activant un pixel. Imaginons que nous sommes en un pixel P, et qu'il faut placer le pixel suivant. Puisque nous sommes dans le deuxième octant, ce pixel sera le point E ou le point F. La méthode de Bresenham consiste à évaluer si le cercle "idéal" d'équation x² + y² − R² = 0 passe au-dessus ou en dessous du point M, milieu du segment EF pour activer respectivement le pixel E ou le pixel F.

Il faut donc calculer à chaque itération une variable m telle que . Alors :

• m > 0 ⇒M au-dessus du cercle idéal ⇒ choix de F ⇒ incrémenter x, décrémenter y
• m < 0 ⇒ M au-dessous du cercle idéal ⇒ choix de E ⇒ incrémenter x

[modifier] Optimisation de l'algorithme

Pour optimiser l'algorithme, on calcule la variable m récursivement.

Plaçons-nous au pointP_i de coordonnées sur la grille de pixel (x_i;y_i) et calculons la variable m. On sait alors que M a pour coordonnées (x_m = x_i + 1;y_m = y_i − 0,5). Donc . Puisqu'on souhaite ne travailler qu'avec des nombres entiers, et puisque seul le signe de m nous intéresse, on utilisera l'équation (1) : .

On va modifier la variable m en fonction du choix du pixel E ou du pixel F. On nommera m_i l'ancienne valeur de m, et m_{i + 1} la nouvelle valeur de m.

• Si on choisit E, alors (x_{i + 1} = x_i + 1,y_{i + 1} = y_i). Or d'après l'équation (1), , donc d'où . En utilisant le fait que , on obtient 4m_{i + 1} = 4m_i + 8x_i + 12 = 4m_i + 8x_{i + 1} + 4. Si on choisit E, il faut donc incrémenter 4m_ide 8x_{i + 1} + 4.

• Si on choisit F, alors (x_{i + 1} = x_i + 1,y_{i + 1} = y_i + 1). En effectuant un raisonnement analogue à celui du cas E, on démontre que si on choisit F, il faut incrémenter 4m_ide 8x_{i + 1} + 4 − 8y_{i + 1}.

On en déduit donc le calcul itératif de m : m_{i + 1} = m_i + 8x_{i + 1} + 4 − d avec d qui vaut 0 si on choisit E, et 8y_{i + 1} si on choisit F.

Pour amorcer le calcul itératif, on remarque que m₀ = ( − 1)² + (R − 0,5)² − R² donc 4m₀ = 5 − 4R.

[modifier] Algorithme optimisé

Algorithme de tracé d'un octant

procédure tracerOctant (entier rayon, entier x_centre, entier y_centre)
        déclarer entier x, y, m ;
        x ←0 ;
        y ← R ;    //on se place en haut du cercle 
        m ←5-4*rayon ;             // initialisation
        Tant que x < y       // tant qu'on est dans le second octant
                tracerPixel( x+x_centre , y+y_centre ) ;
                si m > 0 alors       // choix du point F
                        y ← y - 1 ;
                        m ← m-8*y ;        // correspond au "d" des explications
                fin si ;
                x ← x+1 ;
                m ← m + 8*x+4 ;
        fin tant que ;
fin de procédure ;

On notera que ici la variable m représente le "4m" du paragraphe précédent, ce que l'on peut se permettre puisque seul le signe de 4m nous intéresse et qu'il est le même que celui de m.

Algorithme de tracé du cercle entier

procédure tracerOctant (entier rayon, entier x_centre, entier y_centre)
        déclarer entier x, y, m ;
        x ←0 ;
        y ← R ;    // on se place en haut du cercle 
        m ←5-4*rayon ;             // initialisation
        Tant que x < y       // tant qu'on est dans le second octant
                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 m > 0 alors       //choix du point F
                        y ← y - 1 ;
                        m ← m-8*y ;
                fin si ;
                x ← x+1 ;
                m ← m + 8*x+4 ;
        fin tant que ;
fin de procédure ;

On procède simplement par symétrie dans les différents octants.

[modifier] Remarques sur la méthode de Bresenham

[modifier] La faible complexité

On a vu précédemment que pour chaque pixel placé la complexité de calcul se réduisait à X additions, Y multiplications et Z comparaisons. L'utilisation de fonctions trigonométriques usuelles ou d'une racine carrée auraient nécessité un coût algorithmique considérable en comparaison.

[modifier] Extensions

On peut également se servir du principe de cet algorithme pour tracer des couronnes et des ellipses.

[modifier] Limites de la méthode

Si l'on trace des cercles concentriques de rayon de plus en plus grand, on remarque que l'on ne parvient pas à remplir tout le plan : il y a des "trous" . Ce défaut amène à utiliser d'autres méthodes, comme l'algorithme de tracé d'arc de cercle d'Andres.