vince 2015-09-24 at 03:05pm 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 2015-09-24 at 05:36pmEdited by Kevin Kofler On the 2015-09-25 at 12:23am 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]
