[Résolu] Rotations, trigonometrie et perte de précision

[awbinux]

Bonsoir,

(Niveau Lycée ou supérieur?)

Pour la réalisation d'un algorithme, j'ai besoin d'implémenter un système de rotation de figures géométriques simples (carré, rectangle, triangles).

J'ai donc choisi d’exprimer les coordonnées des points des figures par leur distance au centre de la figure ainsi que l'angle avec l'axe des abscisse.
Ainsi pour faire pivoter la figure je n'aurais qu'a augmenter la valeur de ces angles.

En théorie tout fonctionne, mais pas en pratique.
Dans le cas des triangles non équilatéraux, j'ai une perte de précision pendant les calculs non négligeable (parfois 25% !!)

Voici la procédure suivie:

Je possède initialement les coordonnées cartésiennes des trois points.

Je calcul les coordonnées cartésiennes du centre :
Xg = (Xa + Xb + Xc) / 3;
Yg = (Ya + Yb + Yc) / 3;

Je calcul ensuite les distances de ces points au centre du triangle :
Sqrt((Xb - Xa)² + (Yb - Ya)²);

ainsi que les trois angles du triangle à l'aide du théorème d'Al Kashi :
A^CB = arccos ( (a² + b² - c²) / (2ab));

Je divise les valeurs des angles obtenus par deux et j'applique les derniers changements :
angleC = PI - 2*angleB - angleC;
angleA = angleA + PI;
angleB = angleB * -1;

J'ai donc maintenant les distances des trois points du triangle par rapport au centre ainsi que les angles correspondant.

