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ù ?
avatarWebmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca
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.
avatarMes news pour calculatrices TI: Ti-Gen (fr/en), MobiFiles (de)
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité
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]
avatarMes news pour calculatrices TI: Ti-Gen (fr/en), MobiFiles (de)
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité
Euh... bravo Kevin grin
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !
merci beaucoup !
avatarWebmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca