Intersection de segment

[Argorate]

Bonjour,

Je suis entrain de voir pour créer une petite application en VB dans lequel je reli chacun des points que je créé entre eux, mais j'ai besoin de detecter les intersections pour ne pas dessiner les segments qui coupent les autres, comme ceci :



J'ai le x;y des points, donc les équations des droites.
Je sais le résoudre sur un papier mais pour le faire faire par un pc, j'ai du mal, vous connaissez la démarche a suivre?

Merci.

[Mycroft]

Je réponds naïvement il y a peut être des meilleurs solutions :

Si tu connais :
ax + b = y
cx + d = y

Tu peux résoudre pour l'intersection:
y = (ad -bc) / (c -a)
si a != 0 et c != a
et en déduire de même x = (d -b)/(a-c).

(Si c == a les droites sont parallèles donc à moins d'être confondu il n'y a pas de solution.)

Ca c'est une solution pour des droites, comme tu travailles sur des segments si ta paire de résultat (x;y) n'appartient pas au segment, il n'y a pas d'intersections.

(A vérifier les calculs parce que j'ai fait ça vite fait )

[keke]

y = (ad -bc) / (c -a)
si a != 0 et c != a

Enfait, si "c" != "a" est suffisant car "a" peut être égal à 0 si tu le souhaites.

Pour le reste, Mycroft, tu as tout bon ^^.

Kéké

[Argorate]

Oui j'ai deja pensé a tout ça, le probleme c'est que si les droites sont parallele, il faut verifier quel ne sont pas confondu, si elles ne le sont pas, cela peut faire un nouveau chemin...

Vu que c'est des segments, il faut verifier que les deux points du chemins A sont pas comprit entre les deux points du chemin B.

Ce qu'il y a, c'est que je trouve ça long et fastidieu, je voulais savoir si il n'existait pas quelques chose de plus simple?

[Mycroft]

Oui j'ai deja pensé a tout ça, le probleme c'est que si les droites sont parallele, il faut verifier quel ne sont pas confondu, si elles ne le sont pas, cela peut faire un nouveau chemin...

C'est pas très long et fastidieux à tester ça :

Code :

if (a == c) // les droites sont parrallèles
{
   if(b == d)
   {
      // droites parrallèles et confondus
   }else
   {
     // droites parrallèles distinctes pas de solution.
   }  
}

Vu que c'est des segments, il faut verifier que les deux points du chemins A sont pas comprit entre les deux points du chemin B.

Pas besoin : tu calcules ta solution (x;y) pour tous les cas, c'est juste deux opération arithmétiques.

Et ensuite tu vérifies bien que SegmentAmin < x < SegmentAmax et SegmentBmin < x < SegmentBmax.

Ce qu'il y a, c'est que je trouve ça long et fastidieu, je voulais savoir si il n'existait pas quelques chose de plus simple?

L'algo c'est deux operations arithmétiques, plus trois ou quatre tests de conditions. C'est pas très complexe. Mais bon je m'avance pas, il y a peut être encore plus simple.

[Argorate]

Code :

if (a == c) // les droites sont parrallèles
{
   if(b == d)
   {
      // droites parrallèles et confondus
   }else
   {
     // droites parrallèles distinctes pas de solution.
   }  
}

oui comme ça çà a a l'air simple

Pas besoin : tu calcules ta solution (x;y) pour tous les cas, c'est juste deux opération arithmétiques.

Et ensuite tu vérifies bien que SegmentAmin < x < SegmentAmax et SegmentBmin < x < SegmentBmax.

C'étais ce dont je parlais pour les verifs a faire^^

Bref, rien de neuf quoi

[keke]

Ben, si tu manipules des matrices (au sens mathématique du terme), je me rappelle vaguement qu'il y avait des fonctions qui auraient pu correspondre à ton cas. C'est des éléments comme ça qui permet d'optimiser les calculs lié à la collision de 2 objets en 3D.

De manière récusable à volonté et sans arriver à retrouver mes sources, si le produit de 2 matrices donne une matrice XXXXX, alors les espaces représentés par les matrices sont sécants. (j'ai dit XXXXX, ça aurait pu être orthogonale ou polaire tellement j'ai oublié la formule).

Les matrices pouvant représenter des vecteurs 2D, 3D, 4D, nD ...

Kéké
PS : J'en sais pas plus ^^
PS : en cherchant un exemple, je suis tombé sur cette page là.
http://www.futura-sciences.com/fr/news/t...des_10292/
Juste à côté, une pub ciblé pour savoir comment supprimer ses maux de tête ^^. Mathémigraine ???