IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Calculer les coordonnées 3D d'un point à partir de distances d'autres points


Sujet :

Mathématiques

  1. #21
    Membre confirmé
    Profil pro
    Développeur informatique
    Inscrit en
    Mai 2012
    Messages
    163
    Détails du profil
    Informations personnelles :
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mai 2012
    Messages : 163
    Points : 624
    Points
    624
    Par défaut
    Je ne comprends pas trop la longueur de cette discussion. Le problème peut se résoudre de différentes façons mais classiquement, on utiliserait effectivement un moindre carré non-linéaire (genre levenberg-marquardt) pour minimiser l'erreur de distance (le fameux Formule mathématique). Le calcul de la dérivée n'est pas compliqué mais il n'est même pas nécessaire car les solveurs modernes font de "l'automatic differentiation". Par exemple, avec ceres-solver :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include <ceres/ceres.h>
     
    std::vector<std::array<double,4>> data = {
        {{ 1,  2, 10, 146}},
        {{ 7, -2,  0,  66}},
        {{14,  4, -2,  49}},
        {{ 2,  5,  8,  86}}
    };
     
    struct MyResidual {
        const double x_, y_, z_, d2_;
     
        MyResidual(double x, double y, double z, double d2) : x_(x), y_(y), z_(z), d2_(d2) {}
     
        template <typename T> 
            bool operator()(const T* const x, const T* const y, const T* const z, T* residual) const {
                T dx = *x - T(x_);
                T dy = *y - T(y_);
                T dz = *z - T(z_);
                T d2 = T(d2_);
                residual[0] = d2 - dx*dx - dy*dy - dz*dz;
                return true;
            }
    };
     
    int main() {
        double x = 0.0, y = 0.0, z = 0.0;
        ceres::Problem problem;
        for (const auto & a : data) {
            problem.AddResidualBlock(
                    new ceres::AutoDiffCostFunction<MyResidual, 1, 1, 1, 1>(
                        new MyResidual(a[0], a[1], a[2], a[3])),
                    NULL, &x, &y, &z);
        }
        ceres::Solver::Options options;
        ceres::Solver::Summary summary;
        Solve(options, &problem, &summary);
        std::cout << summary.BriefReport() << std::endl;
        std::cout << "Final: " << x << " " << y << " " << z << std::endl;
        return 0;
    }

  2. #22
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2017
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2017
    Messages : 12
    Points : 1
    Points
    1
    Par défaut
    Et bien, je vois que ma question intéresse
    Et donc le sujet me semble en final encore plus "compliqué" à résoudre que je ne le croyais...
    mais je peux préciser que le point recherché se situe obligatoirement au "centre" des 4 repères, qui sont disposés aux 4 coins du volume d'évolution.
    Que le cas "limite" : le point P se trouvant sur le même axe que 2 points latéraux, donc le même plan est à exclure.

    Mais encore merci pour toutes ces avancées, néanmoins je me permet de rappeler mon objectif final qui est de pouvoir coder simplement ,
    si possible sans librairie mathématiques le calcul des coordonnées X,Y,Z du point de mesure.

  3. #23
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Bonsoir,

    Citation Envoyé par BlueSky77 Voir le message
    Et bien, je vois que ma question intéresse.
    Et donc le sujet me semble en final encore plus "compliqué" à résoudre que je ne le croyais...
    C'est peu de le dire ... C'est un problème original, que pour ma part je n'avais jamais rencontré.
    Le début des calculs n'est pas très difficile, mais débouche sur un système de 3 équations en (x, y, z) de degré 3, dont je n'ai pu tirer jusqu'à présent une suite vectorielle convergente, qui aurait conduit à la solution.

    Citation Envoyé par BlueSky77 Voir le message
    ... mon objectif final qui est de pouvoir coder simplement, si possible sans librairie mathématiques le calcul des coordonnées X,Y,Z du point de mesure.
    Là se trouve précisément la question délicate: qu'appelles-tu un code simple ? Si cela peut te rassurer, le programme est lourd, mais testable sur calculatrice.
    Je posterai les résultats dès que possible ... je suis assez pris en ce moment.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  4. #24
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2017
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2017
    Messages : 12
    Points : 1
    Points
    1
    Par défaut
    Merci de votre soutien ;-)

    coder simplement, dans le sens de ne pas être sur un algorithme trop récursif qui génère des problèmes de dépassement de pile ou autres effets de bord,
    et qui ne demande pas non plus 3 jours d'itération

    Je précise que la résolution reste obligatoirement une approche de la position et pas la solution mathématique exacte car les précisions des mesures en feraient surement une impossibilité de résolution

  5. #25
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Citation Envoyé par BlueSky77 Voir le message
    ... Je précise que la résolution reste obligatoire une approche de la position ...
    Il y a sous cet aspect une solution immédiate et classique, que j'ai déjà indiquée (#14), mais dont je ne suis pas sûr de l'efficacité:

    Une variante ... consisterait à résoudre séparément 3 équations, pour obtenir quatre solutions:
    système (2, 3, 4): P1 ;
    système (1, 3, 4): P2 ;
    système (1, 2, 4): P3 ;
    système (1, 2, 3): P4 .
    Le calcul du barycentre (G), des nouvelles distances (d'i = AiG) et de l'écart moyen par rapport à leur valeur initiale pourrait conduire à un procédé itératif, mais qui me paraît lourd et bien incertain.
    Le tétraèdre obtenu (P1P2P3P4) s'incrirait dans un pavé défini par les inéquations:
    Xmin <= x <= Xmax ; Ymin <= y <= Ymax ; Zmin <= z <= Zmax ,
    avec Xmin = Min(X1, X2, X3, X4) , Xmax = Max(X1, X2, X3, X4) , etc ...
    Compte tenu du comportement des systèmes linéaires (voir les discussions précédentes), il se pourrait que le volume du solide obtenu ne soit pas négligeable vis-à-vis de celui du tétraèdre (ABCD), et le résultat finalement bien décevant.

    Citation Envoyé par BlueSky77 Voir le message
    ... coder simplement, dans le sens de ne pas être sur un algorithme trop récursif qui génère des problèmes de dépassement de pile ou autres effets de bord,
    et qui ne demande pas non plus 3 jours d'itération
    Il n'y a pas de récursivité, et dès que la suite convergente est débusquée (encore faut-il lever le lièvre !), l'itération s'arrête rapidement. Mais il y a malheureusement un os: les suites trouvées sont toutes divergentes ...


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #26
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Partir d'une expression plus générale de la somme à minimiser permet de préserver d'éventuelles issues intéressantes, pour le calcul.

    Étant donné:
    # un espace affine euclidien de dimension (3), orienté par le repère orthonormé (Oxyz),
    # quatre points fixes (A1 ... A4) non coplanaires, et associés à quatre distances non-nulles (d1 ... d4) ,
    on envisage la somme définie à partir d'un autre point quelconque M(x, y, z), notée: U = Si=14(AiM2*n - di2*n)2 .
    Le carré d'une norme s'exprimant simplement par un produit scalaire: AiM2 = AiMAiM = AiM2 ,
    l'expression de la somme précédente devient: U = Si=14((AiM2)n - di2*n)2
    et sa différentiation permet d'exprimer une petite variation de (U) consécutive au déplacement élémentaire (MM' = dOM) du point considéré:

    dU = Si=14(2*((AiM2)n - di2*n)*n*(AiM2)(n-1)*2*(AiM│dOM)) = (4*n)*(Si=14((AiM2*n - di2*n)*AiM(2*n-2)*AiM ))│dOM

    Au voisinage d'un extremum, (dU) est nul que soit (dOM), ce qui implique: Si=14((AiM2*n - di2*n)*AiM(2*n-2)*AiM )= 0 (vecteur nul).

    Il vient finalement: Si=14(AiM(4*n-2)*AiM ) = Si=14((di2*n)*AiM(2*n-2)*AiM) .

    Il est désormais possible d'envisager deux cas particuliers induisant une relative simplification:

    1) n = 1, ce qui conduit à: Si=14(AiM2*AiM ) = Si=14(di2*AiM) (résultat 1) ;

    2) n = 1 / 2, ce qui donne alors: Si=14(AiM ) = Si=14((di / AiM)*AiM) (résultat 2) .

    Une pause s'avère prudente, le temps de relire le texte. Sa mise en forme est vraiment ch pénible.
    Les ennuis ne sont pas terminés - te voilà prévenu .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #27
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Je me suis demandé pourquoi Prof a supprimé ses messages. Une hypothèse était : la solution proposée ne marche pas.
    J'ai donc testé la méthode, et elle marche très bien. Je redonne donc cette méthode.

    On a 4 mesures, donc 4 équations du type :
    Eq1 : (x-x1)² + (y-y1)² + (z-z1)² = d1² et idem pour les balises 2, 3 et 4.

    Quand on a 2 égalités a=b et c=d, on peut soustraire, et ça donne a-c=b-d.

    Ici, je vais faire eq1-eq4, eq2-eq4 et eq3-eq4. :

    (x-x1)² - (x-x4)² + (y-y1)² - (y-y4)² + (z-z1)² - (z-z4)² = d1² - d4²
    (x-x2)² - (x-x4)² + (y-y2)² - (y-y4)² + (z-z2)² - (z-z4)² = d2² - d4²
    (x-x3)² - (x-x4)² + (y-y3)² - (y-y4)² + (z-z3)² - (z-z4)² = d3² - d4²

    Les termes de degré 2 disparaissent, et on obtient un système linéaire à 3 équations et 3 inconnues. C'est très simple à résoudre, c'est assez bien documenté si on ne connait pas la méthode.
    Les 3 équations sont :
    -2(x1-x4) x - 2(y1-y4) y - 2(z1-z4) z = d1²-d4² + x4²-x1² + y4²-y1² + z4²-z1²
    -2(x2-x4) x - 2(y2-y4) y - 2(z2-z4) z = d2²-d4² + x4²-x2² + y4²-y2² + z4²-z2²
    -2(x3-x4) x - 2(y3-y4) y - 2(z3-z4) z = d3²-d4² + x4²-x3² + y4²-y3² + z4²-z3²

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    //  J'ajoute des nouvelles variables pour simplifier les notations ----------------
    x01 = -2*(x1-x4) ; y01 = -2*(y1-y4) ; z01 = -2*(z1-z4)
    x02 = -2*(x2-x4) ; y02 = -2*(y2-y4) ; z02 = -2*(z2-z4)
    x03 = -2*(x3-x4) ; y03 = -2*(y3-y4) ; z03 = -2*(z3-z4)
     
    // Calcul du déterminant :
    DET = x01*y02*z03 + y01*z02*x03 + z01*x02*y03 - x01*z02*y03 - y01*x02*z03 - z01*y02*x03 
     
    si DET = 0 alors 
        // Erreur   le système n'a pas de solution, ou a une infinité de solution 
        // sur quelques milliers de tests, ce n'est jamais arrivé. 
    fin
     
    // Autres variables nouvelles pour simplifier les notations : 
    r1 = d1*d1 - d4*d4  +  x4*x4 - x1*x1  +  y4*y4 - y1*y1  +  z4*z4 - z1*z1 
    r2 = d2*d2 - d4*d4  +  x4*x4 - x2*x2  +  y4*y4 - y2*y2  +  z4*z4 - z2*z2 
    r3 = d3*d3 - d4*d4  +  x4*x4 - x3*x3  +  y4*y4 - y3*y3  +  z4*z4 - z3*z3
     
    // et enfin le calcul proprement dit du point solution :
    pt.x = ( r1*y02*z03 + y01*z02*r3 + z01*r2*y03 - r1*z02*y03 - r2*y01*z03 - r3*y02*z01 ) / DET
    pt.y = ( x01*r2*z03 + r1*z02*x03 + z01*x02*r3 - x01*r3*z02 - r1*x02*z03 - z01*r2*x03 ) / DET
    pt.z = ( x01*y02*r3 + y01*r2*x03 + r1*x02*y03 - x01*r2*y03 - y01*x02*r3 - r1*y02*x03 ) / DET
    En faisant cela, on fait une impasse. On avait 4 équations, et d'une certaine façon, on n'en utilise que 3. Mais dans les faits, ça marche très bien.

    J'ai mis les balises aux 4 coins d'un cube (0,0,0) (0,1,1) (1,0,1) (1,1,0) et le point solution à l'intérieur de ce cube.
    Si les mesures sont parfaites, le point trouvé coïncide parfaitement avec le point réel. Si les mesures sont arrondies au millième, alors le point trouvé est proche du point cherché, avec un écart de l'ordre du millième.

    Si le point cherché est à l'extérieur du cube, et loin du cube, alors la méthode peut donner un résultat un peu décalé par rapport à la réalité. Un arrondi au millième dans les mesures (donc 0.5 millièmes maximum d'écart) peut provoquer une erreur 5 ou 10 fois plus élevée dans le résultat. Mais même là, ça reste acceptable.

    @Zobal
    Tu dis que classiquement, on peut utiliser un levenberg-marquardt.
    Soit ! C'est peut-être classique pour toi, mais je doute que ça parle à BlueSky77. En tout cas, moi, ça ne me parle pas du tout.
    Et (je joue un peu sur les mots...) si BlueSky77 voulait une boite noire pour résoudre son problème, il aurait posté sa question sur le forum algorithmes. En postant dans le forum mathématiques, il demande une approche mathématique.

    Ceci dit, l'aide est utile, j'ai consulté ce que c'était ce levenberg-marquardt.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  8. #28
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2017
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2017
    Messages : 12
    Points : 1
    Points
    1
    Par défaut
    En fait, certes les maths ne sont pas mon "dada", dans le sens que mon niveau ne me permet pas d'empiler certains raisonnements ...
    c'est une question de connaissances, de maîtrise et d'usage
    Mais en fait, j'ai peut-être posté par erreur dans la mauvaise section, bien qu'intitulé "Algorithme & Mathématiques"

    Il m'a apparu après plusieurs articles, avant de poster, que si le problème était bien exposé alors
    il serait plus facilement orienté vers une résolution prenant l'aspect concret (le codage) tout en s'appuyant sur la "véracité" des mathématiques appliquées
    puisque les mesures restent entachées de tolérance/imprécision.

    Si je considère un cas concret mon point de mesure n'est jamais plus éloigné de 10 m d'une balise repère, dans un parallélépipède de 20 m x 20 m x 8 m.
    Et si la résolution donne une position avec une précision de 0,2m = cela est acceptable
    Les mesures ayant une précision de 0,1m

  9. #29
    Membre confirmé
    Homme Profil pro
    .
    Inscrit en
    Juin 2002
    Messages
    239
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : .
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2002
    Messages : 239
    Points : 567
    Points
    567
    Par défaut
    ( texte supprimé par l'auteur )

  10. #30
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Citation Envoyé par tbc92 Voir le message
    ... Une hypothèse était : la solution proposée ne marche pas.
    J'ai donc testé la méthode, et elle marche très bien. Je redonne donc cette méthode.
    On a 4 mesures, donc 4 équations du type :
    Eq1 : (x-x1)² + (y-y1)² + (z-z1)² = d1² et idem pour les balises 2, 3 et 4 ...
    C'est faux si l'on combine ensemble les 4 équations - ce que tu sembles faire, puisque les quatre indices se retrouvent dans le développement de ton calcul.
    C'est envisageable si l'on procède à la résolution séparée de trois d'entre elles seulement, comme je viens de le rappeler (#24), et il faut chercher les quatre solutions, pour respecter la symétrie des données ... tu as toi-même perçu l'imperfection de ta démarche:
    Citation Envoyé par tbc92 Voir le message
    ... En faisant cela, on fait une impasse. On avait 4 équations, et d'une certaine façon, on n'en utilise que 3 ...
    Je n'ai pas abordé la résolution proposée, mais je crois qu'il n'apparaît pas dans ce cas de déterminant d'ordre 3: au moins une difficulté évitée.

    Citation Envoyé par tbc92 Voir le message
    ... Je me suis demandé pourquoi Prof a supprimé ses messages ...
    C'est regrettable, en effet, parce que l'argumentation était claire, et la controverse complète permettait de mieux discerner le piège calculatoire (qui semble toujours aussi efficace).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #31
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2017
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2017
    Messages : 12
    Points : 1
    Points
    1
    Par défaut


    Euh... moi je ne souhaitais pas créer un conflit virtuel, juste poser un problème concret et essayer d'en coder une solution efficace...

    Il est évident (pour moi) qu'aujourd'hui, la société tente de proposer au plus grand nombre, qu'il n'est pas dans la capacité d'entreprendre, de réfléchir, d'innover, car d'autres sont meilleurs et donc il faut leur laisser la place,
    laisser d'autres chercher des solutions et se satisfaire d'être un utilisateur, pour ma part, ma curiosité, m'amène souvent à étudier des solutions à des situations que je rencontre personnellement et professionnellement,
    afin d'apporter une réponse réaliste (prenant en compte les hypothèses de départ), sans vouloir refaire le monde, la vie n'est qu'éternel recommencement, avec un environnement et des hypothèses de départ différents...
    ce qui permet des inventions et évolutions quasi-permanentes, un exemple ?
    https://flyboard.com/news/post/the-n...-flyboard-air/

    Merci pour vos contributions à ma question

  12. #32
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    @Prof
    J'aimerais te contacter par message privé, mais ta messagerie est fermée.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  13. #33
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 410
    Points : 5 801
    Points
    5 801
    Par défaut
    bonsoir,

    je dis des bêtises (souvent), n'étant pas super matheux mais plutôt informaticien
    ce qu'il recherche ne revient pas a chercher le centre d’équilibre de la forme défini par les axe des sphères ?
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  14. #34
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Non: il s'agit de la recherche d'un point qui, pour faire court, comporte une coordonnée de trop, et dont la localisation ne relève pas d'une simple résolution d'équations.
    Il n'existe aucun point du domaine vérifiant simultanément, et d'une manière rigoureuse, les relations
    A1M = d1 ; A2M = d2 ; A3M = d3 ; A4M = d4 ;
    on peut seulement localiser un point (ou le centre d'un petit domaine) où la somme des carrés des écarts est minimale (ou inférieure à un faible seuil).

    Cette propriété, sans doute appréciée pour la sécurisation qu'elle apporte dans la localisation spatiale des objets, a été immédiatement perçue par des participants; elle peine pourtant à se concrétiser en raison de quelques difficultés de calcul, et du trouble manifeste produit par des équations cartésiennes en surnombre.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #35
    Membre confirmé
    Profil pro
    Développeur informatique
    Inscrit en
    Mai 2012
    Messages
    163
    Détails du profil
    Informations personnelles :
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mai 2012
    Messages : 163
    Points : 624
    Points
    624
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Cette propriété, sans doute appréciée pour la sécurisation qu'elle apporte dans la localisation spatiale des objets, a été immédiatement perçue par des participants; elle peine pourtant à se concrétiser en raison de quelques difficultés de calcul, et du trouble manifeste produit par des équations cartésiennes en surnombre.
    Heu non. C'est un problème de minimisation super classique. J'ai déjà donné une solution en C++, et en voici une autre en octave ainsi que quelques liens, au cas où ce ne serait pas encore assez concret...

    https://fr.wikipedia.org/wiki/Moindr...lin%C3%A9aires
    http://ceres-solver.org/
    https://octave.sourceforge.io/optim/...on/leasqr.html

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    pkg load optim
     
    % fonction qui calcule le vecteur des distances a partir de la matrice des points de reference et du vecteur des parametres
    function d = dist_func(refs, params)
        M = refs - repmat(params', rows(refs), 1);
        d = diag(M * M');
    end
     
    % points de reference
    x = [ 1,  2, 10,   % p1
          7, -2,  0,   % p2
         14,  4, -2,   % p3
          2,  5,  8];  % p4
     
    % distances par rapport au point cherche
    y = [146,   % d1
          66,   % d2
          49,   % d3
          86];  % d4
    y = y+randn(size(y))*0.1; % ajoute du bruit, pour simuler le bruit de mesure
     
    % vecteur de parametres initial (le point qu'on cherche a determiner)
    params0 = [0, 0, 0];
     
    [f, params, cvg, iter, corp, covp] = leasqr(x, y, params0, "dist_func");
    params

  16. #36
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 410
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 410
    Points : 5 801
    Points
    5 801
    Par défaut
    salut

    en relisant la demande originel je comprend effectivement mon erreur
    la demande originel est je cite
    Je souhaite calculer la position d'un point P(x,y,z) à partir des distances que le sépare de 4 autres points A(x1,y1,z1), B(x2,y2,z2), C(x3,y3,z3), D(x4,y4,z4).

    Pour imager (si besoin), imaginez-vous avec un télémètre laser dans une pièce,
    dans laquelle les points A,B,C,D sont des réflecteurs, que vous pointiez chaque point et relevez chaque distance mesurée:
    P-A = d1,
    P-B = d2,
    P-C = d3,
    P-D = d4,
    en prenant le problème à l'envers cela veut dire que les distances correspondent au rayon de la sphère de centre P non ?
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  17. #37
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Bonjour,

    Citation Envoyé par anapurna Voir le message
    ... en prenant le problème à l'envers cela veut dire que les distances correspondent au rayon de la sphère de centre P non ?
    Les distances correspondent aux rayons des sphères de centre P et passant par (A, B, C, D).

    S'il est très facile, à partir d'un point M(x, y, z), de calculer les distances (D1, ... ,D4), il est par contre beaucoup plus difficile de remonter de ces dernières au point correspondant ... et cela n'est généralement possible qu'au prix de petits acomodements numériques.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  18. #38
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Fin de calcul (suite du texte #25)
    J'ai dû consacrer pas mal de temps à des essais de programmation, afin de tester l'utilité des résultats obtenus, dont la relative simplicité résulte de la disparition des distances (AiM) dans l'un des membres de l'équation.

    Le but était de parvenir à une suite vectorielle récurrente du type OMk+1 = F(OMk), permettant d'approcher au mieux - au terme d'un nombre raisonnable d'étapes - la position limite correspondant au minimum de la grandeur (U) précédemment définie (#25).
    J'ai pris pour position initiale le barycentre (M0) des 4 sommets du tétraèdre, défini par la combinaison linéaire:
    (Si=14(di-1))*OM0 = Si=14(di-1*OAi)
    dans laquelle les coefficients de pondération sont inversement proportionnels à la distance correspondante.
    Le point de départ se trouve donc à l'intérieur du tétraèdre (A1 ... A4), et vraisemblablement peu éloigné de la limite recherchée.

    Par ailleurs, l'expression des positions successives (OMk) se simplifie un peu si l'on se réfère à un point particulier, dont la définition apparaît spontanément lors du développement des calculs.

    1) Si=14(AiM2*AiM ) = Si=14(di2*AiM) (résultat 1): il vient en posant à droite AiM = AiH + HM = AiH + HO + OM (relation de Chasles)

    Si=14(AiM2*AiM ) = Si=14(di2*AiH) + Si=14(di2*HM) = (Si=14(di2))*(HO + OM) si l'on convient de prendre pour (H) le barycentre des 4 sommets pondérés par les carrés des distances associées, et vérifiant la relation: Si=14(di2*AiH) = 0 (vecteur nul);
    il vient alors en posant S2 = (Si=14(di2)) : OM = OH + (S2-1)*Si=14(AiM2*AiM ) ,
    dont la solution est la limite (s'il en existe une) de la suite: OMk+1 = OH + (S2-1)*Si=14(AiMk2*AiMk) .
    Malheureusement, cette suite diverge, et très rapidement ... Le résultat envisagé ne se prête donc pas à un procédé itératif.

    # Une compensation toutefois: la relation obtenue, mise sous la forme: Si=14((AiM2 - di2)*AiM ) = 0
    (la plus simple et la plus rapidement calculable de toutes celles que l'on peut rencontrer)
    devient équivalente à Si=14((AiM2 - di2)*AiM )║ = 0
    et peut ainsi faire l'objet d'une recherche de minimum nul sur un domaine tridimensionnel; ce procédé, bien que jamais évoqué ici, ne pose pas de difficulté algorithmique particulière.

    2) Si=14(AiM) = Si=14((di / AiM)*AiM) (résultat 2): en introduisant à gauche l'isobarycentre (G) des sommets du tétraèdre, dont la position vérifie
    Si=14(AiG) = 0 , il vient: AiM = AiG + GM = AiG + GO + OM (relation de Chasles) et
    Si=14(AiG + GM) = Si=14(AiG) + Si=14(GO + OM) = 0 + 4*(GO + OM) = Si=14((di / AiM)*AiM) ;
    on obtient dans ce cas: OM = OG + (4-1)*Si=14((di / AiM)*AiM) ,
    résultat qui devient la relation de récurrence: OMk+1 = OG + (4-1)*Si=14((di / AiMk)*AiMk) .
    Cette fois, la suite converge, et permet d'accéder à la limite recherchée.

    Exemples: les calculs suivants se réfèrent à un tétraèdre asymétrique:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    A         B        C         D         G
    0        99       83        10        48
    0        10       95        99        51
    0        90       15        95        50
    Les distances séparant le point M(30, 40, 50) des 4 sommets valent respectivement:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    Sqrt(5000) = 70.7107
    Sqrt(7261) = 85.2115
    Sqrt(7059) = 84.0179
    Sqrt(5906) = 76.8505
    En partant des 4 valeurs précédentes, le programme précédemment décrit donne au bout de 56 itérations,
    dont l'arrêt découle de la condition ║OMk+1 - OMk║ < 10-8 , les résultats suivants:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    M                        Di
    29.999982 = 30.0000      70.710686 = 70.7107      Somme (Ei<sup>2</sup>) = 3.82E-10      Nit = 56
    39.999985 = 40.0000      85.211494 = 85.2115
    50.000035 = 50.0000      84.017891 = 84.0179
                             76.850491 = 76.8505
    On retrouve les valeurs initiales, aux écarts résiduels près: l'algorithme permet effectivement de remonter du quadruplet des distances au point correspondant.
    Si l'on choisit maintenant des valeurs différentes (toutefois proches des précédentes, pour s'assurer de la vraisemblance du résultat), on obtient par la même condition d'arrêt:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    Di°     M            Di           
    71      30.2461      70.8721      Somme (Ei<sup>2</sup>) = 3.56E-2      Nit = 50
    85      39.9223      84.9181
    84      50.1421      83.9732
    77                   76.8915
    @ BlueSky77 Tu devrais trouver ton compte dans tout ce qui précède, pour la rédaction de ton code.
    La vidéo (flyboard-air) était impressionnante.

    @ zobal: il y a peut-être eu un malentendu
    wiwaxia
    Cette propriété ... peine pourtant à se concrétiser en raison de quelques difficultés de calcul ....

    Heu non. C'est un problème de minimisation super classique.
    Je parlais des échanges sur le sujet.
    Tu as donné deux liens intéressants, notamment le dernier (Wikipédia). J'y ai trouvé quelques idées que je pressentais dans un calcul mené au flair, et la motivation pour terminer ce programme qui traînait un peu.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  19. #39
    Nouveau Candidat au Club
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2017
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mai 2017
    Messages : 12
    Points : 1
    Points
    1
    Par défaut
    Merci à tous,
    J'ai dû traiter d'autres urgences, mais je vais essayer de tout comprendre de ce dernier message de wiwaxia
    Si avec tout cela je ne m'en sort pas alors.... je vais aller faire un tour de Fly-Air

    Et évidemment je reviens vous donner ma solution codée

  20. #40
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Calculer les coordonnées 3D d'un point à partir de distances d'autres points
    Bonjour,

    J'ai regardé d'un peu plus près ce que donnait la recherche du zéro dans le cas de la norme du vecteur V = Grad(U(x, y, z)), notamment dans le cas le plus simple (correspondant à n = 1/2): ║Si=14(1 - di/AiM)AiM║ = 0 .
    Tant que l'on reste à l'intérieur du tétraèdre, et qu'interviennent des distances inférieures à la plus grande de ses dimensions, la suite des points successifs (OM = (x, y, z)) converge rapidement (en 130 à 150 étapes) vers une limite (OL = (xL, yL, zL)) indépendante de la position initiale.
    Par contre il n'en est plus de même pour des distances plus importantes: le lancement du programme peut conduire à des résultats divers et peu prévisibles, dépendant de l'endroit où l'exploration a commencé.
    La fonction en cause U(x, y, z) présente alors des variations de complexité croissante: on peut trouver plusieurs minimums secondaires, ainsi que des points singuliers vérifiant la même condition (║V║ = 0) .

    Il vaut donc mieux renoncer à ce procédé ... ce qui n'est pas gênant, puisque la relation de récurrence signalée dans le même message (#38):
    OMk+1 = OG + (4-1)*Si=14((di / AiMk)*AiMk)
    se révèle efficace sur tout le domaine du pavé circonscrit au tétraèdre - c'est bien le moins que l'on puisse exiger !

    ■ La régression à un espace à deux dimensions permet de comprendre ce qui se passe; l'énoncé devient dans ce cas:
    localiser dans le plan d'un triangle (A1A2A3) le point (M) séparé des 3 sommets par des distances se rapprochant au mieux de 3 valeurs données (d1, d2, d3).

    La fonction dont il faut rechercher le minimum ne comporte plus que 3 termes: U = Si=13(di - AiM)2
    et la relation de récurrence devient désormais: OMk+1 = OG + (3-1)*Si=13((di / AiMk)*AiMk) .
    La figure y est définie sous forme du tableau:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    CONST Triangle: Lst3V = ((0.35, 0.35), (0.65, 0.35), (0.45, 0.65));
    dans un programme qui trace sur un domaine ( 0 <= x <= 1 ; 0 <= y <= 1 ) débordant largement le triangle,
    les courbes de niveau (U(x,y) = Cte), ainsi que le segment (GL) joignant l'isobarycentre au point limite (L) atteint par la relation de récurrence.
    a) pour des distances faibles (0.2000 , 0.2500 , 0.1000), inférieures à la moyenne des arêtes, les contours obtenus sont simples (un seul minimum) et pratiquement inchangés lorsque l'on réinjecte dans le programme les valeurs limites obtenues (0.2128 , 0.2618 , 0.1191), lesquelles redonnent les mêmes résultats:

    Nom : D=2000_2500_1000_444x444.png
Affichages : 348
Taille : 111,1 Ko _ Nom : D=2128_2618_1191_444x444.png
Affichages : 405
Taille : 111,7 Ko

    b) pour de plus fortes distances (0.5052 , 0.4652 , 0.4252) dépassant le seuil précédent, l'allure de la surface d'équation z = U(x, y) s'est nettement compliquée (deux minimums secondaires en plus du minimum absolu, et 5 cols à plan tangent horizontal !): on comprend dans ce cas l'échec du procédé recherchant les zéros de ║Grad(U)║ .
    Le segment (GL) pointe toujours le minimum absolu recherché; la réinjection des nouvelles valeurs obtenues (0.5989 , 0.4129 , 0.3722) conserve le point limite (L) mais simplifie toujours les courbes de niveau: on ne trouve plus qu'un seul minimum, et un col.

    Nom : D=5052_4652_4252_444x444.png
Affichages : 350
Taille : 135,1 Ko _ Nom : D=5989_4129_3722_444x444.png
Affichages : 371
Taille : 131,4 Ko

    Remarquer l'efficacité de la relation de récurrence.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Réponses: 8
    Dernier message: 26/01/2014, 14h06
  2. Calculer les coordonnées d'un point en rotation elliptique
    Par MisterG dans le forum Mathématiques
    Réponses: 4
    Dernier message: 03/01/2013, 15h19
  3. Réponses: 3
    Dernier message: 11/06/2009, 10h44
  4. Réponses: 5
    Dernier message: 25/04/2008, 16h59
  5. Calculer les coordonnées de la souris en 3D ?
    Par supergrey dans le forum DirectX
    Réponses: 3
    Dernier message: 26/08/2006, 22h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo