Discussion :

[tnarol]

Salut,

Je cherche l'algorithme le plus rapide en moyenne pour déterminer si un clic de souris défini par ses coordonnées est à proximité d'un segment défini par les coordonnées de ses deux extrémités. A priori la "proximité" se définit par une distance au segment inférieure à une constante, mais on peut l'adapter à l'algo si nécessaire du moment que ça ne change pas l'intuition qu'on en a.

Merci

[Sylvain Togni]

Il suffit de calculer la distance entre le point et le segment.
exemple

[tnarol]

Il suffit de calculer la distance entre le point et le segment.
exemple

Merci c'est très utile !

Mais pensez vous que l'approche suivante soit valable pour optimiser le temps de réponse moyen :

commencer par construire un rectangle élargi autour du segment, puis regarder l'intersection du point avec l'intérieur ce rectangle et seulement en cas d'intersection regarder la distance de plus près...

[Sylvain Togni]

Oui, c'est une optimisation classique pour ce genre de problème.

[souviron34]

et tu peux même décomposer en évitant éventuellement des comparaisons :

rectangle x1,y1 x2,y2 x3,y3 x4,y4

XMI = xmin-marge
YMI = ymin - marge
XMA = xmax+marge
YMA = ymax+marge

si x < XMI ou x > XMA
rien
si y < YMI ou y > YMA
rien

sinon intersection....

[tnarol]

et tu peux même décomposer en évitant éventuellement des comparaisons :

rectangle x1,y1 x2,y2 x3,y3 x4,y4

XMI = xmin-marge
YMI = ymin - marge
XMA = xmax+marge
YMA = ymax+marge

si x < XMI ou x > XMA
rien
si y < YMI ou y > YMA
rien

sinon intersection....

OK merci beucoup je vais faire ça.