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

C++ Discussion :

Besoin d'aide pour un calcul d'intersection


Sujet :

C++

  1. #1
    Membre averti
    Homme Profil pro
    Cimentage
    Inscrit en
    Septembre 2014
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Cimentage
    Secteur : Associations - ONG

    Informations forums :
    Inscription : Septembre 2014
    Messages : 44
    Par défaut Besoin d'aide pour un calcul d'intersection
    Salut à tous,

    Alors voilà, dans le cadre d'un projet de programmation d'une appli en 2D en langage C++, je suis confronté à un ultime problème...

    Trouver le point d'intersection entre deux droites... Comment pourrais-je donc m'y prendre ?

    Par exemple, voici leurs coordoonées :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Droite1.x1 = 140
    Droite1.y1 = 70
    Droite1.x2 = 210
    Droite1.y2 = 270
     
    Droite2.x1 = 200
    Droite2.y1 = 200
    Droite2.x2 = 150
    Droite2.y2 = 270
    Ce qui me donne visuellement ceci :

    https://image.noelshack.com/fichiers...38770-test.png

    J'aimerais que vous m'appreniez à trouver les coordonnées en X/Y du point d'intersection de ces deux droites..
    Je ne veux pas d'un calcul tout fait mais que vous m'expliquiez ( si il y a une âme charitable qui s'ennuie un peu ici :-P ) le fonctionnement du calcul en question.

    ( Quand je bougerais les droites avec la souris et le clavier, le but sera que le calcul s'effectue de manière à ce que le point d'intersection soit recalculé en temps réel, bien entendu ! )

    Merci infiniment !

    Cordialement.

  2. #2
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

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

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Pour ce genre de calculs géométriques, j'aime bien cette ressource : http://www.faqs.org/faqs/graphics/algorithms-faq/
    Ta question est le point 1.03
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  3. #3
    Membre averti
    Homme Profil pro
    Cimentage
    Inscrit en
    Septembre 2014
    Messages
    44
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Cimentage
    Secteur : Associations - ONG

    Informations forums :
    Inscription : Septembre 2014
    Messages : 44
    Par défaut
    Salut JolyLoic :-)

    J'ai beau y mettre toute la volonté du monde, je suis une personne qui fonctionne surtout avec des exemples commentés ( avec des valeurs, de préférence ), c'est comme cela que je mémorise le mieux possible et que j'assimile l'apprentissage..

    Let A,B,C,D be 2-space position vectors. Then the directed line
    segments AB & CD are given by:

    AB=A+r(B-A), r in [0,1]
    CD=C+s(D-C), s in [0,1]
    Dans ce passage là, je ne sais absolument pas d'où vient le " r " ni le " s " d'ailleurs et ils me perturbent...

    Merci de ta participation en tout cas :-)

  4. #4
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2016
    Messages
    34
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2016
    Messages : 34
    Par défaut
    Bonjour,
    tu pourrais calculer les vecteurs directeurs de chacune des droites:

    -soient A(x1;y1) et B(x2,y2) deux points appartenant à droite 1:
    AB |x2-x1=210 - 140 = 70
    |y2-y1=270 - 70 = 200 est directeur de la droite 1.

    Par colinéarité, A'B' | 1
    |200/70 est aussi un vecteur directeur de la droite 1.


    -soient C(x3;y3) et D(x4;y4) deux points appartenant à droite 2:
    CD |x4-x3= 150-200 =-50
    |y4-y3= 270-200 = 70 est directeur de la droite 2.

    Par colinéarité, C'D' |1
    |-70/50 est aussi directeur de la droite 2.

    Il pourrait être intéressant d'implémenter la classe Point qui ne soit pas graphiques pour nous faciliter la tâche:

    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
     
     
    struct Point {
        int x,y;
        Point(int xx, int yy): x(xx), y(yy) {}
        Point(): x(0), y(0) //constructeur par défaut
    };
     
    bool operator==(Point a, Point b){return a.x=b.x && a.y=b.y};
    bool operator!=(Point a, Point b) {return !(a==b);}
     
     
    void vecteur_directeur(Point a, Point b, int &cor_x, int &cor_y  ){
        cor_x= b.x-a.x;
        cor_y=b.y-a.y;
     
        if(cor_x != 1 || cor_x!= 0){   /*le vecteur n'est pas nul et n'est pas encore de la forme  |1
                                                                                                                                         | m */
            cor_x=1;
            cor_y= cor_y / cor_x;   //regles de colinéarité entre vecteurs       
     
        }
    }
    Pour s'assurer que les droites ont 1 unique point d'intersection, on vérifie que les deux vecteurs directeurs ne sont pas colinéaires avec le test suivant:
    xAB*yCD - yAB*xCD= 70*70 - (-50) *200 = 4900 + 10 000 = 14900 != 0

    Comme le résultat n'est pas nul, alors les vecteurs ne sont pas colinéaires, donc les droites dont ils sont directeurs sont bien sécantes en un unique point.

    Programmer ce morceau est simple, il suffit d'une instruction conditionnelle if(formule==0) et tu mets ce que tu veux a l'intérieur.

    Ensuite, il faut calculer les équations de droite grâce aux vecteurs directeurs:
    on a fait en sorte que nos vecteurs soient de la forme |1 , on peut appliquer la propriété suivante:
    |m
    droite 1: y = 20/7*x +p
    droite 2: y =-7/5*x+p

    pour calculer p:
    droite 1: comme A appartient a la droite 1 alors: y1= 20/7*x1 + p
    140= 20/7*70 +p (je ne mets pas les équivalences :/ )
    p = 140 -200 = -60

    Donc, droite 1: y = 20/7*x -60


    droite 2: comme C appartient a la droite 2 alors: y3=-7/5*x3+p
    200= -7/5*200 +p
    p=200 + 280 = 480

    Donc, droite 2: y = -7*5*x+480

    Les ordonnées à l'origine sont particulièrement grandes par rapport au coefficient directeur, je me suis peut etre trompé (pas de feuilles sous la main) mais j'ai mis les notations littérales donc tu devrais comprendre.

    En C++, on pourrait créer une fonction pour gérer ça:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     
    //Il faut implémenter dans ta classe droite les membres coef_dir et ord_orig et les fonctions membres suivantes
     
    void droite::add_coef_dir(droite &dd, int cor_y_vec){  // l'int sort de la fonction  vecteur_directeur//
        dd.coef_dir = cor_y_vec; // a toi de voir en ce qui concerne l'encapsulation, je te laisse gérer les détails 
                                                                 //techniques
    }
     
    void droite::add_ord_orig(droite &dd, Point a){  // le point doit appartenir à la droite 
        dd.ord_orig= a.y - (a.x*dd.coef_dir);    //même remarque pour l'encapsulation
    }

    Connaissant les équations de droite de nos droites:
    il reste a résoudre un système de la forme pour trouver le point d'intersection:


    {y=20/7*x-60
    {y=-7/5*x+480

    equivalent (je le mets juste une fois)

    {y=100/35*x-60
    {y=-49/35*x+480

    {-49y=-4900/35*x+2940
    {100y=-4900/35*x+48000

    {-49y=-4900/35*x+2940
    {149y= 45060

    {-49y=-4900/35*x+2940
    {y=45060/149

    {-49*45060/149=-4900/35*x+2940
    {y=45060/149

    {x=[ (-49*45060/149) -2940]* (-35/4900)
    {y=45060/149

    Du coup, x et y sont les coordonnées respectives de tes points, je peux pas les vérifier car j'ai que la calculatrice windows avec moi ce qui en soi n'est pas super pour faire des maths .


    Pour ce qui est du programme en C++, il suffit de chercher sur le web un solveur de systèmes a deux inconnues et a le custom quelque peu, il y en a beaucoup, tu trouveras facilement.


    Notes:
    -Il est certain que ma solution n'est pas la seule possible, et probablement pas la meilleure non plus, n'hésitez pas à me corriger;
    -ne me jetez pas de pierres si il manque beaucoup de détails d'implémentation, je ne vais pas faire l'exercice en entier et je ne sais pas comment la classe droite a été implémentée, c'est à lui de se charger de ce genre de détails;
    -il y aura probablement des bogues dans mon code car je n'ai pas pu le compiler n'ayant pas les outils pour et je ne fais guere souvent de 'sans fautes' en C++;
    -j'ai écrit le code tel quel sans préciser les headers et ce genre de détails qui là aussi sont du ressort de l'auteur du programme;
    -j'ai possiblement oublié des std::;
    -j'ai développé uniquement des points de coordonnées entières puisque le problème traitait de coordonnées entières;


    Cordialement.

  5. #5
    Expert confirmé
    Homme Profil pro
    Ingénieur développement matériel électronique
    Inscrit en
    Décembre 2015
    Messages
    1 599
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 62
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement matériel électronique
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Décembre 2015
    Messages : 1 599
    Par défaut
    Citation Envoyé par FrostfallDelphi Voir le message
    Let A,B,C,D be 2-space position vectors. Then the directed line
    segments AB & CD are given by:

    AB=A+r(B-A), r in [0,1]
    CD=C+s(D-C), s in [0,1]
    Dans ce passage là, je ne sais absolument pas d'où vient le " r " ni le " s " d'ailleurs et ils me perturbent...
    r et s représentent la position relative d'un point de chaque segment, ils introduisent ces données, puis ensuite donnent le moyen de les calculer dans le cas particulier du point d'intersection.
    L'intersection se calcule alors en 4 lignes
    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
    const double &Ax = Droite1.x1;
    const double &Ay = Droite1.y1;
    const double &Bx = Droite1.x2;
    const double &By = Droite1.y2;
    const double &Cx = Droite2.x1;
    const double &Cy = Droite2.y1;
    const double &Dx = Droite2.x2;
    const double &Dy = Droite2.y2;
    double dvsr = (Bx-Ax)*(Dy-Cy) - (By-Ay)*(Dx-Cx);
    if ( dvsr != 0. ) { // les segments ne sont pas nuls, ni parallèles
       double r = ( (Ay-Cy)*(Dx-Cx) - (Ax-Cx)*(Dy-Cy) ) / dvsr;
       // la position du point d'intersection est :
       double Px = Ax + r * (Bx-Ax);
       double Py = Ay + r * (By-Ay);
    }
    Si on ne veut que l'intersection de segments au lieu des droites entières, on doit vérifier que r et s sont bien compris entre 0.0 et 1.0.

  6. #6
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

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

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Pour l'explication de r, c'est simple :
    Qu'est-ce qu'une droite passant par les points A et B ? C'est l'ensemble des points qui sont alignés avec A et B. Comment construire cet ensemble ? Si tu considères le vecteur AB (que l'on calcule par B-A), tu es d'accord que :
    - A + AB est sur la droite (c'est le point B)
    - A + 0.5 AB est sur la droite (c'est le point milieu du segment [AB])
    - A + 0 AB est sur la droite (c'est A)
    - A + 2 AB est sur la droite (c'est un point C tel que B est le milieu de [AC])
    - ...

    Et donc la droite AB peut être vue comme l'ensemble des points parcourus par A + r * AB quand r varie de -inf à +inf (et le segment [AB] est l'ensemble des ces mêmes points quand r varie entre 0 et 1).

    Et donc, l'algorithme proposé cherche à trouver une valeur qui soit à la fois un point de AB et un point de CD, dont qui résolve les deux équations simultanément.
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  7. #7
    Membre Expert Avatar de Astraya
    Homme Profil pro
    Consommateur de café
    Inscrit en
    Mai 2007
    Messages
    1 048
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Consommateur de café
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Mai 2007
    Messages : 1 048
    Par défaut
    En informatique, il est plus simple et rapide de considérer une droite comme un point et un vecteur normalisé.
    Tu ne penses jamais avec la vielle formule ax+by+c = 0
    Rien que par cette représentation de nombreux calculs sont très simplifiée, optimisé et compréhensible.
    Et surtout il serait beaucoup plus facile pour un utilisateur de dessiner une droite en plaçant un point et un vecteur directeur.

    Une excellente libraire avec sources existe ici : https://www.geometrictools.com/Source/Intersection2D.html#LinearLinear

    En gros, la première étapes est de vérifier l'angle entre les droites avec le produit scalaire (Dot product).
    Si elle ne sont pas parallèles (Angle != 0)
    On trouve le point comme dans l'algorithme suivant ( A toi de le comprendre, ce n'est pas compliqué )
    Sinon elle sont parallèles:
    2 Cas de figures ( Distincte ou non)

    NOTA: Tu verras que dans la calcul ici il trouve non pas un point mais 2 distances:
    Real s0 = diffDotPerpD1*invD0DotPerpD1;
    Real s1 = diffDotPerpD0*invD0DotPerpD1;
    C'est en fait la distance depuis le point d'origine vers le point d'intersection de chaque droite donc le point est:
    line0.origin + s0 * line0.direction
    ou
    line1.origin + s1 * line1.direction
    (les 2 donnes le même point)
    Tu comprendras vite (j'espère) que tu peux très rapidement le transformer pour calculer l'intersection de 2 segments...

    Essayes de la comprendre et poses tes questions.

    Pour tester l'intersection:
    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
    // The intersection of two lines is a solution to P0 + s0*D0 = P1 + s1*D1.
        // Rewrite this as s0*D0 - s1*D1 = P1 - P0 = Q.  If DotPerp(D0, D1)) = 0,
        // the lines are parallel.  Additionally, if DotPerp(Q, D1)) = 0, the
        // lines are the same.  If Dotperp(D0, D1)) is not zero, then
        //   s0 = DotPerp(Q, D1))/DotPerp(D0, D1))
        // produces the point of intersection.  Also,
        //   s1 = DotPerp(Q, D0))/DotPerp(D0, D1))
     
        Vector2<Real> diff = line1.origin - line0.origin;
        Real D0DotPerpD1 = DotPerp(line0.direction, line1.direction);
        if (D0DotPerpD1 != (Real)0)
        {
            // The lines are not parallel.
            result.intersect = true;
            result.numIntersections = 1;
        }
        else
        {
            // The lines are parallel.
            Normalize(diff);
            Real diffNDotPerpD1 = DotPerp(diff, line1.direction);
            if (diffNDotPerpD1 != (Real)0)
            {
                // The lines are parallel but distinct.
                result.intersect = false;
                result.numIntersections = 0;
            }
            else
            {
                // The lines are the same.
                result.intersect = true;
                result.numIntersections = std::numeric_limits<int>::max();
            }
        }
    Pour trouver l'intersection:
    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
    42
    43
    44
    45
    46
    47
    // The intersection of two lines is a solution to P0 + s0*D0 = P1 + s1*D1.
        // Rewrite this as s0*D0 - s1*D1 = P1 - P0 = Q.  If DotPerp(D0, D1)) = 0,
        // the lines are parallel.  Additionally, if DotPerp(Q, D1)) = 0, the
        // lines are the same.  If Dotperp(D0, D1)) is not zero, then
        //   s0 = DotPerp(Q, D1))/DotPerp(D0, D1))
        // produces the point of intersection.  Also,
        //   s1 = DotPerp(Q, D0))/DotPerp(D0, D1))
     
        Vector2<Real> diff = line1.origin - line0.origin;
        Real D0DotPerpD1 = DotPerp(line0.direction, line1.direction);
        if (D0DotPerpD1 != (Real)0)
        {
            // The lines are not parallel.
            result.intersect = true;
            result.numIntersections = 1;
            Real invD0DotPerpD1 = ((Real)1) / D0DotPerpD1;
            Real diffDotPerpD0 = DotPerp(diff, line0.direction);
            Real diffDotPerpD1 = DotPerp(diff, line1.direction);
            Real s0 = diffDotPerpD1*invD0DotPerpD1;
            Real s1 = diffDotPerpD0*invD0DotPerpD1;
            result.line0Parameter[0] = s0;
            result.line1Parameter[0] = s1;
            result.point = line0.origin + s0 * line0.direction;
        }
        else
        {
            // The lines are parallel.
            Normalize(diff);
            Real diffNDotPerpD1 = DotPerp(diff, line1.direction);
            if (std::abs(diffNDotPerpD1) != (Real)0)
            {
                // The lines are parallel but distinct.
                result.intersect = false;
                result.numIntersections = 0;
            }
            else
            {
                // The lines are the same.
                result.intersect = true;
                result.numIntersections = std::numeric_limits<int>::max();
                Real maxReal = std::numeric_limits<Real>::max();
                result.line0Parameter[0] = -maxReal;
                result.line0Parameter[1] = +maxReal;
                result.line1Parameter[0] = -maxReal;
                result.line1Parameter[1] = +maxReal;
            }
        }

Discussions similaires

  1. besoin d'aide pour le calcul d'un intégral double
    Par okitrinaw dans le forum Fortran
    Réponses: 2
    Dernier message: 18/12/2013, 19h08
  2. besoin d'aide pour un gros calcul de malade
    Par thor76160 dans le forum Langage
    Réponses: 4
    Dernier message: 29/03/2010, 16h21
  3. Réponses: 1
    Dernier message: 01/10/2008, 11h36
  4. Besoin d'aide Pour une Requete de Calcul Totaux
    Par good speed dans le forum Requêtes et SQL.
    Réponses: 2
    Dernier message: 08/03/2008, 15h58
  5. Besoin d'aide pour un calcul sur un site
    Par barre dans le forum Général JavaScript
    Réponses: 1
    Dernier message: 23/02/2007, 08h36

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