[Algo] Detecter deux segments qui se croisent Résolu/Fermé

Question

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

dd · Accepted Answer

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.

baladur13 · Answer

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

In Vino Veritas · Answer

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

kilian · Answer

Hey merci à vous!
Chuis pas très matheux alors j'avais pas pensé à passer par tout ça...
Je me lance dessus lundi au boulot...

kilian · Answer

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

baladur13 · Answer

C'est une affaire qui tourne.....!  Voila la loco sur les rails....
STP mets le post "résolu".... merci
A la prochaine.....

[Algo] Detecter deux segments qui se croisent

6 réponses

Discussions similaires