pgrouting | calcolo percorso minimo tra due punti

Prima di tutto e’ necessario creare un database Postgresql ed aggiungerci l’estensione spaziale Postgis.

come utente postgres si entra in un database esistente o in un template:

# psql template1;

– Creiamo il database e impostiamo la proprietà all’utente (nel nostro caso “sit”):

template1=# CREATE DATABASE routing OWNER sit template template_gis;

il template_gis e’ stato creato a priori (database con estensioni spaziali postgis incorporate; questo per evitare ogni volta di dover aggiungere le tabelle “geometry_column” e “spatial_ref_sys”);

– Ci colleghiamo al database appena creato:

template1=# /connect routing;

e diamo i permessi necessari all’utente “sit” sulla tabella spaziali:

routing=# GRANT ALL ON geometry_columns to sit;
routing=# GRANT SELECT ON spatial_ref_sys to sit;

– Aggiungiamo le funzioni di routing (dopo essere usciti dal database ed esserci autenticati come utente “postgres”):

# psql -d routing -f /usr/share/postlbs/routing_core.sql

# psql -d routing -f /usr/share/postlbs/routing_wrappers.sql

# psql -d routing -f /usr/share/postlbs/routing_topology.sql

– Reperiamo i dati: nel mio caso ho reperito il planet italiano dal sito http://download.geofabrik.de/osm/europe/. Ho scaricato gli SHP. Dopo aver fatto un clip dei dati sul confine regionale di interesse (Veneto) medianti i preziosissimi ftools di qgis ho ottenuto il grafo stradale del territorio veneto.

– Importiamo i dati del database mediante il modulo shp2pgsql. Ecco la sintassi del comando (con SRID settato a 4326, i dati sono in lat-long WGS84).

$ shp2pgsql -S -s 4326 /home/sit/geodatabase/shp/stradario_regione/stradario_regione_seg.shp stradario_regione routing > /home/sit/sql/stradario_regione.sql

$ psql -h localhost -U postgres -d routing -f /home/sit/sql/stradario_regione.sql

Per i passi successivi ho seguito questo ottimo tutorial ):

– Aggiungiamo 3 colonne alla tabella: una per memorizzare gli ID dei nodi iniziali, una per gli ID dei nodi finali e la’ltra per la lunghezza:

routing=> ALTER TABLE stradario_regione ADD COLUMN source integer;

routing=> ALTER TABLE stradario_regione ADD COLUMN target integer;

routing=> ALTER TABLE stradario_regione ADD COLUMN length double precision;

– Creiamo la topologia e aggiungiamo il valore della lunghezza al campo appena creato:

routing=> SELECT assign_vertex_id(‘stradario_regione’, 0.0001, ‘the_geom’, ‘gid’);

routing=> UPDATE stradario_regione SET length = length(the_geom);

– Creiamo gli indici per le colonne “source”, “target” e “the_geom”;

routing=> CREATE INDEX source_idx ON stradario_regione(source);

routing=> CREATE INDEX target_idx ON stradario_regione(target);

routing=> CREATE INDEX geom_idx ON stradario_regione USING GIST(the_geom GIST_GEOMETRY_OPS);

– Impostiamo la query di routing e salviamo il tutto in una nuova tabella chiamata “dijkstra_resust” (prima di tutto cancelliamo una eventuale tabella omonima precedentemente creata):

routing=> DROP TABLE IF EXISTS dijsktra_result;

routing=> CREATE TABLE dijsktra_result(gid int4) with oids;

routing=> SELECT AddGeometryColumn(‘dijsktra_result’, ‘the_geom’, ‘4326’, ‘MULTILINESTRING’, 2);

routing=> INSERT INTO dijsktra_result(the_geom) SELECT the_geom FROM dijkstra_sp(‘stradario_regione’, 73441, 13547);

Questa query trova il percorso minimo tra due vertici (con ID pari a 73441 e 133547).

In prima battuta, nel mio caso, ho ottenuto un messaggio d’errore per violazione di un CONSTRAINT:

