Détecter si deux trajets se croisent

**avigeilpro** · 19/04/2016, 03h04

Bonjour,
Je ne suis pas sûr d'être dans la bonne section, si ce n'est pas le cas je m'en excuse.
Voila, je possède deux paires de coordonnées GPS, disons A, B, C et D. Pour chaque point je connais les coordonnées latitude et longitude. Je cherche à savoir si le trajet A -> B croise le trajet C -> D. Je sais qu'il existe un algorithme assez complexe (du moins pour moi) permettant de calculer le point d'intersection, mais je n'ai pas besoin de connaitre ce point, uniquement si oui ou non les deux se croisent. Je cherche à simplifier la détection car je suis assez limité en temps machine sur le microcontrôleur qui fera le calcul, donc si quelqu'un connait un algorithme qui permet ceci, ou bien simplement une idée.
D'avance merci pour toute aide apportée.

ps : à titre d'information je travail en C++.

**CliffeCSTL** · 19/04/2016, 10h03

Comment définis-tu les trajets entre deux points ?

**avigeilpro** · 19/04/2016, 10h17

Ce sont des lignes "droites" (des arcs en réalité vu la courbure de la terre). Ce n'est pas un trajet qui suit des routes ou autres.

**wiwaxia** · 19/04/2016, 10h18

Bonjour,

C'est un problème de trigonométrie sphérique. La position de tout point (M) de la surface terrestre étant définie dans un repère géocentrique direct dont le premier axe (Ox) passe par le point de l'équateur de longitude nulle, et le troisième (Oz) par le pôle Nord, ses coordonnées cartésiennes s'expriment en fonction de longitude (Phi) et latitude (Theta) par les relations:
x_M = R*cos(Theta)*cos(Phi) ,
y_M = R*cos(Theta)*sin(Phi) ,
z_M = R*sin(Theta) .

L'arc (AB) appartient à un cercle équatorial de la sphère terrestre, de normale: N_AB = OA×OB ,
l'arc (CD) appartient à un autre cercle équatorial de normale: N_CD = OC×OD ,
en supposant leurs extrémités (A,B et C,D) non diamétralement opposées.

Si de plus les quatre points (A, B, C, D) ne sont pas coplanaires - ce qui conduirait à deux vecteurs (N_AB, N_CD) colinéaires - alors il existe deux points d'intersection (I et J), extrémités du diamètre commun aux deux cercles et simultanément orthogonal aux vecteurs (N_AB) et (N_CD).
L'orientation dans l'espace de la droite (IJ) est donnée le produit vectoriel N₁ = N_AB×N_CD ; en convenant de noter (N₁) la norme ║N₁║ de ce dernier vecteur, on parvient à exprimer la position des points d'intersection par la relation: OI (ou OJ) = ±(R / N₁)*N₁ .

Reste à déterminer les angles polaires correspondants, permettant de situer les points d'intersection relativement aux extrémités des arcs (AB) et (CD), par l'exploitation appropriée les produits scalaires et vectoriels:
OA·OI = R²*cos(i_A) ; ║OA×OI║ = R²*│sin(i_A)│ ;
OA·OJ = R²*cos(j_A) ; ║OA×OJ║ = R²*│sin(j_A)│ .

Une réponse d'une concision remarquable a été apportée à un problème voisin, lors d'un échange récent sur un grand forum pour développeurs.

**CliffeCSTL** · 19/04/2016, 10h39

Tu considères la terre comme une sphère ou une ellipsoïde ?

**wiwaxia** · 19/04/2016, 12h07

Comme une sphère de rayon R. C'est assez compliqué comme ça !

C'est un problème de trigonométrie sphérique ...
... L'arc (AB) appartient à un cercle équatorial de la sphère terrestre ...

L'essentiel, c'est de savoir bien lire un texte.

**avigeilpro** · 19/04/2016, 14h51

Merci wiwaxia pour toutes ces informations, je vais prendre le temps d'essayer de comprendre tout ça. je reviendrais si quelque chose m'échappe.

**souviron34** · 19/04/2016, 14h54

Une solution plus simple (je pense )

Je pense que le PO ne parle pas dans l'absolu (trigo sphérique ou ellipsoidique) mais par rapport à une certaine vue ou projection..

Dans ce cas, le meux est de transformer les coordonnées en coordonnées rectangulaires avec les équations adhoc, vérifier si les segments s'intersectent...

Mais peut-être que je me trompe....

**Nebulix** · 19/04/2016, 17h13

Sur une sphère les "droites" sont des grands cercles et deux "droites" se coupent toujours en 2 points opposés.
Wiwaxia a bien décrit le calcul des points d'intersection. Faut-il voir s'ils sont dans les plus courts des deux segments de chaque paire de points ?
@souviron : si les deux points ne sont pas très proches, la "droite" en projection Mercator est une courbe compliquée ...