J'ai trouvé 2 fonctions qui permettent de savoir si 2 segments se croisent. Elles utilisent apparement le produit vectoriel. Seulement j'aimerais bien comprendre comment elles marchent, quel est le but de chacune d'elles, le lien, bref l'algo.
 
Ce serait super sympa, merci!
 
Intersect est la fonction principale, il faut lui fournir les 8 coordonnées qui constituent les extrémités des segments (4 points x 2 coordonnées) dans l'ordre logique.
ex: segments [AB],[CD]:
intersect(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy);
 
function ccw ( $p0x, $p0y, $p1x, $p1y, $p2x, $p2y){
 $dx1 = $p1x - $p0x;
 $dy1 = $p1y - $p0y;
 $dx2 = $p2x - $p0x;
 $dy2 = $p2y - $p0y;
 
 if( $dx1 * $dy2 > $dy1 * $dx2 ) return 1;
 else if( $dx1 * $dy2 < $dy1 * $dx2) return -1;
 else{
      if( $dx1 * $dx2 < 0 || $dy1 * $dy2 < 0 ) return -1;
      else if( $dx1 * $dx1 + $dy1 * $dy1 >= $dx2 * $dx2 + $dy2 * $dy2 ) return 0;
      else return 1;
 }
}
function intersect( $p1x, $p1y, $p2x, $p2y, $p3x, $p3y, $p4x, $p4y){
return( ccw ( $p1x, $p1y, $p2x, $p2y, $p3x, $p3y) * ccw ( $p1x, $p1y, $p2x, $p2y, $p4x, $p4y) <= 0 ) && ( ccw( $p3x, $p3y, $p4x, $p4y, $p1x, $p1y) * ccw( $p3x, $p3y, $p4x, $p4y, $p2x, $p2y) <= 0 );
}
 
Merci beaucoup!

ccw => counter clock wise ?
je suis en pleine digestion, mais on dirait que ccw retourne 1 si les points p0,p1,p2 sont dans le sens contraire des aiguilles d'une montre (sens trigo).... (et -1 inversement, ptet 0 quand 2 points sont confondus)
 
ça me fait mal au crâne..........
apparemment, 4 couples de "triangles" sont testés d'un point de vue ccw, et dont si un des 4 quatres ccw retourne 0 y'a pas intersection (m'enfin on obtient pas le point d'intersection avec ce code, y'aurait ptet mieux approche)
fodrait faire des dessins beuhhhhh

bjone-> j'essaye une approche par les angles!
C'est horrible ce truc mais je dois savoir comment ça marche! Le pire c'est que ça marche d'enfer.
 
Voici le site où j'ai trouvé le code mais aucune explications:
http://www.enseignement.polytechni [...] 0/a10.html

Voilà les seuls commentaires du site:

 
 
Voilà ce que quelq'un m'a répondu aussi, ça devrait aider:

ouaip, l'idée ça doit être ça..... fodrait passer du temps, sinon moi pour calculer une intersection entre 2 segments (dans la pratique, genre un missile qui change de position / mur), je ferais une projection des points d'un segment sur l'autre (ancienne & nouvelle position missile => sur segment de mur), tu peux alors en déduire les coordonnées du point d'intersection....
tu veux quoi savoir seulement si y'a intersection (& uniquement ça, dans ce cas cette routine peut être idéale), mais si tu veux ensuite la coordonnée du point d'intersection, fo changer d'approche je pense....

m'enfin ce que j'en dis, j'ai aps fait polytechnique

l'algo est tout joli ! en cas d'intersection, les segments [AB] et [CD] formeront les diagonales du quadrilatère ABCD ou ABDC, suivant l'organisation des points.
 
le but de l'algo est de tester si :
 
* les points C et D sont de part et d'autre de (AB)
* la même chose pour l'autre segment : si les points A et B sont de part et d'autre de (CD)
 
si ces deux conditions sont remplies, les segments s'intersectent.
 
ccw(point a, point b, point c) renvoie 1 si l'angle (bac) > 0, -1 s'il est < 0. (et 0 par convention, regarde la fonction, là au moins c'est expliqué)
 
comment tester si C et D sont de part et d'autre de (AB) ?  
deux cas :
* si l'angle (bac) > 0 et l'angle (bad) < 0
* si l'angle (bac) < 0 et l'angle (bad) > 0
 
soit  
* si ccw(abc) = 1 et ccw(abd) = -1
* si ccw(abc) = -1 et ccw(abd) = 1
 
ce qui se ramène à ccw(abc) * ccw(abd) <= 0  
 
pareil pour tester si A et B sont de part et d'autre de [CD].
 
// j'ai peut-être confondu l'ordre des angles (bac et non pas abc ou je ne sais quoi), mais ça ne change rien au raisonnement.

j'oubliais : si tu as du mal à comprendre, qq figures aident beaucoup.

Merci les gars!
 
bijone-> C'est juste pour savoir s'il y a intersection. J'ai pas besoin des coordonnées du point d'intersection.