ERROR: new row for relation “dijkstra_result” violates check constraint “enforce_geotype_the_geom”

Ho cancellato questo constraint (via pgadmin3) e re-impartito la query ottenendo la nuova tabella dijkstra popolata. Il risultato si può visualzzare in qgis.

Annunci

pgrouting | compilazione in debian Lenny

Ho provato ad installare l’estensione di postgresql-postgis per il routing chiamata pgRouting. Si tratta di una estensione che consente di effettuare analisi di reti.

Ho tentato la compilazione (in Debian Lenny)  in quanto non esiste come pacchetto precompilato per debian. Questo perche’ la compilazione “canonica” dei sorgenti mi ritornava un errore in sede di “make”. Ho notato (alla fine di tutta la storia) che la creazione dei .deb e la loro installazione può risultare propedeutica alla compilazione canonica (se il lettore ha notizie certe che possono confermare o demolire questa ipotesi posti un commento al post; sarei molto felice di approfondire la questione). La creazione dei .deb che vediamo tra poco consente di installare solo la parte “core” delle librerie. Questo a causa della della mancanza delle librerie GAUL nei repos ufficiali (necessarie per il problema del TSP – Travel Sale Person) e delle CGAL (necessarie per le driving distance) rilasciate sotto licenza QPL, quindi non libere.

Per avere TSP e driving distance e’ pertanto necessario installare dai sorgenti, la cui compilazione va a buon fine (o almeno per me e’ stato cosi’) solo dopo l’installazione del “core” pacchettizzato debian.

Creazione dei pacchetti .deb delle core library (senza funzioni TSP e DD)

Prima di tutto ho scaricato i sorgenti da qui.

Seguendo le istruzioni riportati nel sito ho seguito i seguenti passi:

– diamo un controllo ai requirements: cmake ed i compilatori C e C++ li dovremmo trovare già installati nella nostra distro; mancano invece le librerie Boost Graph Library (BGL), le Genetic Algorithm Utility Library (GAUL, per il problema del “commesso viaggiatore”), e le librerie computazionali Geometry Algorithms Library (CGAL, per il driving);

– per installare le BGL ho usato apt-get (sono già nei repo di Lenny): # apt-get install libboost-graph-dev

– anche le CGAL si trovano: installate via synaptic;

– le GAUL invece le ho scaricate dal sito: una volta fatto, scompattare il sorgente e impartire i comandi riportati nella pagina di istruzioni indicata sopra. I comandi sono:

$ ./configure –disable-slang

$ make

# make install

Seguendo le istruzioni riportate su questa pagina (nascosta, in quanto non c’e’ link del sito che la punti) ho compilato le librerie a partire dall’SVN:

– creare una directory in cui scaricare i sorgenti (nel mio caso $ mkdir compila_pgrouting);

– spostarsi nella directory appena creata e lanciare: $ svn checkout http://pgrouting.postlbs.org/svn/pgrouting/trunk pgrouting

– spostarsi nella directory pgrouting: $ cd pgrouting e diventare root

– creare i paccheti con: # dpkg-buildpackage -b -rfakeroot -uc -us

– risalire di una posizione : # cd ..

– installare i pacchetti con: # dpkg -i *.deb

A questo punto bisogna aggiungere le funzioni di routing al database (che deve essere gia’ un database spaziale). NB: il database ci chiama routing nel nostro caso.

psql -d routing -f /usr/share/postlbs/routing_core.sql
psql -d routing -f /usr/share/postlbs/routing_core_wrappers.sql

L’installazione copia due file con le istruzioni SQL. (routing_core.sql e routing_core_wrappers.sql). Seguendo i tutorial si notera’ che ad un certo punto, dopo avere importato i dati del database, e’ necessario creare la topologia dei dati. Per fare questo viene indicata una funzione “add_vertex_id” secondo questa sintassi:

nome_db=> SELECT assign_vertex_id(‘stradario_regione’, 0.0001, ‘the_geom’, ‘gid’)

dove:

– stradario_regione= nome tabella che contiene i dati;

