Recherche un algorithme. [Résolu]

[Pierre95]

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

[pseudocode]

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, ...

[Pierre95]

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

[souviron34]

Envoyé par Pierre95

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..

[Graffito]

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°).

[Pierre95]

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

[disedorgue]

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

[Pierre95]

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

[Graffito]

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

[souviron34]

Envoyé par Pierre95

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".

[Pierre95]

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

[Graffito]

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.

[souviron34]

Envoyé par Graffito

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)

[Graffito]

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

Non : un ArcTangente !

[souviron34]

OK, autant pour moi alors...

Envoyé par souviron34

(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..

[Pierre95]

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

[souviron34]

euh.. Tu dois avoir un quicksort incorporé dans la biblo (qsort)

[Pierre95]

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