Besoin d'aide pour un calcul d'intersection..

[Slash94]

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: Tout sélectionner

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/20 ... 0-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 ) 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.

[MJoe]

Bonjour à tous,

Il s'agit de calculer le point d'intersection de la droite D1 et de la droite D2 sachant que vous pourrez changer les points de passage de ces deux droites.
On commence par calculer les équations des deux droites :

Droite D1 d'équation y = ax + b
On calcule le coefficient directeur, a, en exprimant un taux d'accroissement :

Pour b, on écrit le fait que A1(140;70) appartient à D1 :

Finalement l'équation de la droite D1 est :

Droite D2 :
On effectue les mêmes calculs et on obtient :

Il reste à déterminer les coordonnées du point d'intersection P(x;y) :
P appartient à la droite D1 donc ses coordonnées vérifient l'équation de D1. De même, P appartient à D2 donc ses coordonnées vérifient également l'équation de D2. On obtient donc un système de 2 équations à 2 inconnues :



Il ne reste plus qu'à résoudre ce système pour pouvoir déterminer les coordonnées du point P.

Petit graphique Geogebra :



MJoe.

[WillyCagnes]

bjr

equation de la 1ère droite : D1 =aX+b

le pt x1 donne y1=aX1+b
le pt X2 donne y2=aX2+b

tu resous le systeme pour trouver a=(y1-y2)/(x1-x2)
et b=y1- [(y1-y2)/(x1-x2)]*x1

même logique pour l'autre droite D2=aX+b, tu calculeras a et b
ensuite les droites se couperont au même point d'intersection (x,y)


exemple
http://www.webmaths.com/comment-trouver ... A9quations

http://calculis.net/intersection

https://www.youtube.com/watch?v=vymPFajz4xE
D1=D2 à resoudre

[Slash94]

WillyCagnes > Merci beaucoup pour tes éclaircissements :-]
MJoe > Merci énormément pour ta contribution, j'y vois beaucoup plus clair désormais, ta réponse est d'une qualité extra, t'es vraiment adorable !
Merci, merci, merci !!!!!

[MJoe]

Merci à toi

MJoe.

[Slash94]

Je t'en prie

Dernière chose, je voudrais juste savoir comment tu procèdes afin de résoudre le système final, je n'ai pas envie de passer par une application de calcul quelconque, je veux être capable d'apprendre à le faire tout seul, en toutes circonstances, j'avais déjà suivi des tutos sur youtube pour résoudre des systèmes mais ils étaient beaucoup plus simplistes que ça et surtout.. sans fraction..!

Merci encore !

[MJoe]

Bonjour @slash94 et bonjour à tous,

Il reste donc à déterminer les coordonnées du point d'intersection P(x;y) :
P appartient à la droite D1 donc ses coordonnées vérifient l'équation de D1. De même, P appartient à D2 donc ses coordonnées vérifient également l'équation de D2. On obtient donc un système de 2 équations à 2 inconnues :



Pour résoudre ce système on peut, par exemple, effectuer une combinaison linéaire c'est-à-dire faire l'équation (1) - l'équation (2) ainsi la variable y "disparaît", ce qui donne une équation avec uniquement la variable x. On obtient :

soit :


On remplace ensuite cette valeur dans l'une des deux équations afin de déterminer la valeur de la variable y. Dans l'équation (1) par exemple :


On aurait pu également procéder par substitution en remplaçant l'expression de y de l'équation (1) (c'est-à-dire ) dans l'équation (2). Bien sûr cela aurait donné le même résultat.

MJoe.

[MJoe]

Suite 1 : Comment programmer tout ceci

Ceci est donc une méthode "manuelle". Si tu veux le programmer, il faut mettre les valeurs dans des variables.
La droite D1 passe par les points A1(x1;y1) et A2(x2;y2). Son équation est de la forme : y = a*x+b
La droite D2 passe par les points A3(x3;y3) et A4(x4;y4). Son équation est de la forme : y = a'*x+b'

Si on reprend les calculs précédents, on peut calculer les expressions des termes a, b, a' et b' :

de même :


Pour le calcul des coordonnées du point d'intersection , il suffit de refaire le calcul de mon message précédent mais avec les variables a, b, a' et b'. On obtient :

et


MJoe.

[MJoe]

Suite 2 : Petit programme de détermination des coordonnées du point d'intersection P.

Voici ce que cela donne avec le langage Scilab :

Code: Tout sélectionner

x1 = 140
y1 = 70
x2 = 210
y2 = 270
x3 = 200
y3 = 200
x4 = 150
y4 = 270

a = (y2-y1)/(x2-x1)
b = y1 - a*x1

aprime = (y4-y3)/(x4-x3)
bprime = y3 - aprime*x3

xp = (bprime - b)/(a - aprime)
yp = a*xp + b

printf("Coordonnées du point d''intersection P :\n")
printf("xp = %0.2f%s%0.2f\n",xp," et yp = ",yp)


Et à l'affichage dans la console Scilab :

Code: Tout sélectionner

Coordonnées du point d'intersection P :
xp = 190.27 et yp = 213.62


Et une petite capture d'écran :



Télécharger le programme Scilab ci-dessus (fichier au format ".sci" (ou copier/coller le code source ci-avant)).

MJoe.

[MJoe]

Suite 3 : Petit programme de détermination des coordonnées du point d'intersection P.

Voici ce que cela donne avec le langage Python :

Code: Tout sélectionner

x1 = 140
y1 = 70
x2 = 210
y2 = 270
x3 = 200
y3 = 200
x4 = 150
y4 = 270

a = (y2-y1)/(x2-x1)
b = y1 - a*x1

aprime = (y4-y3)/(x4-x3)
bprime = y3 - aprime*x3

xp = (bprime - b)/(a - aprime)
yp = a*xp + b

print("Coordonnées du point d'intersection P :")
print("xp = ",xp," et yp = ",yp)


Et à l'affichage dans la console Python Scripter (PyScrypter) :

Code: Tout sélectionner

>>>
Coordonnées du point d'intersection P :
xp =  190.26845637583892  et yp =  213.62416107382546


Et une petite capture d'écran :



Télécharger le programme Python ci-dessus (fichier au format ".py" (ou copier/coller le code source ci-avant)).

MJoe.

[Slash94]

Salut à toi MJoe, tu es un grand altruiste pour m'accorder autant de temps gratuitement, c'est vraiment super de ta part tant de considération et je t'en remercie grandement.

Je voulais juste savoir comment tu as fait pour arriver à 100+49/35 ? Je n'arrive pas à trouver la manière dont tu t'y es pris afin de trouver ce calcul..

[WillyCagnes]

bjr,

additionne 20x/7 + 7x/5=?

revise ton cours sur les fractions...

[Slash94]

Salut Willy..

J'ai arrêté les études en 4ème. ( Oui, je sais, le minimum légal sur la scolarisation étant porté à 16 ans en France ).

Je me suis mis à la programmation il y a 1 an, discipline dans la quelle je n'ai eu besoin que de calculs primitifs jusqu'à présent.

J'ai décidé de me mettre à l'étude du Raycasting, d'où mon besoin d'apprendre à bien gérer les intersections.
Je fais tout ça dans un but réacréatif / de hobbie et non pour une quelconque étude.
Je suis avant tout autodidacte.

Merci tout de même

EDIT : Effectivement, avec ce calcul j'arrive bien à 100+49/35 soit 4.25 mais pourquoi multiplier 810 ( donc 480+330 ) par 35 dans ce cas là ? ( autrement-dit, le dénominateur de la précédente fraction ), c'est ça que j'ai du mal à capter

EDIT 2 : Ahhh, j'ai compris ! Vu qu'on passe de l'autre côté, on passe de la division à la multiplication, logique finalement, j'ai capté ! Je vais en faire plein plein plein avec des données aléatoires histoire de m'entraîner cet après-midi, encore merci à tous pour votre réactivité :-]

[MJoe]

Bonjour @Slash94 et bonjour à tous,

Tout est ok ? N'hésite pas si tu as d'autres questions.

MJoe.

[MJoe]

Salut Willy..

EDIT : Effectivement, avec ce calcul j'arrive bien à 100+49/35 soit 4.25 mais pourquoi multiplier 810 ( donc 480+330 ) par 35 dans ce cas là ? ( autrement-dit, le dénominateur de la précédente fraction ), c'est ça que j'ai du mal à capter

EDIT 2 : Ahhh, j'ai compris ! Vu qu'on passe de l'autre côté, on passe de la division à la multiplication, logique finalement, j'ai capté ! Je vais en faire plein plein plein avec des données aléatoires histoire de m'entraîner cet après-midi, encore merci à tous pour votre réactivité :-]

Bonjour à tous,
Je détaille les calculs. On avait donc l'égalité suivante :

Ce qui s'écrit :

On réduit au même dénominateur :

Soit :

On peut donc faire la somme des numérateurs :

On ajoute 810 au membre de droite et au membre de gauche :

On multiplie par 35 le membre de droite et le membre de gauche :

On divise par 149 le membre de droite et le membre de gauche :


Voilà
MJoe.

[Slash94]

Merci infiniment l'ami !

Grâce en très grande partie à toi, j'ai bien assimilé le concept, j'en fais plein tous les jours dorénavant afin de ne pas perdre le cap, encore merci Tu es top de chez top man !

[MJoe]

Merci à toi
Bon courage et bonne continuation.
MJoe.

[Slash94]

Merci MJoe

Donc grâce à cette compréhension et surtout grâce à toi, j'ai pu enfin développer une fonction fonctionnelle qui renvoi le bon résultat :

Code: Tout sélectionner

#include "Headers/Intersect.h"

Intersect::Intersect()
{

}


void Intersect::printCoords(float D1X1, float D1Y1, float D1X2, float D1Y2,
                            float D2X1, float D2Y1, float D2X2, float D2Y2)
{
    float A = (D1Y2-D1Y1)/(D1X2-D1X1);
    float Y = D1Y1 - (A*D1X1);

    float Ap = (D2Y2-D2Y1)/(D2X2-D2X1);
    float Yp = D2Y1 - (Ap*D2X1);

    float intersectX = (Yp-Y)/(A-Ap);
    float intersectY = A * intersectX + Y;

    std::cout << intersectX << std::endl;
    std::cout << intersectY << std::endl;
}


Néanmoins, j'aimerais savoir comment déterminer à présent, si je suis sur le RESTE d'une des droites où si je suis bien dessus..?

[MJoe]

Bonjour @Slash94 et bonjour à tous,

Bravo pour le programme en C++ !

Qu'est-ce que tu appelles le "RESTE" d'une des droites ?
Pour savoir si un point M(Xm;Ym) est sur une droite, il suffit de vérifier que ses coordonnées Xm et Ym vérifient l'équation de la droite, c'est-à-dire si Ym = a*Xm + b pour une droite d'équation y = a*x + b.

MJoe.

[MJoe]

Bonjour à tous,

Voici un petit exemple de points situés au-dessus, en dessous ou bien sur une droite donnée d'équation .



MJoe.