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:
id | source | target | seq |
23359 | 14331 | 14299 | 1 |
23420 | 14299 | 14368 | 2 |
23489 | 14368 | 14301 | 3 |
23419 | 14301 | 14362 | 4 |
23421 | 14362 | 14300 | 5 |
23348 | 14300 | 4332 | 6 |
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