Bonjour

Euh , je ne connais pas de formule typique pour ça mais ce que tu peux faire c'est donner l'équation des deux droites contenant les segments . Tu calcules leur point d'intersection et tu regardes si il appartient au segment


Jord

Merci pour cette réponse

J'avais pensé à cette méthode mais la routine doit être utilisée pour comparer + de 10000 segments et cela va demamder un grand nombre de calcul. Si une astuce permettait de ce passer du calcul du point d'intersection, le traitement serait plus rapide.

Pour tester l'intersection de deux segments s1=(d1,f1) et s2=(d2,f2), il suffit de voir si
d1 et f1 sont de part et d'autre du support de (d2,f2) et
d2 et f2 sont de part et d'autre du support de (d1,f1).

Pour voir si C est à gauche du segment AB, l'aire signée du triangle ABC sera positive, c-à-d

Si C est à droite de AB ce déterminant sera négatif.

La méthode directe qui teste chaque paire de segments est en O(n²) et plutôt longue, c'est clair. Il y a une méthode de balayage en O((n+k)log(n)), avec n le nombre de segments et k le nombre d'intersections, qui est assez avantageuse quand il y a peu d'intersections.

Cet algorithme s'appelle Bentley-Ottman. L'idée est de trier les segments par rapport à leur ordonnée puis de balayer ces extrémités par rapport à leur ordonnée et ne tester l'intersection que pour des segments voisins. Tu trouveras très probablement plus d'infos en cherchant Bentley-Ottman sur Google par exemple.

Isis

Je dois donc faire l'analyse du calcul de 4 triangles pour vérifier si j'ai intersection
T1=C/[AB]
T2=D/[AB]
T2=A/[CD]
T4=B/[CD]

Intersection si (T1*T2<0) et (T3*T4<0)

Cette méthode est peut être plus rapide, je vais tester

La méthode est efficace en fait il faut vérifier si (T1*T20) et (T3*T40)

Il reste toutefois une incertitude lorsque les deux produits sont égales à zéro. Cela correpond à des points alignés. Il me faut donc tester si un des 2 points appartient au segment.
J'y arrive en vérifiant que la distance AB-(AC+CB)=0 mais cela demmande de nombreux calculs.
N'existe'il pas une solution plus simple de connaitre l'appartenance d'un point à un segment

Merci

Bonjour,
M]AB[ ssi AM=kAB et 0<k<1
M]CD[ ssi AM=lAB et 0<l<1
Il est possible de calculer k et l en fonction des coordonnées de A, B, C, D puis de tester les conditions su k et l : programmable.

M[CD] ssi AM=lAB et 0<l<1 ?

Je comprend pas bien comment calculer les facteurs k et l ?

x+k(xa-xb)=xa
x+l(xc-xd)=xc
D'où une équation d'inconnues k et l.
Avec les y, on obtient de même une autre équation en k et l.
Système en k, l à résoudre (en utilisant plutôt des déterminants (Cramer)).
A vérifier.

Mon avis très très personnel est qu'il ne faut pas réinventer la roue. Il y en a qui ont bossé dur pour inventer des algorithmes efficaces et si tu veux que ton programme tourne rapidement, autant appliquer ces algos.

C'est très intéréssant de comprendre comment ils marchent et les implémenter dans le cas particulier que l'on rencontre, mais dans le cas général il ne faut pas hésiter à chercher les codes en accès libres si cela évite des heures de programmation, de débuggage et des heures d'éxécution parce que l'on n'a pas programmé de manière efficace.

Par exemple la bibliothèque LEDA propose des fonctions rapides et sans bug prêtes à l'emploi pour ce type de problème, mais la licence n'est pas gratuite. Autrement il a d'autres gens qui proposent leur code en C++ ou java le plus souvant et que l'on peut utiliser selon les règles GPL.

Ces algos évitent de tester l'intersection pour chaque paire de segments et ceci diminue sensiblement le temps d'éxécution.

Isis

Merci pour ces infos

J'ai consulté le site de LEDA, je ne vois pas explicitement de librairie qui couvre mon besoin.
J'ai en fait un trajet de mémorisé par les coordonnées GPS toutes les secondes. Ma recherche consiste à trouver les segments ou il y a croisement des trajectoires (normalement il ne doit pas y en avoir)
Ce dévellopement n'est pas commerciale mais GPL et je ne peux utiliser de tel sources. J'ai cherché dans les sources GPL mais il est difficile de trouver des algo aussi spécifique sans clé de recherche adéquate.

Merci de ton aide

Pour LEDA je comprends que le fait que ce soit payant est embêtant. Voici tout de même un lien:

Voici un site qui propose l'algo en GPL implémenté en Java

Je n'ai rien trouvé de très intéréssant en C++ (ça devrait être plus rapide que Java), mais les mots clés les plus indiqués pour la recherche sont le nom des algorithmes. Voici une page regroupant les 3 algorithmes pour l'intersection de segments de droite:

Isis