IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Détecter si deux trajets se croisent


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut 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++.
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  2. #2
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2012
    Messages
    538
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2012
    Messages : 538
    Points : 262
    Points
    262
    Par défaut
    Comment définis-tu les trajets entre deux points ?

  3. #3
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut
    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.
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  4. #4
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Detecter si deux trajets se croisent.
    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:
    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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  5. #5
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2012
    Messages
    538
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2012
    Messages : 538
    Points : 262
    Points
    262
    Par défaut
    Tu considères la terre comme une sphère ou une ellipsoïde ?

  6. #6
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Detecter si deux trajets se croisent.
    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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut
    Merci wiwaxia pour toutes ces informations, je vais prendre le temps d'essayer de comprendre tout ça. je reviendrais si quelque chose m'échappe.
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  8. #8
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    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....
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  9. #9
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    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 ...
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  10. #10
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Nebulix Voir le message
    @souviron : si les deux points ne sont pas très proches, la "droite" en projection Mercator est une courbe compliquée ...
    Pourquoi Mercator ? On ne sait pas ce qu'il veut utiliser ou utilise, mais entre Lambert, stéréographique, etc, c'est pas forcément des courbes... (dans un autre temps j'ai fait un outil SIG d'affichage de cartes, avec transfos de projections, et calculs avec données...) Des droites peuvent être des droites.... Heureusement.... Et même avec Mercator.... tu es capable de tracer une droite entre 2 points.... Maintenant ça dépend si tu veux par exemple la distance à la surface du globe ou sur la projection.. Ca c'est autre chose....

    Pour les intersections, il est à mon avis toujours préférable de revenir aux coordonnées rectangulaires, ou alors d'utiliser le sphérique (qui est une approximation) ou l'ellipsoide.... Mais si on utilise l'ellipsoide ou sphérique, il faut alors utiliser les détails spécifiques à la portion qui nous intéresse (les paramètres de l'ellipsoide (position du centre, ellipticité, etc) sont ajustés par pays, en fonction du terrain et des latitudes / longitudes, pour représenter au plus près la réalité, vu que même l'ellipsoide WGS est une approximation / moyenne).

    Comme la vraie géométrie spherique est compliquée, et que dans l'écrasante majorité des cas on se réfère à une projection, je suggère très fortement de rester dans cette projection... (les intersections seront réellement correspondantes à ce qu'on voit) . Si maintenant on travaille réellement en sphérique, alors oui on fait tout en sphérique, et le visuel correspondra..

    (sinon, tu peux avoir des surprises visuelles, dans lesquelles tu déclares des intersections que tu ne voies pas, ou pas comme ça, ou des formes qui ne correspondent pas)


    Dans l'absolu, le plus simple serait d'utiliser juste lat/lon... mais à cause de ces phénomènes visuels, c'est compliqué...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  11. #11
    Membre confirmé
    Homme Profil pro
    .
    Inscrit en
    Juin 2002
    Messages
    239
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : .
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2002
    Messages : 239
    Points : 567
    Points
    567
    Par défaut
    Bonjour.

    Je vais noter x la latitude et y la longitude, 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 trajet le plus court entre deux points A et B situés sur une sphère est l'arc de grand cercle passant par A et B.

    Pour simplifier, je vais supposer que les points A et B ne sont pas trop près d'un bord du rectangle précédent.
    Dans ce cas, cet arc de grand cercle est représenté dans le plan de coodonnées x,y par le segment AB.

    Si les points A et B sont proches de la frontière du rectangle, il suffit de faire un changement de coordonnées judicieux :
    remplacer le couple (équateur, méridien de Greenwich) par un autre couple de grands cercles orthogonaux dont l'une des intersections est à proximité de A et B.

    On peut donc en théorie se ramener au premier cas, le seul que je vais étudier.

    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.

    La droite AB est donnée en paramétrique par : Formule mathématique, Formule mathématique

    Si Formule mathématique et Formule mathématique, cela s'écrit :

    Formule mathématique

    De même, la droite CD est donnée par :

    Formule mathématique

    L'intersection de ces deux droites est solution du système :

    Formule mathématique

    où les inconnues sont Formule mathématique et Formule mathématique

    On a là un système linéaire de deux équations à deux inconnues, que l'on résout à la main ou à l'aide d'un logiciel de calcul symbolique.

    La solution est donnée par Formule mathématique

    où :

    Formule mathématique

    Formule mathématique

    Formule mathématique

    Maintenant qu'on a la solution, il ne reste plus qu'à examiner si elle se trouve dans les segments AB et CD.
    Cela est très simple, puisqu'avec la définition de Formule mathématique et Formule mathématique, il suffit de vérifier que

    Formule mathématique.

    D'où la fonction suivante, écrite en Python :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    >>> def f(x1,y1,x2,y2,x3,y3,x4,y4):           #  x = latitude, y = longitude
        N1 = (x3-x1)*(y4-y3) - (y3-y1)*(x4-x3)
        N2 = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)
        D  = (x2-x1)*(y4-y3) - (y2-y1)*(x4-x3)
        b  = (0 <= N1/D <= 1) and (0 <= N2/D <= 1)
        return(b)
    La traduction de cette fonction en C ne pose aucun problème.

    Vérifions la formule sur deux exemples.

    Considérons les 5 villes suivantes :
    Paris : 48.85°, 2.35°
    Berlin : 52.52°, 13.40°
    Madrid : 40.43°, 3.68°
    Rome : 41.88°,12.48°
    Londres: 51.50°, 0.12°

    Pour les trajets Madrid-Berlin et Londres-Rome :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    >>> f(40.43,3.68,52.52,13.40,51.50, 0.12,41.88,12.48)
    True
    ils se rencontrent, ce qui est évident.

    Pour les trajets Madrid-Paris et Londres-Rome :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    >>> f(40.43,3.68,48.85, 2.35,51.50, 0.12,41.88,12.48)   # Madrid-Paris / Londres-Rome
    False
    ils ne se rencontrent pas, ce qui se vérifie en consultant une carte de l'Europe ...

    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.

  12. #12
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Prof Voir le message
    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.



    Précision utile et malheureusement nécessaire et presque toujours de nos jours non écoutée / appliquée (j'avais fait une note sur le forum SIG où je me suis fait blasté exactement là-dessus (ici))
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  13. #13
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut
    bonsoir,
    Tout d'abord merci pour toutes vos interventions.
    Suite au commentaire de Prof j'ai reproduit en C la fonction f et fait les essais avec les même coordonnées, cela fonctionnait parfaitement.
    J'ai donc pris les coordonnées issues de mon projet, et malheureusement je n'ai pas le bon résultat.
    voici les 4 couple de coordonnées utilisés:
    A : 46.197666 , 0.633814
    B : 46.197526 , 0.633770
    C : 46.197659 , 0.633627
    D : 46.197647 , 0.633702

    l'appel de la fonction est donc le suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    f(46.197666,0.633814,46.197526,0.633770,46.197659,0.633627,46.197647,0.633702)
    celle-ci me renvoie true, alors que comme on peut le voir sur cette carte, les deux ne se croisent pas (A et B sont en mauve, C et D en rouge, cliquez sur un point pour faire apparaitre les coordonnées GPS)
    Points.html
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  14. #14
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Je me permettrais de dire que ceci est une projection et non une représentation sphérique

    De là plusieurs problèmes : la transformation de l'image satellite (quel angle choisi par rapport à l'image d'origine ? quel angle avait le satellite ? (donc sous quel angle voyait-il la Terre, et sous quel angle la Terre "était-elle plate" ou orthogonale à l'axe ?)) et son placement ici, la transformation/cadrage entre le plan et l'image, et enfin la transformation des coordonnées GPS sur cette image...

    La route doit faire 10 m à peu près, les 2 points rouges séparés d'environ 2m50, soit inférieur à la précision du GPS, non ?

    L'ensemble de toutes ces imprécisions me semble être le résultat que tu obtiens...


    Mais la plus importante me semble la projection....


    (en France en général on utilise Lambert 2. L'équation et démonstration de Prof me semblent exactes, mais, comme il le dit, "en théorie". En pratique, même en ayant pris la sphère universelle, vu les différences de positionnement du centre de la Terre pour s'ajuster à la France, ça ne m'étonnerait pas que cela produise des différences de ces ordres de grandeur... D'où mon conseil de revenir aux coordonnées de projection....qui au moins ont le mérite d'être non deformées théoriquement à une seule latitude, mais en pratique sur une tranche d'au moins 30 degrés... donc à +/- 5 degré c'est garanti)



    (si je me permet d'insister là-dessus, c'est que j'ai eu affaire à des données de positonnement dont certains points n'étaient séparés que de 1m, et qu'il fallait absolument que j'en fasse des contours... J'ai appris à mes dépens que l'utilisation directe des lat/lon était très mauvaise dès qu'on appliquait ça à une projection (ce qui est le cas ici, on est quasiment en vision verticale avec le sol horizontal). Alors il est tout à fait possible que les bibliothèques et de GoogleMap. GoogleSatellite, et des GPS se soient mises d'accord, mais je doute fortement, avec les incertitudes énoncées au paragraphe précédent)

    Mais je suis peut-être un vieux radoteux, n'ayant pas eu accès à des données GPS sur des cartes...
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  15. #15
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut
    L'image n'était la que pour mieux se représenter les points que j'ai donné.
    Si l'on regarde de plus près, sans représentation, les longitudes des point C et D sont toutes deux inférieur aux longitudes des point A et B, il est donc clair que les deux arc ne peuvent pas se croiser, indépendamment d'une quelconque représentation ou projection.

    Ensuite, pour ce qui est de la précision du récepteur satellite, les deux points sont espacés de 6m environs, mon récepteur utilise 3 constellations différentes pour augmenter la précision (GPS, galiléo et glonass), et je peux affirmer qu'on est pas en dessous de la précision, voici les données brute reportées sur une carte, on y vois les trajectoires empruntées, et on aperçois aussi les incertitudes (lorsque la trajectoire passe dans l'herbe). ces données sont brutes, c'est à dire que j'enregistre tel quel les données transmises du récepteur via sa connexion sériel
    tracker.html
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  16. #16
    Membre éprouvé Avatar de avigeilpro
    Homme Profil pro
    Ambulancier
    Inscrit en
    Janvier 2004
    Messages
    880
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Creuse (Limousin)

    Informations professionnelles :
    Activité : Ambulancier
    Secteur : Transports

    Informations forums :
    Inscription : Janvier 2004
    Messages : 880
    Points : 971
    Points
    971
    Par défaut
    Bon, en fait ça fonctionne très bien c'est entièrement ma faute, en recopiant, j'ai changé un N2 en N1, ce qui provoquait l'erreur.

    Merci Prof pour cette solution extrêmement simple et pourtant très efficace.
    Merci aussi à tous ceux qui se sont penché sur la question.
    La connaissance seule ne suffit pas. La vraie compréhension vient de la mise en expérience.
    Règles|FAQ|Tuto

  17. #17
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    Avril 2012
    Messages
    538
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Avril 2012
    Messages : 538
    Points : 262
    Points
    262
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Comme une sphère de rayon R. C'est assez compliqué comme ça !



    L'essentiel, c'est de savoir bien lire un texte.
    La question était pour l'auteur

  18. #18
    Expert éminent sénior

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 603
    Détails du profil
    Informations personnelles :
    Âge : 66
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 603
    Points : 17 913
    Points
    17 913
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par avigeilpro Voir le message
    Bon, en fait ça fonctionne très bien c'est entièrement ma faute, en recopiant, j'ai changé un N2 en N1, ce qui provoquait l'erreur.

    Merci Prof pour cette solution extrêmement simple et pourtant très efficace.
    Merci aussi à tous ceux qui se sont penché sur la question.
    Alors toutes mes excuses à tous
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  19. #19
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut
    Citation Envoyé par CliffeCSTL Voir le message
    La question était pour l'auteur
    @ CliffeCSTL: Désolé pour ce malentendu; la question m'avait sur le coup sidéré, et j'avais pris cela pour de la provoc'.
    Ma réaction était donc infondée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  20. #20
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Détecter si deux trajets se croisent.
    Citation Envoyé par souviron34 Voir le message
    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 Voir le message
    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 Voir le message
    ... 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 Voir le message
    ... 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 Voir le message
    ...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 Voir le message
    ... 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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Réponses: 9
    Dernier message: 12/07/2011, 18h25
  2. Réponses: 5
    Dernier message: 13/02/2008, 11h15
  3. Détecter les lignes identiques entre deux matrices
    Par totovich dans le forum MATLAB
    Réponses: 5
    Dernier message: 17/04/2007, 10h42
  4. [Javascript] Détecter collision de deux objets <img>
    Par Invité4 dans le forum Général JavaScript
    Réponses: 5
    Dernier message: 04/04/2006, 09h54
  5. Réponses: 23
    Dernier message: 23/01/2006, 22h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo