lundi 15 février 2016

PostGIS et pgrouting: Comment ordonner les segments d'une rue ?

On a chargé dans PostGIS une table des segments des rues (table "segment"). Cette table a été construite sous ArcGIS et transférer dans PostGIS avec FME. Le réseau que l'on a créé est orienté: le sens positif correspond au sens de circulation. Lorsque les voies sont à double sens, une convention est utilisée pour orienter les segments. Ainsi, tous les segments d'une même voie (rue ou route) sont dans le même sens.

Dans PostGIS, on utilise l'extension pgRouting pour travailler avec ce réseau. La première étape est de créer la topologie avec la fonction "pgr_CreateTopology". Cette fonction ajoute deux colonnes "source" et "target" à la table "segment" (celle qui contient la géométrie des segments) et elle crée un nouvelle table "segment_vertices_pgr" (le préfixe "segment" provient du nom de notre table). C'est une table de points: un champ géométrie de type point et un identifiant, les autres champs ne sont pas importants. Ces points sont les jonctions entre les segments, c'est-à-dire les nœuds du réseau topologique. La fonction "pgr_CreateTopology" ajoute les identifiants des nœuds de début et de fin de chaque segment dans les champs "source" et "target".

Dans la table des segments, j'ai aussi des informations sur les codes des rues. Une rue est généralement composée de plusieurs segments. Par exemple, je fais une requête pour retrouver tous les segments de la rue 380027 (c'est son code: son nom n'a pas d'importance ici):

select id, source, target
from route.segment
where code_rue = 380027
order by id ;


Ce qui me renvoie le tableau suivant:


id source target
23348 14300 4332
23359 14331 14299
23419 14301 14362
23420 14299 14368
23421 14362 14300
23489 14368 14301

Avec QGIS, voila ce que ça donne:


En blanc, on a représenté la table "segment" avec l'identifiant comme label. On a aussi ajouté la table "segment_vertices_pgr" dont les identifiant sont soulignés. La rue 380027 est en jaune sur l'image et commence à gauche. Le premier segment est le 23359, puis 23420, 23489, 23419, 23421 pour finir par le segment 23348.

On voit que les segments ramenés par la requête ne sont pas dans l'ordre d'affichage. Sur l'image, les numéros des segments (les "id" de la requête) ne se suivent pas. Il n'y a pas d'ordre non plus dans les identifiants des nœuds. Le "order by" de la requête ne sert à rien!

On sait que les champs "source" et "target" donnent une information sur le sens du segment: le nœud "target" du premier segment de la rue est le nœud "source" du second segment, etc. Les segments sont chaînés grâce à ces deux champs, mais quelle requête pourrait les lister dans l'ordre d'affichage ?

Ce problème de chaînage est classique en informatique. On utilise souvent un algorithme récursif de parcourir d'arbre. La documentation de PostgreSQL fourni un mécanisme de pré-requête avec "WITH" et une variante intéressante pour notre cas "WITH RECURSIVE". Cette pré-requête a pour intérêt d'éviter une sous-requête (syntaxe lourde et peu performant). Le fonctionnement récursif n'est pas très  bien expliqué dans la documentation de PostgreSQL. Par contre, le blog de Tran Xuan Truong donne un exemple d'utilisation de "WITH RECURSIVE" pour parcourir un arbre.

Pour qu'un algorithme récursif "fonctionne", il y a trois conditions à respecter: une condition de départ, une condition de propagation et une condition d'arrêt. Dans notre cas, la condition de départ est donnée par le premier segment: c'est celui dont le nœud "source" ne se retrouve pas dans les "target" des segments de la rue (il n'est chaîné à aucun segment de la rue):

select s.id, s.source, s.target
from route.segment s
where s.code_rue = 380027
and s.source not in (select s.target
    from route.segment s
    where code_rue = 380027) ;

 
Ce qui renvoie:

id source target
23359 14331 14299

La condition de propagation est donnée par le chaînage: le noeud "source" du segment suivant est le noeud "target" du segment précédent. La condition d'arrêt est ici assez simple puisque la liste des segments de la rue est finie (5 segments).

Ces trois conditions sont mis en forme dans la requête SQL de la manière suivante:

WITH RECURSIVE ordered_list(id, source, target, seq) as (
    select id, source, target, 1
    from route.segment
    where code_rue = 380027
    and source not in (select target
        from route.segment
        where code_rue = 380027)
    UNION ALL
    select s.id, s.source, s.target, ol.seq + 1
    from route.segment s
    join ordered_list ol on s.source = ol.target
    where code_rue = 380027
    )
select *
from ordered_list ;



L'ordre "WITH RECURSIVE" crée une table temporaire, que j'appelle "ordered_list". Dans la première partie de la définition, on retrouve la condition de départ. Ensuite, "UNION ALL" permet d'ajouter la condition de propagation: un "select" sur les tables "segment" et "ordered_list" (la récursivité s'applique ici) et une jointure entre les nœuds "target" et "source". On peut remarquer que j'ai ajouté un attribut "seq" pour suivre le parcours.

Le résultat est le suivant:


idsourcetargetseq
2335914331142991
2342014299143682
2348914368143013
2341914301143624
2342114362143005
233481430043326

Grâce à cette ordre "WITH RECURSIVE" on peut parcourir tout un réseau dans l'ordre. Cette extension du langage SQL est particulièrement intéressante pour les réseaux où ce type de problème se rencontre fréquemment.
 




Aucun commentaire:

Enregistrer un commentaire