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

Algorithmes et structures de données Discussion :

Interpolation "linéaire" sur un point dans triangle (3D)


Sujet :

Algorithmes et structures de données

  1. #1
    Vol
    Vol est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 42
    Points : 38
    Points
    38
    Par défaut Interpolation "linéaire" sur un point dans triangle (3D)
    J'ai trois points (P1,P2,P3) en x,y,z qui forment un triangle. Chacun de ces points a une valeur qui lui est accordée. J'ai un 4e point (Pi) qui est situé dans le triangle (évidemment il est sur le plan de ce triangle). Je cherche à interpoler les trois valeurs sur le 4e point Pi.

    J'ai fait beacoup de recherche mais je n'ai rien trouvé. Peut-être que je ne cherchais pas avec les bons termes mais bon...

    J'ai implémenté un algorithme qui permet une interpolation mais elle a de très grande lacune de précision (l'erreur d'interpolation est assez sévère). La voici:

    -Créer une droite passant par P3 et Pi -> P3_Pi
    -Créer une droite passant par P1 et P2 -> P1_P2
    -Trouver l'intersection de la droite P3_ Pi avec la droite P1_P2 -> Point Pi2
    -Faire une interpolation linéaire entre les points P1 et P2 pour Pi2 -> valeur interpolée pour Pi2
    -Faire une interpolation linéaire entre les points Pi2 et P3 pour Pi -> valeur interpolée pour Pi


    Si quelqu'un a une meilleure suggestion je serais très reconnaissant!

  2. #2
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 369
    Points : 40 164
    Points
    40 164
    Par défaut
    bien le bonjour,

    si tu ne cherches la valeur qu'un un seul point, la notion de barycentre te sera utile. On parle d'interpolaton (bi)linéaire lorsqu'il y a plusieurs points à définir.

    Ta méthode fonctionne, il faut toutefois ne pas oublier que pour ton interpolation entre Pi2 et P3, le point Pi2 doit compter comme P1 + P2, il doit donc peser plus lourd que P3.

    La méthode que je t'aurais proposée est quasiment la même : trouver la droite passant par Pi et parallèle à P1 elle coupe le triangle en A et B.
    On peut donc faire une interpolation pour trouver A et B. Et ensuite, on interpole entre A et B pour trouver Pi.

    Disons que de cette manière, on peut bien voir la notion de balayage. Il apparait clairement que 2 boucles imbriquée suffiront à parcourir tout ton triangle (interpolation bilinéaire)

  3. #3
    Vol
    Vol est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 42
    Points : 38
    Points
    38
    Par défaut
    Merci pour la réponse.

    Citation Envoyé par khayyam90
    Ta méthode fonctionne, il faut toutefois ne pas oublier que pour ton interpolation entre Pi2 et P3, le point Pi2 doit compter comme P1 + P2, il doit donc peser plus lourd que P3.
    Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.

    Sans avoir testé ta technique proposée, est-ce exact de dire que les mêmes résultats seraient obtenus? Si non, permettrait-elle d'avoir de meilleurs résultats?

  4. #4
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 369
    Points : 40 164
    Points
    40 164
    Par défaut
    Citation Envoyé par Vol
    Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.
    si on prend une approche purement mathématique, on regroupe 2 points en leur barycentre, il doit donc être pondéré de la somme des pondérations.

    mais si on prend une approche plus intuitive, ... un simple exemple sera plus parlant.
    considérons un triangle ABC, les médianes, et les points A' (resp B', resp C') en face de A (resp B, resp C).
    G centre de gravité.

    Il est évident que G est le point où chaque A,B,C pèse la même chose.
    Regroupe A et B en C'. Fais peser C' et C. Dans ton cas ils pèsent la même chose et le centre de gravité doit se trouver au milieu, hors il n'en est rien. Fais peser C' comme A+B et tu retombes bien sur G.

    Citation Envoyé par Vol
    Sans avoir testé ta technique proposée, est-ce exact de dire que les mêmes résultats seraient obtenus? Si non, permettrait-elle d'avoir de meilleurs résultats?
    Les résultats doivent être les mêmes. Ensuite, on peut pencher pour une méthode ou pour une autre (en terme de rapidité) selon ce que tu cherches à faire.

    Si tu cherches à déterminer tous les points de ton triangle, il peut être coûteux de déterminer des intersections et si on truande bien, on peut dégager des cas où ces calculs se simplifient (droites parallèles aux côtés, droites horizontales, verticales ...)

    Ce n'est qu'une autre méthode (très proche) pour arriver au même résultat.

  5. #5
    Vol
    Vol est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 42
    Points : 38
    Points
    38
    Par défaut
    Citation Envoyé par khayyam90
    Citation Envoyé par Vol
    Je ne vois pas pourquoi la valeur de Pi2 devrait peser plus.
    si on prend une approche purement mathématique, on regroupe 2 points en leur barycentre, il doit donc être pondéré de la somme des pondérations.

    mais si on prend une approche plus intuitive, ... un simple exemple sera plus parlant.
    considérons un triangle ABC, les médianes, et les points A' (resp B', resp C') en face de A (resp B, resp C).
    G centre de gravité.

    Il est évident que G est le point où chaque A,B,C pèse la même chose.
    Regroupe A et B en C'. Fais peser C' et C. Dans ton cas ils pèsent la même chose et le centre de gravité doit se trouver au milieu, hors il n'en est rien. Fais peser C' comme A+B et tu retombes bien sur G.
    Si je comprends bien, ce sont mes formules pour caluler val_Pi et val_Pi2 qui tiennent comptent du poids des points P1 à P3 (voir "détails" de calculs). Vrai?

    Je trouve les coordonnées de Pi2 en calculant l'intersection des droites.
    La valeur interpolée de Pi2 selon P1 et P2 est val_Pi2:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    val_Pi2  = val_P1 + (d1 * (val_P2 - val_P1)) / (d1+d2)
    La valeur interpolée de Pi selon Pi2 et Pi3 est val_Pi (c'est la valeur recherchée):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    val_Pi  = val_Pi2 + (d3 * (val_P3 - val_Pi2)) / (d3+d4)
    (d1 à d4 sont les distances entre les points sur la figure)


    Citation Envoyé par khayyam90
    Les résultats doivent être les mêmes. Ensuite, on peut pencher pour une méthode ou pour une autre (en terme de rapidité) selon ce que tu cherches à faire.

    Si tu cherches à déterminer tous les points de ton triangle, il peut être coûteux de déterminer des intersections et si on truande bien, on peut dégager des cas où ces calculs se simplifient (droites parallèles aux côtés, droites horizontales, verticales ...)

    Ce n'est qu'une autre méthode (très proche) pour arriver au même résultat.
    Je n'ai qu'un seul points par triangle qui nécessite une valeur calculée par interpolation (ce point peut-être n'importe où dans le triangle). Par contre, la rapidité de calcul est très importante. Pourrions-nous affirmer que ma méthode serait plus rapide puisqu'elle nécessite seulement le calcul d'une intersection contrairement à la tienne qui en nécessite deux?

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Je me trompes peut-être, car tout ça c'est bien loin, mais il me semble qu'on peut travailler avec des vecteurs:
    Il existe un triplet (a, b, c) tel que
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    a * vect(Pi,P1) + b * vect(Pi, P2) + c * vect(Pi,P3) = 0
    A partir de là, on doit pouvoir décliner avec les poids de P1, P2, P3 :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    a*poids(P1)*vect(Pi,P1) + b*poids(P2)*vect(Pi, P2)+c*poids(P3)*vect(Pi,P3)=0
    Qu'en pensez-vous ?
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  7. #7
    Membre habitué Avatar de larnicebafteur
    Inscrit en
    Mai 2006
    Messages
    133
    Détails du profil
    Informations forums :
    Inscription : Mai 2006
    Messages : 133
    Points : 131
    Points
    131
    Par défaut
    Une méthode consiste à determiner l'équation cartésienne du plan qui passe par les 3 points (la 3ème cordonnée étant la valeur affectée à chaque point).
    On determine ainsi facilement et rapidement la valeur interpolée pour n'importe quel point dans le triangle.

    J'avais déjà répondu à une question similaire :

    http://www.developpez.net/forums/sho...6&postcount=12
    S'il n'y a pas de solution, c'est qu'il n'y a pas de problème

  8. #8
    Membre averti Avatar de dazz_x
    Profil pro
    Inscrit en
    Mars 2006
    Messages
    269
    Détails du profil
    Informations personnelles :
    Âge : 44
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2006
    Messages : 269
    Points : 328
    Points
    328
    Par défaut
    Trap-D a raison, c'est une bonne méthode... Il faut chercher du côté des coordonnées barycentriques. En gros, c'est se placer dans un repère propre au triangle :
    *********-->** -->
    p(s,t)= A + sAB + tAC
    ou plutôt :
    *********-->**-->**-->
    p(s,t,w)= wOA + sOB + tOC avec w = 1-(s+t)
    tu interpoles donc tes valeurs aux sommets avec les coefficients de pondération s,t,w pour B, C et A et c'est bon... (c'est ce qui est utilisé pour l'évaluation de la normale à un triangle pour le modèle d'éclairage de Gouraud)

    voili voilu
    La différence entre la théorie et la pratique est plus mince en théorie qu'en pratique

  9. #9
    Vol
    Vol est déconnecté
    Nouveau membre du Club
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    42
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 42
    Points : 38
    Points
    38
    Par défaut
    Désolé, je n'ai pas eu la chance de répondre plus tôt. Merci pour toutes les suggestions. J'ai finalement choisi une méthode dérivée de celle indiquée par larnicebafteur.

    Citation Envoyé par larnicebafteur
    Une méthode consiste à determiner l'équation cartésienne du plan qui passe par les 3 points (la 3ème cordonnée étant la valeur affectée à chaque point).
    On determine ainsi facilement et rapidement la valeur interpolée pour n'importe quel point dans le triangle.

    J'avais déjà répondu à une question similaire :

    http://www.developpez.net/forums/sho...6&postcount=12
    Voici une image qui représente la technique que j'ai finalement choisie:


    Les 3 points 'val P..' sont obtenus en faisant une translation de la valeur (poids) des points P1 à P3 selon la normale (les lignes pointillées) au plan P1P2P3. On détermine ensuite l'intersection (valPp) entre le plan formé par valP1-valP2-valP3 et la droite normale au plan P1P2P3 et passant par Pp. La distance entre Pp et valPp correspond à la valeur interpolée qui est recherchée.

    J'ai comparé cette méthode avec ma méthode initiale ainsi que celle proposée par khayyam90 et des différences maximales de 0.5% pour les valeurs interpolées sont observées. Donc, peu importe la méthode utilisée, les résultats sont valides et très similaires. Par contre, en terme de temps d'exécution, la dernière méthode utilisée (celle expliquée dans ce message) est quelque peu plus rapide. En fait, moins de 1% plus rapide, ce qui est négligeable.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [Google Maps] Afficher des infos après clic sur un point
    Par jbaudin dans le forum APIs Google
    Réponses: 0
    Dernier message: 24/12/2008, 12h54
  2. besoin d'aide sur un point dans la FAQ
    Par Jim_Nastiq dans le forum Delphi
    Réponses: 11
    Dernier message: 28/03/2007, 11h09

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