Envoyé par
ben.oeilnoir
Pour tout ceux qui tombent sur ce topic à la recherche d'un algo d'intersection, je tiens à dire que celui qui est donné plus haut n'est pas fiable à 100%, comme la plupart. Il est vrai que le probleme de l'intersection n'est pas trivial. Voici une explication et un début de solution :
D'abord, crois-tu être meilleur que ce qui est déposé sur Computational Geometry, où les meilleurs de la planète participent depuis plus de deux décennies ???
D'autre part, alors que je fais un usage intensif de la fameuse routine dont j'ai donné le lien ci-dessus, je ne l'ai jamais vu dysfonctionner depuis plus de 20 ans... Alors que je m'en sers plus de 10 000 fois par jour...
Il y a bien 2 divisions, mais le test :
if ( (r > 0.0) && (r < 1.0) && (s >= 0.0) && (s <= 1.0) )
donne bien la bonne solution.
Envoyé par
ben.oeilnoir
- Premièrement :
L'algorithme ne gère pas la plupart des cas de colinéarité. Pour rappel, deux droites sont colinéaires lorsqu'elles ont deux points en commun (elles sont "alignées", quoi). De plus, deux droites colinéaires sont effectivement sécantes, en une infinité de points. La réponse "NULL" est donc très discutable.
- Deuxièmement :
L'algorithme ne gère pas le cas des droites parallèle, ce
Si on a besoin d'une fonction pour chercher des intersections, ce n'est pas pour savoir si les droites sont parallèles ou confondues. Il y a des moyens plus simples.
D'autre part, la fonction indiquée est suffisante, il suffit de modifier les critères sur r et s.
Comme vient de le dire ac_wingless (et tel que c'est mentionné dans les liens donnés), évidemment en informatique il y a un problème d'exactitude et d'arrondi.
C'est toute la différence entre les maths pures et les maths appliquées.
Si on veut tenir compte des imprécisions, il suffit d'ajouter (ce que je fais dans mes tests) des "marges" dépendant de la précision attendues :
if ( (r > ACCURACY) && (r < (1.0-ACCURACY)) && (s >= -ACCURACY) && (s <= (1.0+ACCURACY)) )
Cependant je prend ton post pour de la publicité pour ton soft, et à ce titre je souhaiterais qu'il soit supprimé, car encore une fois je n'ai pas dans mon expérience pu mettre en défaut la routine mentionnée..
Quant à la question de savoir si un point est à gauche ou à droite d'un segment, une excellente publication il y a peu (2000), a donné une solution élégante et plus simple que la fameuse routine ccw de Sedgewick :
http://softsurfer.com/Archive/algori...rithm_0101.htm
PS: et le coût de 2 divisions est inférieur de loin à éxécuter 4000 lignes de code..
Partager