Le cercle enchanté d'andres gît en nos mémoires

Soyez le premier à donner votre avis sur cette source.

Vue 4 128 fois - Téléchargée 392 fois

Description

Pour compléter le "post" de Barbichette sur l'algorithme de tracé de cercle de Bresenham et l'optimisation, visible ici :

http://www.delphifr.com/codes/COMPARATIF-ALGO-CERCLES_54052.aspx

voici une petite présentation d'un autre algorithme de tracé de cercle.

«Mais rien ne ressemble plus à un cercle qu'un autre cercle», me direz-vous ?
- Que nenni, mon bon monsieur ! Il existe dans le monde de la géométrie discrète un cercle merveilleux et pourtant mal connu : le cercle d'Andres.

«Mais ce cercle qu'est-ce qu'il a-t'il de si merveilleux que ça ?»
- Eh bien, cet algorithme permet de paver entièrement le plan par des cercles concentriques, sans les trous que laissent habituellement les autres méthodes de tracé de cercle.

La première utilisation de cette remarquable propriété qui vient à l'esprit, est le dessin de dégradés radiaux particuliers (voir la capture).
Une autre utilisation, moins évidente, est son application dans les logiciels de jeux. Cette algo permet en effet de simuler la "vision" d'un personnage de l'IA. Il suffit de centrer des cercles d'Andres sur le personnage et d'explorer exhaustivement les pixels de la carte du jeu. L'algo donnera la distance précise du premier adversaire (par exemple) rencontré, puis des suivants. De la même façon, on simulera un radar ou le flair d'un animal, etc... dans un rayon donné.
Il est à noter que l'algo concerve cette propriété si on le transpose en 3D.

Pour mettre cet algo en oeuvre je vous propose, dans cette démo, de tester deux méthodes différentes :
- par TCanvas
- directement dans la mémoire du Bitmap

Si vous testez cette démo, vous vous rendrez compte que le travail en mémoire est, de loin, la méthode la plus rapide.

Conclusion :


Fait sous D7 et Seven.
Accepte des Bitmaps de 24 et 32 bits.
Pour obtenir des temps de traitement significatifs (<>0) pour la méthode "en mémoire", vous pouvez jouer sur le nombre de passes et sur la taille du Bitmap, la fiche étant "sizable".

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
2106
Date d'inscription
mardi 10 décembre 2002
Statut
Modérateur
Dernière intervention
15 décembre 2014
5
lol
Messages postés
2527
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
16 octobre 2019
14
@Cantador
En fait, j'aurais dû titrer :
« LE CERCLE ENCHANTÉ D'ANDRES GÎT EN NOS MÉMOIRES D'ORDINATEUR »
pour mettre l'accent sur le traitement en mémoire.

Mais j'ai préféré l'alexandrin, qui sonne à notre oreille comme le pf32bit sonne au gestionnaire de mémoire de Windows.

@Mauricio
Je viens juste de comprendre ta 'vanne' : « ...cercle vicieux... »
^-^

Comme quoi il est bon de prendre la peine de relire...
;)
Messages postés
4715
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
13
et dire que cashmire a dès sa naissance cet algorithme implanté dans son cerveau...
nous en revanche pauvres humains qui avons perdu nos ressources naturelles sommes obligés
de concevoir des machines pour faire la même chose.
beau travail de Caribensila pour ce rafraîchissement de nos mémoires !
Peut-être, as-tu la possibilité à partir de ce programme de concevoir de belles images
comme par exemple: http://commons.wikimedia.org/wiki/File:Dizzy_thorns.jpg?uselang=fr
ce qui nous changerait un peu des traditionnelles fractales.
8/10
Messages postés
2527
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
16 octobre 2019
14
@Mauricio
Il ne te reste plus qu'à créer une nouvelle gamme de compos... tous circulaires !
( Et t'as intérêt à ce que le code tourne rond ! ;)

@Fredelem
« Mais puisque ton algorithme est plus simple, je vais essayer de le mettre en couleurs. Est-ce que ça te paraît possible ou est-ce désespéré ? »

A priori, si tu veux présenter un choix de couleur sur un disque, cet algo est le seul qui te permette de le faire de façon smple et sans trou.

En fait, je suppose que tu penses à faire un cercle chromatique ?
- Pourquoi pas.
A condition de diviser ce cercle en 8 couleurs primaires et de présenter ces couleurs de façon discrète et non pas continue; car l'algo d'Andres ne se prête pas bien à une représentation continue. Voir :
http://fr.wikipedia.org/wiki/Cercle_chromatique
Cet algo calcule les pixels de façon dynamique et non pas statique. En effet, la position de chaque pixel dépend d'un pixel calculé précédemment, mais cette relation ne recouvre pas toujours une position logique dans le plan.
Pour s'en convaicre, il suffit de dessiner un cercle avec cet algo, en choisissant une couleur différente pour chaque octant et en le faisant dessiner pixel par pixel avec des Sleep() bien placés (c'est la meilleure méthode pour comprendre la logique de l'algo).

Tu verras que dessiner un cercle chromatique de façon continue sera très difficile.
En revanche Andres se prête bien à un dessin de cercle secteur par secteur...
Messages postés
132
Date d'inscription
dimanche 29 octobre 2006
Statut
Membre
Dernière intervention
24 août 2020
2
Dans ma petite mémoire, il ne gît aucun souvenir relatif à l'algorithme d'Andres mais grâce à Wilkipedia, j'ai compris de quoi il s'agissait.

Tracer le premier point d'un cercle (celui qui est à la verticale du centre), c'est facile. Mais à partir du suivant, les choses se compliquent. On peut bien sûr, calculer y en fonction de x et du rayon, sachant que x²+y²=R². Mais dans les premiers temps de l'informatique, si on utilisait cette technique pour tracer un cercle en assembleur, on voyait le cercle se tracer très lentement, plus lentement que dans un langage évolué.

L'idée qui venait à l'esprit, c'était de fabriquer une table des sinus une bonne fois pour toutes, de la mettre dans un fichier, puis chaque fois qu'on voulait tracer un cercle, la lire, la mettre en mémoire et tracer ses points à toute vitesse.

Andres était sans doute un type qui n'a pas aimé cette méthode et qui a eu une autre idée: Il s'est sans doute dit "Je trace le premier point et ensuite, le suivant, c'est soit celui qui est juste à sa droite, soit celui qui est juste au dessous soit celui qui est juste au dessous et à droite. Si je trouve un algorithme simple pour trouver lequel des trois je dois prendre, j'aurais fait un grand pas vers la simplicité". Il y est parvenu et du coup, on bénéficie de sa trouvaille même dans les langages évolués.

Je cherchais à créer un composant pour remplacer le Colordialog, un cercle contenant des couleurs très variées sur lequel il suffirait de cliquer pour choisir une couleur. Quand j'ai vu l'envoi de Barbichette, je me suis dit que je le tenais. Mais puisque ton algorithme est plus simple, je vais essayer de le mettre en couleurs. Est-ce que ça te paraît possible ou est-ce désespéré ?
Afficher les 6 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.