Créer un objet 3D à partir des distances.

[Dlzlogic]

Bonjour,
Il y a un joli problème qui a été posé il y un peu plus de deux ans et qui semble avoir été évoqué dernièrement.
Soit un certain nombre d'objets que l'on assimile à des points.
On connait des distances entre ces objets. C'est à dire qu'on connait certaines distances, mais pas toutes. Par distance, il faut comprendre une liaison assimilable à une distance.
On souhaite construire un objet 3D tel que les distances entre les points soient respectées le mieux possible.
Par exemple, si on a 4 objets et 6 distances, il s'agit d'un tétraèdre et s'il n'y a pas incompatibilité, il y a une solution unique. S'il y a incompatibilité certaines distances seront légèrement modifiées, dans la mesure du possible, pour obtenir un objet satisfaisant.

Bonne journée.
-----

[invitebd98b571]

Bonjour,

On connait des distances entre ces objets.

Chaque distance se traduit par une équation polynomiale de degré 2.

s'il n'y a pas incompatibilité, il y a une solution unique. S'il y a incompatibilité certaines distances seront légèrement modifiées, dans la mesure du possible, pour obtenir un objet satisfaisant.

Bien que le mot "satisfaisant" ne soit pas défini mathématiquement dans l'énoncé, on voit bien que tout le problème réside simplement à résoudre un système d'équations de degré 2, et ce que tout logiciel de calcul peut faire (et dans le cas d'une incompatibilité, j'imagine qu'on pourrait utiliser les moindres carrés pour obtenir une solution "satisfaisante").

[Dlzlogic]

Bonjour,
Avant de trouver les formules ou fonctions ou méthodes de calcul pour trouver le résultat définitif, il me parait indispensable d'étudier la méthode pour résoudre ce problème, c'est à dire, en gros, écrire l'algorithme. Si la question posée avait été d'ordre numérique, je l'aurais posée dans le forum mathématique. Ici, il s'agit d'informatique. Le but final, mais non exprimé, étant d'avoir une visualisation de l'objet ainsi créé.

[invitebd98b571]

Avant de trouver les formules ou fonctions ou méthodes de calcul pour trouver le résultat définitif, il me parait indispensable d'étudier la méthode pour résoudre ce problème, c'est à dire, en gros, écrire l'algorithme.

Avant de se lancer dans l'écriture d'un algorithme répondant au problème, il faudrait avoir des informations importantes sur la situation, comme celles du nombre de points (une dizaine, une centaine, des milliers) ?
Un exemple peut-être ?

Si la question posée avait été d'ordre numérique, je l'aurais posée dans le forum mathématique. Ici, il s'agit d'informatique. Le but final, mais non exprimé, étant d'avoir une visualisation de l'objet ainsi créé.

Ok, c'est une question d'informatique et pas d'ordre numérique (c'est pour cela qu'on y parle de distances, par exemple). C'est une sorte de visualisation géométrique, sans calcul de coordonnées ?

[A voir en vidéo sur Futura]

[Dlzlogic]

Concernant le nombre de points, ce n'est pas précisé, en tout cas par moi. D'ailleurs, je ne vois pas en quoi c'est important à savoir, sachant que plus il y en aura, plus le temps de traitement sera long. J'ai fait mes essais avec une vingtaine de points. A toi de te faire un jeu d'essai.
Naturellement rien n'impose de calculer des coordonnées, mais il me semble que c'est le meilleur moyen de créer un objet 3D et de le visualiser. Si tu connais un autre moyen, c'est pas un problème.

[invitebd98b571]

Concernant le nombre de points, ce n'est pas précisé, en tout cas par moi. D'ailleurs, je ne vois pas en quoi c'est important à savoir, sachant que plus il y en aura, plus le temps de traitement sera long.

Ben au contraire, la taille des systèmes d'équations a une influence sur les méthodes de résolution. C'est ce qu'on appelle le calcul de complexité... en informatique !
Certains algorithmes sont efficaces avec peu d'équations, mais explosent quand le nombres d'équations augmentent. D'autres algorithmes, plus compliqués, sont utiles quand le nombre d'équations est élevé. Il y a aussi la "densité" des équations : ici, les équations sont "creuses" car elles ne mettent en jeu que 6 inconnues à la fois, quel que soit le nombre d'équations : certains algorithmes tirent avantage de cette particularité.
Bref, faire de l'algorithmique avancé, c'est pas de l'amateurisme : il faut déjà bien spécifier le problème... A moins de se contenter d'un algo naïf avec quelques points, et dans ce cas, un tableur peut faire l'affaire.

J'ai fait mes essais avec une vingtaine de points. A toi de te faire un jeu d'essai.

En plus de compléter l'énoncé, il faut aussi se faire soi-même des exemples. Ben...

Naturellement rien n'impose de calculer des coordonnées, mais il me semble que c'est le meilleur moyen de créer un objet 3D et de le visualiser.

Ainsi, tu admets que le problème peut se traiter de manière numérique, par calcul de coordonnées. Ta remarque << Si la question posée avait été d'ordre numérique >> n'a donc pas lieu d'être !

[Dlzlogic]

Oh, j'ai ouvert ce sujet ni comme défi, ni comme problème à résoudre.
Il s'agit d'un problème théorique qui me parait intéressant. Si des hypothèses comme le nombre de points te paraissent importantes, à toi de fixer les limites et d'écrire différents algorithmes suivant les tranches de nombre de points, si ça te parait nécessaire.
Tu parles de systèmes d'équation, donc tu as un début de résolution.
Bien sûr on peut faire un calcul de complexité, mais c'est pas ça qui va permettre une visualisation.
Quand j'ai fait mon programme, il a bien fallu que je me fasse un générateur de jeux d'essais. Je l'ai fait moi-même, si tu veux je peux te le donner.
J'ai un peu de mal à comprendre cette phrase : "Ainsi, tu admets que le problème peut se traiter de manière numérique, par calcul de coordonnées." J'ai posé le problème avec un énoncé que je considère comme complet, en ce sens que si certaines condition sont à fixer ou tester, c'est pas à moi de le faire. Je l'ai posé dans le forum informatique puisqu'il s'agit d'écrire un algorithme. Il est bien évident qu'une connaissance minimum des mathématiques est nécessaire, mais l'algorithme doit être "complet" c'est à dire qu'il ne doit pas faire appel à des logiciels existants. A titre d'exemple l'opération "inverser la matrice" est inconnue du lecteur (humain) de l'algorithme, puisque l'utilisation de la représentation sous forme de tableau d'une application linéaire est un outil mathématique (tableau noir ou papier/crayon). [Bon, mais si tu y tiens vraiment, comme je me suis fait les modules nécessaires au calcul matriciel, moi, je pourrai comprendre.]

[invitebd98b571]

Tu parles de systèmes d'équation, donc tu as un début de résolution.

en effet, confer le message #2

Bien sûr on peut faire un calcul de complexité, mais c'est pas ça qui va permettre une visualisation.

Si le problème est uniquement un souci de pixels à allumer, en effet, avoir des algorithmes d'une complexité énorme n'a aucune importance.

J'ai posé le problème avec un énoncé que je considère comme complet

je considère également ma réponse message #2 complète.

il s'agit d'écrire un algorithme

ok : (1) on traduit les distances en équations de degré 2 ; (2) on résout le système d'équations ; (3) on allume les pixels des points calculés.
dois-je détailler certains points ?

ne doit pas faire appel à des logiciels existants.

(humour) il faut réinventer la roue ? on fait tous les calculs à la main ? (/humour)

[Dlzlogic]

Bonsoir,
j'ai créé ce fil suite à cette question : http://www.les-mathematiques.net/pho....php?8,1360194
Ce problème a été évoqué il y a deux ans, et les échanges ont tourné court. Il a été de nouveau évoqué et indépendamment de réponse il me parait intéressant sur un plan théorique.
C'était le seul but de mes messages.
[HS] je regrette un peu que ce forum ne soit limité qu'aux question/réponses. Il me parait intéressant d'évoquer d'autres choses. [/HS]