Comment c'est fait ?

Salut les amis,

Nelson m'a demandé comment je calcule l'enveloppe convexe.
La théorie est assez simple.
La pratique est plus délicate, surtout la manipulation informatique des fichiers de données.
Soyez indulgents, je ne suis ni géographe, ni informaticien.
J'accepte toute critique constructive : pour cela inscrivez-vous au forum et postez un message dans la partie "Discussions".

Ne lisez pas le texte ci-dessous sans avoir bien assimilé le règlement de la CFDM :
https://cfdm.forumperso.com/t141-reglement-de-la-cfdm

Voici les étapes à réaliser pour calculer une enveloppe convexe pour la CFDM :

1) Projeter les points de la trace GPS sur plan
On peut mathématiquement calculer une enveloppe convexe en 3D, mais c'est horriblement compliqué et ça ne nous sert à rien.
C'est pourquoi je vais négliger la composante verticale et travailler en 2D.
Le première étape consiste donc à projeter tous les points GPS de la trace d'origine sur un plan :



Ça paraît simple, mais il faut bien comprendre qu'il s'agit de projeter une portion de sphère sur une portion de plan :



Vous comprendrez qu'il y aura une erreur mathématique, quelle que soit la qualité de la projection.
Cette erreur est d'autant plus petite que le diamètre de la sphère est grand par rapport à la taille de la surface projetée.
Enfin bref, les géographes sont venus à notre secours et ont défini une projection dite "Lambert 2 étendu" pour laquelle l'erreur est faible en France métropolitaine (3 mètres maximum dans le sud de la France).
Vous comprenez à présent pourquoi il est difficile d'homologuer des traces dans les DOM-TOM : il faut changer de projection* (voir au bas de l'article).
L'autre avantage de cette projection, c'est qu'elle transforme les coordonnées sphériques (latitude, longitude) en coordonnées cartésiennes (x, y). Bref, on se retrouve en géométrie classique.
Pour réaliser cette transformation, j'utilise le programme "Circé" fourni gratuitement par l'IGN : http://geodesie.ign.fr/index.php?page=circe






2) Calculer l'enveloppe convexe
On dispose maintenant d'un nuage de points en coordonnées cartésiennes.
Le calcul d'une enveloppe convexe en 2D est un problème assez bien documenté. Il existe une multitude d'algorithmes différents.
Les plus simples sont très lents, les plus sophistiqués arrivent au résultat en quelques itérations mais leur compréhension nécessite un doctorat en recherche opérationnelle .
Voir une animation sympa (merci wikipedia https://fr.wikipedia.org/wiki/Enveloppe_convexe ) :



Bref, pas la peine de ré-inventer la poudre, surtout pour nos quantités de données assez faibles. J'utilise donc un programme existant, Qhull : http://www.qhull.org/.
Pour la petite histoire, les programmeurs de Qhull hurleraient de rire en voyant notre application, puisque nous n'utilisons qu'une fraction triviale du logiciel.
Celui-ci est capable de calculer des enveloppes convexes en 3 dimensions et bien plus : essayez d'imaginer un espace en 4 dimensions. Facile ? Maintenant en 5 dimensions. Puis en 6. Puis en "N" dimensions... bravo, vous pouvez commencer à lire la documentation de Qhull   .




3) Renvoyer le tout dans Google Earth obsolète depuis 2021 voir plus bas
Avec les deux étapes précédentes, nous avons calculé l'enveloppe convexe.
Mais pour arriver au rapport d'homologation CFDM tel que vous le connaissez, il y a encore un peu de travail.
Le premier travail consiste à projeter l'enveloppe convexe obtenue à l'étape 2 à une hauteur de 50 m au-dessus du sol (pour éviter qu'elle "n'entre" dans une montagne et que son affichage soit donc discontinu).
Voilà le résultat :



Le deuxième travail consiste à "habiller" l'enveloppe avec les points "arrivée" et "départ" et la distance "AD" (en bleu) :



Je réalise tout ce travail avec le logiciel GPSBabel : https://www.gpsbabel.org/
J'utilise aussi sa variante web, appelée GPSVisualizer, qui permet de gagner du temps quand les fichiers d'entrée sont un peu "exotiques" : http://www.gpsvisualizer.com
Si vous vous rendez coupable de fichiers "exotiques", vous me feriez gagner beaucoup de temps en les convertissant vous-même en fichier GPX classique grâce à ce site web.
Pour info, les fonctions de GPSVisualizer dépassent parfois celles de GPSBabel, notamment en terme d'affichage dans Google Earth.

A noter que GPSBabel permet aussi de calculer la longueur des traces, ce dont je me sers sans modération pour extraire toutes les données chiffrées du rapport d'homologation :




Naturellement, j'ai automatisé la quasi-totalité de ces manipulations.
Une homologation prend actuellement entre 2 et 5 minutes, principalement à cause de la mise à jour du forum qui reste manuelle.

Voilà, vous savez tout !

Bons vols à tous,

Julien


* Edit du 29/11/16 :
la Nouvelle-Calédonie est à présent intégrée à la CFDM. La projection utilisée est "RGNC1991-Lambert_Nouvelle_Calédonie".

* Edit du 23/05/18 :
Vous pouvez maintenant calculer l'enveloppe convexe chez vous grâce à CFDM-Go : https://cfdm.forumperso.com/t2678-cfdm-go

* Edit 05/01/2022 :
Depuis 2021, la programmation est réalisée en JAVA avec des fonds de carte gratuits. Une homologation "simple" prend à présent moins de 60 secondes.
Voir : https://cfdm.forumperso.com/t2020-qui-gere-la-cfdm#9651

Salut à tous,

Je suis assez fier de mon algorithme qui retrouve la force et la direction du vent à partir d'une trace GPS.
C'est intéressant pour les pilotes un peu matheux, j'aimerai donc partager cela avec vous.

Note : l'idée de calculer le vent à partir de la trace vient de Jacky NIORT que j'ai traité de cinglé, jusqu'à
ce qu'on me fasse remarquer que les varios faisaient très bien ce calcul. Qu'il soit remercié ici.




1) Modéliser le problème
On dispose d'un fichier de points GPS (latitude, longitude).
Pour chaque point, on dispose de l'heure d'enregistrement du point à un format appelé timestamp.
Modéliser le problème, ça consiste à le réduire à un problème mathématique connu. C'est ce qui a été le plus dur.
Après plusieurs jours à tourner autour de la solution, je suis finalement tombé sur ça :
http://blueflyvario.blogspot.fr/2012/09/calculating-wind-speed-from-gps-track.html
Je ne remercierai jamais assez Dickie ALISTAIR pour avoir partagé son travail. Achetez-lui un vario pour le remercier !

En fin de compte, la modélisation est très simple :
- on calcule, pour chaque point, le cap et la vitesse jusqu'au point suivant
 (en divisant la distance entre les deux points par la différence de leur timestamp)
- on ramène le vecteur correspondant sur l'origine d'un graphique orthonormé
- on obtient un nuage de points qui correspond à "tous les caps et toutes les vitesses enregistrées" :



Comme vous le voyez, la première caractéristique de ce nuage de point, c'est qu'il a la forme approximative d'un cercle.
Ceci est dû au fait que nos paramoteurs ont une vitesse "air" à peu près constante.
Le rayon de ce cercle est la vitesse air moyenne sur le parcours.

La deuxième caractéristique de ce cercle, c'est qu'il n'est pas centré sur l'origine du graphique.
En réfléchissant un peu, vous comprendrez que ce cercle est tout simplement "décalé" par le vent !
Prenons un exemple : si le vent venait du Nord a une vitesse de 50 km/h, notre vitesse vers le Nord serait nulle,
et notre vitesse vers le sud serait de 100 km/h (pour une vitesse air de 50 km/h) :



Le cercle est "décalé" par le vent selon sa direction et sa force.
Pour quantifier ce décalage, il suffit simplement de connaître la position de son centre.
Et c'est plié !



Le problème se résume donc à trouver le cercle qui est le plus représentatif du nuage de points, et surtout son centre.
Ça tombe bien, c'était une partie de mon sujet de fin d'études !


2) Calculer le cercle le plus représentatif du nuage de points
Il s'agit là d'un problème d'optimisation classique, mais dont la solution n'est pas si simple à trouver sur le web.
En optimisation, on cherche à trouver le cercle qui minimisera la somme des distances entre le cercle et chacun des points.
Autrement dit, on cherche par le calcul direct ou par des algorithmes itératifs "à minimiser l'erreur".
Des mathématiciens ont montré qu'il est plus pertinent de mettre cette erreur au carré pour chacun des points,
avant d'en faire une somme globale (ça pénalise "exponentiellement" les points qui sont très loin).
C'est pourquoi vous trouverez souvent l'expression "cercle des moindres carrés".

Je vous passe les formules mathématiques impliquées, si ça vous intéresse je peux vous les fournir.
J'utilise la version matricielle de l'estimateur des moindres carrés.
Ce mode de calcul implique certes une inversion de matrice, mais il est quand même plus facile à programmer que des méthodes itératives.
Pas besoin de dégainer Matlab et autres logiciels pointus, Excel sait faire tout ça assez simplement.

Si vous vous débrouillez bien, à la fin, le programme crache 3 valeurs :
- le rayon du cercle, c'est-à-dire votre vitesse air moyenne
- les coordonnées du centre, qui indiquent la direction du vent et sa force
Hourra !

Souvenirs, Souvenirs... en 2000, je calculais des sphères des moindres carrés dans ma chambre d'étudiant :




3) Efficacité de l'algorithme ?
La force d'un algorithme des moindres carrés, c'est d'abord qu'il prend en compte tous les points.
On peut le dire autrement : chaque point apporte sa contribution au calcul.
Ces algorithmes sont par ailleurs réputés pour être très robustes aux erreurs de mesure ou incertitudes diverses.
En pratique, nous sommes confrontés à plusieurs difficultés :

* Variation de la vitesse air (barreau, trims)
Ici un bel exemple de pilote qui a fait usage de son accélérateur (et/ou de ses trims), surtout face au vent.
On obtient le même genre de tracé lorsque le vent change au cours du vol : la couronne s'élargit.
Note : ce n'est pas moi, car moi je suis sur le barreau tout le temps.  




* Cercle incomplet (= vol selon seulement un ou deux caps)
Voici un vol en aller-retour :



Et voici le diagramme correspondant, avec deux nuages de points très caractéristiques :



Nous sommes dans le cas le plus défavorable : aller-retour avec vent de travers de 90°.
Le pilote n'est quasiment jamais face au vent ni vent de dos, ce qui empêche tout calcul intuitif du vent.
Mais l'algorithme, lui, s'en sort formidablement bien grâce aux petites altérations de cap au cours du parcours
qui "courbent" les deux taches et lui permettent de reconstruire le cercle. Qu'est ce qu'on dit ?



Notez que Dickie ALISTAIR, dans son article cité plus haut, estime que les altérations de cap doivent couvrir un arc
d'environ 60° pour avoir une estimation fiable. Mais il faut savoir qu'il calcule en temps réel sur les dernières 90 secondes,
alors que nous considérons tout le vol et disposons donc de beaucoup plus de points.
Il est donc plus que probable que nous ayons un arc suffisant.


