Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Intersection de 2 segments

Posté par Alaseconde (invité) 19-02-05 à 19:29

Bonjour

Pour faire une analyse de trajectoire j'ai besoin de savoir si deux segments de droite se coupent. Mes souvenirs de géomérie étant lointain, quelqu'un aurait'il une idée sur la méthode la plus rapide pour comparer deux segments finis.
ex:  A(xa,ya)B(xb,yb) coupe t'il C(xc,yc)D(xd,yd)

Merci

Posté par
Nightmare
re : Intersection de 2 segments 19-02-05 à 19:31

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

Posté par Alaseconde (invité)re : Intersection de 2 segments 19-02-05 à 20:08

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.

Posté par
isisstruiss
re : Intersection de 2 segments 19-02-05 à 21:28

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
\|\array{X_a&Y_a&1\\X_b&Y_b&1\\X_c&Y_c&1\\}\|>0
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

Posté par Alaseconde (invité)re : Intersection de 2 segments 20-02-05 à 14:27

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

Posté par Alaseconde (invité)re : Intersection de 2 segments 20-02-05 à 20:11

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

Posté par Dasson (invité)re : Intersection de 2 segments 20-02-05 à 20:31

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.

Posté par Alaseconde (invité)re : Intersection de 2 segments 20-02-05 à 20:48

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

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

Posté par Dasson (invité)re : Intersection de 2 segments 20-02-05 à 22:14

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.

Posté par
isisstruiss
re : Intersection de 2 segments 20-02-05 à 23:05

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

Posté par Alaseconde (invité)re : Intersection de 2 segments 21-02-05 à 13:28

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

Posté par
isisstruiss
re : Intersection de 2 segments 21-02-05 à 14:01

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



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1478 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !