Outil de recherche de vols CFD (SIG / BdD géospatiales)

[marc]

Je vais finir par etre obligé de m'interesser a ces histoires de bases de donnees geospatiales dont Marc m'a parlé.

si ca te va de faire ca va geodjango & bd postgis, je suis partant pour participer ! Ca sera plus simple que les espaces aeriens, dont finalement, tout le monde se fout

[PiRK]

Est-ce qu'un gentil modo pourrait scinder ce sujet juste apres la premiere reponse de Mathieu et deplacer la suite dans le coin du geek avec un titre qui va bien ?   

[PiRK]

Bon, j'ai pas ete tres clair dans ma requete et du coup il manque deux ou trois messages qui permettent de comprendre qu'on parlait de faire un outil de recherche  geographique de vols CFD en utilisant les traces GPS Il se peut que ca degenere en un truc plus general sur l'utilisation des traces GPS pour diverses statistiques (je pense par exemple a une carte des thermiques en additionnant les Vz a un endroit donné).

Pour commencer j'ai fait une liste par saison des vols déclarés a la CFD avec les infos disponibles sur le site de la FFVL : http://pirk.wiki-parapente.fr/cfd/listes_vols/

Il y a deja de quoi faire de belles statistiques pour les amateurs de graphiques excel.

[Suspente]

si ca te va de faire ca va geodjango & bd postgis, je suis partant pour participer ! Ca sera plus simple que les espaces aeriens, dont finalement, tout le monde se fout

Non, non, tout le monde ne se fout pas des espaces aériens. J'attends avec impatience ta moulinette pleinement fonctionnelle 

Mais si en plus tu y ajoutes les fonctions suggérées par PiRK, alors là moi je dis 

[PiRK]

Ca avance petit a petit :


Il faut que je fasse des tests pour decimer les traces GPS avant de les charger dans la bdd parceque pour l'instant c'est assez lent si on centre la zone de recherche sur Saint Hil. Et apres il va falloir s'attaquer aux aspects cosmétiques de l'interface.

[marc]

L'interface, je pourrais aider... dans quelques temps ! On pourrait même intégrer avec le machin à espace aérien, vu que bizarrement, on utilise la même techno

Bravo !!!!

[Suspente]

Ouahou, à vous deux (Pirk et Marc) vous allez nous sortir un outil bien sympa. Désolé mes compétences sont limitées dans ce domaine (la programmation). Juste fait un peu de Basic et C++ ... il y a bien longtemps.

  et 

[marc]

Ouahou, à vous deux (Pirk et Marc)

c'est gentil, mais à part donner qqs pointeurs à Pirk, j'ai rien fait, donc c'est juste lui qu'il faut féliciter 
 

[Suspente]

c'est gentil, mais à part donner qqs pointeurs à Pirk, j'ai rien fait, donc c'est juste lui qu'il faut féliciter 
 

Euh et la moulinette à espaces aériens ça vient pas de toi ?

Donc système de recherche géographique de Pirk + moulinette de Marc (et quelques pointeurs) = cet outil bien sympa
D'où un  à chacun.

Marc, tu es trop modeste 

[PiRK]

Oui, Marc, ne soit pas si modeste. Sans toi j'aurais programmé le truc en assembleur Avec ton interface graphique ca aura nettement plus de gueule.

Il reste tout de meme un peu de boulot de mon coté, il faut que je trouve l'intervalle d'echantillonage maximum acceptable pour alléger le plus possible les traces. J'ai testé 9 s, mais ca prend toujours 1 minute pour la recherche centrée sur Saint Hil, et chaque année on va rajouter ~2000 traces a la bdd. Dix secondes pour un parapente qui vole en ligne droite bras haut sans vent  ca fait deja 100m  

[ptitkiki]

super vos truc les gars, continuez !  &

[PiRK]

J'ai besoin de vos avis de potentiels utilisateurs. J'ai fait quelques tests pour trouver la methode la plus efficace pour decimer les traces.

J'ai les resultats suivants :
* sur mes ~ 14500 traces GPS, j'ai un total de 43 millions de points
* si je decime en prenant pour critere un minimum de 10 secondes entre 2 points, j'ai 15 M de points
* si je decime en prenant pour critere un minimum de 20 secondes entre 2 points, j'ai  8 M de points
* si je decime en prenant pour critere un minimum de 50 metres entre 2 points, j'ai 18 M de points
* si je decime en prenant pour critere un minimum de 100 m entre 2 points, j'ai 9 M de points
* si je decime en prenant pour critere un minimum de 150 m entre 2 points, j'ai 6 M de points
* si je decime en prenant pour critere un minimum de 200 m entre 2 points, j'ai 4.6 M de points
* si je decime en prenant pour critere un minimum de 300 m entre 2 points, j'ai 3 M de points
* si je decime en prenant pour critere un minimum de 400 m entre 2 points, j'ai 2.3 M de points
* si je decime en prenant pour critere un minimum de 500 m entre 2 points, j'ai 1.8 M de points

