Discussion :

[bakonu]

Bonjour,

Voilà, j'ai besoin de faire un algo qui prend en paramètres 2 segments, dont les point sont connus. Cet algo doit vérifier si les 2 segments se chevauchent partiellement ou non (s'ils se croisent, ça ne compte pas), et si tel est le cas, supprimer la partie se chevauchant pour en ressortir un ou deux nouveau segments.

Mon problème est que, je ne me rappelle plus du tout de mes cours de math

Je vois à peu près comment ressortir le ou les nouveau(x) segment(s), cependant je ne vois pas comment vérifier si deux segments se chevauchent ou non.

[oiffrig]

Le mieux à faire à mon avis pour savoir si les segments se chevauchent c'est de tester dans un premier temps si les extrémités sont alignées (produit vectoriel nul, ...), et dans un deuxième temps, de raisonner en termes de distances algébriques (à l'aide de produits scalaires ?)

[Zavonen]

Ce problème est-il dans le plan dans l'espace ????
Que signifie ils se 'croisent' ?

[bakonu]

j'ai résolu en grande partie le problème, désolé de ne pas avoir répondu depuis.

1. Je vérifie que les équations de mes 2 segments (ax + b) sont identiques.

2. je vérifie si l'extrémité d'un des 2 segments est sur l'autre segment (par les x et les y).

3. si tel est le cas, j'en ressort mes nouveaux segments voulus.

[oiffrig]

Qu'est-ce qui te manque encore alors ?

Attention quand même avec les équations de la forme y = ax + b, si la droite est verticale ça ne marchera pas.
Pour tester l'alignement tu peux calculer un déterminant: (x-x')(y-y") - (x-x")(y-y'), égal à 0 si les points de coordonnées (x, y), (x', y'), (x", y") (en repère orthonormé) sont alignés.
Après, pour connaître l'ordre d'alignement il te suffit de comparer leurs coordonnées.

Cela t'évite de calculer des équations de droite, et aussi de diviser par 0.

[souviron34]

une autre solution est de calculer les angles en prenant un segment et un sommet de l'autre.

Si les 2 angles sont 180 degrés, c'est fini..

[TanEk]

Un algo tiré tout droit du Cormen, savoir si deux segments p1p2 et p3p4 s'intersectent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
INTERSECTION-SEGMENTS(p1,p2,p3,p4)
d1 = DIRECTION(p3,p4,p1)
d2 = DIRECTION(p3,p4,p2)
d3 = DIRECTION(p1,p2,p3)
d4 = DIRECTION(p1,p2,p4)
 
si ((d1>0 et d2 < 0) ou (d1 < 0 et d2 > 0)) et
         ((d3 > 0 et d4 < 0) ou (d3 < 0 et d4 > 0)
              alors retourner VRAI
sinon si d1 = 0 et SUR-SEGMENT(p3,p4,p1)
        alors retourner VRAI
sinon si d2 = 0 et SUR-SEGMENT(p3,p4,p2)
        alors retourner VRAI
sinon si d3 = 0 et SUR-SEGMENT(p1,p2,p3)
        alors retourner VRAI
sinon si d4 = 0 et SUR-SEGMENT(p3,p4,p4)
        alors retourner VRAI
        sinon retourner FAUX
 
DIRECTION(pi,pj,pk)
   retourner (pk - pi) x (pj - pi)
 
où x est le "produit vectoriel" de p1xp2 (le determinant dans ce cas de [p1 p2] = x1*y2 - x2*y1)
 
SUR-SEGMENT(pi,pj,pk)
   si min(xi,xj) <= xk <= max(xi,xj) et min(yi,yj) <= yk <= max(yi,yj)
         alors retourner VRAI
         sinon retourner FAUX