[Algo] Detecter deux segments qui se croisent
Résolu
kilian
Messages postés
8732
Date d'inscription
Statut
Modérateur
Dernière intervention
-
dd -
dd -
Bonjour,
J'ai un petit soucis d'algorithmique. En fait, j'ai deux segments représentés chacuns par deux points de coordonnées x,y
Segment 1:
x(a) = 14
y(a) = 8
x(b) = ...
y(b) = ...
Segment 2:
x(c) = ...
y(c) = ...
x(d) = ...
y(d) = ...
Ayant ces coordonées, comment je peux faire pour savoir si ces deux segments se croisent?
J'ai beau faire des schémas pour essayer de trouver une condition plausible, j'y arrive pas :-/
Merci d'avance...
J'ai un petit soucis d'algorithmique. En fait, j'ai deux segments représentés chacuns par deux points de coordonnées x,y
Segment 1:
x(a) = 14
y(a) = 8
x(b) = ...
y(b) = ...
Segment 2:
x(c) = ...
y(c) = ...
x(d) = ...
y(d) = ...
Ayant ces coordonées, comment je peux faire pour savoir si ces deux segments se croisent?
J'ai beau faire des schémas pour essayer de trouver une condition plausible, j'y arrive pas :-/
Merci d'avance...
6 réponses
Avis à ceux qui veulent s'inspirer des solutions proposées. Elles sont vraies dans le cas général mais fausses si on a une équation de droite du type x=cste. Celle de in vino veritas est vraie mais peu explicite sur la manière de calculer le point d'intersection des droites. Les méthodes utilisant les équations de droite nécessitent de décomposer en plusieurs cas selon la forme des équations de droite. (y= ou x=)
Je propose une dernière solution valable dans le cas général purement géométrique:
On veut savoir si [AB] coupe [A'B']
ceci est vrai ssi :
->produit vectoriel (AB A'B') != 0 cad les droites ne sont pas parallèles (et aussi A'!=B', A!=B).
->ET produit vectoriel (AB,AB').produit vectoriel (AB,AA')<=0 cad le point d'intersection est entre B' et A' (donc sur le segment [A'B'])
->ET produit vectoriel (A'B',A'B).produit vectoriel (A'B',A'A)<=0 cad le point d'intersection est entre B et A (donc sur le segment [AB])
Cette méthode est toujours valable tant que les points sont distinct deux à deux. Cette méthode ne fonctionne cependant pas dans le cas où 3 des points décrivant les segment au moins sont identiques, en effet la première condition n'est alors pas vérifiée et pourtant les deux segments se croisent: ils ont un point en commun.
Pour une généralisation il faut rajouter un test qui gère ce cas particulier:
-> OU (A=B et A=B') OU (A=B et A=A') OU ( A'=B 'et A=A') OU (A'=B' et B=A')
Cependant ce cas particulier n'était pas non plus géré par les solutions proposées ci dessus, et nécessitait le même type de test.
Je propose une dernière solution valable dans le cas général purement géométrique:
On veut savoir si [AB] coupe [A'B']
ceci est vrai ssi :
->produit vectoriel (AB A'B') != 0 cad les droites ne sont pas parallèles (et aussi A'!=B', A!=B).
->ET produit vectoriel (AB,AB').produit vectoriel (AB,AA')<=0 cad le point d'intersection est entre B' et A' (donc sur le segment [A'B'])
->ET produit vectoriel (A'B',A'B).produit vectoriel (A'B',A'A)<=0 cad le point d'intersection est entre B et A (donc sur le segment [AB])
Cette méthode est toujours valable tant que les points sont distinct deux à deux. Cette méthode ne fonctionne cependant pas dans le cas où 3 des points décrivant les segment au moins sont identiques, en effet la première condition n'est alors pas vérifiée et pourtant les deux segments se croisent: ils ont un point en commun.
Pour une généralisation il faut rajouter un test qui gère ce cas particulier:
-> OU (A=B et A=B') OU (A=B et A=A') OU ( A'=B 'et A=A') OU (A'=B' et B=A')
Cependant ce cas particulier n'était pas non plus géré par les solutions proposées ci dessus, et nécessitait le même type de test.
Voilà, c'est fait!
Merci à vous.
Je fais donc un petit rappel si quelqu'un rencontre le même problème.
On a quatre points:
P1: (x1, y1)
P2: (x2, y2)
P3: (x3, y3)
P4: (x4, y4)
On a deux droites:
D1 traverse P1 et P2
D2 traverse P3 et P4
On appelera a1 le coefficient directeur (le a dans la fonction) de D1 et a2 le coefficient directeur de D2.
Même chose avec l'ordonnée à l'origine (le b dans la fonction), b1 pour D1 et b2 pour D2.
On a donc.
Pour D1:
et
Pour D2:
et
On cherche d'abord a1 et a2:
On cherche ensuite b1 et b2:
Voilà on tout ce qu'il faut pour partir.
On veut d'abord savoir si deux droites se croisent.
On vérifie donc si elles ne sont pas parallèles, pour ça rien de plus simple: vérifier que les coefficients sont différents:
Maintenant on cherche le x ou se croisent ces deux droites:
Heureusement qu'on a vérifié que a1 et a2 étaient différents, on aurait pu avoir une division par 0!
Il n'y a plus qu'à vérifier que xcommun est d'une part compris entre x1 et x2 et d'autre part entre x3 et x4.
Si c'est bon, c'est que nos segments se croisent.
Par contre pas besoin de vérifier que le y commun est compris entre y1 et y2 etc.... Si le x du point commun aux droites est aussi compris entre les x des extrémités des segments, c'est suffisant. Euh...j'espère que j'explique bien...
Voilà donc, et merci à vous.
Merci à vous.
Je fais donc un petit rappel si quelqu'un rencontre le même problème.
On a quatre points:
P1: (x1, y1)
P2: (x2, y2)
P3: (x3, y3)
P4: (x4, y4)
On a deux droites:
D1 traverse P1 et P2
D2 traverse P3 et P4
On appelera a1 le coefficient directeur (le a dans la fonction) de D1 et a2 le coefficient directeur de D2.
Même chose avec l'ordonnée à l'origine (le b dans la fonction), b1 pour D1 et b2 pour D2.
On a donc.
Pour D1:
y1 = a1 * x1 + b1
et
y2 = a1 * x2 + b1
Pour D2:
y3 = a2 * x3 + b2
et
y4 = a2 * x4 + b2
On cherche d'abord a1 et a2:
a1 = (y2 - y1) / (x2 - x1) a2 = (y4 - y3) / (x4 - x3)
On cherche ensuite b1 et b2:
b1 = y1 - (a1 * x1) b2 = y3 - (a2 * x3)
Voilà on tout ce qu'il faut pour partir.
On veut d'abord savoir si deux droites se croisent.
On vérifie donc si elles ne sont pas parallèles, pour ça rien de plus simple: vérifier que les coefficients sont différents:
si a1 = a2 alors les segments ne se croisent pas.
Maintenant on cherche le x ou se croisent ces deux droites:
xcommun=(b2-b1)/(a1-a2)
Heureusement qu'on a vérifié que a1 et a2 étaient différents, on aurait pu avoir une division par 0!
Il n'y a plus qu'à vérifier que xcommun est d'une part compris entre x1 et x2 et d'autre part entre x3 et x4.
Si c'est bon, c'est que nos segments se croisent.
Par contre pas besoin de vérifier que le y commun est compris entre y1 et y2 etc.... Si le x du point commun aux droites est aussi compris entre les x des extrémités des segments, c'est suffisant. Euh...j'espère que j'explique bien...
Voilà donc, et merci à vous.
Il manque une chose à cette algorithme, qui risque de provoquer une division par 0, c'est vérifier si x1 et x2 sont différent, ainsi que si x3 et x4 sont différents.
(exemple:
_____________________________
|
|
|
|
|
|
)
Cette algorithme indiquerait que les segments se croisent, ce qui est manifestement faux.
Cela donne d'ailleurs une division par 0, /(x2-x1)
Il faut donc commencer par prendre deux booléan
v1=(x1==x2)
v2=(x3==x4)
renvoyer faux si v1 et v2 (encore une fois à cause du parallélisme)
sinon, si v1, alors on calcule a2 et b2 de la même manière,puis x=(y1-b2)/a2 et il ne reste qu'à voir si x se trouve entre x3 et x4.
De même:
si v2, alors on calcule a1 et b1 de la même manière,puis x=(y3-b1)/a1 et il ne reste qu'à voir si x se trouve entre x1 et x2.
sinon, si ni v1, ni v2, alors on effectue le reste de l'algorithme cité plus haut.
(exemple:
_____________________________
|
|
|
|
|
|
)
Cette algorithme indiquerait que les segments se croisent, ce qui est manifestement faux.
Cela donne d'ailleurs une division par 0, /(x2-x1)
Il faut donc commencer par prendre deux booléan
v1=(x1==x2)
v2=(x3==x4)
renvoyer faux si v1 et v2 (encore une fois à cause du parallélisme)
sinon, si v1, alors on calcule a2 et b2 de la même manière,puis x=(y1-b2)/a2 et il ne reste qu'à voir si x se trouve entre x3 et x4.
De même:
si v2, alors on calcule a1 et b1 de la même manière,puis x=(y3-b1)/a1 et il ne reste qu'à voir si x se trouve entre x1 et x2.
sinon, si ni v1, ni v2, alors on effectue le reste de l'algorithme cité plus haut.
Je me suis trompé dans les formule, je reformule:
si v1, alors on calcule a2 et b2 de la même manière,puis y=a2*x1+b2 et il ne reste qu'à voir si y se trouve entre y1 et y2 et entre y3 et y4
De même:
si v2, alors on calcule a1 et b1 de la même manière,puis y=a1*x3+b1 et il ne reste qu'à voir si y se trouve entre y1 et y2 et entre y3 et y4
si v1, alors on calcule a2 et b2 de la même manière,puis y=a2*x1+b2 et il ne reste qu'à voir si y se trouve entre y1 et y2 et entre y3 et y4
De même:
si v2, alors on calcule a1 et b1 de la même manière,puis y=a1*x3+b1 et il ne reste qu'à voir si y se trouve entre y1 et y2 et entre y3 et y4
Bonjour...
Il faut trouver les équations des droites supportants les segments. puis trouver leur (eventuel) point de croisement. enfin voir si le point de croisement(s'il existe) appartient aux deux segments
1) la droite supportant le segment 1 ayant pour equation Y1=a1x1+b1
Elle passe par les points x(a), y(a) et x(b), y (b)
donc il suffit de resoudre le systéme de 2 équations a deux inconnues :
y(a) =a1 x(a)+b1 et y(b)= a1x(b) + b1 pour trouver la valeur de a1 et b1.
de même
2) la droite supportant le segment 2 ayant pour equation Y2=a2x2+b2
Elle passe par les points x(c), y(c) et x(d), y (d)
donc il suffit de resoudre le systéme de 2 équations a deux inconnues :
y(c) =a2 x(c)+b2 et y(b)= a2x(b) + b2 pour trouver la valeur de a2 et b2.
3) Ensuite si les droites se croisent l'équation suivante a une solution
a1x+b1=a2x+b2
soit x=(b2-b1)/(a1-a2)
4) si x est compris entre ou égal aux abcisses x(a) et x(b) et compris entre ou égal aux abcisses x(c)et x(d), alors les deux segments se croisent a cette valeur d'abcisse.
Salut
Il faut trouver les équations des droites supportants les segments. puis trouver leur (eventuel) point de croisement. enfin voir si le point de croisement(s'il existe) appartient aux deux segments
1) la droite supportant le segment 1 ayant pour equation Y1=a1x1+b1
Elle passe par les points x(a), y(a) et x(b), y (b)
donc il suffit de resoudre le systéme de 2 équations a deux inconnues :
y(a) =a1 x(a)+b1 et y(b)= a1x(b) + b1 pour trouver la valeur de a1 et b1.
de même
2) la droite supportant le segment 2 ayant pour equation Y2=a2x2+b2
Elle passe par les points x(c), y(c) et x(d), y (d)
donc il suffit de resoudre le systéme de 2 équations a deux inconnues :
y(c) =a2 x(c)+b2 et y(b)= a2x(b) + b2 pour trouver la valeur de a2 et b2.
3) Ensuite si les droites se croisent l'équation suivante a une solution
a1x+b1=a2x+b2
soit x=(b2-b1)/(a1-a2)
4) si x est compris entre ou égal aux abcisses x(a) et x(b) et compris entre ou égal aux abcisses x(c)et x(d), alors les deux segments se croisent a cette valeur d'abcisse.
Salut
Salut kilian,
je te conseillerais de faire la chose suivante:
1) Etablir les équations des droites qui portent ces deux vecteurs.
2) Calculer, s'il existe, les coordonnées du point en lesquelles ces deux droites ce coupent.
3) Vérifier que ce point appartient bien à chaque vecteur. Puisque ce point appartient à la fois aux deux droites qui portent ces vecteurs, cela revient à vérifier que (en notant E le point de contact trouvé):
i) x(E) est compris entre x(a) et x(b)
ii)x(E) est compris entre x(c) et x(d)
iii)y(E) est compris entre y(a) et y(b)
ii)y(E) est compris entre y(c) et y(d)
Par "compris", j'entends que cela peut éventuellement être égal (à la différence de "compris strictement").
Si ces quatre conditions sont réunies, alors les deux segments se coupent (en E)... Elle est pas belle la vie? :-)
je te conseillerais de faire la chose suivante:
1) Etablir les équations des droites qui portent ces deux vecteurs.
2) Calculer, s'il existe, les coordonnées du point en lesquelles ces deux droites ce coupent.
3) Vérifier que ce point appartient bien à chaque vecteur. Puisque ce point appartient à la fois aux deux droites qui portent ces vecteurs, cela revient à vérifier que (en notant E le point de contact trouvé):
i) x(E) est compris entre x(a) et x(b)
ii)x(E) est compris entre x(c) et x(d)
iii)y(E) est compris entre y(a) et y(b)
ii)y(E) est compris entre y(c) et y(d)
Par "compris", j'entends que cela peut éventuellement être égal (à la différence de "compris strictement").
Si ces quatre conditions sont réunies, alors les deux segments se coupent (en E)... Elle est pas belle la vie? :-)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question