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

[Eltamin]

Je connais pas PostGis, mais je suppose que

Ce qui est instantane c’est quand je fait :

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 :

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

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 )

[pol]

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.

[pol]

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

[pol]

Tu veux dire qu’on considere des coordonnees spheriques comme des coordonnées lineaires ? :affraid:
C’est vrai que pour ce que jeux en faire, a l’echelle de la France on peut faire une bidouille dans ton genre, mais faut voir si ca va encore marcher convenablement pour les traces GPS de la reunion :grat:

[marc]

Je suis pas sûr qu’on se soit compris… Mais si tu prends 2 points dont les coords sont données par (lon1, lat1) et (lon2, lat2), la distance euclidienne (sqrt( (lon2-lon1)²+(lat2-lat1)²)) te donnes bien une distance… Elle est juste pas en mètre, et tu as le droit de t’en servir :D. Ça va coincer dès que tu va avoir besoin de raisonner “distance classique” (en mètre, projetée sur un plan).

Mon approximation, c’est qu’une distance X calculée comme ça aura une valeur projetée constante Y. Plus la distance considérée est petite, moins ça va nous gêner. Les 2 trucs qui sont approximer:

• la terre est ronde, pas plate
• la terre n’est pas une sphère parfaite

Pour des distance de 50m, je doute que ça vienne perturber nos calculs. Très souvent les calculs qu’on croisent font l’approximation que la terre est une sphère, ça ne choque personne (à juste titre). Ce genre d’approximation est par contre gênante si tu cherches à calculer la vitesse de neutrinos. Les parapente, je pense que ça va aller

Utiliser des coordonnées sphérique “comme ci” c’était des coordonnées linéaire, ça marche pour plein de chose… tant que tu n’a pas besoin de la distance projetée au sol. Si tu regardes par exemple la bibliothèque “shapely” (souvent utilisée avec des coords sphériques), c’est ce qui se passe.

[Hub]

Donner comme tu le suggères, le même poids relatif aux minutes de latitude et aux minutes de longitude dans un calcul de distance est suffisamment OK pour une 1ère approximation, tant qu’on ne monte pas dans des latitudes importantes.

Plus près des pôles, on peut franchir des milliers de minutes de longitude en un seul pas.

C’est pourquoi la formule “correcte” utilise plutôt : i/cos(lat moyenne) [/i]

[marc]

Effectivement, je n’y avais pas pensé

[pol]

Le soucis c’est qu’un degre de longitude a une longueur variable et generalement differente d’un degre de latitude, donc ca va introduire de l’anisotropie dans la simplification, je vais avoir moins de precision dans la direction Nord-Sud que dans la direction Est-Ouest. Et c’est pas negligeable, en France ca fait un rapport de 1/1.42.
http://www.paraglidingforum.com/xcplanner/?location=Fiesch&flightType=cfd2&turnpoints=[[45.0,5.5],[46.0,5.5]]
http://www.paraglidingforum.com/xcplanner/?location=Fiesch&flightType=cfd2&turnpoints=[[45.25,6.0],[45.25,5.0]]

Au minimum il faudrait multiplier toutes les longitudes par le sinus cosinus de la latitude.

EDIT : grillé par Hub

[marc]

Dans ce cas, le mieux (je pense) est de projeter tes données avant de faire le calcul, mais ça risque de te coûter assez chers et il va falloir choisir la projection judicieusement en fonction des données traitées.

Et cette imprécision, ça va donner quoi au final tu penses ? J’ai du mal à voir l’impact que ça peut avoir sur la simplification des données.

[pol]

Et cette imprécision, ça va donner quoi au final tu penses ? J’ai du mal à voir l’impact que ça peut avoir sur la simplification des données.

