1

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ù ?
avatar
Webmaster 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

2

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
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é

3

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]
avatar
Mes news pour calculatrices TI: Ti-Gen
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é

4

Euh... bravo Kevin grin

5

merci beaucoup !
avatar
Webmaster 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