Détecter si deux trajets se croisent
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++.
Detecter si deux trajets se croisent.
Bonjour, :D
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:
xM = R*cos(Theta)*cos(Phi) ,
yM = R*cos(Theta)*sin(Phi) ,
zM = R*sin(Theta) .
L'arc (AB) appartient à un cercle équatorial de la sphère terrestre, de normale: NAB = OA×OB ,
l'arc (CD) appartient à un autre cercle équatorial de normale: NCD = 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 (NAB, NCD) 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 (NAB) et (NCD).
L'orientation dans l'espace de la droite (IJ) est donnée le produit vectoriel N1 = NAB×NCD ; en convenant de noter (N1) la norme ║N1║ de ce dernier vecteur, on parvient à exprimer la position des points d'intersection par la relation: OI (ou OJ) = ±(R / N1)*N1 .
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 = R2*cos(iA) ; ║OA×OI║ = R2*│sin(iA)│ ;
OA·OJ = R2*cos(jA) ; ║OA×OJ║ = R2*│sin(jA)│ .
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.
Detecter si deux trajets se croisent.
Comme une sphère de rayon R. C'est assez compliqué comme ça !
Citation:
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. :mrgreen:
Détecter si deux trajets se croisent.
Citation:
Envoyé par
souviron34
Une solution plus simple (je pense ;))
... le mieux est de transformer les coordonnées [sphériques] en coordonnées rectangulaires avec les équations adhoc, vérifier si les segments s'intersectent ...
C'est une solution graphique, radicale par le changement de variable qu'elle implique, et bien adaptée si l'on s'en tient à vérifier l'existence du point d'intersection, comme le suggère avigeilpro ... Mais elle demande l'intervention d'un logiciel assurant le calcul et le tracé des deux géodésiques, tâche déjà lourde à laquelle s'ajoutera éventuellement la représentation de la carte géographique sous-jacente ... Je me demande dans ces conditions si cela ne sera pas trop lourd en temps de calcul et volume de mémoire pour le petit appareil sur lequel il est prévu d'installer le programme ...
Citation:
Envoyé par
avigeilpro
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,
... et il ne sera pas facile de comprendre le comportement des géodésiques au voisinage des pôles - mais c'est là une difficulté inévitable.
# La solution simplifiée la plus longuement détaiilée ...
Citation:
Envoyé par
Prof
... Je vais noter x la longitude et y la latitude, en degrés.
Tout point M de la surface terrestre est repéré par le couple (x,y) qui appartient au rectangle ]-180,+180] x [-90,+90].
(le lapsus initial n'a pas eu de conséquences)
... qui revient à assimiler la sphère au cylindre parallèle à l'axe des pôles, implique des erreurs systématiques d'autant plus élevées que l'on s'éloigne de l'équateur et travaille sur de plus grandes distances; elle conduit à des résultats aberrants aux latitudes extrêmes.
Citation:
Envoyé par
Prof
... Le problème posé se ramène alors à celui-ci : les segment AB et CD se coupent-ils ?
Pour répondre, il suffit de calculer l'intersection des droites AB et CD et d'examiner sa position.
Considérons les 5 villes suivantes : ... Berlin ... Madrid ...
Remarque : j'ai donné les coordonnées des 5 villes ci-dessus avec 2 décimales, ce qui était amplement suffisant.
En effet, un degré correspondant à environ 111 km, un centième de degré est de l'ordre du kilomètre.
Et les 5 villes ci-dessus ont un taille nettement supérieure à 1 km ...
Si on veut traiter le cas de points connus plus précisément, on se rappellera que la précision du GPS est de l'ordre du mètre.
On utilisera donc des coordonnées avec 5 chiffres significatifs.
Pour s'en tenir aux villes les plus éloignées: Madrid et Berlin sont distantes de 1871 km, soit un arc circulaire vu depuis le centre sous un angle w = d / R = 0.294 rad = 16.8 ° compte de la valeur du rayon terrestre (R = 6371 km).
Pour un écart angulaire (h) exprimé en radians, le procédé introduit dans le calcul des distances une erreur relative de l'ordre de (h2) aux latitudes moyennes, soit ici: (w/2) = 2.2 % , d'où une incertitude sur les distances de l'ordre de: R*h2 = R*(w/2)2 = 137 km !
S'inquiéter dans ces conditions de la précision des données pour parvenir à une localisation au mètre près relève d'un vain scrupule.
Par contre si l'on se limite à une zone de dimension 5 km, vue depuis le centre sous un angle w = 785 µrad, l'incertitude sur les distances se réduit alors à: R*(785E-6/2)2 = 0.98 m , ce qui justifie le recours aux données les plus précises; c'est ce qu'a fait avigeilpro dans l'exemple qu'il a proposé.
# Quand à la solution vectorielle que j'ai proposée, elle a l'avantage de conduire à deux points (ce qui est plus facile à étudier que les intersections de deux graphes), de ne comporter qu'un nombre modéré d'instructions (3 produits vectoriels et une renormalisation, ce n'est pas le bout du monde). et surtout de rester utiiisable au voisinage des points singuliers de la sphère (les pôles).
Cependant, faute de temps, j'ai hypocritement esquivé la question finale de l'intersection par un flou algorithmique approprié
Citation:
Envoyé par
wiwaxia
...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 = R2*cos(iA) ; ¦OA×OI¦ = R2*¦sin(iA)¦ ;
OA·OJ = R2*cos(jA) ; ¦OA×OJ¦ = R2*¦sin(jA)¦ .
en comptant sur un intervenant pour y répondre. Nebulix a bien levé le lièvre,
Citation:
Envoyé par
Nebulix
... Faut-il voir s'ils [ le points d'intersection ] sont dans les plus courts des deux segments de chaque paire de points ? ...
mais rien n'a suivi. Donc je termine.
Il faut s'en tenir à la définition la plus simple d'une géodésique, à savoir le plus court chemin joignant deux points (M et N) d'une surface donnée; la longueur d'un arc ne peut alors dépasser celle d'un demi grand cercle (soit Pi*R), et cet arc rencontre en son milieu la diagonale du losange (OMPN) construit sur les vecteurs (OM) et (ON) .
On déterminera donc, pour les deux couples de vecteurs, la résultante géométrique, puis le point d'intersection de la demi-droite qui le porte avec le cercle correspondant:
OS = OA + OB ; NOS = ║OS║ ; OE = (R/NOS)*OS ;
OT = OC + OD ; NOT = ║OT║ ; EF = (R/NOT)*OT .
La comparaison de deux produite scalaires permet alors de localiser les points d'intersection, et conduit aux réponses définitives:
a) (I) appartient à (AB) si et seulement si OE·OI >= OE·OA (Test IAB) ;
b) (I) appartient à (CD) si et seulement si OF·OI >= OF·OC (Test ICD) ;
c) (J) appartient à (AB) si et seulement si OE·OJ >= OE·OA (Test JAB) ;
d) (J) appartient à (CD) si et seulement si OF·OJ >= OF·OC (Test JCD) ;
Il suffit de lire la valeur des 4 booléens.
Note: la prévisualisation des messages fonctionne à nouveau ... C'était bloqué hier soir et ce matin.