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 trace d x27 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 des cercles en image matricielle Sommaire Historique Explication de l'algorithme de base dans le premier octant Un huitième su ?t 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 Historique Cet algorithme publié par Bresenham en février 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 Explication de l'algorithme de base dans le premier octant Un huitième su ?t 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 su ?t d'exploiter la symétrie pour positionner les pixels dans les sept autres octants L'algorithme de base CL 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 ??M au-dessus du cercle idéal ?? choix de F ?? incrémenter x décrémenter y m ?? M au-dessous du cercle idéal ?? choix de E ?? incrémenter x Optimisation de l'algorithme Pour optimiser l'algorithme on calcule la variable m récursivement On montre que 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 et on obtient On va modi ?er la variable m en fonction du choix du pixel E ou du pixel F On nommera valeur de m et la nouvelle valeur de m On montre que si on choisit E l'ancienne Il faut donc incrémenter de démonstration Si on choisit E alors Or d'après l'équation COr d'après l'équation donc d'o? En utilisant le fait que on obtient On montre que si on