Algorithme pour arcs de cercles
Francois
Ma question n'est pas électronique, mais j'imagine que certains
ont déjà été confrontés à ce problème.
J'ai réalisé une table à découper plasma pilotée par un PC sur le
port parallèle.
Aujourd'hui je me tourne vers quelque chose de plus "portable"
(utilisation d'un microcontroleur)
et Je suis à la recherche d'une formule mathématique n'utilisant
ni fonctions trigonométriques, ni table (quantité de ram limitée)
,me permettant de calculer les points d'un arc de cercle.
pour ceux qui utilisent des machines à commande numérique, je cherche
à refaire les fonctions G02 et G03.
donc suivre une courbe avec 2 moteurs PAP grace aux informations suivantes :
- position de départ
- position de fin
- rayon
- sens horaire/inverse (G02 ou G03)
- > ou < que 180°
Si vous avez des idées, je suis toutes ouïes
merci
a+ François
Sam
Bonjour,
y = racine(rayon� - x�)
En faisant varier x de -rayon � + rayon, tu obtiens un demi-cercle
Cordialement
Michel dit "Sam"
"Francois" <francoisp...@wanadoo.effer> a �crit dans le message de
news: 4c124ddf$0$2986$ba4a...@reader.news.orange.fr...
> Bonjour,
>
> Ma question n'est pas �lectronique, mais j'imagine que certains
> ont d�j� �t� confront�s � ce probl�me.
>
> J'ai r�alis� une table � d�couper plasma pilot�e par un PC sur le
> port parall�le.
>
> Aujourd'hui je me tourne vers quelque chose de plus "portable"
> (utilisation d'un microcontroleur)
> et Je suis � la recherche d'une formule math�matique n'utilisant
> ni fonctions trigonom�triques, ni table (quantit� de ram limit�e)
> ,me permettant de calculer les points d'un arc de cercle.
>
> pour ceux qui utilisent des machines � commande num�rique, je cherche
> � refaire les fonctions G02 et G03.
> donc suivre une courbe avec 2 moteurs PAP grace aux informations suivantes
> :
> - position de d�part
> - position de fin
> - rayon
> - sens horaire/inverse (G02 ou G03)
> - > ou < que 180�
>
> Si vous avez des id�es, je suis toutes ou�es
>
> merci
>
> a+ Fran�ois
LeLapin
Oui mais en fait tu veux quoi ?
--
LeLapin
maior�
"Francois" <francoisp...@wanadoo.effer> a �crit dans le message de
news: 4c124ddf$0$2986$ba4a...@reader.news.orange.fr...
>
> Ma question n'est pas �lectronique, mais j'imagine que certains
> ont d�j� �t� confront�s � ce probl�me.
>
> port parall�le.
>
> Aujourd'hui je me tourne vers quelque chose de plus "portable"
> (utilisation d'un microcontroleur)
> ni fonctions trigonom�triques, ni table (quantit� de ram limit�e)
>
> donc suivre une courbe avec 2 moteurs PAP grace aux informations suivantes
> :
> - position de fin
> - rayon
> - sens horaire/inverse (G02 ou G03)
> - > ou < que 180�
Il te faudra tout de m�me utiliser un peu de trigonom�trie, transformer les
coordonn�es polaires (angle et rayon) en coordonn�es rectangulaire ( x et
y )
x=rayon * cos(phi)
y=rayon * sin(phi)
Ce qui est d'une grande simplicit� � calculer pour un microcontr�leur
moyen
Si tu programmes en asm et que tu ne trouves pas les routines math�matiques
ad�quates , tu peux ajouter au �C un coprocesseur math�matique de ce genre
par exemple
http://www.lextronic.fr/P1547-coprocesseur-mathematique-um-fpu-v3.html
Jean-Christophe
> Il te faudra tout de m me utiliser un peu de trigonom trie, transformer les
> coordonn es polaires (angle et rayon) en coordonn es rectangulaire ( x et
> y )
> x=rayon * cos(phi)
> y=rayon * sin(phi)
> Ce qui est d'une grande simplicit calculer pour un microcontr leur
> moyen
Il a dit qu'il ne voulait pas de fonctions trigo.
> Si tu programmes en asm et que tu ne trouves pas les routines math matiques
> ad quates , tu peux ajouter au C un coprocesseur math matique de ce genre
> par exemple
> http://www.lextronic.fr/P1547-coprocesseur-mathematique-um-fpu-v3.html
Ajouter un chip au lieu d'émuler ca par soft ?
Tu en as d'autres comme ca, des solutions qui compliquent ?
Jean-Christophe
> Je suis à la recherche d'une formule mathématique n'utilisant
> ni fonctions trigonométriques, ni table (quantité de ram limitée)
> ,me permettant de calculer les points d'un arc de cercle.
La question est : préfères-tu optimiser
la vitesse de calcul ou la taille mémoire ?
Soit tu devras émuler les fonctions par soft (une seule fonction
en fait, puisque sin et cos c'est la meme chose à pi/2 près)
et cela prendra du temps de calcul,
soit tu implémentes une table avant autant de points qu'il te faut
sachant que tu n'as pas forcément besoin de 360 points ...
et que la table n'a pas besoin d'etre en RAM.
Et pour mettre dans une table par exemple la fonction sin,
tu peux gagner un facteur 4 sur la taille de la table
en n'y implémentant que les valeurs de zéro à pi/2
(le reste se retrouve par symétrie)
Darwin
> Aujourd'hui je me tourne vers quelque chose de plus "portable"
> (utilisation d'un microcontroleur)
> et Je suis à la recherche d'une formule mathématique n'utilisant
> ni fonctions trigonométriques, ni table (quantité de ram limitée)
> ,me permettant de calculer les points d'un arc de cercle.
En graphique 2D, il y a des algorithmes intéressants pour tracer à bas
niveau des cercles et des lignes de façon efficace en temps et en
mémoire. Pour les arcs de cercle, voici une page intéressante de
Wikipedia :
Stan
> Bonjour,
> y = racine(rayon - x )
> En faisant varier x de -rayon + rayon, tu obtiens un demi-cercle
En géométrie euclidienne ou hyperbolique ?
--
-Stan
Sam
Bonjour,
tu as perdu les "² "!
je ne savais même pas que la géométrie hyperbolique existait !
tout comme je fais de la prose, je crois que je fais de la géométrie
euclidienne.
la perte de tes ² m'intrigue, je vais écrire la formule autrement
y=racine(rayon*rayon - x*x)
Cordialement
Michel dit "Sam"
"Stan" <t...@neuf.fr> a écrit dans le message de news:
17b9a725-5190-4fd2...@y4g2000yqy.googlegroups.com...
Stan
> Bonjour,
> tu as perdu les "² "!
>
> je ne savais même pas que la géométrie hyperbolique existait !
> tout comme je fais de la prose, je crois que je fais de la géométrie
> euclidienne.
>
> la perte de tes ² m'intrigue, je vais écrire la formule autrement
> y=racine(rayon*rayon - x*x)
>
Pourtant, ils sont bien là à présent.
Mais je ne sais pas d'où viennent ces pb
d'encodage de page...
--
-Stan
Stan
J'avais pensé au courbes de Bézier :
http://www.rdrop.com/~cary/program/bezier.c
Mais on ne peut pas tracer d'arc de cercle :-(
--
-Stan
whygee
> Si vous avez des idées, je suis toutes ouïes
j'ajoute la mienne : CORDIC :-)
il faut une multiplication constante suivie d'itérations
de décalages/additions, et on fait toutes les fonctions
trigo et même plus, les doigts dans le nez.
c'est un peu bourring mais ça prend peu de place en mémoire
et les opérations sont possibles en précision arbitraires,
tant qu'on a les primitives qu'il faut (addition, soustraction,
décalage, multiplication par constante).
ça fonctionne en "virgule fixe", tout est normalisé entre 0 et 1.
j'ai fait joujou avec ça à une époque, pour faire des
oscillateurs numériques mais chut...
http://en.wikipedia.org/wiki/CORDIC
(ne pas faire gaffe aux maths, c'est juste pour comprendre
pourquoi ça marche et à quoi servent chaque opération)
http://fr.wikipedia.org/wiki/CORDIC
(pas pire, avec du code source plus digeste)
note : le 8087 (coproc arithmétique du 8086)
utilisait ça en interne, sur 80 bits.
un peu lent, mais efficace.
en nombres entiers sur 16 ou 32 bits
on fait déjà des trucs sympas :-)
Sinon, pour les cercles il y aussi l'algorithme de Bresenham
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d%27arc_de_cercle_de_Bresenham
et
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
(meilleur)
> merci
ben bon courage !
on attend de voir les résultats ;-)
> a+ François
yg
kiriak
En suivant ton premier lien, j'ai trouv� celui-ci :
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
qui me semble r�pondre parfaitement au probl�me initial.
Cordialement,
CK
"whygee" <y...@yg.yg> a �crit dans le message de news:
huv9ak$2hd$1...@speranza.aioe.org...
Francois wrote:
> Si vous avez des id�es, je suis toutes ou�es
il y a d�j� eu plein de pistes post�es,
j'ajoute la mienne : CORDIC :-)
il faut une multiplication constante suivie d'it�rations
de d�calages/additions, et on fait toutes les fonctions
trigo et m�me plus, les doigts dans le nez.
c'est un peu bourring mais �a prend peu de place en m�moire
et les op�rations sont possibles en pr�cision arbitraires,
tant qu'on a les primitives qu'il faut (addition, soustraction,
d�calage, multiplication par constante).
�a fonctionne en "virgule fixe", tout est normalis� entre 0 et 1.
j'ai fait joujou avec �a � une �poque, pour faire des
oscillateurs num�riques mais chut...
http://en.wikipedia.org/wiki/CORDIC
(ne pas faire gaffe aux maths, c'est juste pour comprendre
pourquoi �a marche et � quoi servent chaque op�ration)
http://fr.wikipedia.org/wiki/CORDIC
(pas pire, avec du code source plus digeste)
note : le 8087 (coproc arithm�tique du 8086)
utilisait �a en interne, sur 80 bits.
un peu lent, mais efficace.
en nombres entiers sur 16 ou 32 bits
on fait d�j� des trucs sympas :-)
Sinon, pour les cercles il y aussi l'algorithme de Bresenham
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d%27arc_de_cercle_de_Bresenham
et
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
(meilleur)
> merci
ben bon courage !
on attend de voir les r�sultats ;-)
> a+ Fran�ois
Jean-Christophe
C'est pas mal, mais l'algo Cordic nécéssite une table ?
Alors autant y coller directement les valeurs des cosinus, non ?
whygee
> C'est pas mal, mais l'algo Cordic nécéssite une table ?
> Alors autant y coller directement les valeurs des cosinus, non ?
dans mes souvenirs, non, CORDIC n'a besoin que d'une constante.
je n'ai pas pris le temps de bien regarder l'article de wikipedia,
je ne sais pas ce qu'ils ont bien pu traficoter avec l'algorithme...
qui est d'ailleurs assez fascinant :-)
whygee
> salut,
> En suivant ton premier lien, j'ai trouvé celui-ci :
> http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andres
> qui me semble répondre parfaitement au problème initial.
je l'ai mis comme dernier lien dans mon post :-D
comme quoi il faut lire jusqu'au bout avant de cliquer partout ;-)
> Cordialement,
> CK
Jean-Christophe
>> C'est pas mal, mais l'algo Cordic nécéssite une table ?
>> Alors autant y coller directement les valeurs des cosinus, non ?
> dans mes souvenirs, non, CORDIC n'a besoin que d'une constante.
Pas dans le lien que tu as donné :
http://tinyurl.com/36tk8yy
Francois
Je n'ai pas eu accès au net de tout le WE (merci les orages), et
ce matin je vois tous ces messages : SUPER !!
Merci à vous tous, je vais aller voir toutes vos pistes
(pour le tracé de cercle avec racine carré j'avais déjà fait,
mais ça ne résoud pas mon problème d'arcs)
a+ François
maioré
Francois wrote:
Si vous avez des idées, je suis tout ouïe
================
Si tu préfères un copié-collé (qui marche ..) , voici un fichier source
extrait d'un compilateur commercial
http://www.google.fr/search?hl=fr&source=hp&q=glcd_circle&aq=f&aqi=&aql=&oq=&gs_rfai=
( J'ai trouvé ça, fonction élaborée par les informaticiens de la société CCS
qui normalement ne devrait pas se trouver sur le Web car,
attachée seulement à chaque licence du produit )
Cette méthode, s'inspirant des (vieux) travaux de Bresenham est surtout
adaptée pour "allumer" des pixels sur un écran.
La transposition en n'importe quel langage est simple , int 16 bits mais
"signed"