Partage
  • Partager sur Facebook
  • Partager sur Twitter

calcul du point d'intersection de deux segments

Algorithme

Sujet résolu
    18 mars 2009 à 15:13:20

    Bonjour !

    Voila... J'aimerai calculer l'intersection de deux segments (s'ils se coupent). On dispose des coordonnées des extrémités des deux segments. Connaitriez-vous un moyen de le faire ?

    Siouplait. ^^
    • Partager sur Facebook
    • Partager sur Twitter
      18 mars 2009 à 16:37:17

      Déjà, sais-tu déterminer si ils se coupent ?
      • Partager sur Facebook
      • Partager sur Twitter
        18 mars 2009 à 16:38:28

        Bonjour,

        Ca n'a pas grand chose à voir avec le C++, c'est plus des maths que de l'algo...

        J'ai une solution à proposer (il y a peut être mieux, car là c'est un peu bourrin ^^ ) :

        Soient (AB) et (CD) les deux droites avec A(Xa,Ya), B(Xb,Yb), C(Xc,Yc) et D(Xd,Yd).
        On suppose un cas non trivial où aucune des droites n'est verticale. Si une des deux droites est verticale il faut échanger les coordonnées X et Y pour ne pas avoir de dénominateur nul dans les calculs. Si en plus les droites sont perpendiculaires, alors le problème est résolu (à méditer ^^ ).
        On a alors les équations des deux droites :
        (AB) : ((Yb-Ya)/(Xb-Xa))*(X-Xa)+Ya=Y
        (CD) : ((Yd-Yc)/(Xd-Xc))*(X-Xc)+Yc=Y
        Pour trouver l'intersection I(Xi,Yi) des droites il suffit de résoudre le système.
        On trouve Xi en soustrayant les deux équations puis Yi par substitution :
        Xi=[((Yb-Ya)/(Xb-Xa))*Xa+Ya-((Yd-Yc)/(Xd-Xc))*Xc-Yc] / [((Yb-Ya)/(Xb-Xa))-((Yd-Yc)/(Xd-Xc))]
        Yi=((Yb-Ya)/(Xb-Xa))*([((Yb-Ya)/(Xb-Xa))*Xa+Ya-((Yd-Yc)/(Xd-Xc))*Xc-Yc] / [((Yb-Ya)/(Xb-Xa))-((Yd-Yc)/(Xd-Xc))]-Xa)+Ya

        Voilà ce qui arrive quand on pose pas de variables intermédiaires :)

        On peut trouver une intersection seulement si [((Yb-Ya)/(Xb-Xa))-((Yd-Yc)/(Xd-Xc))] != 0 (sinon les droites sont parallèles).

        Enfin pour vérifier que l'intersection se situe bien sur les segments il suffit de vérifier la condition "Xi appartient à l'intervalle [Xa,Xb]".

        PS : Attention, ya forcément des erreurs de calcul involontaires (faut pas rêver) ! Il faudrait les reprendre (ou les vérifier par l'expérience).

        Edit3 : Comme promis le calcul était globalement faux. C'est un peu moins faux maintenant. :)
        • Partager sur Facebook
        • Partager sur Twitter
        Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
          18 mars 2009 à 16:47:14

          tu es une brute épaisse iNaKoll :D
          il y a une solution avec thalès ;)
          • Partager sur Facebook
          • Partager sur Twitter
            18 mars 2009 à 17:04:01

            En même temps j'ai tout de suite annoncé la couleur..

            Si je ne me trompe pas pour appliquer Thalès il faut deux droites sécantes (OK) et deux droites parallèles (NO-OK dans le cas général). Sinon ça aurait pu être plus simple effectivement.. :)
            • Partager sur Facebook
            • Partager sur Twitter
            Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
              18 mars 2009 à 17:18:00

              on calcule les coordonnées des droites
              puis on fait une petite équation comme sa : "droite1 = droite2"
              et puis on a tout les point d'intersections après il faut que le programme puisse géré sa ^^ mais ça marche

              rappel (même si tu le sais peut-être sa m'occupe :p ) :

              - calcul d'une droite à partir de 2 points :
              droite d'équation : y = ax + b
              a = (y1 - y2 ) / (x1 - x2)
              b = y1 - a.x1
              (Sachant que le point A a pour coordonnées : x1 et y1
              et le point B : x2 et y2)

              - savoir si elles sont sécantes :
              on a deux droite :
              y1 = a1.x + b1
              y2 = a2.x + b2

              on fait y1 = y2
              ce qui revient à :
              y1 - y2 = 0
              a1.x + b1 - a2.x - b2 = 0
              x(a1 - a2) + b1 - b2 = 0
              x = (b2 - b1) / (a1 - a2)

              et donc on à la fin de l'équation on obtient la valeur x où elle se croisent
              (si elles se croisent) et si elles se croisent pas alors tu aura un petit
              a1 - a2 = 0 (donc tu fait une condition pour vérifié si a1 - a2 != 0 ;)

              voilà
              si je me trompe dites moi que je parte pas sans avoir dit n'importe quoi ^^
              ça fait longtemps que j'ai pas fait de trigo ^^
              • Partager sur Facebook
              • Partager sur Twitter
                18 mars 2009 à 17:26:35

                A priori DoBeL on a la même solution sous une forme différente. Tu utilises des "variables intermédiaires" (a1,b1,a2 et b2) qui rendent sans aucun doute ta démonstration plus digeste.. :)
                • Partager sur Facebook
                • Partager sur Twitter
                Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
                  18 mars 2009 à 17:30:50

                  oui je me disais aussi ^^
                  c'est vrai que c'est plus joli à voir :p
                  mais bon je vois pas comment faire autrement ...
                  • Partager sur Facebook
                  • Partager sur Twitter
                    18 mars 2009 à 17:52:32

                    Vous proposez des solutions en se basant sur les équations cartesiennes des droites.
                    Elles sont juste ! (attention au cas des droites verticales, mais l'auteur en a déja parlé)

                    Je vous propose une solution paramétrique :
                    Soit le segment [AB], et le segment [CD].
                    Je note I le vecteur AB, et J le vecteur CD

                    Soit k le parametre du point d'intersection du segment CD sur la droite AB. on sera sur le segment si 0<k<1
                    Soit m le parametre du point d'intersection du segment AB sur la droite CD, on sera sur le segment si 0<m<1

                    Soit P le point d'intersction
                    P = A + k*I; // equation (1)
                    P = C + m*J;

                    D'ou :
                    A + k*I = C + m*J

                    On décompose les points et vecteurs, on a :
                    Ax + k*Ix = Cx + m*Jx
                    Ay + k*Iy = Cy + m*Jy

                    2 équations, 2 inconnues, en résolvant, on trouve :

                    m = -(-Ix*Ay+Ix*Cy+Iy*Ax-Iy*Cx)/(Ix*Jy-Iy*Jx)
                    k = -(Ax*Jy-Cx*Jy-Jx*Ay+Jx*Cy)/(Ix*Jy-Iy*Jx)

                    (Notez que les dénominateurs sont les meme)
                    Attention, si Ix*Jy-Iy*Jx = 0 , alors les droites sont paralleles, pas d'intersection.
                    Sinon, on trouve m et k

                    On vérifie que 0<m<1 et 0<k<1 --> sinon, cela veut dire que les droites s'intersectent, mais pas au niveau du segment.

                    Ensuite, pour retrouver P, on réinjecte m ou k dans une des 2 équations (1)

                    Voila donc une forme paramétrique :)
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Recueil de code C et C++  http://fvirtman.free.fr/recueil/index.html

                      18 mars 2009 à 18:18:08

                      C'est déjà plus élégant :
                      - plus de problème de verticalité
                      - extensible à la 3D
                      - système simple à résoudre (avec la méthode de Cramer)
                      - condition super simple sur les paramètres..

                      J'attendais ta solution ! :p

                      Sinon, j'imagine qu'il doit y avoir le même genre de systèmes paramétriques pour les intersections droite/plan, plan/plan ?
                      • Partager sur Facebook
                      • Partager sur Twitter
                      Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
                        18 mars 2009 à 18:19:01

                        ma solution pour trouver l'intersection de deux droites ... donc pour deux segments ça marche aussi, suffit de vérifier que les segments s'intersectent :)
                        je commente pas tout de suite ... faut que j'y aille , m'enfin ça vous fera méditer un peu :D

                        #include <cstdlib>
                        #include <cstdio>
                        #include <algorithm>
                        #include <math.h>
                        
                        const double EPSILON=0.00000001;
                        
                        struct Point{
                          int x,y;
                          Point(int _x,int _y):x(_x),y(_y){}
                        };
                        struct Vecteur{
                          int x,y;
                          Point a,b;
                          Vecteur(Point _a,Point _b):a(_a),b(_b)
                          {
                            x=b.x-a.x;
                            y=b.y-a.y;
                          }
                          int vecto(Vecteur autre){
                            return (x*autre.y-y*autre.x);
                          }
                          double norme(){
                            return sqrt(x*x+y*y);
                          }
                        };
                        
                        int main(void){
                          int x1,y1,x2,y2;
                          scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                          Point a1(x1,y1);
                          Point a2(x2,y2);
                          Vecteur A(a1,a2);
                        
                          scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                          Point b1(x1,y1);
                          Point b2(x2,y2);
                          Vecteur B(b1,b2);
                          
                          double a=(double)A.vecto(Vecteur(a1,b1))/A.norme(); 
                          double b=(double)A.vecto(Vecteur(a1,b2))/A.norme(); 
                        
                          double nouveauB=B.norme()+(B.norme()*b)/(a-b);
                          double resX,resY;
                          double vraiRapport=nouveauB/B.norme();
                        
                          resX=(double)b1.x+(double)B.x*vraiRapport;
                          resY=(double)b1.y+(double)B.y*vraiRapport;
                         
                          printf("%lf %lf\n",resX,resY);
                          
                          return 0;
                        }
                        



                        comme ça , pas besoin de math compliqués ...
                        • Partager sur Facebook
                        • Partager sur Twitter
                          18 mars 2009 à 18:30:22

                          Merci beaucoup!
                          o_O Euh... Je dois avouer que je n'ai pas encore les connaissances mathématiques requises pour la solution de iNakoll... Pour la solution de Dobel, ca a l'air de marcher mais comment on fait pour connaitre la position y ?
                          • Partager sur Facebook
                          • Partager sur Twitter
                            18 mars 2009 à 18:30:25

                            Citation : iNaKoll

                            C'est déjà plus élégant :
                            - plus de problème de verticalité
                            - extensible à la 3D
                            - système simple à résoudre (avec la méthode de Cramer)
                            - condition super simple sur les paramètres..

                            J'attendais ta solution ! :p

                            Sinon, j'imagine qu'il doit y avoir le même genre de systèmes paramétriques pour les intersections droite/plan, plan/plan ?



                            Alors, plus de probleme de verticalité en effet :) Mais il faut toujours tester le dénominateur (pour les droites paralleles) : on note d'ailleurs que le dénominateur est logiquement la formule du déterminant :)

                            Pour l'extention a la 3D, en effet ! Mais attention, ça créé un systeme a 2 inconnues et 3 équations. Donc l'idée est de résoudre le systeme avec 2 équations (comme ici), et de vérifier que la 3e équation est vérifiée avec les résultats trouvés :)
                            --> Dans les autres cas, on a affaire a des droites dans l'espace non paralleles, mais qui ne coupent pas (prend 2 stylos, dans ta main gauche tu le tiens horizontalement, dans ta main droite (que tu mets plus haut) tu le tiens en biais)

                            Intersection droite plan, c'est le meme concept, un plan sera de la forme (avec P point d'intersection)

                            P = O + k*I + m*J
                            que tu joins l'intersection de la droite :
                            P = A + n*K

                            Pareil, on assemble les 2 équations en enlevant P, et on développe les vecteurs en 3 dimensions, donc 3 équations, et 3 inconnues (k,m,n)
                            Donc trouve donc le parametre sur la droite d'origine A, et sur le plan d'origine O, dans lesquel on aura définis 2 vecteurs orthogonaux I, et J.

                            Pour l'intersection de 2 plans, c'est un peu plus compliqué car l'intersection est une droite (sauf si les plans sont paralleles). Mais tout ceci se calcule également :)
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Recueil de code C et C++  http://fvirtman.free.fr/recueil/index.html

                              18 mars 2009 à 18:34:18

                              Citation : Naj

                              Merci beaucoup!
                              o_O Euh... Je dois avouer que je n'ai pas encore les connaissances mathématiques requises pour la solution de iNakoll... Pour la solution de Dobel, ca a l'air de marcher mais comment on fait pour connaitre la position y ?



                              y n'est pas une position mais un nom d'une équation de droite ^^
                              j'aurais pu l'appeller f(x) si tu préfère ;)
                              • Partager sur Facebook
                              • Partager sur Twitter
                                18 mars 2009 à 18:35:12

                                Oups, sorry Fvirtman, j'ai pas lu ton post avant de poster mon message (pas vu). Je lis.
                                EDIT : Dobel, je voulais parler de la position y de l'intersection. ;)
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  18 mars 2009 à 18:39:45

                                  tu prend le x que tu as récupéré
                                  tu utilise soit l'équation de la première droite ou de la seconde droite
                                  et alors tu trouve y ;)
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    18 mars 2009 à 18:43:15

                                    Merci beaucoup ! :) J'essaie quand meme de comprendre la solution de Fvirtman.
                                    EDIT: Euh... C'est quoi ce que vous appelez le paramètre d'un point ? :euh: J'ai l'habitude de me baser sur des articles trouvés sur des sites internets pour comprendre les notions abordées, mais on ne trouve pas grand chose quand on recherche "parametre" ou "parametrique"...
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      18 mars 2009 à 19:40:35

                                      Merci Fvirtman pour les précisions! Je pense que je me souviendrais de tout ca si un jour j'en ai besoin! ;)
                                      Pour l'intersection plan/plan j'y ai réfléchi un peu et même si ca doit être faisable, pour le coup le problème serait plus compliqué avec les équations paramétriques des plans.. (jusqu'à 50% de chance de se planter dans le choix des bonnes hypothèses si les vecteurs des plans sont perpendiculaires à l'intersection)

                                      Pour la petite histoire, je me rappelle avoir utilisé la méthode proposée par Homeomath (avec les équations cartésiennes) en cours de maths il y a quelques années de cela maintenant ! ;) Avec cette méthode on a jusqu'à 33% de chance de se planter dans le choix du paramètre (ex : on choisit 'z' alors que l'intersection est dans un plan // à (xy)).

                                      PS : J'ai bien réfléchi et je ne crois pas dire de connerie.. :euh:

                                      Edit pour Naj : Essaye de regarder du côté des "équations paramétriques de droites" mais j'ai l'impression qu'il n'y a pas grand chose à ce sujet sur internet..
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
                                        18 mars 2009 à 20:48:05

                                        Pour l'explication du code utilisant Thalès :
                                        Image utilisateur

                                        Grâce à geogebra (meilleur ami du lycéen :D ) , on a : C' et D' projetés orthogonaux de C et D .

                                        Donc, il y a des chances que (CC') et (DD') soient parallèles ...on peut donc utiliser thalès.
                                        A coup de produits scalaires, on détermine le rapport du plus petit sur le plus grand.
                                        Puis on applique ce rapport comme il faut pour trouver un vecteur par la translation duquel , on obtiendra l'intersection...

                                        comme ça , pas de formules compliquées :)

                                        edit: pour finir l'exemple : on a d'après Thalès : f/e=AI/AB avec I le point que l'on cherche.
                                        Donc AI=AB*(f/e) et ouala , c'est gagné :)
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          18 mars 2009 à 21:53:34

                                          Dakeyras Khan > Il faut supposer que (AC) et (BD) ne sont pas parallèles... Donc dans le cas général, ça ne fonctionne pas avec Thalès. En y regardant de plus prêt je crois que je comprends enfin ce que tu as fait.. mea culpa.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                          Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
                                            18 mars 2009 à 21:59:47

                                            Ben j'espère bien que ça ne marche pas si les droites sont parallèles ... parceque le point d'intersection serait achement plus compliqué à trouver ;)

                                            plus sérieusement, il suffit de tester avant si les 2 segments s'intersectent :) (ou même les droites ... encore plus facile ;) )

                                            (edit: pas faux ton histoire de parallelogramme et de diagonales :) ,mais est-ce plus simple ? )
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              19 mars 2009 à 16:50:00

                                              Merci beacoup ! Finalement, je vais utiliser la solution de Fvirtman (expliquée par ma prof de maths :p ).
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                19 mars 2009 à 16:56:37

                                                :) Tu nous montreras le résultat !
                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                Recueil de code C et C++  http://fvirtman.free.fr/recueil/index.html

                                                  19 mars 2009 à 17:04:05

                                                  Le programme dans lequel c'est utilisé ? Désolé, mais les segements ne sont pas apparents. En fait, c'est pour créer un grand polygone (utilisé pour les collisions) à partir de plusieurs petits.
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    19 mars 2009 à 17:05:14

                                                    ok ! mais apres, tu auras un programme qui detectera la collision avec les polygones, ça tu pourras nous le montrer ? :)
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter

                                                    Recueil de code C et C++  http://fvirtman.free.fr/recueil/index.html

                                                      19 mars 2009 à 17:09:42

                                                      Ouaip, mais il faudra attendre un peu. :-° Avec un peu de chance, on aura fait la première version dans 3-4 mois (premier programme de cette dimension pour moi et pour Shembox). Désolé. ;)
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        16 avril 2015 à 17:18:43

                                                        Bonjour à tous,

                                                        je déterre le sujet, non pas pour le remettre en cause, mais plutôt pour confirmer la solution de Fvirtman.

                                                        Dans le cas où des internautes continueraient à fouiner sur cette page, je vous met le code C++ implémentant la solution de Fvirtman :

                                                        Point getIntersectionPoint(const Point& _A, const Point& _B, const Point& _C, const Point& _D)
                                                        {
                                                            Point I(_B.x - _A.x, _B.y - _A.y);
                                                            Point J(_D.x - _C.x, _D.y - _C.y);
                                                            float m(0), k(0), diviseur(I.x * J.y - I.y * J.x);
                                                        
                                                            if(diviseur != 0)
                                                            {
                                                                m = (I.x * _A.y
                                                                     - I.x * _C.y
                                                                     - I.y * _A.x
                                                                     + I.y * _C.x
                                                                    ) / diviseur;
                                                                k = (J.x * _A.y
                                                                     - J.x * _C.y
                                                                     - J.y * _A.x
                                                                     + J.y * _C.x
                                                                    ) / diviseur;
                                                            }
                                                            return Point(_C + m * J);
                                                            // ou bien en utilisant k
                                                            // return Point(_A + k * I);
                                                        }

                                                        En considérant bien sûr les éléments suivants :

                                                        • Point est une classe implémentant les opérateurs '*', '/', '+' et '-'
                                                        • Les paramètres sont passés par référence constante (je considère que les points fournis en paramètre ne sont pas des pointeurs)

                                                        -
                                                        Edité par groolot 16 avril 2015 à 17:31:14

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter

                                                        calcul du point d'intersection de deux segments

                                                        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                        × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                        • Editeur
                                                        • Markdown