intersection de droites mais avec en plus des infos supplémentaires sur le point d'intersection

Bonjour à tous et à toutes,

Voila mon problème. J'avais trouvé il y a longtemps un code source (vb6 il me semble) permettant non seulement de trouver le point d'intersection de deux segments de droites(s'il existe), mais aussi de renvoyer une info précisant les points suivants.

• - le point d'intersection est il situé directement sur les 2 segments (cas le plus simple, les segments se croisent.) ?.
• - sinon (les segments ne sont pas parallèles), le point d'intersection est situé en dehors d'un ou des 2 segments :
• - si, il faut "étendre" un des deux segments pour trouver le point d'intersection, renvoyer sur quel segment(non étendu) le point d'intersection  figure.
•       - et dernier cas, s'il faut "étendre les deux segments" pour trouver l'intersection, renvoyer aussi cette info.
  

Exemple de valeurs retournées par la fonction :
         point d'intersection :P.x p.y(p.z*)
         type positionnement : 0= pas d'intersection,
                                         1= le point d'intersection est sur le segment de droite num 1
                                         2= le point d'intersection est sur le segment de droite num 2
                                         3= le point d'intersection existe mais n'est ni sur le segment 1 ni le segment 2

Une fonction vb avait été écrite réalisant exactement cela, je crois même que c'était ici (???), mais impossible de la retrouver. Mes capacités mathématiques sont malheureusement dépassées pour pouvoir la réécrire .

Un sucre d'orge virtuel et toute ma considération à celui (ou celle) qui saura me renseigner soit par un "code plein d'equations" soit par l'adresse internet référençant cette vieille fonction

Petitlu

PS (p.z*) la 3d au cas ou un gars extrèmement doué en serait capable

Pour repondre au probleme dans le cas de la 2D, il faut considerer qu'une droite c'est un vecteur directeur + un point du plan.
Un segement c'est un point + un vecteur qui definit le segment.

ainsi une droite (D) sera parametrée par :
 (D) =  (a ; b) * s + (u ; v)
(où (a ; b) est le vecteur directeur de la droite et (x ; y) un point par lequel passe D)

Si l'on cherche le point I = (x, y) intersection de deux droites (D1) et (D2)
on aura alors
    (x, y) = (a1, b1) * s + (u1, v1)
    (x, y) = (a2, b2) * r + (u2, v2)

   soit le systeme 2 equation 2 inconues:
     a1 * s - a2 * r  = u2 - u1
     b1 * s - b2 * r = v2 - v1

Ensuite on resoud le systeme avec comme inconues : (s, r)
    - Ce systeme n'a pas de solution (si les deux droites sont parallele) si 
    det = -a1 * b2 + a2 * b1 = 0
    - Si les droite ne sont pas parallele alors det <> 0 et on a
    (je passe les calcules matricielles qui sont long et pas comprehensible)
    d'où
         r = (1 / det) * ( b2 * (u1 - u2) + a2 * (v2 - v1) )
         s = (1 / det) * ( b1 * (u1 - u2) + a1 * (v2 - v1) )

    Ensuite, il suffit d'analyser les resultats :
        si 0 <= r <= 1 alors le point d'intersection se trouve sur le segement definit par le vecteur (a1, b1) et le point (u1, v1)
        sinon le point d'intersection n'est pas sur ce segement
        si 0 <= s <= 1 alors le point d'intesection se trouve sur le segement definit par le vecteur (a2, b2) et le point (u2, v2)
        sinon le point d'intersection n'est pas sur ce segement

Pour la 3D l'equation de la droite devient
     (D) = (a ; b ; c) * t + (u, v, w)
     ensuite si l'on est sure que les deux droites se croisent, on vire une coordonée de notre droite et on se place dans le cas 2D (par exemple la composante sur les z) ainsi les droite de l'espace sont comme des droite du plan.

Sauf qu'il n'y a AUCUNE chance pour que deux droite de l'espace s'intersepte. Il faut donc calculer le point pour lequel la distance de ces deux droites est minimale, ce que l'on considerera comme point d'intesection (ensuite par une valeur de distance seuil on considerera que les deux droites se coupe ou pas)

On va maintenant calculer les points de distance minimal entre les deux droites.

Donc considerons deux droites
(D1) = U * r + O1
(D2) = V * s + O2
(où U est le vecteur directeur de D1 et O1 un point de D1,
      V est le vecteur directeur de D2 et O2 un point de D2)

Soit A un point de D1 et B un point de D2
AB² est la distance au carré de A a B, on va donc chercher les parametre r et s pour lesquel cette distance est minimale.
    AB² = AB ¤ AB
(où ...¤... designe le produit scalaire)
    AB² = (AO1 + O1O2 + O2B) ¤ (AO1 + O1O2 + O2B)
           = ( -r * U + K + s * V ) ¤ ( -r * U + K + s * V )
           =  r*r * U¤U + K ¤ K + s*s * V ¤ V +
               - 2*r* U¤K + 2*s* V¤K - 2*r*s * U¤V
(pour des raison de lisibilité, K = O1O2)

    ensuite pour connaitre la distance minimal il faut annuler les deux derivé partielle par raport a r (d(AB²)/dr) et par raport a s (d(AB²)/ds) ce qui nous donnera un systeme de 2 equations a 2 inconues

   d(AB²)/dr = 2*r * U¤U - 2 * U¤K - 2*s * U¤V
   d(AB²)/ds = 2*s * V¤V + 2 * V¤K - 2*r * U¤V

le systeme a resoudre (en r et s) est donc
    2*U¤U  *  r  -  2*U¤V * s  =  2*U¤K
   -2*U¤V  *  r  + 2*V¤V * s  =  -2V¤K

(s'il n'y a pas de solution c'est que les droite sont forcement paralleles)
(il se resoud comme tout systeme lineaire de 2 eq a 2 inconues, ce que j'ai fait dans la page precedente)
on obtient alors les deux parametres r et s qui definissent les point des deux droites ou la distance est minimale
ensuite on obtient aisement la distance
et
pour savoir si ces point sont ou non dans le segment on verifie si 0< r < 1 (par exemple) comme ci-dessus.

Remarque : - si on a deux vecteur U(a,b,c) et V(x,y,z)
                  U¤V = a*x + b*y + c*z
                  - cette methode marche egalement en 2D et meme mieux que la premiere que j'ai donné. cette fois pour U(a,b) et V(x,y) on aura :
                  U¤V = a*x + b*y

Voila j'espere avoir pu t'etre utile...
(et merci pour le compliment)

"Sauf qu'il n'y a AUCUNE chance pour que deux droite de l'espace s'intersepte. Il faut donc calculer le point pour lequel la distance de ces deux droites est minimale, ce que l'on considerera comme point d'intesection (ensuite par une valeur de distance seuil on considerera que les deux droites se coupe ou pas)"

Salut, Neron2005,

Comment peuyx-tu écrire ceci (ta citation) ?
Les chances sont nombreuses, pourvu qu'elles soient dans le même plan.
Elles ne sont quasiment nulles que si elles sont dans deux plans distincts
Elles sont nulles si aucune des deux droites n'a de point d'intersection avec la droite résultant de l'intersection des deux plans.

Non je confirme la proba pour que deux droites de l'espaces prisent au hazard appartiennent a un meme plan est nulle (meme si cela ne veut pas dire que ca ne peut pas arriver).
Par contre dire que les chances sont nombreuses ca c'est une grosse absurdité.
d'autre part pour que deux droites s'interceptent il faut forcement qu'elles soient dans un meme plan.

Je te demande d'analyser et d'expliquer ce que pourrait bien vouloir dire ceci :

citation :

"est nulle (meme si cela ne veut pas dire que ca ne peut pas arriver)."
Nul, c'est nul (donc jamais, dans ce cas) ! et si "ca peur arriver", ce n'est pas "nul"
La pensée commence par son organisation et une bonne organisation de la pensée ne conduit JAMAIS à l'expression de contradictions de la sorte !!!

Faux, faux et archi faux.
Une probabilité nulle n'implique pas qu'un evenement ne peut pas arrivé.
Un exemple tout bete :
Si on joue au flechette, la probablité d'atteindre une certaine zone de la cible vaut la surface de la zone / surface de la cible.
La proba d'atteindre un point, c'est a dire une zone surface nulle, est egale a 0.
Pourtant quand on jette la flechette, on atteint bien un point, et pourtant, la proba qu'on avait d'atteindre ce point particulier etait nulle. Mais c'a s'est produit.

Et dans le cas qui nous concerne la probabilite pour qu'une droite de dimention 1 appartienne a un plan de dimention 2 vaut "1 / infini" = 0

Expose vite la chose aux contrôleurs aériens et envoie-les illico-presto au chômage...
Leur tâche est inutile !

Non mais c'est vrai la proba c'est difficile et je conçois que certaine personne n'y comprenne absolument rien.