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 ?
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.
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
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..
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
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 ) :
- 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
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..
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
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)
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 !
Sinon, j'imagine qu'il doit y avoir le même genre de systèmes paramétriques pour les intersections droite/plan, plan/plan ?
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
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
#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;
}
Merci beaucoup! 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 ?
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 !
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
Merci beaucoup! 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
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.
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 ? 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"...
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..
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..
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
Grâce à geogebra (meilleur ami du lycéen ) , 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é
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.
Inkamath on GitHub - Interpréteur d'expressions mathématiques. Reprise du développement en cours.
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.
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é.
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
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.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html