Posté le 24/09/2015 à 15:05 Membre depuis le 11/11/2001, 116497 messages
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
Posté le 24/09/2015 à 17:29 Membre depuis le 10/06/2001, 40275 messages
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é
Posté le 24/09/2015 à 17:36Edité par Kevin Kofler le 25/09/2015 à 00:23 Membre depuis le 10/06/2001, 40275 messages
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é
Posté le 24/09/2015 à 17:46 Membre depuis le 18/06/2001, -26078 message
Euh... bravo Kevin grin
avatar<<< Kernel Extremist©®™ >>>
Feel the power of (int16) !
Posté le 24/09/2015 à 18:43 Membre depuis le 11/11/2001, 116497 messages
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