vince Le 24/09/2015 à 15:05 Je cherche à faire un test d'intersection booléen "performant". J'ai un point A avec ses coordonnées x et y, idem pour les points B, C et D.
J'ai juste besoin de savoir si le segment AB croise le segment CD, je cherche la performance et les seuls algos que j'ai trouvé se basent sur les maths pour tenter de trouver le point I, avec les coordonnée de l'intersection.
Connaissez vous une solution avec le moins de calculs possible (surtout les divisions) qui permette de tester si AB croise CD, peut importe où ?
Les droites (AB) et (CD) découpent chacune le plan en 2 demi-plans.
Si A et B sont de part et d'autre de (CD), alors (AB) n'est pas parallèle à (CD), donc I existe, et I appartient au segment [AB].
Si C et D sont de part et d'autre de (AB), alors (AB) n'est pas parallèle à (CD), donc I existe, et I appartient au segment [CD].
Donc si on a les deux, [AB] et [CD] se coupent (en le point I, qui ne doit pas être calculé explicitement).
Pour trouver "de part et d'autre", si tu as les droites sous la forme f(x,y)=0, alors c'est un simple changement de signe, trivial à tester.
Une manière de calculer cette équation est de prendre la fonction vecteur normal n(u) qui à (xU,yU) associe (yU,-xU). Alors l'équation de (AB) est f(u)=(u-A).n(AB)=0 (produit scalaire) et les 2 demi-plans sont f(u)<0 et f(u)>0.
Kevin Kofler Le 24/09/2015 à 17:36Edité par Kevin Kofler le 25/09/2015 à 00:23 Version TL;DR:
result = ((((xC-xA)*(yB-yA)+(yC-yA)*(xA-xB)<0)^((xD-xA)*(yB-yA)+(yD-yA)*(xA-xB)<0)) && ((xA-xC)*(yD-yC)+(yA-yC)*(xC-xD)<0)^((xB-xC)*(yD-yC)+(yB-yC)*(xC-xD)<0));
sous réserve que les cas où le point d'intersection est exactement A, B, C ou D ne sont pas gérés par cette version.
[EDIT: fautes d'accord dans le texte corrigées]
