Matheux, besoin de vous!

Recherche :

Dernière réponse
Sujet : Matheux, besoin de vous!
shinji	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. :)

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

shinji

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.

:)

youdontcare

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

youdontcare

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.

bjone

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

bjone

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

shinji

Voilà les seuls commentaires du site:

Citation :

On cherche à savoir si l'angle P1P0P2 > 0 ?

En calculant le produit vectoriel P0 P1 Ù P0 P2. Si l'angle est nul, par convention on compare les normes.

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

Citation :

En théorie, le produit vectoriel en 2D te donne pour 3 points, les
coordonnées du 4ème pour faire un parallèlogramme ! En fait, si tes
points
sont A, O, et B, le produit vectoriel OA par OB te donne le vecteur OC
de
manière à avoir : OACB est un parallèlogramme.

En fait si je comprend bien ce qu'il fait, il cherche à savoir de quel
coté
d'un segment se trouve un point donné. C'est quelque chose du genre :
Je caclule le vecteur OC, si sa valeur algébrique (Longueur orientée !)
est
nulle, les point sont allignés, si elle est positive, le point est
(mettons
!) à droite et si elle est négative, à gauche. Je dis pas que c'est
éxactement çà, mais c'est l'idée. Ensuite si par raport à un segment,
les
deux points de l'autre segments de sont pas du même coté (et
réciproquement), c'est que les segments sont séquants !

shinji

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

bjone

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

shinji

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!