[Algo] Detecter deux segments qui se croisent
Résolu/Fermé
kilian
Messages postés
8731
Date d'inscription
vendredi 19 septembre 2003
Statut
Modérateur
Dernière intervention
20 août 2016
-
10 août 2007 à 17:13
dd - 31 oct. 2012 à 10:30
dd - 31 oct. 2012 à 10:30
A voir également:
- Intersection de deux segments
- Un ecouteur sur deux marche ✓ - Forum Audio
- Deux comptes whatsapp - Guide
- J'ai deux compte facebook avec la meme adresse mail ✓ - Forum Facebook
- Deux ecran pc - Guide
- Itinéraire google map entre deux adresses - Guide
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.