On voit que filtrer avec un critere de distance marche mieux qu'avec un critere de temps, parcequ'on se debarasse de toute l'info sur les enroulages de thermiques qui ne sert a rien dans notre cas.
Pour moi, moins j'ai de points et mieux ce sera (plus rapide, moins de ressources, moins de chances de planter si plusieurs utilisateurs se connectent en meme temps). Personnellement je pense que la precision de 500 m serait suffisante, si j'ai besoin de trouver les traces qui  passent par un sommet donné je dessinerais un gros carre de 1 ou 2 km de coté. Mais en meme temps, au-dela des 200 m on n'a plus tellement de gain en efficacité, donc c'est probablement ce que je choisirais.

Si vous deviez utiliser ce programme pour trouver une trace GPS, combien de precision vous faudrait-il ? (voila une echelle pour vous faire une idée : http://www.paraglidingforum.com/xcplanner/?location=Fiesch&flightType=cfd2&turnpoints=[[45.23537,5.76211],[45.23673,5.76044]])



 

[piwaille]

 

une idée (qui vaut ce qu'elle vaut hein )
et si tu commençait par séparer les traces par région ? (après, quand tu cherches un point, tu sais retrouver de quelle région il s'agit)
tu stockes les traces (CFD) dans diverses bases : alpesN, alpesS, pyrénées ...

tu va me dire : le blème c'est que les traces des alpesN sont sur-majoritaires ... ben tu peux continuer à diviser jusqu'au niveau : chartreuse, belledonne etc ...
et les traces qui vont d'un massif à l'autre elles peuvent bien être doublées (triplées) vu que tu aura divisé ton temps de recherches.

non ?

[marc]

Avant de chercher à optimiser, il faut savoir ce qui coûte chers. Le nombre de points coûte :
 - en stockage: ça, je n'y crois pas trop, le stockage coûte plus grand chose
 - en calcul: certes. Mais avant de toucher aux données, il est parfois possible de "mieux" calculer.

Une fois que t'as retiré de l'info, c'est perdu pour toujours. Je serais toi, je calculerai différemment plutôt que de dégrader les données. Tu peux aussi faire du précalcul, comme à partir d'une trace, prendre une trace dont la topologie est équivalente ('simplify' je crois dans geos) mais avec le minimum de point nécessaires. Pour les polygone, je vois bien. Avec des traces, il faudrait tester pour voir si ça convient (tu l'as peut être déjà fait).

Et quand tu dis "on n'a plus tellement de gain en efficacité", tu as mesuré comment ? C'est quoi que tu appelles "efficacité" ?

La séparation par région n'aide pas, la BD fait déjà un tri par boîte englobante, et les traces qui traversent plusieurs région sont rares.

[PiRK]

Une fois que t'as retiré de l'info, c'est perdu pour toujours. Je serais toi, je calculerai différemment plutôt que de dégrader les données. Tu peux aussi faire du précalcul, comme à partir d'une trace, prendre une trace dont la topologie est équivalente ('simplify' je crois dans geos) mais avec le minimum de point nécessaires. Pour les polygone, je vois bien. Avec des traces, il faudrait tester pour voir si ça convient (tu l'as peut être déjà fait).

Perdu pour toujours, bof... on peut facilement faire deux bdd separees, une avec tous les points pour nos applications du futur et une allégée qui ne servira que pour la recherche. Comme tu dis l'espace disque n'est pas cher, d'autant plus que la base de donnees prend significativement moins de place que la somme des fichiers IGC d'origine.

Pour le precalcul, je n'ai pas encore testé, il faut que je vois ca. Mais l'idée que je m'en fais c'est que ca va pas etre forcement adapté a une trace GPS d'un vol en parapente, qui est quelque chose de tres specifique. Ce que j'essaye de faire en mettant une distance mini entre points c'est de virer tous les thermiques qui concentrent les points sans rien apporter a la recherche. J'ai peur qu'une fonction de simplification standard soit plus adaptee pour reduire le nombre de points sur de grandes lignes droite que pour des petites spirales. Mais comme dit, il faut que je teste.

Et quand tu dis "on n'a plus tellement de gain en efficacité", tu as mesuré comment ? C'est quoi que tu appelles "efficacité" ?

Je parle juste du taux de reduction du nombre de points par unité de distance perdue en precision. Genre quand on passe d'une precision de 50 m a 100 m on divise par 2, quand on passe de 400 a 500 le gain marginal est nettement plus faible.

[piwaille]

Perdu pour toujours, bof... on peut facilement faire deux bdd separees, une avec tous les points pour nos applications du futur et une allégée qui ne servira que pour la recherche.

eumpf .. me permet de réfléchir à "voix haute" hein

2 bases de données peut être pas ... mais 2 tables :
une table des points et une table des chemins (qui relie les points) ...
du coup dans ta table des chemin tu peux avoir (pour 1 même vol) et le chemin complet et le "symplify" (un DL2 5 ? ) qui "représente" le vol

réflexion suivante : quand tu calcules le simplify (si tu te fais une fonction perso), vu que tu as le temps, tu peux déjà tenter de t'appuyer sur des points déjà existants ... un peu comme le fait actuellement la déclaration CFD : la trace passe à moins de x km de tel point remarquable (remarqué) ... on la fait passer par ...
après faut nourrir la base des points remarquables

[marc]

Plutôt que 2 tables, 1 champs supplémentaire serait plus judicieux/facile (Pirk utilise GeoDjango) 1 vol serait alors représenté par sa trace complète et une version simplifiée (+ d'autres info bien sûr).

[PiRK]

après faut nourrir la base des points remarquables

Oui, ca serait un gros boulot.

une table des points et une table des chemins (qui relie les points) ...

Plutôt que 2 tables, 1 champs supplémentaire serait plus judicieux/facile (Pirk utilise GeoDjango) 1 vol serait alors représenté par sa trace complète et une version simplifiée (+ d'autres info bien sûr).

Je ne sais pas exactement comment fonctionne une base de donnees et qu'est ce qui influence la performance des recherches, mais quand j'ai fait mes test "traces completes" vs. "decimation a 10s" vs. "decimation a 20s"  j'ai eu l'impression que la recherche des traces etait quasiment instantannee dans tous les cas mais que ca ralentissait au moment d'y acceder en fonction de la quantité de données trouvée meme en n'accedant qu'a des champs leger tel que le nom du pilote, la distance... donc avant meme d'essayer d'acceder a la trace. Donc je me demande si rajouter un champ tout en gardant la grosse trace complete va vraiment arranger les choses. Mais je rajoute ca sur ma liste de tests a faire quand j'aurais le temps.

EDIT: Peut-etre que la recherche initiale se fait uniquement sur les boites englobantes et que la recherche precise se fait par la suite au moment d'acceder aux donnees   Tu comprends comment ca marche precisement, Marc ?
Si l'idees de faire deux champs fonctionne, on peut meme imaginer faire une recherche initiale sur le champs avec une precision de 500 m voir 1 km puis une seconde recherche avec la trace complete sur le premier sous-ensemble.

EDIT2: Non, en fait mon idee est conne. On va perdre des traces a la premiere recherche et on va pas les retrouver a la deuxieme. 

[marc]

Plusieurs choses... Faut voir quelle opération prend du temps *exactement*. La BD fait effectivement un filtre avec les boîtes englobantes (cherche "index spatial", regarde ce que fait la bibliothèque "rtree", par exemple. Il y a beaucoup de chose à lire là dessus) pour les opérations qui peuvent en bénéficier (recherche d'intersection & cie).
Par contre, tu utilises une couche d'abstraction qui potentiellement te cache des opérations coûteuses ! La recherche peut être super rapide, et dès que tu regardes les valeurs retournées, ça prend du temps: peut être que tu fais des conversions sans t'en rendre compte ? (pense que tu agis à plusieurs niveaux: BD/postgis, puis GeoDjango, puis GEOS, puis peut être JSON & cie ? Une même opération peut se faire à chaque niveau, mais à des coûts très différents ! Autant que possible, il faut faire les opérations coûteuses au niveau BD car elle est sensée être fait pour ça. Plus tu montes dans les abstractions, plus ça va te coûter bonbon. Si tu boucles sur les points d'une trace dans ton code python par exemple, ça va être lent à mourir.

Effectivement, rajouter un champs dans la table ne va pas arranger ton problème car je pensais l'utiliser pour les recherches, qui sont déjà instantanées d'après ce que tu dis. Si tu peux me dire où dans ton code se passe l'opération qui prend trop de temps à ton goût, je peux essayer d'y jeter un oeil...

[PiRK]

Effectivement, rajouter un champs dans la table ne va pas arranger ton problème car je pensais l'utiliser pour les recherches, qui sont déjà instantanées d'après ce que tu dis. Si tu peux me dire où dans ton code se passe l'opération qui prend trop de temps à ton goût, je peux essayer d'y jeter un oeil...

Ce qui est instantane c'est quand je fait :

Code:

v = Vol.objects.filter(trace_gps__intersects = GEOMGeometry("POLYGON((5.85 45.3667, 5.9667 45.3667, 5.8333 45.2667, 5.85 45.3667))")).order_by('-distance') 

Et ce qui prend du temps c'est d'acceder a un element ou tous les elements de v :

Code:

print(v)   # 45 s
print(v[156].distance)  # 15 s
for tmp in v:
    print (tmp.date, tmp.pilote, tmp.distance)   # 45 s
len(v)    # 45 s pour 2476 traces

A noter que dans le cas des commandes qui accedent a toutes les donnees (len(v), print(v) ou la boucle for), seule la premiere prend du temps. Les suivantes sont instantanees.

Je fais l'equivalent de la boucle for dans mon template de page web, je perd peut etre de la performance avec la couche django.contrib.template.

[Eltamin]

Je connais pas PostGis, mais je suppose que

Ce qui est instantane c'est quand je fait :

Code:

v = Vol.objects.filter(trace_gps__intersects = GEOMGeometry("POLYGON((5.85 45.3667, 5.9667 45.3667, 5.8333 45.2667, 5.85 45.3667))")).order_by('-distance') 

Ca te fait un prepared statement lors de l'instanciation de v, mais à ce moment là la requete n'est pas éxécutée.

Et ce qui prend du temps c'est d'acceder a un element ou tous les elements de v :

Code:

print(v)   # 45 s
print(v[156].distance)  # 15 s
for tmp in v:
    print (tmp.date, tmp.pilote, tmp.distance)   # 45 s
len(v)    # 45 s pour 2476 traces

A noter que dans le cas des commandes qui accedent a toutes les donnees (len(v), print(v) ou la boucle for), seule la premiere prend du temps. Les suivantes sont instantanees.

Je fais l'equivalent de la boucle for dans mon template de page web, je perd peut etre de la performance avec la couche django.contrib.template.

Quand tu accèdes pour la première fois à ta ressource (ton instance v) la requête postgresql est exécutée. Ce qui est bizarre c'est que print(v[156].distance) mette ensuite 15sec. Cela voudrait dire qu'une requete spécifique est réalisée pour accéder à cet élément. Marc va me corriger sur le python, mais je pense qu'à chaque accès à une donnée de ta liste v, tu crées une nouvelle instance d'un objet postgis ou que sais-je (ton v[156] ou tous les tmp dans la boucle) et qu'à chaque fois une requete est exécutée (on a les mêmes problèmes avec des couches d'abstractions de bdd en php comme doctrine ou propel)

Tu pourrais sniffer ce qu'il se passe entre ta base postgresql et ton programme avec un bon vieux

Code:

tcpdump -Xvv port "portdelabdd"

, ou débugger chaque requete sql depuis python et ainsi voir exactement quelles requetes sont exécutées et à quel moment. Y'a pas moyen de construire ton v comme une liste imbriquée de données ou alors une liste avec des dictionnaires imbriqués et non pas une liste d'objets postgis, comme ça a l'air d'être le cas (puisque distance est un membre de l'instance v[156] dans l'exemple) ? Ca te ferait une bonne grosse liste en mémoire (quoique 2476 éléments y'a pire...) mais une seule requête initiale (ça fait un bail que j'ai fait ni python ni sql hein, pas tapper )

[PiRK]

Quand tu accèdes pour la première fois à ta ressource (ton instance v) la requête postgresql est exécutée. Ce qui est bizarre c'est que print(v[156].distance) mette ensuite 15sec. Cela voudrait dire qu'une requete spécifique est réalisée pour accéder à cet élément. Marc va me corriger sur le python, mais je pense qu'à chaque accès à une donnée de ta liste v, tu crées une nouvelle instance d'un objet postgis ou que sais-je (ton v[156] ou tous les tmp dans la boucle) et qu'à chaque fois une requete est exécutée (on a les mêmes problèmes avec des couches d'abstractions de bdd en php comme doctrine ou propel)

Ce que je voulais dire c'est que chacune de ces commandes met le temps spécifié si je l'execute directement apres l'instanciation de v. Mais une fois que j'ai executé une commande qui accede a toutes les données, les suivantes prennent chacune moins d'une seconde (y compris l'acces a un champ distance d'un element v[156]).
Donc je suppose que si je lance n'importe quelle commande qui doit acceder a au moins un champ de chaque element, ca force la requete a etre completement executee et on doit se retrouver avec une simple liste d'objets python en memoire.


Pour en revenir a l'histoire de la simplification de la trace, on m'a dit sur un autre forum que l'algo utilisé par "simplify" est Douglas-Peuker. Ca a l'air bien efficace pour ecremer la trace en gardant la forme generale, j'ai hate d'avoir le temps de le tester (en ce moment je passe moins d'une heure devant un pc par jour, trop de vrai boulot  ).  Mais on va forcement perdre des donnees dans l'affaire.

[marc]

Simplify <=> DP, c'est marqué dans la doc

GEOSGeometry.simplify(tolerance=0.0, preserve_topology=False)
Returns a new GEOSGeometry, simplified using the Douglas-Peucker algorithm to the specified tolerance. A higher tolerance value implies less points in the output. If no tolerance is tolerance provided, it defaults to 0.

By default, this function does not preserve topology - e.g., Polygon objects can be split, collapsed into lines or disappear. Polygon holes can be created or disappear, and lines can cross. By specifying preserve_topology=True, the result will have the same dimension and number of components as the input, however, this is significantly slower.

Sinon, tu peux rapeller sur quelle type de machine tu fais tes tests ? Je crois que tu parlais d'un EeePC à un moment... Les BD restent des applications relativement gourmandes en ressources. Si ton code est facilement distribuable, je peux tester sur la machine que j'utilise pour mes tests.

[PiRK]

Sinon, tu peux rapeller sur quelle type de machine tu fais tes tests ? Je crois que tu parlais d'un EeePC à un moment... Les BD restent des applications relativement gourmandes en ressources. Si ton code est facilement distribuable, je peux tester sur la machine que j'utilise pour mes tests.

Oui, c'est un EeePC avec 1 Go de ram, c'est pas tres performant comme bete. Et je fait mes test sous windows, ce qui n'arrange pas les choses. Je vais essayer de mettre ce que j'ai deja fait en ligne quand j'aurais le temps. Il ne doit pas y avoir grand chose a adapter, juste un ou deux noms de fichiers codés en dur dans ma fonction de chargement des traces GPS.

GEOSGeometry.simplify(tolerance=0.0, preserve_topology=False)
Returns a new GEOSGeometry, simplified using the Douglas-Peucker algorithm to the specified tolerance. A higher tolerance value implies less points in the output. If no tolerance is tolerance provided, it defaults to 0.

By default, this function does not preserve topology - e.g., Polygon objects can be split, collapsed into lines or disappear. Polygon holes can be created or disappear, and lines can cross. By specifying preserve_topology=True, the result will have the same dimension and number of components as the input, however, this is significantly slower.

J'ai pas reussi a trouver dans quelle unité la tolerance doit etre exprimé. Metres ? Degres ? Minutes d'arc ?

[marc]

Sinon, tu peux rapeller sur quelle type de machine tu fais tes tests ? Je crois que tu parlais d'un EeePC à un moment... Les BD restent des applications relativement gourmandes en ressources. Si ton code est facilement distribuable, je peux tester sur la machine que j'utilise pour mes tests.

Oui, c'est un EeePC avec 1 Go de ram, c'est pas tres performant comme bete. Et je fait mes test sous windows, ce qui n'arrange pas les choses. Je vais essayer de mettre ce que j'ai deja fait en ligne quand j'aurais le temps. Il ne doit pas y avoir grand chose a adapter, juste un ou deux noms de fichiers codés en dur dans ma fonction de chargement des traces GPS.

tu me dis !

J'ai pas reussi a trouver dans quelle unité la tolerance doit etre exprimé. Metres ? Degres ? Minutes d'arc ?

en général, quand rien n'est spécifié pour les unité, c'est que c'est "agnostique", la distance étant calculée classiquement à partir des coordonnées que tu donnes. Si tu donnes des coord GPS (lat/lon), tu travailles avec des mesures d'angle... Je t'avoue que je me suis pas casser la tête quand j'ai eu à faire un échantillonnage basé sur la distance: j'ai regardé quelle était la distance mesurée de 2 points que je savais à 50m l'un de l'autre et ai utilisé cette valeur... C'est un peu approximatif (en principe, la terre n'étant pas ronde, la correspondance angle/distance projetée n'est pas constante avec la position).
Si tu veux un truc un peu plus exact, tu dois pouvoir jouer avec la classe Distance offerte par GeoDjango... Mais là, ça me semble un peu overkill. Ma bidouille devrait déjà donner des résultats acceptables