– 0.0001= tolleranza di snap per la ricerca di nodi non collegati agli archi (espressa in unita’ di misua dei dati; nel mio caso avendo EPSG=4326 sono decimillesimi di grado);

– the_geom=colonna geometrica della tabella interessata;

– gid= colonna con gli id degli oggetti (solitamente la colonna “gid”).

In prima battuta, lanciando la query ho ottenuto questo messaggio:

ERROR:  function assign_vertex_id(unknown, numeric, unknown, unknown) does not exist

Infatti, navigando all’interno del database, nella sezione “Function” dello schema “public” non si trova una funzione chaimata “add_vertex_id”. Scrivendo il lista pgrouting mi e’ stato indicato da Anton Patrushev (che ringrazio infinitamente) che le regole per la pulizia topologica sono state spostate in un file di struzioni SQL chiamato “routing_topology.sql”. Ma purtroppo questo file non viene copiato in “usr/share/postlibs/” come gli altri due files indicati sopra (forse un bug?). Tuttavia questo file si trova nei sorgenti scaricati da SVN. Quindi ho copiato il file in “/usr”share/postlibs/” e lanciato l’istruzione (come utente postgres):

psql -d routing -f /usr/share/postlbs/routing_topology.sql

e magicamente la funzione “add_vertex_id” si trova tra le “Function” del database.

A questo punto ho re-impartito la query (dopo essere entrato nel db come utente “sit”) per la creazione della topologia:

SELECT assign_vertex_id(‘stradario_regione’,0.0001, ‘the_geom’, ‘gid’);

e questo e’ l’output del comando:

NOTICE:  CREATE TABLE will create implicit sequence “vertices_tmp_id_seq” for serial column “vertices_tmp.id”
CONTEXT:  SQL statement “CREATE TABLE vertices_tmp (id serial)”
PL/pgSQL function “assign_vertex_id” line 14 at EXECUTE statement
assign_vertex_id
——————
OK

(1 row)

Aprendo i dati in qgis e interrogando un qualsiasi arco del grafo si nota che i campi “sorce” e “target” sono popolati con gli ID dei nodi iniziale e finale dell’arco stesso.

Compilazione integrale dei sorgenti

La compilazione integrale dei sorgenti (per avere le funzioni di TSP e driving distance) avviene come da manuale: ho seguito anche questa ottima guida.

– spostarsi nella directory ottenuta dalla scompattazione dei sorgenti di pgrouting, quindi:

– $ cmake -DWITH_TSP=ON -DWITH_DD=ON .

– $ make

– # make install

[ 16%] Built target routing_tsp
[ 50%] Built target routing_dd
[100%] Built target routing
Install the project…
— Install configuration: “”
— Installing: /usr/lib/postgresql/8.3/lib/librouting.so
— Installing: /usr/share/postlbs/routing_core.sql
— Installing: /usr/share/postlbs/routing_core_wrappers.sql
— Installing: /usr/share/postlbs/routing_topology.sql
— Installing: /usr/lib/postgresql/8.3/lib/librouting_tsp.so
— Installing: /usr/share/postlbs/routing_tsp.sql
— Installing: /usr/share/postlbs/routing_tsp_wrappers.sql
— Installing: /usr/lib/postgresql/8.3/lib/librouting_dd.so
— Installing: /usr/share/postlbs/routing_dd.sql
— Installing: /usr/share/postlbs/routing_dd_wrappers.sql

– Quindi ho aggiunto le funzioni TSP e DD al database “routing” creato in precedenza:

– (come utente postgres):

# psql -d routing -f /usr/share/postlbs/routing_tsp.sql (crea 1 funzione)

# psql -d routing -f /usr/share/postlbs/routing_tsp_wrappers.sql (crea 5 funzioni)

# psql -d routing -f /usr/share/postlbs/routing_dd.sql (crea 2 funzioni)

# psql -d routing -f /usr/share/postlbs/routing_dd_wrappers.sql (crea 1 funzione)

# ./configure --disable-slang