Algorithme pour arcs de cercles

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From French to

Threaded View
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

Re: Algorithme pour arcs de cercles

Bonjour,
y = racine(rayon² - x²)
En faisant varier x de  -rayon à + rayon, tu obtiens un demi-cercle
Cordialement
Michel dit "Sam"

Quoted text here. Click to load it



Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it

En gE9%omE9%trie euclidienne ou hyperbolique ?

--
-Stan

Re: Algorithme pour arcs de cercles


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"

snipped-for-privacy@y4g2000yqy.googlegroups.com...
Quoted text here. Click to load it

En géométrie euclidienne ou hyperbolique ?

--
-Stan



Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it

Pourtant, ils sont bien lE0% E0% prE9%sent.
Mais je ne sais pas d'oF9% viennent ces pb
d'encodage de page...
--
-Stan

Re: Algorithme pour arcs de cercles
Bonjour,

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

Re: Algorithme pour arcs de cercles
Francois a tapoté du bout de ses petites papattes :
Quoted text here. Click to load it

Oui mais en fait tu veux quoi ?

--
LeLapin



Re: Algorithme pour arcs de cercles

Quoted text here. Click to load it
====================
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



Re: Algorithme pour arcs de cercles
On Jun 11, 6:34 pm, "maior "

Quoted text here. Click to load it

Il a dit qu'il ne voulait pas de fonctions trigo.

Quoted text here. Click to load it

Ajouter un chip au lieu d'E9%muler ca par soft ?
Tu en as d'autres comme ca, des solutions qui compliquent ?

Re: Algorithme pour arcs de cercles
On Jun 11, 4:53 pm, Francois

Quoted text here. Click to load it

La question est : prE9%fE8%res-tu optimiser
la vitesse de calcul ou la taille mE9%moire ?

Soit tu devras E9%muler les fonctions par soft (une seule fonction
en fait, puisque sin et cos c'est la meme chose E0% pi/2 prE8%s)
et cela prendra du temps de calcul,
soit tu implE9%mentes une table avant autant de points qu'il te faut
sachant que tu n'as pas forcE9%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 implE9%mentant que les valeurs de zE9%ro E0% pi/2
(le reste se retrouve par symE9%trie)

Re: Algorithme pour arcs de cercles

Quoted text here. Click to load it

En graphique 2D, il y a des algorithmes intE9%ressants pour tracer E0% bas
niveau des cercles et des lignes de faE7%on efficace en temps et en
mE9%moire. Pour les arcs de cercle, voici une page intE9%ressante de
Wikipedia :

http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it

J'avais pensE9% au courbes de BE9%zier :

http://www.rdrop.com/~cary/program/bezier.c

Mais on ne peut pas tracer d'arc de cercle :-(
--
-Stan


Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it
il y a dE9%jE0% eu plein de pistes postE9%es,
j'ajoute la mienne : CORDIC :-)
il faut une multiplication constante suivie d'itE9%rations
de dE9%calages/additions, et on fait toutes les fonctions
trigo et mEA%me plus, les doigts dans le nez.
c'est un peu bourring mais E7%a prend peu de place en mE9%moire
et les opE9%rations sont possibles en prE9%cision arbitraires,
tant qu'on a les primitives qu'il faut (addition, soustraction,
dE9%calage, multiplication par constante).
E7%a fonctionne en "virgule fixe", tout est normalisE9% entre 0 et 1.

j'ai fait joujou avec E7%a E0% une E9%poque, pour faire des
oscillateurs numE9%riques mais chut...

http://en.wikipedia.org/wiki/CORDIC
(ne pas faire gaffe aux maths, c'est juste pour comprendre
  pourquoi E7%a marche et E0% quoi servent chaque opE9%ration)
http://fr.wikipedia.org/wiki/CORDIC
  (pas pire, avec du code source plus digeste)

note : le 8087 (coproc arithmE9%tique du 8086)
utilisait E7%a en interne, sur 80 bits.
un peu lent, mais efficace.
en nombres entiers sur 16 ou 32 bits
on fait dE9%jE0% 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_d =
e_Bresenham
et
http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_cercle_d%27Andre =
s
(meilleur)

Quoted text here. Click to load it
ben bon courage !
on attend de voir les rE9%sultats ;-)

Quoted text here. Click to load it
yg

--20%
http://ygdes.com / http://yasep.org

Re: Algorithme pour arcs de cercles
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.
Cordialement,
CK

huv9ak$2hd$ snipped-for-privacy@speranza.aioe.org...
Francois wrote:
Quoted text here. Click to load it
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)

Quoted text here. Click to load it
ben bon courage !
on attend de voir les résultats ;-)

Quoted text here. Click to load it
yg

--
http://ygdes.com / http://yasep.org



Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it
je l'ai mis comme dernier lien dans mon post :-D
comme quoi il faut lire jusqu'au bout avant de cliquer partout ;-)

Quoted text here. Click to load it
yg
--20%
http://ygdes.com / http://yasep.org

Re: Algorithme pour arcs de cercles
On Jun 12, 7:45A0%am, whygee

C'est pas mal, mais l'algo Cordic nE9%cE9%ssite une table ?
Alors autant y coller directement les valeurs des cosinus, non ?

Quoted text here. Click to load it

Re: Algorithme pour arcs de cercles
Quoted text here. Click to load it

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 :-)
yg
--20%
http://ygdes.com / http://yasep.org

Re: Algorithme pour arcs de cercles
On Jun 12, 9:38A0%pm, whygee

Quoted text here. Click to load it


Pas dans le lien que tu as donnE9% :
http://tinyurl.com/36tk8yy

Re: Algorithme pour arcs de cercles

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"






Site Timeline