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

Question

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

Neron2005 · Answer

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)

Neron2005 · Answer

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)

jmf0 · Answer

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

Neron2005 · Answer

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.

jmf0 · Answer

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

Neron2005 · Answer

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.

Neron2005 · Answer

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

jmf0 · Answer

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

Neron2005 · Answer

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

jmf0 · Answer

Et ta flêchette ne se termine pas par un point, mais par une surface, et elle frappe une surface, aussi petite fût-elle.
Je regrette beaucoup, mais le sujet est bien le point d'intersection et non le point le plus proche entre deux droites... et les droites, comme le point, n'ont pas d'épaisseur.... !:
Boinne nuit.

Neron2005 · Answer

que la flechette se termine par un point ou par une surface c'est la meme chose. la proba que toute la surface de la flechette soit exactement egale a une meme surface de la cible est quand meme nulle.Mais bon pour revenir a mes plans et mes droites il y a dans tous l'espace un infini ^ 3 points possible dans un plan il y a un infini ^ 2 points possible et dans une droite il y a un infini point possible, si tu fait le quotient pour trouver quelle est la proba pour que tous les points de la droites (infini) soit dans un plan precis (infini ^ 2)  tu trouve P infini / (infini ^ 2) 0. 
Sans vraiment de rigueur on trouve que la proba qu'une droite soit contenue dans un plan est nulle.
D'autre part pour les controleurs aeriens ne trouverons jamais de proba nulle et pour te donner un exemple la proba qu'un electron lie a un atome, qui se trouverais sur terre, se retrouve a l'autre bout de la galaxie est non nulle.
Maintenant si tu considere une infinite de valeur la proba d'en choisir une en particulier est nulle. Et si ca tu peux pas le comprendre et bien tant pis pour toi. Moi je sais que j'ai raison et sur ceux bonne nuit.

jmf0 · Answer

Tu as sûrement raison ....

Je dois alors être le roi des chanceux car (ainsi que mes autres collègues chasseurs) :
Ô combien de canards, combiens de perdrix, combien de lièvres et combien d'autres ... à poils ou à plumes ... ont eu l'énorme malchance, en dépit de la probabilité d'y échapper... de suivre une trajectoire qui était celle des projectiles...

Bon... c'est maintenant vrai :
- pour les canards : à peine 7 sur 10 "descendus" (pour les meilleurs d'entre nous)
- mais pour les perdrix : quasiment 10/10 "descendues"

C'est à croire que nous étions les dieux de la maîtrise de la probabilité.

Mais redescendons (sans jeu de mots par rapport aux "descendus" de la chasse) sur terre, vite fait bien fait :
Il ne s'agit pas (ce sujet) de calcul de probabilité et/ou de savoir si la probabilité est proche ou non de zéro, mais bien de déterminer, s'il existe, les coordonnées du point d'intersection de deux droites.
On peut toujours :
- soit démontrer que les deux droites n'en ont pas
- soit (s'il existe), en calculer les coordonnées.

J'imagine fort simplement et tout bêtement que notre ami demandeur pose une telle question car il met en place un mécanisme de détermination de collisions, un point (toujours sans jeu de mots) c'est tout. Et la collision existe ou n'existe pas ! Elle n'est certes pas l'absence de collision remplacée par je ne sais quoi qui serait la distance minimum constatée, en tel et tel autre point de deux trajectoires, entre deux trajectoires.
Je suggère que l'on attende les explications du demandeur sur la finalité de sa demande, afin d'éviter ce genre d'égarement...

Neron2005 · Answer

Oui, c'est exactement ca. 
Mais ce que je voulais dire au debut, c'est que dans l'espace si on prends deux droites n'importe comment, la plus part du temps et meme toujours, ces deux droite n'auront pas de point d'intersection, il serait donc inutile de developper un code pour gerer une telle situation. Maintenant l'avantage de ma sollution de plus petite distance est de permetre une marge d'erreur quant a la collistion des deux droites (si elle ne sont pas dans le meme plan mais presque) qui serait alors d'une probabilité plus qu'acceptable.
De toute facon cette methode marche encore lorsque les droite se coupe car le point de moindre distance serait alors le point de distance nulle.

Intersection de droites mais avec en plus des infos supplémentaires sur le point

13 réponses

Votre réponse

Discussions similaires