SpatiaLite Cookbook

	Repas gastronomique: Chez Dijkstra
Février 2011

Précèdent

Table des matières

SpatiaLite supporte nativement un module interne appelé VirtualNetwork
A partir de n'importe quel network (réseau) ce module est capable d'identifier le chemin le plus court.
Le module VirtualNetwork est basé sur des des algorithmes très efficaces, ce qui lui permet de traiter très rapidement des réseaux de très grande taille.

Bases de l'analyse réseau

Toutes les couches de type réseau routier ne correspondent pas forcement à un réseau.
Un vrai réseau doit satisfaire de nombreuses conditions particulières, i.e. qu'il doit être un graphe.

La théorie des Graphes est une branche complexe des mathématiques;
Si cela vous intéresse, vous trouverez des informations sur:
Graph Theory
Shortest Path Problem
Dijkstra's Algorithm
A* Algorithm

En simplifiant:

une réseau est un ensemble d'arcs
chaque arc est connecté à deux noeuds (nodes)
chaque arc possède une direction:
i.e. l'arc allant du nœud A au nœud B n'est pas nécessairement le même que celui allant de B à A.
chaque arc est caractérisé par un coût (cost) (e.g. longueur, temps de trajet, capacité, ...)
Les arcs et les noeuds doivent être identifiés de manière unique et explicite via un identifiant unique.
la géométrie des arcs se doit d'être topologiquement correcte.

A partir d'un réseau aka graphe , les algorithmes Distraite et A* sont capables de déterminer le chemin le plus court (coût minimal de liaison) entre deux points.

Il existe plusieurs sources de données de type type réseau.
L'un des plus connus et couramment utilisés est OSM [Open Strette Mao], une base de donnée mondiale totalement gratuite.
Il existe plusieurs sites distribuant les données OSM; les principaux étant:

Pour notre exemple, on téléchargera le jeu de donné à partir de cette adresse: fossilisation
On téléchargera le jeu de donnée TOSCANA.osm.bz2

Étape 1: décompressez le jeu de donnée OSM..
e.g. vous pouvez utiliser 7-zip pour l'extraction. www.7-zip.org

Step 2: les jeux de donnée OSM sont des fichiers XML
(visualisable avec un simple éditeur de texte).
SpatiaLite propose d'un outil spécifique pour charger les données OSM dans une BDD: spatialite_osm_net

>spatialite_osm_net -o TOSCANA.osm -d tuscany.sqlite -T tuscany -m
SQLite version: 3.7.4
SpatiaLite version: 2.4.0-RC5
using IN-MEMORY database
Loading OSM nodes ... wait please ...
  Loaded 1642867 OSM nodes
Verifying OSM ways ... wait please ...
  Verified 60893 OSM ways
Disambiguating OSM nodes ... wait please ...
  Found 40 duplicate OSM nodes - fixed !!!
Loading network ARCs ... wait please ...
  Loaded 121373 network ARCs
Dropping temporary table 'osm_tmp_nodes' ... wait please ...
  Dropped table 'osm_tmp_nodes'
Dropping index 'from_to' ... wait please ...
  Dropped index 'from_to'
exporting IN_MEMORY database ... wait please ...
  IN_MEMORY database succesfully exported
VACUUMing the DB ... wait please ...
  All done: OSM graph was succesfully loaded
>

Très rapidement:

-o TOSCANA.osm sélectionne les données OSM à charger.
-d tuscany.sqlite sélectionne la BDD a créer et peupler.
-T tuscany va créer la colonne géométrique contenant les données OSM
-m une BDD temporaire va être utilisée, afin d'accélérer le processus

SELECT *
FROM tuscany;

id	osm_id	class	node_from	node_to	name	oneway_from_to	oneway_to_from	length	cost	geometry
...	...	...	...	...	...	...	...	...	...	...
2393	8079944	tertiary	659024545	659024546	Via Cavour	1	1	7.468047	0.537699	BLOB sz=80 GEOMETRY
2394	8079944	tertiary	659024546	156643876	Via Cavour	1	1	12.009911	0.864714	BLOB sz=96 GEOMETRY
2395	8083989	motorway	31527668	319386487	Autostrada del Sole	1	0	424.174893	13.882087	BLOB sz=80 GEOMETRY
2396	8083990	motorway	31527665	31527668	Autostrada del Sole	1	0	130.545183	4.272388	BLOB sz=112 GEOMETRY
...	...	...	...	...	...	...	...	...	...	...

JPetite vérification:

une seule table Tuscany dans la BDD créée par spatialite_osm_net
chaque ligne correspond à un arc (network arc)
les noeuds connectant chaque arc sont identifiés par les colonnes node_from et node_to
oneway_from_to et oneway_to_from détermine si l'arc peut être parcouru dans les deux sens.
length est la longueur de l'arc (en mètres).
cost est l'estimation du temps de trajet (en secondes).
geometry est la représentation géométrique (LINESTRING) de l'arc.

note #1: les noeuds ne sont pas représentés dans une table séparée, car ils peuvent être déduits grâce aux arcs.

note #2: til s'agit ici d'un vrai réseau, mais en l'état actuel, il ne permet pas de lancer les analyses.
une étape supplémentaire est nécessaire, i.e. créer une table VirtualNetwork.

On va utiliser spatialite_gui afin de créer cette table.
Notons tout de même que cette opération est également permise par l'outil spatialite_network
(cet outil permet par ailleurs de diagnostiquer les problèmes rencontrés lors de l'opération).

SELECT *
FROM tuscany_net
WHERE NodeFrom = 267209305
AND NodeTo = 267209702;

Algorithm	ArcRowid	NodeFrom	NodeTo	Cost	Geometry	Name
Dijkstra	NULL	267209305	267209702	79.253170	BLOB sz=272 GEOMETRY	NULL
Dijkstra	11815	267209305	250254381	11.170037	NULL	Via Guelfa
Dijkstra	11816	250254381	250254382	8.583739	NULL	Via Guelfa
Dijkstra	11817	250254382	250254383	12.465016	NULL	Via Guelfa
Dijkstra	16344	250254383	256636073	15.638407	NULL	Via Cavour
Dijkstra	67535	256636073	270862435	3.147105	NULL	Piazza San Marco
Dijkstra	25104	270862435	271344268	5.175379	NULL	Piazza San Marco
Dijkstra	25105	271344268	82591712	3.188657	NULL	Piazza San Marco
Dijkstra	11802	82591712	267209666	4.978328	NULL	Piazza San Marco
Dijkstra	20773	267209666	267209702	14.906501	NULL	Via Giorgio La Pira

Enfin, vous pouvez lancer votre première analyse:

la requête est basé sur la clause WHERE NodeFrom = ... AND NodeTo = ...
le chemin le plus court (shortest path) est alors sélectionné.
la première ligne du résultat résume le chemin en entier, et contient la géométrie correspondante.
ales autres lignes représentent chacun des arcs à traverser.

UPDATE tuscany_net SET Algorithm = 'A*';

UPDATE tuscany_net SET Algorithm = 'Dijkstra';

Dans SpatiaLite, les tables VirtualNetwork supportent deux algorithmes alternatifs:

Dijkstra's shortest path est un algorithme classique, disposant d'une base mathématique robuste, et identifiera à coût sûr le chemin le plus court.
A* est un algorithme basé sur des hypothèses heuristiques :
Il est en général plus rapide que Dijkstra, mais est susceptible d'échouer dans certains cas, ou de ne pas retourner le résultat optimal.
Passer de l'un à l'autre se fait relativement facilement.
l'algorithme par défaut est celui de Dijksta.

une table VirtualNetwork représente simplement une photographie instantanée d'un réseau.
Ceci permet d'adopter une représentation binaire très efficace (i.e. calculs plus rapides), mais ne supporte pas les changements dynamiques.

A chaque modification du réseau, la table VirtualNetwork correspondante doit être supprimée (DROP) puis recréée, afin de refléter le nouvel état du réseau.

Dans la plupart des cas ce n'est pas un problème: cependant, dans des scénarios très dynamiques, cela peut être gênant.
Soyez conscient de cette limite.

Table des matières

	Author: Alessandro Furieri a.furieri@lqt.it Traduced from English by RIVIERE Romain
	This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.

	Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.