Besoin d'aide pour un calcul d'intersection

Version imprimable

05/08/2017, 15h21
FrostfallDelphi

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:

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.
05/08/2017, 15h53
JolyLoic

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
05/08/2017, 16h03
FrostfallDelphi

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..

Citation:

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 :-)

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:

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:

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.

Citation:

Envoyé par FrostfallDelphi

Citation:

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:

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.

06/08/2017, 21h12
JolyLoic

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.

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:

Citation:

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:

Citation:

line0.origin + s0 * line0.direction

Citation:

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:

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:

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;
        }
    }