Inscription / Connexion Nouveau Sujet
Algorithme de calcul d'intersection de deux droites dans l'espac
Bonjour les îleux,
J'ai besoin d'un génie parmi vous qui saurait répondre à mon problème :
Pour le grand oral j'ai choisi un sujet original que je ne pensais pas aussi prise de tête au départ. L'intitulé est : quelle est la probabilité que deux droites dans l'espace se coupe ? (référence à l'improvisation improbable de notre prof de math lors d'un exercice d'entraînement).
Pour répondre à cette question, je dois faire une stat sur la probabilité que deux droites se coupent (j'ajoute quelques conditions pour ''réduire'' le nombre de droites comme une intervalle de [-9 ; 9] pour le choix des points (mais l'intersection peut se faire à l'extérieur de ce ''cube de definition'') et la possibilité de ne prendre qu'une fois chaque point de cette intervalle pour la représentation paramétrique de chaque droite.) Malgré les conditions, je vais utiliser la loi des grands nombres pour faire une proba d'intersection (oui à la fin j'aurai une proba de proba, c'est pas très exact mais mon pauvre petit Core I5 et ma GTX 1080 ne sont pas à la hauteur pour tout calculer). Voilà pour le sujet, j'espère que vous avez pu le saisir.
Pour calculer cette première proba, j'ai vérifié si les deux droites sont parallèles et si oui si elles sont confondues. Un algo relativement simple à indenter (au passage, je code en python).
Mais pour l'intersection, j'ai besoin de résoudre un système à 2 inconnues. Et c'est là que je bloque :
Y a-t-il un algorithme pas trop compliqué qui permet de résoudre ça ? J'ai pas mal cherché chez mon ami Google mais je ne trouve pas de réponse satisfaisante (impossible de savoir la formule qui permet de simplifier les 3 équations).
Si vous avez une quelconque piste, une question sur le post ou même la réponse, je vous écoutes.
Merci de votre aide.
PS : ce soir je modifierai le post avec un peu de latex pour une meilleure lisibilité et je mettrai le lien Github vers le fichier python
salut
tu dis dans ton enoncé droite de l'espace et tu termine par la resolution d'un systeme à deux inconnues , ne serait ce pas plutot droite du plan ?
Bonsoir,
je crois qu'il faut que tu précises comment tu tires deux droites « au hasard ».
Avec les méthodes de tirage que j'imagine la probabilité pour que les deux droites soient sécantes est nulle.
Salut flight,
Je cherche à résoudre un système de ce genre :
(Pas ces équations précisément mais j'aimerai une formule générale ^^)
En général ce genre de système n'a pas de solutions.
Tu peux essayer de résoudre le système formé par les deux premières équations.
Dans ton exemple
On trouve, sauf erreur de ma part, et
.
Ensuite tu reportes les valeurs obtenues dans la troisième équation.
Les droites sont sécantes si et seulement si la troisième équation est vérifiée.
C'est le cas dans ton exemple.
Salut Verdurin,
Pour tirer au hasard je m'y prend de la sorte :
par exemple avec cette équation,
On a 6 valeurs (qui sont ici ) à choisir qu'on prend dans l'intervalle
.
En python ça donne :
droites = [(randint(-9, 9) for valeur in range(6) for droite in range(très grand nombre)]
(j'ai abandonné la seconde condition car elle n'est pas appliquée au cas de base. On a donc
En général ce genre de système n'a pas de solutions.
Tu peux essayer de résoudre le système formé par les deux premières équations.
Dans ton exemple
On trouve, sauf erreur de ma part,
Ensuite tu reportes les valeurs obtenues dans la troisième équation.
Les droites sont sécantes si et seulement si la troisième équation est vérifiée.
C'est le cas dans ton exemple.
Oui c'est ce je pensais faire (désolé je m'étais mal exprimé) mais la question est donc plutôt Quel algo pour résoudre un système à deux inconnues ?
Et effectivement, c'est très peu probable mais en laissant tourner mon pc 24h je vais pouvoir trouver 5 ou 6 bonnes équations ^^.
Ok,
tu as donc droites possibles (il faut que le vecteur directeur soit non nul ).
Regarder toutes les couples de droites possibles est un peu trop long.
Si tu veux faire une simulation je te conseille un algorithme du genre :
répéter un nombre assez grand de fois
tirer deux droites au hasard suivant ta règle
regarder si elles sont sécantesOk,
tu as donc
Regarder toutes les couples de droites possibles est un peu trop long.
Si tu veux faire une simulation je te conseille un algorithme du genre :
répéter un nombre assez grand de fois
tirer deux droites au hasard suivant ta règle
regarder si elles sont sécantesc'est de cette dernière ligne dont j'ai besoin ^^
Lien vers le repository Github :
Quelques remarques sur ton programme.
La fonction colineaires est utile mais va provoquer une erreur quand le second vecteur a une coordonnée nulle.
Ce qui est assez probable avec les droites que tu tires au hasard.
Je proposerais volontiers une réécriture de cette fonction et de la fonction paralleles comme suit
def colineaires(v1, v2):
det1=v1.x*v2.y-v2.x*v1.y
det2=v1.y*v2.z-v2.y*v1.z
det3=v1.x*v2.z-v2.x*v1.z
return det1 == 0 and det2 == 0 and det3 == 0
def paralleles(d1, d2):
return colineaires(d1.vecteur_directeur,d2.vecteur_directeur)Il n'y a pas de problème si tu utilises ces fonctions avec des vecteurs à coordonnées entières, si tu les utilises avec des flottants il faudra remplacer le test ==0 par un test qui vérifie que le résultat est « assez proche » de zéro.
On peut vérifier facilement que 3 vecteurs de l'espace sont coplanaires en calculant leur déterminant par exemple avec la fonction
def determinant(v1,v2,v3) :
a=v1.x*v2.y*v3.z + v2.x*v3.y*v1.z + v3.x*v1.y*v2.z
b=v1.x*v3.y*v2.z + v3.x*v2.y*v1.z + v2.x*v1.y*v3.z
return a-bles vecteurs sont coplanaires si et seulement si le déterminant est nul.
Et
deux droites coplanaires sont soit parallèles soit sécantes
deux droites non coplanaires n'ont aucun point commun.
Merci beaucoup Verdurin pour cette réponse et pour la rectification.
À priori je n'utiliserai que des entiers (j'ai bien assez de valeurs comme ça ^^).
Après, je pense faire en sorte de ne pas avoir de vecteur nul dans mes équations de droite mais plus c'est optimisé et général, plus je je prend 
.
J'ai du mal à comprendre en quoi la fonction
determiantOn a deux vecteurs directeurs et un vecteur défini par les deux points origines des droites.
Si ces vecteurs sont coplanaires alors les droites le sont aussi et réciproquement.
PS : quand tu tires un vecteur directeur n'oublie pas de vérifier qu'il est non nul.
On a deux vecteurs directeurs et un vecteur défini par les deux points origines des droites.
Si ces vecteurs sont coplanaires alors les droites le sont aussi et réciproquement.
PS : quand tu tires un vecteur directeur n'oublie pas de vérifier qu'il est non nul.
Et c'est à ce moment là que la fonction vecteur_depuis_deux_points() sera utile !
merci beaucoup pour cet éclaircissement, je vous tiens au courant sur l'avancée du projet
C'est bon ! 
Vous pouvez voir le code fonctionnel sur mon git:
Fonctionnel mais pas encore optimisé
Un grand merci à Verdurin pour son aide.
Bonsoir,
je me permets encore une critique.
Tu tires au hasard une liste de droites, mais rien ne garantie qu'elles soient toutes distinctes.
Or s'il y a deux droites confondues dans ta liste, toute droite ayant un point commun avec l'une a par définition un point commun avec l'autre.
Ce qui va conduire à une surestimation de la probabilité cherchée d'un facteur presque égal à 2.
Pour être précis il faudrait évaluer la proba de tirer plusieurs fois la même droite, elle est faible mais je ne suis pas sur qu'elle soit négligeable, en tout cas j'ai la flemme de faire le calcul.
Je te recommande donc un algo du type
répéter un nombre assez grand de fois
tirer deux droites au hasard
regarder si elles sont sécantesC'est moins sympa que d'utiliser itertools mais plus exact.
À la rigueur on peut optimiser un peu en gardant la dernière droite tirée.
Annuler
connectez vous