Forum général.hors-sujets hauteur tétraèdre irrégulier et jeu spatial

Posté par pralines le 08 août 2023 à 16:27. Licence CC By‑SA.

Étiquettes :

août

2023

Bonjour à toutes et tous,

je souhaite écrire un programme affichant une carte 3D (pour un jeu qui sort en septembre ;-)
mais ce jeu n'affiche que les distances entre les étoiles donc je cherche à calculer leurs coordonnées

je peux déterminer les coordonnées des 3 premiers points (dans un repère que j'aurai fixé), mais je ne trouve pas la formule pour calculer les coordonnées du 4ème point

j'ai compris que cette formule va donner 2 solutions (2 points de part et d'autre du plan déterminé par les 3 premiers points), mais je peux m'en accommoder

une fois ces 4 premiers points de références calculés, la partie mathématique du problème sera résolue (j'ai trouvé la formules de calcul des coordonnées x,y,z des points suivants à partir des distances avec les 4 premiers points calculés).

j'ai essayé gogole et le duck-duck, mais je ne trouve que des formules de calcul de la hauteur de tétraèdres réguliers (ce qui ne sera jamais mon cas)…

est-ce qu'il y a dans le coin un(e) matheux(se) passionné(e) de jeux spatiaux pour me décrire ce calcul ou pour me mettre sur la piste ?

# Quoi?

Posté par GG (site web personnel) le 08 août 2023 à 16:33. Évalué à 2.

Je ne comprends pas ton problème.

Quelles distances? Entre quoi et quoi?
Pourquoi cette histoire de tétraèdre dans ton cas?

Et si tu as des formules mathématiques que tu as trouvées, complète ton message, ça va aider.

Bon courage

Pourquoi bloquer la publicité et les traqueurs : https://greboca.com/Pourquoi-bloquer-la-publicite-et-les-traqueurs.html
- [^] # Re: Quoi?
  
  Posté par pralines le 08 août 2023 à 16:42. Évalué à 2. Dernière modification le 08 août 2023 à 16:44.
  
  désolé, je suis tellement dans mon truc que je n'ai pas donné beaucoup de contexte…
  
  j'ai la distance en année lumière entre des étoiles, et je cherche à calculer les coordonnées x,y,z de ces étoiles afin d'afficher une carte galactique
  
  j'ai une formule (trop longue pour être écrite ici) qui calcule les coordonnées d'un point à partir des distances avec 4 autres points dont les coordonnées sont connues
  
  ma difficulté est de calculer les coordonnées de ces 4 premiers points (formant un tétraèdre irrégulier) qui vont me servir de référence
  
  pour les coordonnées des 3 premiers points, pas de problème, j'ai ce qu'il faut comme formules trigo
  
  pour le calcul des coordonnées du 4ème point je sèche, d'où l'appel à l'aide
  
  EDIT : c'est un projet perso pour des joueurs
  
  Envoyé depuis mon Archlinux
  - [^] # Re: Quoi?
    
    Posté par pralines le 08 août 2023 à 16:56. Évalué à 1.
    
    EDIT 2 : il semble que je doive chercher du côté du "true range multilateration" dans un espace cartésien à 3 dimensions
    
    Envoyé depuis mon Archlinux
    - [^] # Re: Quoi?
      
      Posté par GG (site web personnel) le 08 août 2023 à 20:00. Évalué à 2.
      
      Peut être que tu auras des pistes sur leur forum…
      https://pioneerspacesim.itch.io/pioneer
      Si ça se trouve, ils ont déjà été confronté à ton problème.
      
      Pourquoi bloquer la publicité et les traqueurs : https://greboca.com/Pourquoi-bloquer-la-publicite-et-les-traqueurs.html
      - [^] # Re: Quoi?
        
        Posté par pralines le 08 août 2023 à 21:10. Évalué à 1. Dernière modification le 08 août 2023 à 21:10.
        
        je ne connaissais pas
        merci
        
        Envoyé depuis mon Archlinux
  - [^] # Re: Quoi?
    
    Posté par Barnabé le 09 août 2023 à 11:05. Évalué à 1.
    
    Ce que tu nous dit, (ou au moins ce que j'en comprend), c'est:
    
    J'ai une formule qui calcule les coordonnées d'un point à partir des distances avec 4 autres points dont les coordonnées sont connues,
    
    je voudrais une formule qui calcule les coordonnées d'un point à partir des distances avec 3 autres points dont les coordonnées sont connues.
    
    Du coup, as tu des infos supplémentaires sur le 4e point qui permettraient de calculer ses coordonnées à partir des distances à 3 autres points ?
    - [^] # Re: Quoi?
      
      Posté par pralines le 09 août 2023 à 11:14. Évalué à 1. Dernière modification le 09 août 2023 à 11:15.
      
      pour le 4ème point (comme pour tous les suivants), je connais uniquement la distance avec les 3 autres points (dont les positions sont connues)
      
      donc, au mieux, le calcul va me donner 2 positions possibles (il faudra que je décide laquelle est la bonne, au dessus ou bien au dessous du plan déterminé par les 3 premiers points)
      
      pour plus de détail, cf ma réponse à un autre commentaire plus bas
      
      edit : je sais qu'il aurait fallu que je poste un schéma pour illustrer tout ça…
      
      Envoyé depuis mon Archlinux
# comprends toujours pas

Posté par Jean-Baptiste Faure le 09 août 2023 à 08:13. Évalué à 4.

Si tu as 4 étoiles A,B,C et D et que tu sais calculer les coordonnées de A, B et C, qu'est-ce qui t'empêche de calculer de la même façon ceux de B, C et D (ou de n'importe quel autre triplet extrait de ce groupe de 4 étoiles) ?
- [^] # Re: comprends toujours pas
  
  Posté par pralines le 09 août 2023 à 10:51. Évalué à 2. Dernière modification le 09 août 2023 à 10:54.
  
  la seule info dont je dispose est la distance entre les étoiles, je dois construire une référence/origine (en partie par des choix, en partie par des calculs)
  
  pour me simplifier le travail, je décide que les 3 premières étoiles sont dans un plan du repère :
  - point 1 en (x=0,y=0)
  - point 2 en (x=0,y=distance avec le point 1)
  - point 3 calculé
  (si je ne me plante pas complètement : arcos() pour calculer les angles à partir des longueurs des arêtes du triangle, puis sin() ou cos(), je sais plus, pour calculer les x,y du point 3
  
  mais la 4ème étoile ne sera jamais dans le même plan que les 3 premières, ce qui implique de calculer en 3D
  
  mais je pense avoir trouvé une formule de calcul de l'intersection de 3 sphères (true range multilateration dans un espace cartésion 3d),
  
  ce calcul va me donner 2 positions possibles pour le point 4 : 1 au dessus du plan des 3 premières étoiles et 1 au dessous de ce plan, il faudra que je décide laquelle est la bonne
  
  ces 4 points calculés vont me servir de référence pour le calcul de tous les points suivants (pour autant que je dispose de leurs distances avec ces 4 positions connues), même méthode, mais avec 4 sphères
  
  enfin, c'est ce que j'espère, ça fait longtemps que je suis sorti de l'école, j'étais vraiment mauvais en maths et en plus je pense qu'une partie de ces calculs n'étaient pas au programme de mon cursus (la trigo oui, mais pas le reste)…
  désolé si ces explications sont confuses (ou pire, erronées), je ne peux pas mieux expliquer ce que je comprends à peine ;-)
  
  Envoyé depuis mon Archlinux
- [^] # Re: comprends toujours pas
  
  Posté par bing le 09 août 2023 à 11:36. Évalué à 4.
  
  De ce que j’ai compris il n’a aucune coordonnée. Seulement les distances entre les étoiles. Il veut construire une carte à partir de ça.
  
  C’est possible mais probablement très compliqué ; j’en étais pas convaincu au départ mais j’ai une piste, qu’il faudrait valider et qui demande un sérieux background en math, plus précisément en algèbre linéaire.
  
  L’idée est d’utiliser quatre étoiles (choisies avec précaution…) qui seront nos points Ces étoiles forment un repère $\mathcal{R}$ d'origine et d'axes les vecteurs $\mathbf{S_0S_i},\ i\in[1,3].$
  
  Par construction $s_{ij} = \delta_{ij}$ est la -ième composante des coordonnées des points . Autrement dit les coordonnées des points dans $\mathcal{R}$ sont (0,0,0), (1,0,0), (0,1,0), (0,0,1).
  
  Facile. :D
  
  L’arnaque c’est que $\mathcal{R}$ n’est pas orthonormé et qu’on peut rien en faire en l’état. Pour poursuivre il faut trouver une métrique . Pour ceux qui ne savent pas ce que c’est : c’est une manière de définir un produit scalaire (et donc une distance), différent de celui que vous avez appris à l’école (qui est le produit scalaire canonique). La métrique se calcule dans le référentiel $\mathcal{R}$ comme un tableau de 3×3 (c’est un tenseur). Le tenseur est symétrique : $g_{ij} = g_{ji}$ .
  
  La diagonale est triviale : $g_{ii} = d(S_0,S_i)^2$ . Où est la distance entre deux points. De manière plus générique : $d(S_i,S_j)^2 = g(\mathbf{S_iS_j},\mathbf{S_iS_j}) = g(S_j-S_i,S_j-S_i)=\sum_{k,l}g_{kl}(s_{jk}-s_{ik})(s_{jl}-s_{il})$ ce qui nous donne un système de 6 équations à 6 inconnues au départ, avec la diagonale triviale, il reste 3 équations à 3 inconnues et vu la simplicité des coordonnées $s_{ij}$ il y a probablement une astuce pour les résoudre analytiquement. Pour bien faire, il faut s’assurer que est bien défini positif (numériquement j’ai peur que ça ne soit pas garanti).
  
  Une fois la métrique acquise, on n’est pas au bout de nos peines…
  
  Il faut trouver un repère orthonormé (au sens de ) ; on utilise l’algorithme de Gram-Schmidt : en partant des vecteurs $\mathbf{S_0S_i}$ et en pensant à bien calculer les projections au moyen de . On aboutit donc à une base vectorielle qui sert à former le repère orthonormé $\mathcal{O}$ d’origine identique à celle de $\mathcal{R}$ . On a trivialement la matrice de passage associée $\mathbf{M}$ , qui est une matrice carré donc chaque colonne est un des vecteurs de la base trouvée.
  
  Pour finir, il va falloir adapter, au moyen de la métrique , la trilatération pour calculer les coordonnées $\mathbf{X}$ d’une étoile quelconque dans le repère $\mathcal{R}$ (visuellement parlant il s’agit non plus de trouver l’intersection de sphères, mais d’ellipsoïdes).
  
  Les coordonnées dans $\mathcal{O}$ s’obtiennent par la multiplication matricielle $\mathbf{MX}$ .
# Intersection de sphères et changement de repère.

Posté par GaMa (site web personnel) le 09 août 2023 à 16:11. Évalué à 6.
Intersection de 3 sphères.

On a donc 3 étoiles A, B, C.

Choisissons un repère que nous arrange bien tel que :
A: (0, 0, 0)
B: (1, 0, 0)
C: (K, L, 0)

Nos trois étoiles sont dans le même plan X/Y et B est alignée sur X

Soit D: (x, y, z)
Si on connais AD, BD, CD (Les distances entre A et D, B et D, …), D est a l'intersection de 3 sphères de centre A, B, C et de rayon AD, BD et CD. Donc:
- x² + y² + z² = AD²
- (x-1)² + y² + z² = BD²
- (x-K)² + (y-L)² + z² = CD²
On trouve facilement que x² - (x-1)² = AD²-BD² => X = (AD²-BD² + 1)/2

On peut "simplifier" les équations en :
- y² + z² = AD² + x² = M (par que ça simplifie les écritures)
- (y-L)² + z² = CD² - (x-K)² = N

Donc que y² - (y-L)² = M - N => y = (M - N + L²)/2L

Et donc que z² = AD² - x² - y².
Donc deux solutions pour z, ce qui est cohérent avec ce qu'on attendait (D est au dessus ou en dessous du plan)

Changement de repère.

"C'est bien gentil les intersections de trois sphères mais mes 3 étoiles connues, elles ont pas ces coordonnées" tu vas me dire.
Et je te répondrais: "On s'en fout, on applique une matrice de changement de repère pour être dans le repère qui nous intéresse (facilite la vie), on résout notre problème, et on applique la matrice inverse pour avoir notre solution dans notre repère d'origine."

Du coup la question, c'est "Mais qu'elle est cette matrice de changement de repère ?".

On va devoir la calculer (mais je vais pas le faire ici, j'ai pas vraiment le temps je t'avoue :)) mais en gros:
- C'est une matrice 4x4
- C'est la composition des transformations élémentaires suivante:
. Translation de -(Ax, Ay, Az) pour se "placer A en zéro"
. Rotation de l'angle AB^X, avec pour axe la normale au plan AB^X => ça va pivoter notre repère pour placer l'étoile B sur l'axe X
. Rotation de l'angle AC^Y, avec pour axe la normale au plan AC^Y (=X) => ça va pivoter notre repère pour placer l'étoile C sur le plan XY
. Un changement d'échelle de 1/AB pour placer B en coordonnée 1 sur X

Je te conseille fortement d'utiliser des lib de transformations matricielles dans ton langage favori, tu n'as probablement pas envie de réimplémenter tout ça.

Matthieu Gautier|irc:starmad
- [^] # Re: Intersection de sphères et changement de repère.
  
  Posté par pralines le 09 août 2023 à 17:25. Évalué à 1. Dernière modification le 09 août 2023 à 17:28.
  
  pour ce qui est du repère, j'avais prévu de faire comme tu dis, mais je vais pouvoir me simplifier grandement le travail car les 4 premières étoiles que je pense pouvoir choisir dans le jeu existent aussi IRL et leur coordonnées sont connues (Sol, Sirius, Tau Ceti, Alpha Centauri), donc pas de changement de repère après coup :-)
  
  merci tout de même pour toutes tes informations
  
  Envoyé depuis mon Archlinux
  - [^] # Re: Intersection de sphères et changement de repère.
    
    Posté par GaMa (site web personnel) le 10 août 2023 à 17:20. Évalué à 2.
    Le changement de repère n'est pas là parce que tu connais pas les coordonnées, il est là pour simplifier les calculs.
    Si tu veux t'en passer tu vas avoir des équations de ce style:
    - (Dx-Ax)² + (Dy-Ay)² + (Dz-Az)² = DA²
    - (Dx-Bx)² + (Dy-By)² + (Dz-Bz)² = DB²
    - (Dx-Cx)² + (Dy-Cy)² + (Dz-Cz)² = DC²
    Et là, à résoudre c'est pas facile du tout.
    
    (Après tu peux faire les opérations changement de répère, résolution, changement de repère inverse sur le papier et trouver les formules finales, que tu appliques après dans ton programme)
    
    Matthieu Gautier|irc:starmad

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.

Intersection de 3 sphères.

Changement de repère.