igc-xc-score

[mmomtchev]

Bonjour,

J'ai créé un outil de scoring XC pour les traces GPS. Je suis en train d'analyser les traces de la CFD et je me rends compte qu'il y a un bon nombre de vols qui sont mal évalués (surtout les années d'avant, mais j'en ai vu même en 2019).

Pour ceux qui ne sont pas au courant, le scoring XC est un problème très complexe sans solution générique en temps raisonnable. La complexité est en O(n^5) ce qui est complètement prohibitif pour un vol qui va contenir parfois jusqu'au 40,000 points.

A ma connaissance ceci est le premier outil complètement gratuit et open-source. A différence du logiciel de la FFVL qui est approximatif, celui-là est 100% précis et déterministe. Il se base uniquement sur les points du tracé, sans interpolations et changements d'échelle. La contrepartie est qu'il peut être relativement lent. J'ai implémenté un mode solution idéale et un mode exécution en temps borné. Dans le deuxième cas, à la fin, l'outil vous dira s'il a trouvé la meilleure solution possible ou non et ce que c'est l'ordre de grandeur de la différence.

Il est assez performant et il rajoute quelques pourcents en général à la plupart des vols de la CFD. Pour certains, il en enlève   ... (j'ai l'impression que l'outil de la FFVL fait son calcul à partir d'une version simplifiée des vols).

Pour l'instant j'ai implémenté uniquement le scoring FFVL mais l'outil est modulaire et il est prévu qu'il supporte d'autre méthodes de scoring.
Le scoring FFVL est respecté à la lettre, y inclus la condition qui figure dans le règlement, que les distances doivent être mesurée en prenant en compte pas seulement la courbature de la Terre mais aussi l’aplatissement des pôles (ellipsoïde WGS84) qui ne donne qu'une différence de 500m pour 500km.

L'outil ne dispose pas de son propre interface de visualisation et il est prévu pour qu'il puisse être intégré dans un autre logiciel.

https://github.com/mmomtchev/igc-xc-score

[giloutho]

  Bravo pour cette excellente initiative...

Je viens de tester vite fait, c'est très prometteur. Il n'y a effectivement pas d'outil open source disponible. Je te contacte en MP pour un échange technique sur ce magnifique projet.

[sylvain_p]

Sympa !!! Faudrait proposer à flyxc.app de l'intégrer 

[mmomtchev]

Même si mon outil est systématiquement plus précis que celui de flyxc.app (sauf éventuels bugs, il est encore très jeune), celui de flyxc.app a l'avantage de trouver une solution très rapidement et je me demande si, pour cette utilisation-là, son algorithme n'est pas pour l'instant le meilleur choix.

Si j'arrive à faire d'en sorte que le mode exécution en temps borné avec un temps limité à, disons 10 secondes, soit systématiquement meilleur que le sien, alors oui. Mais pour l'instant je crains que ce n'est pas encore le cas.

Par exemple le record de distance de France, vol D3P en diagonale par rapport à l'axe nord-sud (le point faible de mon algorithme actuel) est évalué à 1km de moins que l'évaluation officielle en 10s (solution rapide) et à 150m de plus en 5 minutes (solution garantie optimale).

Je ne sais pas comment fonctionne flyxc.app, mais à vue de nez, il réduit le nombre de points du vol avant de lancer le calcul.

Je viens d'officialiser la 1.0 avec un traitement beaucoup plus rapide des vols D3P.

Sympa !!! Faudrait proposer à flyxc.app de l'intégrer 

[sylvain_p]

C'est pas flyxc qui calcule les points c'est directement la FFVL et en amont, sûrement une fois pour toute à l'upload de la trace (cf plus bas).
Pour le calcul du score tout se passe là (en fonction de la "league" ffvl, xccontest...) : https://github.com/vicb/flyxc/tree/master/frontend/src/viewer/logic/score

Donc pour ceux qui veulent utiliser flyxc en standalone t'auras pas le scoring automatique, à moins de tracer toi même les points
Victor pourra m'arrêter si je dis des âneries

Digression technique
Pour les points de calcul le chemin est passé directement dans l'url de flyxc intégré dans la iframe de la cfd sous le paramètre p qui est chemin encodé/décodé par l'API GMaps, exemple:
https://flyxc.app/?track=https%3A%2F%2Fparapente.ffvl.fr%2Ftrackserver%2Fffvl_igc_files-189574-6-1356999-raw.igc&location=&p=%7B_roGspni%40fxrAn_%7EAsjkDdh%5Cr%60qAogaCr%7B%40hmA&l=fr&s=29
p vaut {_roGspni@fxrAn_~AsjkDdh\r`qAogaCr{@hmA

ce qui se décode en :(44.6619, 6.9609000000000005),(44.2329, 6.47442),(45.1154, 6.72895),(45.102270000000004, 7.395910000000001),(45.09257, 7.383380000000001)

Ensuite flyxc calcule la longueur totale de chaque segments (encore via l'API GMaps), ce qui donne la distance totale, puis calcul le scoring via les classes données plus haut

[mmomtchev]

Ah, je ne savais pas que flyxc aussi était sur github. Mais de ce que je vois, il y a bien un optimiseur de distances dedans :
https://github.com/vicb/flyxc/blob/master/frontend/src/viewer/logic/score/measure.ts

Je vois aussi un moteur d'interpolation, ce qui confirme mon hypothèse.

Après, peut-être le scoring c'est la FFVL qui le fait?

Est-ce que son auteur passe ici sur le forum? Je vais peut-être le contacter en direct. Merci en tout cas.

C'est pas flyxc qui calcule les points c'est directement la FFVL et en amont, sûrement une fois pour toute à l'upload de la trace (cf plus bas).
Pour le calcul du score tout se passe là (en fonction de la "league" ffvl, xccontest...) : https://github.com/vicb/flyxc/tree/master/frontend/src/viewer/logic/score

Donc pour ceux qui veulent utiliser flyxc en standalone t'auras pas le scoring automatique, à moins de tracer toi même les points
Victor pourra m'arrêter si je dis des âneries

Digression technique
Pour les points de calcul le chemin est passé directement dans l'url de flyxc intégré dans la iframe de la cfd sous le paramètre p qui est chemin encodé/décodé par l'API GMaps, exemple:
https://flyxc.app/?track=https%3A%2F%2Fparapente.ffvl.fr%2Ftrackserver%2Fffvl_igc_files-189574-6-1356999-raw.igc&location=&p=%7B_roGspni%40fxrAn_%7EAsjkDdh%5Cr%60qAogaCr%7B%40hmA&l=fr&s=29
p vaut {_roGspni@fxrAn_~AsjkDdh\r`qAogaCr{@hmA

ce qui se décode en :(44.6619, 6.9609000000000005),(44.2329, 6.47442),(45.1154, 6.72895),(45.102270000000004, 7.395910000000001),(45.09257, 7.383380000000001)

Ensuite flyxc calcule la longueur totale de chaque segments (encore via l'API GMaps), ce qui donne la distance totale, puis calcul le scoring via les classes données plus haut

[mmomtchev]

J'ai bidouillé une démo rapide sur https://www.meteo.guru/xc-score

Le moteur tournera dans votre navigateur, la beauté du Javascript fait que le CPU qui est utilisé pour chercher une solution optimale est celui de votre ordinateur -> c'est donc celui qui l'utilise qui paye la facture (d'électricité et le reste).

Dès que j'ai fini le nettoyage des sources qui ont servi à fabriquer la démo, je vais les mettre en ligne

[cargol]

Vraiment du beau boulot de codage et d'analyse.
Chapeau.
  

[sylvain_p]

y'a pas à dire, avec un petit front ça claque quand même plus! Bravo

[mmomtchev]

Je viens d'officialiser la 1.1.1 qui apporte

• support des règles XContest en plus des règles FFVL
• traitement 4x plus rapide des vols en ligne droite en diagonale (le record de France, le pire vol possible pour cet algo passe à 20s)
• externalisation de la configuration des règles de scoring, maintenant il est relativement facile à rajouter un autre système de scoring sans toucher au code
• corrections de bugs
• intégration plus facile avec les logiciels non-JS (mode stdin/stdout)

Je considère que la phase développement/optimisation est finie, maintenant il reste à trouver et à corriger tous les éventuels bugs 

[sylvain_p]

Hello, j'ai fait à la va vite un petit outils pour tester igc-xc-score :
https://spasutto.github.io/test-igc-xc-score/dist/score.html
on peut l'utiliser en y chargeant un fichier IGC ou bien en cliquant dans la carte les différents points du parcours. Dans le second cas on peut partager le parcours par une url, exemple :
https://spasutto.github.io/test-igc-xc-score/dist/score.html?pl=uapsGkw|b@fqAjgArz@|dBdZ|zB`s@hwCzcFrkIatFqrIqaBum@cZoaAi`AsvBok@ka@|FcyD
Il y'a quelques bugs...

[mmomtchev]

Bon boulout

Juste deux suggestions:

L'API est prévue pour être utilisée sur une page web sans la bloquer pendant le calcul - c'est exactement pour ça qu'elle est un peu bizarre (un générateur JS) - il faut appeler la fonction, lui donner un temps max de calcul (100ms c'est bien), puis on met à jour la page web et on refait du calcul par tranches de 100ms pour ne jamais bloquer l'interface

Puis, je crois que quand je change le système de scoring, le score lui-même n'est pas mis à jour - juste le nom de la règle

[sylvain_p]

Merci,
Pour le score je pense que c'est bon par exemple sur ce parcours bidon le score et le type de parcours changent bien :
https://spasutto.github.io/test-igc-xc-score/dist/score.html?pl=onxqGypfa@{|YyrGefUadW`vWocKhpXljY
 mais je t'avoue que je suis pas sûr d'avoir saisi toutes les nuances du scoring
Pour l'appel en boucle il me semble avoir suivi les recommandations que tu donnes sur ton github? Voilà comment est appelée ta librairie (la méthode score utilise une boucle comme tu dis via requestIdleCallback) :
https://github.com/spasutto/test-igc-xc-score/blob/master/src/index.js
Le code est piqué d'un de tes exemples je crois
Bon et ça m'a fait passer le temps et bricoler avec leaflet, npm et webpack

[mmomtchev]

Oui tout à fait, j'ai pas fait attention, le score est bien mis à jour - c'est juste que le temps de rafraichissement est un peu lent - avec 100ms au lieu de 1s ça sera plus fluide et on n'aura plus l'impression que la page se fige

[sylvain_p]

Ok je m'en occupe 

[Lucas.CSH]

Mais c'est génial.
En JS, parfait.

Gros boulot. Bravo.

[sylvain_p]

Voilà ! J'ai mis à 100ms puis remis à 1000ms car j'avais des erreurs de calcul sur des fichiers IGC, tant pis pour les lags (ça ne devrait pas arriver quand on trace le parcours à la souris vu le faible nombre de point)
J'ai rajouté aussi les secteurs FAI piqués directement de XC Planner :
https://spasutto.github.io/test-igc-xc-score/dist/score.html#y%7CosGox%7Cb%40~~CbxG%7Ck%40heD%7BfCieAuwAm%7DD%7BFagE
Y'a encore des bugs (notamment les dessins des secteurs qui sont coupés par moment)