J'applique une rotation d'un angle lambda (on va dire 0rad pour faire simple et montrer les problèmes, mais ça pourrait être n'importe quelle valeur).

Puis je reconverti les couples distance+angle en coordonnées cartésiennes pour le traitement et l'affichage : (pour A)
x = cos(angleA)* distanceA + Xg;
y = sin(angleA)* distanceA + Yg;

Et là je me dis c'est niquel, ça fonctionne, mais il n'en est rien !

En effet, si je prends un triangle rectangle ayant ses côtés de longueur 3 4 et 5, avec les positions cartésiennes initiales suivante :
A(0, 0)
B(3, 0)
C(3, 4)

après passage à la moulinette trigonométrique, j'obtiens ces coordonnées :
A(-0.14993539954628, 0.258365633560193)
B(3.17851130197758, 0.154822031355754)
C(2.90061707240709, 4.03518455055459)



Il y a bien un air de ressemblance, mais la marge d'erreur est beaucoup trop grande ! Impossible d'utiliser correctement l'algorithme si les dimensions des triangles sont modifiées dès le début du processus. :mur:

à priori la perte d'info viendrait du passage par cos et arccos, puisque les distances ne sont données que par un simple calcul et ne changent jamais.

Ou alors suis-je complètement a côté de la plaque et il est normal que les résultats ne concordent pas?

Comment puis-je augmenter la précision du processus?

J'ajouterais qu'il n'y a aucun problème avec les triangles équilatéraux.


Pour info, je code en C#

[C.Ret]

Bonsoir.

Et oui, c'est ainsi depuis l'invention du numérique, la moindre opération arithmétique crée des erreurs de calcul et d'arrondi.
Il ne faut pas croire que les ordinateurs savent calculer. Bien au contraire, pour faire tourner un objet mieux vaut avoir un tour, un plateau et un axe qu'un calculateur. Et le nombre de décimale, bits, ou registre ne change rien à cette affaire.

Un ordinateur ça sert surtout à ordonner les choses et à faire des calculs répétitifs. Ce sont en fait des moulins à poivre. Met des moulinettes d'un genre particulier car il faut y faire semblant de tourner la manivelle. Si on la tourne pour de vrai, contrairement à un poivrier, tout ce casse très vite.

L'astuce et donc de faire "semblant" de tourner les objets. D'utiliser le fait que refaire à l'infini les calculs et transformations est facile dans un programme, mais il faut toujours partir d'une image immuable de l'objet.

En clair, il suffit pour chaque objet à animer de conserver les coordonnées initiales (phase immobile de représentation de l'objet). Et pour chaque étape de l'animation, ou à chaque pas du mouvement, ou à chaque étape d'un calcul itératif, on ne modifie pas ces coordonnées (surtout pas ! On accumule les erreurs et décalage et on casse le moulin à vent !). On recalcule à chaque avancement à partir des coordonnée initiale et du paramètre d'avancement (par exemple l'angle de rotation - mais cela s'applique aussi pour les autres mouvements ou déplacements).

De cette façon, même si on ne peut pas empêcher les erreurs d'arrondi et autres décalages numériques, au moins on ne les accumule pas.

Et cela est valable que l'on utilise des coordonnées cartésiennes ou polaires. Quelque soit le système en fait, on a intérêt à conserver et ne pas modifier les coordonnées initiales (sauf si l'objet se déforme) et recalculer les coordonnée instantanées (phase mobile) directement à partir des coordonnées initiales et de l'avancement du truc.

Concrètement, en C c'est facile, il suffit de définir double un jeu de coordonnée et caractériser chaque représentation par son degré d'avancement (rotation, déplacement, etc).
Le premier jeu de coordonnées sert de référence (coordonnée initiale, phase immobile, forme de l'objet et éventuellement déformation), le second jeu sert à mémoriser la position actuelle (phase mobile) obtenue par un unique et identique calcul directement à partir du premier jeu de coordonnée et de l'unique avancement de la représentation. A chaque pas on remplace les coordonnées de la phase mobile par le résultat du calcul. En aucun cas on ne doit utiliser un résultat mobile précèdent sous risque d'accumuler les co....ies.


Le second jeu (phase mobile) sert donc transitoirement à la représentation de l'objet en mouvement et pour d'éventuel traitemtn des collisions ou autres interactions.


Le calcul doit être identique à chaque pas de l'avancement et toujours le même pour minimiser les erreurs, ou à défaut les systématiser. On saura ainsi, si besoin est, évaluer leur importance (calcul d'incertitude).

Il n'y a pas qu'en informatique que ce type d'algorithme est utilisé. En navigation c'est le même principe, on calcule sa trajectoire toujours en fonction de nouveaux relevés amers ou azimut. Jamais, au Grand Poséidon jamais, à partir d'une position précédente même si on l'est sûr qu'elle est bien juste. Car là aussi, il faut éviter d'accumuler les erreurs et écarts.

Ah! Combien de navigateurs étourdis se sont perdus corps et âmes en mer en faisant cette erreur !

Au moins en informatique c'est moins risqué... quoi que...

[awbinux]

Merci pour ta réponse très pertinente. Tu as anticipé sur un problème que j'aurais rencontré plus tard :zen:


Mais même si je ne peux éradiquer l'imprécision, il faudrait tout de même que l'on parvienne à la minimiser, car dans l'état actuel des choses l'implémentation de la rotation des triangles non équilatéraux est fortement remise en question :soupir2:

J'avais pensé à multiplier toutes les valeurs par une constante assez élevée pour les calculs et diviser les résultats de manière à décaler l'imprécision dans décimales, mais avec le modulo 2PI des fonctions trigonométriques ça ne doit pas être possible.

J'ai du mal à concevoir un autre système de rotation.

J'ai également du mal à voir comment en utilllisant des nombres à 16 chiffres significatifs je peux arriver à des erreurs aux dixièmes ?

[C.Ret]

Cela ne changera rien, quelque soit la façon dont on mène les calculs, sauf à n'utiliser que des entiers, la méthode de réprensentation et de traitemetn des nombres crée irrémédiablemetn des erreurs.

Le défi du programmeur est de faire en sorte que ces erreurs n'ayent pas d'incidence sur les résultats de son processus.

Concernant les rotation, nous avons un problème avec les environnement de développement actuel, les fonction cos et sin utilise des radiants. Or PI n'est pas un nombre rond. Alors, comment peut faire exactement un tour complet ?
Une partie de l'ereur que tu observe vient de cela, le nombre PI que peut repréenter ton ordi n'est qu'une approximation, la valeur des sin et cos en est de ce fait encore une plus grande, y compris ce que tu appèle "un tour".

Si j'ai bien compris, tous tes triangles tournent sur eux-même selon un axe qui passe par leur centre géométrique.

Ton idée d'utiliser des coorodnnées angulaires relatives à ce centre est excellente. Ta seule erreur est de les modifier à chaque pas élémentaire, tu accumule en même temps les approximation (car cos et sin sont faux sur ton ordi, comme sur tous les miens d'ailleurs et tous ceux que j'ai utilisé depuis 1979).

Une fois que tu as calculé les coordonnées (angle et distance) de chaque sommet, il ne faut plus les modifier.

Pour dessiner les points, il te suffit d'ajouter l'angle de rotation à l'angle de la coorodnnée pour obtenir la position du sommet à dessiner. Mais, il ne faut pas perdre la position initale et la réutiliser le coup suivant avec l'angle de rotation suivant.

Ensuite, si tu veux vérifer la justesse des positions, rappèle toi qu'une partie de l'erreur observée provient du fait que tu ne sait pas faire un tour exact car ton ordi ne connais pas PI exact et travaille en radian.


Ce que l'on fait souvent, c'est qu'au leu d'utilisr les fonction sin et cos, on crée un tableau avec les valeur précalculée des sin et cos de façon à ce qu'un tour corresponde exactement à la hauteur du tableau et on ajuste les valeur afin que la première ligne (0°) et la dernière (360°) soient strictement identique

Cette technique de pré-calcul permet :
- de calculer plus vite les sin et cos lors de l'animation (c'était un vrai problème de mon temps car le calcul des cos et sin est une méthode itérative qui, sur les machine lente du précèdent millènaire posait un réel problème pour l'animation). Aujourd'hui c'est un détail,
- de définir un tour exactement et rigoureusement, par exemple après 128 rotations élémentaire font exactement un tour et pas 128/3.141569.... qui ne donne pas des nombre rond et entier et donc est une source d'ennuis
- de pouvoir ajuster les valeurs afin d'arrondir les angles et homogéniéser la rotation (la représentation sur un écran n'est pas rigouruse non plus à cause des pixels)

Et quelqeu soit le language utilisé, compilé ou non, lireune valeur pré-calculé dans un tableau, tous les ordinateur le font mieux et plus rapidemetn que faire des calculs longs, compliqués et très savants pour produire une valeur erronée d'un cos et sin !

Et le code devient souple et facile, il y a le tableau des coordonnées initiales, des cos et sin pré-calculé, des coorodnnées de l'objet animé. Ce n'est plus qu'un jeu de décallage des pointeurs.



P.S.: J'oubliais un truc important avec arccos.

Comme les cos et sin sont déjà faux et que arccos est calculé en interne à l'aide de ceux-ci, arccos est encore plus fausse.

De plus, l'argument est un nombre float entre 0 et 1 obtenu en faisant un rapport. Hors la division c'est pas le fort des ordin (test ton compilatuer c en lui demandant de calculer (1/3)*3) tu sera pas déçu du voyage.

Tu as donc intérêt à améliorer les choses en :
- calculant la coordonnée angulaire de chaque sommet non pas à partir des distances, mais directement à partir des coordonnées cartésiennes (du sommet comparé au centre de rotation).
- précalculer la fonction arccos de façon à travailler avec des unités cohérente (éviter les PI et autre radian), ce qui permet aussi de:
- ne pas utiliser la fonction arcos, mais trouver l'angle par une méthode de résolution numérique (dichotomie, ou newton ou autre), qui sera peut-être moins rapide, mais qui pourrait être plus fiable. En particulier si les coordonnées cartésienne sont toujours des entiers dans un intervalle donné. Ce qui peut simplifier et faciliter la résolution itérative et trouver simultanément coorodnnée angulaire et distance.

[awbinux]

Merci infiniment, tu a résolu le problème de précision (du moins à une échelle plus que suffisante !)

L'idée de calculer le produit vectoriel entre un vecteur unité partant du centre du triangle et les vecteurs centre-point est beaucoup plus simple à coder que celle que j'ai décrite dans le premier post.

On obtient le bon angle par un seul calcul contre 3 pour l'autre méthode.

Du coup beaucoup moins (quasiment aucune) imprécision.

J'avais également implémenté sans m'en appercevoir le système de calcul des coordonnées des points en fonction des coordonnées de l'état initial du triangle.

Voila, tout fonctionne.

RESULTAT : Le produit vectoriel est beaucoup plus précis que de passer par plusieurs opérations consécutives.

Encore merci :lol3:

[hammana]

Bonsoir,

(Niveau Lycée ou supérieur?)

Pour la réalisation d'un algorithme, j'ai besoin d'implémenter un système de rotation de figures géométriques simples (carré, rectangle, triangles).

J'ai donc choisi d’exprimer les coordonnées des points des figures par leur distance au centre de la figure ainsi que l'angle avec l'axe des abscisse.
Ainsi pour faire pivoter la figure je n'aurais qu'a augmenter la valeur de ces angles.

En théorie tout fonctionne, mais pas en pratique.
Dans le cas des triangles non équilatéraux, j'ai une perte de précision pendant les calculs non négligeable (parfois 25% !!)

Voici la procédure suivie:

Je possède initialement les coordonnées cartésiennes des trois points.

Je calcul les coordonnées cartésiennes du centre :
Xg = (Xa + Xb + Xc) / 3;
Yg = (Ya + Yb + Yc) / 3;

Je calcul ensuite les distances de ces points au centre du triangle :
Sqrt((Xb - Xa)² + (Yb - Ya)²);

ainsi que les trois angles du triangle à l'aide du théorème d'Al Kashi :
A^CB = arccos ( (a² + b² - c²) / (2ab));

Je divise les valeurs des angles obtenus par deux et j'applique les derniers changements :
angleC = PI - 2*angleB - angleC;
angleA = angleA + PI;
angleB = angleB * -1;

J'ai donc maintenant les distances des trois points du triangle par rapport au centre ainsi que les angles correspondant.

J'applique une rotation d'un angle lambda (on va dire 0rad pour faire simple et montrer les problèmes, mais ça pourrait être n'importe quelle valeur).

Puis je reconverti les couples distance+angle en coordonnées cartésiennes pour le traitement et l'affichage : (pour A)
x = cos(angleA)* distanceA + Xg;
y = sin(angleA)* distanceA + Yg;

Et là je me dis c'est niquel, ça fonctionne, mais il n'en est rien !

En effet, si je prends un triangle rectangle ayant ses côtés de longueur 3 4 et 5, avec les positions cartésiennes initiales suivante :
A(0, 0)
B(3, 0)
C(3, 4)

après passage à la moulinette trigonométrique, j'obtiens ces coordonnées :
A(-0.14993539954628, 0.258365633560193)
B(3.17851130197758, 0.154822031355754)
C(2.90061707240709, 4.03518455055459)



Il y a bien un air de ressemblance, mais la marge d'erreur est beaucoup trop grande ! Impossible d'utiliser correctement l'algorithme si les dimensions des triangles sont modifiées dès le début du processus. :mur:

à priori la perte d'info viendrait du passage par cos et arccos, puisque les distances ne sont données que par un simple calcul et ne changent jamais.

Ou alors suis-je complètement a côté de la plaque et il est normal que les résultats ne concordent pas?

Comment puis-je augmenter la précision du processus?

J'ajouterais qu'il n'y a aucun problème avec les triangles équilatéraux.


Pour info, je code en C#

Je propose d'aborder le problème comme suit:

Pour faire tourner un point M de coordonnées x1,y1, d'un angle b autour d'un point O1 de coordonnées x0,y0 je prend des axes ayant pour origine O1, soit O1u,O1v. Les nouvelles coordonnées deviennent:
u1=x1-x0, v1=y1-y0
O1M fait avec O1u un angle a=arctangente(v1/u1)
(choisir la valeur de a compatible avec le signe de sin(a))
je calcule la distance d=O1M=racine(u1²+v1²)
Après rotation de l'angle b les coordonnées deviennent u2=d*cos(a+b), v2=d*sin((a+b).
Je reviens aux axes initiaux : x2=u2+x0, y2=v2+y0

Après rotation de pi/3 autour de G, les coordonnées du triangle rectangle (0,0)-(0,3)-(3,4) deviennent
(2.15,-1.07)-(3.65,1.53)-(0.19,3.53)
Aucune déformation n'est décelable.