* Variation importante du vent au cours du vol    (edit du 16/04/17)
Si le vent change brutalement de direction ou d'intensité au cours du vol, l'effet est similaire à une variation de la vitesse air de l'aile (voir plus haut).
On a vu qu'en règle générale, le calcul reste valable.
Pourtant, si le pilote se sert activement de ce changement de vent, il peut fausser considérablement le calcul à son avantage.
Il lui "suffit" de modifier son cap au moment adéquat en fonction du vent rencontré.
Des pilotes chevronnés et calés en météo peuvent par exemple utiliser :
- une couche de cisaillement  (= le vent au-dessus de la couche de cisaillement est très opposé à celui rencontré en-dessous)
- des entrées maritimes (= le vent sur la côte est très opposé à celui rencontré quelques kilomètres à l'intérieur des terres)
Voici un exemple extrême :



et la situation météo correspondante ce jour-là :



Sur 1h40, ce pilote a une vitesse air moyenne calculée de 84 km/h... (pour une vitesse sol moyenne de 80 km/h).
Au vu du matériel utilisé, cette vitesse air est théoriquement impossible.
Vous pouvez voir le vol ici : https://cfdm.forumperso.com/t889-0710-14-04-17-serge-lagrave-1349-km-homologue.
Il y a vraiment des types très forts ! Cela reste une exception et nécessite des conditions très particulières.


* Précision insuffisante des données GPS
Alors celle-là, je ne l'attendais pas.
A plusieurs reprises, j'ai vu ça :



Après moultes recherches, il s'avère que la transmission de fichiers GPS entre certains varios et certains systèmes
d'exploitation (notamment les Mac) entraîne une réduction du nombre de décimales des coordonnées de latitude et de longitude.
Le standard, c'est 6 décimales. Avec 5 décimales, vous avez une précision d'un mètre. Autrement dit, les points sont sur une grille
dont la maille fait 1 mètre de côté. Sachant qu'on enregistre un point toutes les N secondes, on se retrouve avec un nombre faible
de combinaison distances/temps (aussi appelées "vitesses"  ). Et n'oubliez pas que 1 m/s = 3.6 km/h...
Voilà donc pourquoi ces "grilles" apparaissent. En tous cas, je n'ai pas encore trouvé d'autre explication.
A ma grande surprise, les erreurs de grille se compensent les unes les autres et le résultat final est plutôt bon.
A l'inverse, pour l'anecdote, du côté de chez GARMIN ils sont connus pour avoir jusqu'à 10 décimales, ce qui est parfaitement ridicule puisque
ça correspond à une précision au 1/100ème de milimètre. Ça pose des problèmes de conversion de types de données et ça emm... tout le monde  .
edit 1 : il semblerait aussi que le format IGC soit à l'origine du phénomène de grille. Si quelqu'un en sait plus, qu'il me tienne au courant.
edit 2 : les spécifications du format IGC imposent le codage des valeurs de latitude/longitude avec 3 décimales de minute soit 1.66 m,
ce qui correspondrait à une taille de maille de grille de 6 km/h sur le diagramme du vent ! C'est donc bien le format IGC qui est en cause.
edit 3 : et voici la confirmation que c'est bien l'IGC qui est en cause avec ses problèmes d'arrondi.
La même trace enregistrée par le même instrument dans les deux format (instrument = Syride Sys'nav, vol 3369) :

Notez que le résultat pour le calcul du vent est strictement le même, puisque les erreurs d'arrondi se compensent !


4) Conclusion : ça marche !
Vous l'avez donc compris, à ma grande surprise, les résultats sont exceptionnellement bons.
Je me prends même à regarder souvent les diagrammes des vols pour comprendre ce qu'a fait le pilote, quand il a accéléré,
la vitesse de son aile, et la variation probable du vent au cours du vol.
Ce serait du boulot, mais je réfléchis à mettre le diagramme en ligne pour chacune des homologations.
edit : Le diagramme du vent fait désormais intégralement partie du rapport d'homologation  .

Julien


P.S. N'hésitez pas à poster vos commentaires ici :
https://cfdm.forumperso.com/f5-discussions


* Edit du 10/05/19 :
Vous pouvez maintenant calculer vous-même le vent et la vitesse air chez vous grâce à VENTIX :
https://cfdm.forumperso.com/t4563-ventix-calculez-vous-meme-la-vitesse-air-a-partir-d-une-trace-gps-pour-utilisateurs-avertis