Si je convertissais 1 m en x degrés en me basant uniquement sur les degrés de latitude, avec une tolerance de 100 m j’aurais effectivement une tolerance de 100 m dans la direction N-S mais une tolerance de seulement 70 m dans la direction E-W parcequ’un point situé x degrés de longitude d’une ligne N-S seraient considéré comme étant 100 m alors qu’il n’est qu’a 70 m (et dans une direction intermediaire, ca serait une valeur intermediaire entre 70 et 100). Ca serait pas critique, mais par rapport a la simplification rigoureuse on perdrait en efficacité si on se base sur la direction N-S pour la conversion m<->degrés et on perdrait en précision si on se base sur la direction E-W.

[Hub]

C’est quand même pas la mort de diviser par un cos(lat1+lat2/2) précalculé, pour avoir une distance plus “correcte” ?

[Hub]

[je veux dire cos(latmin+latmax/2) bien sûr, pas la peine de recaculer le bazar pour tous les points]

[pol]

C’est quand même pas la mort de diviser par un cos(lat1+lat2/2) précalculé, pour avoir une distance plus “correcte” ?

Oui, c’est une solution simple qui va bien marcher (sauf pour la Reunion et la Polynesie). Mais rien que pour le plaisir de faire un peu d’algorithmique, je reprogrammerais bien un Douglas-Peucker avec la distance rigoureuse en coordonnees geographiques. On verra si j’ai le temps. Pour ce qui est de la performance qui sera probablement degradee, c’est pas tres grave vu qu’on parle d’un bout de code qui ne sera appliqué qu’une seule fois au moment de charger les traces dans la base de donnees. Au lieu de 2 heures ca va prendre 6h, juste le temps d’aller faire un cross et de revenir en stop :ppte: .

[thanjuzo]

Si vous voulez du millimètre, c’est ceci qu’il vous faut :
http://geodesie.ign.fr/contenu/fichiers/Calcul_distance_volOiseau.pdf

:init:

[Hub]

C’est quand même pas la mort de diviser par un cos(lat1+lat2/2) précalculé, pour avoir une distance plus “correcte” ?

Oui, c’est une solution simple qui va bien marcher (sauf pour la Reunion et la Polynesie).

Bah pourquoi ça marcherait pas pour léziles?
Ca marche pour toute distance entre 2 points quelconques pas “trop” éloignés l’un de l’autre, en divisant le delta-longitude par le cosinus de la latitude moyenne de ces 2 points.
Mébon, je n’ai ptêt pas comprite la distance que tu veux calculer, c’est bien possible que ça marche pas trop bien pour la distance entre la métropole et léziles.

[pol]

J’avais dans l’idee de faire la bidouille en prenant une latitude moyenne pour toute la France, donc j’aurais ete oblige d’en definir une autre pour leziles.

[Hub]

Ah OK, vu. Je pensais (je n’ai pas lu toute la discussion) prendre une latitude moyenne pour un vol, ce qui (en l’état actuel de nos performances) ne s’étale pas sur plus de 2-3 degrés de latitude…

[pol]

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

Et avec une simplifcation de Douglas-Peucker:

• tolerance 10 m : 15.0 M de points (~34.4 % du nombre initial)
• tolerance 25 m : 9.5 M de points (~21.8 %)
• tolerance 50 m : 4.4 M de points (~10.1 %)
• tolerance 75 m : 2.4 M de points (~5.5 %)
• tolerance 100 m : 1.6 M de points (~3.7 %)
• tolerance 150 m : 1 M de points (~2.3 %)
• tolerance 200 m : 0.7 M de points (~1.7 %)
• tolerance 500 m : 0.3 M de points (~ 0.67 %)

http://pirk.wiki-parapente.fr/tmp/dp_eff.png

C’est mucho bueno ! A 10 m de tolerance on divise deja le nombre de points par 3 ! Je vais essayer de charger les traces avec une tolerance de 75 m pour voir de combien ca ameliore la vitesse de la recherche.

Pour le calcul de la distance j’ai corrigé la longitude avec la latitude moyenne du vol comme tu le suggerais, Hub. La distance du grand cercle c’est plus complique que ce que je croyais, il ne suffit pas de connaitre la formule entre deux points, il faut aussi trouver la distance du grand cercle entre un point et un autre grand cercle et ca fait mal a la tete.