Inscription / Connexion Nouveau Sujet
Niveau Grand oral
Partager :

Algorithme de calcul d'intersection de deux droites dans l'espac

Posté par
seram03
02-06-22 à 14:43

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

Posté par
flight
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 14:57

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 ?

Posté par
Bcarre
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 17:05

Seram03
Laisse moi un peu le temps d'y réfléchir.
Je te reviens demain

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 19:17

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.

Posté par
carpediem
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 20:04

salut

ouais ça me semble un sujet très ... aléatoire !!!

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 20:47

Salut flight,

Je cherche à résoudre un système de ce genre :


 \\ \begin{cases}
 \\ 5+6t  &= 9+2t' \\
 \\ t'    &= 4-t   \\
 \\ 2+5t  &= 7+t'
 \\ \end{cases}
 \\

(Pas ces équations précisément mais j'aimerai une formule générale ^^)

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 21:03

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
\begin{cases}5+6t  &= 9+2t' \\t'    &= 4-t   \end{cases}
On trouve, sauf erreur de ma part, t=\frac32 et t'=\frac52.
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.

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 21:17

Salut Verdurin,

Pour tirer au hasard je m'y prend de la sorte :
par exemple avec cette équation,


 \\ \begin{cases}
 \\  & x = 9 + 2t' \\ 
 \\  & y = 0 + 1t'  \\ 
 \\  & z = 7 + 1t' 
 \\ \end{cases}
 \\

On a 6 valeurs (qui sont ici  {9 ; 2 ; 0 ; 1 ; 7 ; 1}) à choisir qu'on prend dans l'intervalle {-9 ; 9}.
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 19! possibilités pour chaque droite)

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 21:27

verdurin @ 02-06-2022 à 21:03

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
\begin{cases}5+6t  &= 9+2t' \\t'    &= 4-t   \end{cases}
On trouve, sauf erreur de ma part, t=\frac32 et t'=\frac52.
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 ^^.

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 21:41

Ok,
tu as donc 19^6-19^3=47\,039\,022 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écantes

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 02-06-22 à 23:07

verdurin @ 02-06-2022 à 21:41

Ok,
tu as donc 19^6-19^3=47\,039\,022 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écantes


c'est de cette dernière ligne dont j'ai besoin ^^
Lien vers le repository Github :

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 03-06-22 à 11:40

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

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

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 03-06-22 à 17:43

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

determiant
est utile lorsqu'on a que 2 vecteurs (ceux des droites) et qu'elle en demande 3 😅

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 03-06-22 à 19:38

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.

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 03-06-22 à 20:33

verdurin @ 03-06-2022 à 19:38

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

Posté par
seram03
re : Algorithme de calcul d'intersection de deux droites dans l' 04-06-22 à 16:53

C'est bon !
Vous pouvez voir le code fonctionnel sur mon git:
Fonctionnel mais pas encore optimisé
Un grand merci à Verdurin pour son aide.

Posté par
verdurin
re : Algorithme de calcul d'intersection de deux droites dans l' 04-06-22 à 18:00

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écantes

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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !