+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Intersection de segment (/showthread.php?tid=3822)
Intersection de segment - Argorate - 23-03-2009
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 :
![[Image: intersection.PNG_u1237794921.png]](http://upload.jeuweb.org/uploaded/intersection.PNG_u1237794921.png)
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.
RE: Intersection de segment - Mycroft - 23-03-2009
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
)
RE: Intersection de segment - keke - 23-03-2009
(23-03-2009, 10:25 AM)Mycroft a écrit : 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é
RE: Intersection de segment - Argorate - 23-03-2009
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?
RE: Intersection de segment - Mycroft - 23-03-2009
(23-03-2009, 10:54 AM)Argorate a écrit : 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.
}
}Citation :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.
Citation :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.
RE: Intersection de segment - Argorate - 23-03-2009
(23-03-2009, 11:02 AM)Mycroft a écrit :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
(23-03-2009, 11:02 AM)Mycroft a écrit : Pas besoin : tu calcules ta solution (x;y) pour tous les cas, c'est juste deux opération arithmétiques.C'étais ce dont je parlais pour les verifs a faire^^
Et ensuite tu vérifies bien que SegmentAmin < x < SegmentAmax et SegmentBmin < x < SegmentBmax.
Bref, rien de neuf quoi
RE: Intersection de segment - keke - 23-03-2009
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/physique-1/d/un-nouveau-test-pour-la-theorie-des-cordes_10292/
Juste à côté, une pub ciblé pour savoir comment supprimer ses maux de tête ^^. Mathémigraine ???