Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 18 sur 18
  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut Recherche un algorithme.

    Bonjour,

    Je développe une application qui gère des aéroports.
    Une table (fichier texte) contient la liste de ces aéroports(10600 lignes).
    les lignes sont composées de:
    Code Aéroport : XXXX; 4 caractères
    Nom : XX..X; Caractères nombre variable
    Élévation en pieds : XX.X; Caractères nombre variable.
    Code (autre) Aéroport : XXX; 4 caractères.
    Latitude: +/-XX.XXXXXX; Signe - si nécessaire + 1 à 2 caractères + '.'+ 6 caractères.
    Longitude: +/- XXX.XXXXXX; Signe - si nécessaire + 1 à 3 caractères + '.' + 6 caractères.
    Nombre de pistes : XX; 2 caractères

    Le séparateur est ';'.

    Mon problème est le suivant:
    Partant des coordonnées d'un aéroport, je souhaite trouver tous ceux qui sont dans rayon de 225 miles nautiques autour de lui.

    Pourriez vous m'aider à trouver un algorithme pour parvenir à ce résultat?

    Merci d'avance pour votre aide

    Cordialement
    Pierre

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 961
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 961
    Points : 15 082
    Points
    15 082

    Par défaut

    A partir du moment où l'on sait calculer la distance entre 2 points long/lat, le reste du problème n'est qu'une question de performance:

    parcours exhaustif, tables pré-calculées, partitionnement de l'espace, ...
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Merci de ta réponse,

    Pourrais-tu m'en dire un peu plus car je suis assez novice dans ce domaine.
    Je sais calculer la distance entre deux points, mais c'est la méthode de traitement qui me pose problème.
    Je ne sait comment organiser celui-ci.

    Merci d'avance
    Cordialement
    Pierre

  4. #4
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    Par défaut

    Citation Envoyé par Pierre95 Voir le message
    Je sais calculer la distance entre deux points
    En es-tu sûr ??

    Ce n'est pas la distance eucilidenne entre 2 couples (lat-lon) qui te donnera la distance réelle en mètres..
    "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

  5. #5
    Expert Confirmé Sénior Avatar de Graffito
    Inscrit en
    janvier 2006
    Messages
    5 790
    Détails du profil
    Informations forums :
    Inscription : janvier 2006
    Messages : 5 790
    Points : 6 676
    Points
    6 676

    Par défaut

    parcours exhaustif, tables pré-calculées, partitionnement de l'espace, ...
    dans les "..." je mettrai l'optimisation du parcours exhaustif : comme la simple élimination des aéroports dont la différence de latitude avec celui de base est supérieure à 225' (3.75°).
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Merci de vos réponses,
    Oui, je sais calculer un triangle sphérique qui donne la distance orthodromique.

    Voila mon idée:
    - je parcours tous les aéroports de ma liste et calcule leur distance par rapport au mien.
    - Je mets dans une liste ceux situés à moins de 225 nm de mon aéroport.
    - Je trie la liste par distance ascendante.

    Qu'en pensez vous ?

    Cordialement
    Pierre

  7. #7
    Expert Confirmé
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    décembre 2012
    Messages
    1 046
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : Finance

    Informations forums :
    Inscription : décembre 2012
    Messages : 1 046
    Points : 2 549
    Points
    2 549

    Par défaut

    Bonjour,

    Ton algorithme semble bon, mais le mieux serait d'avoir déjà un fichier trié comme ça cela réduirait la quantité de calcul.
    Après tu peux aussi trier ta liste au fur et a mesure.
    Le choix dépend surtout de l'utilisation dans le temps:
    -Ton fichier est il figé (évolue-t-il dans le temps) ?
    -Là, tu parles d'une distance de 225 mn, se sera toujours le cas ou on peut te redemander la même chose avec une autre valeur ?

    Cordialement,
    disedorgue

  8. #8
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Bonjour,

    Merci de cette réponse qui me rassure.

    Le fichier peut se voir modifié, (nouvel aéroport construit ou mis hors service),
    La distance de 225 nautiques va changée définitivement (ce qui sera le cas bientôt pour 600 nautiques)

    c'est surtout l'aéroport central qui change à chaque fois.
    Je m'explique.
    En aéronautique, un vol doit comporter un aéroport de départ, un aéroport d'arrivée et un aéroport de dégagement au cas ou il serait impossible de se poser sur celui d'arrivée.

    Mon appli doit trouver sur lequel(s) dans un rayon de 600 nautiques.


    Cordialement
    Pierre

  9. #9
    Expert Confirmé Sénior Avatar de Graffito
    Inscrit en
    janvier 2006
    Messages
    5 790
    Détails du profil
    Informations forums :
    Inscription : janvier 2006
    Messages : 5 790
    Points : 6 676
    Points
    6 676

    Par défaut

    J'ai fait un petit test avec les 9500 positions des stations aéronautiques de COM VHF en Europe, déjà chargées en mémoire par mon application. Dans un environnement C#/.net, avec le parcours exhaustif (sans optimisation) de toutes ce positions, le calcul des 9500 distances prend 6 millisecondes.

    Pour info, le code :
    Code :
    1
    2
    3
    4
    5
    6
    7
    System.Diagnostics.Stopwatch Sw = new System.Diagnostics.Stopwatch();
    Sw.Start();
    int TheCount=0 ;
    for (int k=0;k<100;k++) for (int i=0;i<Facilities.Count;i++) if (DistPtPt(Facility1.Coord,Facilities[i].Coord)<225) TheCount++ ;
    Sw.Stop();
    MessageBox.Show("Pour 100 fois le calcul : "+Sw.Elapsed.Seconds + " secondes "+Sw.Elapsed.Milliseconds+"   Count="+TheCount.ToString());
    // Résultat : pour 100 calculs ==> 0 secondes 628
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  10. #10
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    Par défaut

    Citation Envoyé par Pierre95 Voir le message
    Merci de vos réponses,
    Oui, je sais calculer un triangle sphérique qui donne la distance orthodromique.

    Voila mon idée:
    - je parcours tous les aéroports de ma liste et calcule leur distance par rapport au mien.
    - Je mets dans une liste ceux situés à moins de 225 nm de mon aéroport.
    - Je trie la liste par distance ascendante.

    Qu'en pensez vous ?

    Cordialement
    Pierre
    Une optimisation serait de calculer les lat/lon-min et max auquel ça correspond pour ton aéroport de départ, et ne calculer les distances que pour ceux tombant dans ce "rectangle". Et ce test peut lui-même être optimisé en faisant 4 ifs et non pas des ET ou des OU. Et d'autre part tu n'as besoin que du carré de la distance (puisque c'est pour une comparaison).

    Calculer une distance (au carré) demande au minimum 3 additions et 2 multiplications. Faire de 1 à 4 tests, tu y gagnes.

    Et du coup ta liste serait déjà réduite aux aéroports tombant dans le "rectangle".
    "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 du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Merci à vous deux.

    En fait Souviron34, il ne s'agit pas d'un rectangle, mais d'un cercle.
    C'est peut être plus complexe non ?

    Cordialement
    Pierre

  12. #12
    Expert Confirmé Sénior Avatar de Graffito
    Inscrit en
    janvier 2006
    Messages
    5 790
    Détails du profil
    Informations forums :
    Inscription : janvier 2006
    Messages : 5 790
    Points : 6 676
    Points
    6 676

    Par défaut

    il ne s'agit pas d'un rectangle, mais d'un cercle.
    Souviron34 considérait une optimisation du calcul prenant en compte le "rectangle" (minlat/maxlat, minlon/maxlon avec un cas spécial pour longitude proche de 180°) dans lequel le cercle est inscrit.

    Par contre, sa proposition sur l'optimisation avec le carré de la distance ne s'appliquerait que pour une distance dans le plan, mais pas à une distance orthodromique sur la sphère.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  13. #13
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    Par défaut

    Citation Envoyé par Graffito Voir le message
    Par contre, sa proposition sur l'optimisation avec le carré de la distance ne s'appliquerait que pour une distance dans le plan, mais pas à une distance orthodromique sur la sphère.


    Pourquoi ??

    Quand tu vas calculer des distances, tu vas bien faire une racine carrée, non ??

    On n'a tout simplement pas besoin de calculer la racine.

    Si distance < 600 km <=> Si carré(distance) < 600*600 ... Donc on calcule une fois 600*600, et ensuite on en fait que calculer en utilisant la formule appropriée le carré de la distance.. On évite une racine carrée.. Et l'ordre reste le même, donc le tri suit la même règle..

    @Pierre95 :

    ton cercle centré sur ton aéroport définit un rectangle englobant maximum en lat/lon.

    Donc, comme dans ta table tu as les lat/lon des aéroports, tu calcules ce rectangle en départ, et ensuie, au lieu de claculer les distances pour tous les aéroports, tu testes :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    si lat >= lat min
       si lat <= lat max
          si lon >= lon min
             si lon <= lon max
                  calcul
             fin si
          fin si
       fin si
    fin si
    Que tu peux présenter sous forme de ET..

    Comme ça, tu évites tout plein de calculs... Et tu n'as grosso-modo que des calculs à faire pour le cercle + qques points... Et comme e disais pour liminer un aéroport tu as au max 4 tests, et en moyenne beaucoup moins.. (on peut ordonner différemment les tests si on sait comment les aéroports sont triès au départ dans la table)
    "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

  14. #14
    Expert Confirmé Sénior Avatar de Graffito
    Inscrit en
    janvier 2006
    Messages
    5 790
    Détails du profil
    Informations forums :
    Inscription : janvier 2006
    Messages : 5 790
    Points : 6 676
    Points
    6 676

    Par défaut

    Quand tu vas calculer des distances, tu vas bien faire une racine carrée, non ??
    Non : un ArcTangente !
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  15. #15
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    Par défaut

    OK, autant pour moi alors...

    Citation Envoyé par souviron34 Voir le message
    (on peut ordonner différemment les tests si on sait comment les aéroports sont triès au départ dans la table)
    Je rajouterais là-dessus que sans doute tu aurais intérêt à trier une fois pour toutes ta table en latitude décroissante, par exemple..

    Ensuite, pour chaque demande : déterminer l'indice correspondant à la latitude max du "rectangle" par dichotomie (log(N)), parcourir, et si latitude < latitude min on s'arrête.

    Tu enlèves en plus un test , tu t'arrêtes, et tu ne parcoures que le strict minimum...

    Et je pense qu'il est plus judicieux de trier par latitude que par longitude...

    Le pseudocode donné deviendrait alors simplement :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    start = Finds_Index ( Lat_Max )
    
    pour i = start juqu'à i = N
    
      si lat < lat min
         break 
    
      si lon >= lon min
         si lon <= lon max
               calcul
         fin si
      fin si
    fin pour
    qui devrait être assez optimal..
    "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

  16. #16
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Bonjour,

    Merci à tous pour vos idées très intéressantes.
    Finalement j'ai opté pour le parcours de tous les aéroports dont ceux dans le rayon de 600 nm seront placés dans un stringlist.

    Le soucis restant est le tri sur la distance.
    J'ai cherché sur le web des précisions sur CustomSort, mais je ne parviens pas à en maîtriser l'usage.

    J'ai écrits une fonction de tri sur le modèle:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    function CompareInt(List: TStringList; Index1, Index2: Integer): Integer;
    var
      d1, d2: Integer;
      r1, r2: Boolean;
    
      function IsInt(AString : string; var AInteger : Integer): Boolean;
      var
        Code: Integer;
      begin
        Val(AString, AInteger, Code);
        Result := (Code = 0);
      end;
    
    begin
      r1 :=  IsInt(List[Index1], d1);
      r2 :=  IsInt(List[Index2], d2);
      Result := ord(r1 or r2);
      if Result <> 0 then
      begin
        if d1 < d2 then
          Result := -1
        else if d1 > d2 then
          Result := 1
        else
         Result := 0;
      end else
       Result := lstrcmp(PChar(List[Index1]), PChar(List[Index2]));
    end;
    Puis un procédure de tri sur celui-ci:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    procedure TForm1.SearchNearest(Sender: TObject);
    var
      sl: TStringList;
    begin
      sl := TStringList.Create;
      try
        sl.Assign(Memo1.Lines); //Liste non triée contenant Code sur 5                                      caractères  et distance
        sl.CustomSort(CompareInt);
        Memo1.Lines.Assign(sl);
      finally
        sl.Free;
      end;
    end;
    Je ne sais pas comment déclarer les fonctions imbriquées dans la partie Interface de l'unité.

    Merci de votre aide.

    Cordialement
    Pierre

  17. #17
    Expert Confirmé Sénior

    Inscrit en
    janvier 2007
    Messages
    10 173
    Détails du profil
    Informations personnelles :
    Âge : 56

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 173
    Points : 12 816
    Points
    12 816

    Par défaut

    euh.. Tu dois avoir un quicksort incorporé dans la biblo (qsort)
    "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

  18. #18
    Membre du Club
    Profil pro
    Inscrit en
    avril 2003
    Messages
    209
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2003
    Messages : 209
    Points : 49
    Points
    49

    Par défaut

    Bonjour,

    J'ai fini par trouver une solution qui résout ce problème.

    Je vous remercie vivement de m'avoir mis sur la piste.

    Très cordialement
    Pierre

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •