Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithme de tracé d'arc de cercle de Bresenham L’algorithme de tracé d'arc de

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. Historique Explication de l'algorithme de base dans le premier octant Un huitième suffit L'algorithme de base Optimisation de l'algorithme Algorithme optimisé Remarques sur la méthode de Bresenham La faible complexité Extensions Limites de la méthode Exemple d'implémentation En C# Notes Cet algorithme, publié par Bresenham en février 1977, est inspiré de son travail précédent sur le tracé de segments, et de l'algorithme plus général de Pitteway sur le tracé des coniques , dont les cercles sont un cas particulier. 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 pixels dans les sept autres octants. Sommaire Historique 1 2 Explication de l'algorithme de base dans le premier octant Un huitième suffit 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 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 Pour optimiser l'algorithme, on calcule la variable m récursivement. On montre que (1) démonstration Plaçons-nous au point de coordonnées sur la grille de pixel et calculons la variable m. On sait alors que M a pour coordonnées . Donc . Puisqu'on souhaite ne travailler qu'avec des nombres entiers, et puisque seul le signe de m nous intéresse, on multiplie l'équation par 4 et on obtient . On va modifier la variable m en fonction du choix du pixel E ou du pixel F. On nommera l'ancienne valeur de m, et la nouvelle valeur de m. On montre que si on choisit E, . Il faut donc incrémenter de . démonstration Si on choisit E, alors . Or d'après l'équation (1) L algorithme de base Optimisation de l'algorithme Or d'après l'équation (1), , donc d'où . En utilisant le fait que , on obtient . On montre que si on choisit F, . Il faut donc incrémenter de . démonstration Raisonnement analogue à celui où l'on choisit E On en déduit donc le calcul itératif de m : avec d qui vaut 0 si on choisit E, et si on choisit F. Pour amorcer le calcul itératif, on remarque que donc . 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 ← rayon ; // 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 ; La variable m représente le « 4m » du paragraphe précédent, 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 tracerCercle (entier rayon, entier x_centre, entier y_centre) déclarer entier x, y, m ; x ← 0 ; y ← rayon ; // 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 ) ; Algorithme optimisé 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. 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. On peut également se servir du principe de cet algorithme pour tracer des couronnes et des ellipses. 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é de cercle d'Andres. Remarques sur la méthode de Bresenham La faible complexité Extensions Limites de la méthode Exemple d'implémentation En C# public static List<Point> BresenhamCircle(int xc,int yc,int r) { List<Point> ret = new List<Point>(); int x,y,p; x=0; y=r; ret.Add(new Point(xc+x,yc-y)); p=3-(2*r); for(x=0;x<=y;x++) { if (p<0) 1. (en) Jack Bresenham, « A linear algorithm for incremental digital display of circular arcs », Communications of the ACM, vol. 20, n 2,‎ février 1977, p. 100-106 (DOI 10.1145/359423.359432 (https://dx.doi.org/10.1145/359423.359432)) 2. (en) Michael L.V. Pitteway, « Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter », The Computer Journal, vol. 10, n 3,‎ novembre 1967, p. 282-289 (ISSN 0010-4620 (https://www.worldcat.org/issn/0010-4620&lang=fr), OCLC 4653069003 (https://worldcat.org/oclc/4653069003&lang=fr), DOI 10.1093/comjnl/10.3.282 (https://dx.doi.org/10.1093/comjnl/10.3.282)) [PDF] Ce document provient de « https://fr.wikipedia.org/w/index.php? title=Algorithme_de_tracé_d%27arc_de_cercle_de_Bresenham&oldid=179838963 ». La dernière modification de cette page a été faite le 12 février 2021 à 13:59. Droit d'auteur : les textes sont disponibles sous licence Creative Commons attribution, partage dans les mêmes conditions ; d’autres conditions peuvent s’appliquer. Voyez les conditions d’utilisation pour plus de détails, ainsi que les crédits graphiques. En cas de réutilisation des textes de cette page, voyez comment citer les auteurs et mentionner la licence. Wikipedia® est une marque déposée de la Wikimedia Foundation, Inc., organisation de bienfaisance régie par le paragraphe 501(c)(3) du code fiscal des États-Unis. Politique de confidentialité À propos de Wikipédia Avertissements Contact Développeurs Statistiques Déclaration sur les témoins (cookies) (p ) { p=(p+(4*x)+6); } else { y-=1; p+=((4*(x-y)+10)); } ret.Add(new Point(xc+x,yc-y)); ret.Add(new Point(xc-x,yc-y)); ret.Add(new Point(xc+x,yc+y)); ret.Add(new Point(xc-x,yc+y)); ret.Add(new Point(xc+y,yc-x)); ret.Add(new Point(xc-y,yc-x)); ret.Add(new Point(xc+y,yc+x)); ret.Add(new Point(xc-y,yc+x)); } return ret; } Notes o o uploads/Marketing/ algorithme-de-trace-d-x27-arc-de-cercle-de-bresenham.pdf