Suite

Séparation de segments de chemin GPS disjoints dans Postgres


Cela implique beaucoup de code ; si cela convient mieux à StackOverflow, faites-le moi savoir !

Je travaille sur un projet de trajets construits à partir de coordonnées GPS. Je cartographie les trajets enregistrés sur une page Web, avec la version 0.35 de Windshaft. Les trajets sont collectés à partir d'une application mobile et les données GPS sont insérées dans une base de données Postgres (9.3) (avec PostGIS (2.1.2) installé). Les tableaux concernés sont :

coord_geog : Colonne | Type | ---------+-------------------------------| identifiant | entier | id_voyage | entier | enregistré | horodatage sans fuseau horaire | geog | géographie(Point,4326) | géom | géométrie(Point,4326) | suivant | entier | trip_geom: Colonne | Type | ---------+-------------------------------| identifiant | entier | but | caractère variable (255) | démarrer | horodatage sans fuseau horaire | arrêter | horodatage sans fuseau horaire | géom | géométrie(LineString,4326) |

Leid_voyagecolonne decoord_geogcorrespond à laidentifiantcolonne devoyage_geom. L'application fournit des données pour leidentifiant,id_voyage,enregistré, etgeogcolonnes decoord_geom, et leidentifiant,objectif,début, etarrêtercolonnes devoyage_geom. En fait, je ne suis pas sûr de ce quegéomcolonne decoord_geogest utilisé pour, mais j'ai trop peur de le supprimer (et il ne semble pas être utilisé dans tout ce qui est mentionné dans cette question).

Je ne sais pas trop comment fonctionne l'ensemble de Windshaft, mais si cela peut aider, la configuration de Windshaft est actuellement définie comme suit :

req.params.sql = "(sélectionnez * de trip_geom_frag où le but est semblable à '" + req.params.purpose + "%') comme trip_geom_frag"; req.params = _.extend({}, req.params, {style: style});

je vais précisertrip_geom_fragplus bas - c'est similaire àvoyage_geom.

La tâche spécifique que j'essaie d'améliorer consiste à construire un chemin LineString à partir de tous les points d'un chemin.

J'ai hérité d'un script Python censé gérer cette tâche. Bien que je ne connaisse pas particulièrement bien Python ou SQL, j'ai reconnu que beaucoup de choses que le script faisait pouvaient être effectuées en tant que SQL pur, ce qui a entraîné une accélération majeure au début. Une fois que les points sont anonymisés (découpés à chaque fin d'un voyage), une requête comme celle-ci construit le LineString :

UPDATE trip_geom t SET geom=(SELECT ST_MakeLine(line.geom) FROM (SELECT c.recorded, c.geom FROM coord_geog c WHERE c.trip_id=t.id ORDER BY c.recorded ASC) comme ligne) WHERE t.id= %s ;

où le%sparamètre est unidentifiantchamp d'une rangée dansvoyage_geom. Cela construit un LineString reliant les points du voyage. Cependant, il y a généralement des erreurs dans les données GPS, où une mauvaise position GPS provoque la localisation incorrecte d'un ou plusieurs points loin, ou l'enregistrement est interrompu et repris plus tard, ce qui entraîne un grand « saut » dans le voyage.

Les points valides sont généralement proches les uns des autres (puisque les trajets sont des trajets à vélo à une vitesse relativement faible), donc lorsqu'un trajet a toutes les données GPS valides, le LineString est un tracé assez lisse (fond de carte par CartoDB) :

Cependant, de nombreux trajets (surtout les longs) comportent des sauts ou des erreurs, ce qui donne des trajets qui ressemblent à ceci :

Bien que je sois sûr qu'il existe des cyclistes très accomplis, je doute que quelqu'un ait pu traverser une rivière à vélo; la ligne droite semble être causée par le cycliste faisant une pause et reprenant un enregistrement de trajet. Ces erreurs ne sont pas un gros problème lorsqu'elles sont isolées, mais lorsqu'elles sont nombreuses, la carte des trajets devient très encombrée de lignes droites qui traversent de grandes zones de la carte.

Par conséquent, la tâche spécifique que j'essaie d'accomplir consiste à générer des chemins LineString sans points adjacents très éloignés les uns des autres. J'imagine que c'est une tâche bien adaptée à PostGIS (ou SQL en général), mais j'ai du mal à trouver une solution.

Ma première tentative de solution a été de supprimer des points qui étaient loin du point précédent. Comme je n'ai plus le SQL exact, voici la procédure en pseudo-code :

pour t en trajets : i = 1 tandis que i < t.points.longueur : current_pt = t.points[i] last_pt = t.points[i-1] if ! ST_DWithin( current_pt, last_pt, 100 ): delete_point( current_pt ) else: i = i + 1

Cela a résulté en des trajets en douceur, mais les trajets avec des sauts dans les données GPS ont été tronqués après le saut. Par exemple, dans un trajet avec un saut entre le premier et le deuxième point du trajet, tous les points du trajet après le premier point seraient supprimés.

Ma deuxième (et actuelle) solution consiste à créer une deuxième table commevoyage_geompour contenir les LineStrings des voyages, qui sont séparés chaque fois qu'il y a un saut entre les points. J'ai décidé d'appeler ces chemins fragmentés - il y a probablement un meilleur terme. Voici le nouveau tableau que j'ai créé :

trip_geom_frag: Colonne | Type | ---------+-------------------------------| identifiant | entier | géom | géométrie(LineString,4326) | but | caractère variable (255) | voyage_orig| entier |

Ensuite, en utilisant leSuivantcolonne decoord_geog(que j'ai ajouté), j'utilise une requête comme celle-ci pour construire une sorte de liste chaînée des points de chaque trajet, de sorte qu'un-1valeur représente soit un saut dans les points, soit la fin d'un trajet :

UPDATE coord_geog cur_pt SET next = CASE WHEN ST_DWithin( cur_pt.geog, (SELECT geog FROM coord_geog WHERE trip_id=cur_pt.trip_id ET enregistré > cur_pt.recorded ORDER BY enregistré ASC LIMIT 1), %s) THEN 1 ELSE -1 END;

Ensuite, en Python, j'insère une ligne danstrip_geom_fragpour chaque segment d'un trajet, la fin d'un segment étant signalée par un -1 :

pour t dans les trajets : trip_id = t.id c.execute('SELECT id, next FROM coord_geog WHERE trip_id=%s ORDER BY id ASC;', (trip_id,)); coords = c.fetchall() ind = [coord[1] for coord in coords] tandis que len(coords) > 0 : i = ind.index(-1) c.execute('INSERT INTO trip_geom_frag (geom, orig_trip, purpose ) SELECT ST_MakeLine(line.geom), %s, %s FROM (SELECT c.geom FROM coord_geog c WHERE c.trip_id=%s AND c.id >= %s AND c.id <= %s ORDER BY c. enregistré ASC) comme ligne ;', (trip_id, purpose, trip_id, coords[0][0], coords[i][0], )) del coords[:i+1] del ind[:i+1]

Encore une fois, je ne suis pas très expérimenté en Python ou en SQL, alors pardonnez-moi si c'est horrible ; Je suis presque sûr qu'il existe un moyen de le faire sans mélanger les données entre Python et Postgres.

Dans le meilleur des cas, en l'absence de sauts ou d'erreurs GPS, cela produit un seul LineString, ou, dans le cas de sauts ou d'erreurs, éventuellement plusieurs LineStrings. Cela produit des chemins qui sont séparés chaque fois qu'il y a un saut entre les points (mêmes données illustrées):

Ces données sont exactement comme je l'espérais qu'elles sortent, c'est donc une solution suffisante pour le moment. Cependant, il y a actuellement 800 voyages et environ 1,5 million de points au total ; les traiter a pris environ quatre jours (sur un serveur de merde) - je ne sais pas si c'est parce qu'il y a quelque chose qui ne va pas avec Postgres ou si c'est juste parce que ma solution Python est si inefficace. Quoi qu'il en soit, si pour une raison quelconque je dois re-traiter tous les voyages, cela pourrait prendre beaucoup trop de temps avant que les voyages ne soient prêts.

À mon avis, voici quelques approches qui pourraient bien fonctionner :

  • Insérer des coordonnées dans le LineString d'une manière qui permet d'exclure des segments particuliers
  • Partitionner chaque voyage en segments contigus, en changeant les arguments en ST_MakeLine
  • Faire en sorte que Windshaft ignore les segments d'une chaîne de ligne qui dépassent une certaine longueur
  • Supprimez ST_MakeLine et créez plutôt un chemin personnalisé qui ignore en quelque sorte un saut de points
  • Quelque chose d'évident que je ne connais pas car je ne connais pas trop les outils présents

J'espère qu'il existe une solution simple, ne nécessitant idéalement que PostGIS, qui puisse déterminer où les points d'un voyage doivent être partitionnés et les insérer dans une table. Ma question est donc la suivante : quelle approche dois-je adopter pour partitionner les chemins utilisés dans les appels à ST_MakeLine pour ne dessiner que des points contigus ?

Étant donné que j'enregistre déjà les données telles qu'elles ont été précédemment construites (non fragmentées) dans une table séparée, je suis libre de modifier n'importe laquelle des tables ou de modifier n'importe laquelle des données si cela aide d'une manière ou d'une autre.


Mise à jour : j'ai configuré Postgres sur ma machine locale (beaucoup plus puissante) et téléchargé la base de données, en réexécutant le traitement localement. C'est beaucoup plus rapide - il semble que tous les points puissent être traités en moins de 30 minutes, ce qui signifie que le coupable était en effet un serveur de merde. Ce serait quand même bien d'avoir une solution en SQL pur.


Ceci est ma tentative pour une requête qui devrait créer des parties de voyages, divisées en sauts d'environ 100 m.

CREATE TABLE trip_geom_parts ( trip_id entier NON NULL, part_id entier NON NULL, horodatage de début sans fuseau horaire, horodatage d'arrêt sans fuseau horaire, geom geometry(linestring, 4326), PRIMARY KEY (trip_id, part_id)); CRÉER UNE SÉQUENCE TEMPORAIRE seq; INSERT INTO trip_geom_parts (trip_id, part_id, start, stop, geom) AVEC s1 AS (SELECT trip_id, CASE WHEN trip_id = lag(trip_id) OVER w THEN CASE WHEN ST_Distance_Sphere(geom, lag(geom) OVER w) < 100.0 THEN currval( 'seq') ELSE nextval('seq') END ELSE setval('seq', 1) END AS part_id, enregistré, geom FROM coord_geog WINDOW w AS (PARTITION BY trip_id ORDER BY enregistré)) SELECT trip_id, part_id, min(recorded ) AS start, max(enregistré) AS stop, ST_MakeLine(geom ORDER BY enregistré) FROM s1 GROUP BY trip_id, part_id;

Pour de meilleures performances, il peut être utile de

CRÉER UN INDEX SUR coord_geog (trip_id, enregistré);

Je ne l'ai pas testé, donc peut-être besoin d'un débogage.


Voir la vidéo: Jeux en bout des segments (Octobre 2021).