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.

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

Postgis | calcolare la lunghezza totale di uno strato lineare

Postgis offre 1000 strumenti per l’analisi spaziale. Una di queste, semplice quanto efficace, e’ la possibilita’ di calcolare la lunghezza totale degli oggetti memorizzati in una tabella di tipo LINESTRING.

Per esempio possiamo porci questa domanda : qual e’ la lunghezza totale delle strade, espressa in Km?
Procediamo:

– connettersi al database con psql:

$ psql -h nome_host -U nome_utente nome_database;

– una volta entrati (dopo aver digitato la password) impartire la seguente istruzione SQL:

nome_database=> SELECT sum(length(the_geom))/1000 AS km_roads FROM nome_tabella;

Nel mio caso ho ottenuto:

km_roads
——————
187.869370073215

che rappresenta la lunghezza totale espressa in Km.

Nel caso si volesse recuperare la lunghezza delle strade distinte per categoria (o meglio “classificazione”):

nome_database=> SELECT classifica,sum(length(the_geom))/1000 AS km_roads FROM grafo_new GROUP BY classifica;

classifica  |     km_roads
————-+——————-
| 0.278103249728031
provinciale |  7.57308599148574
statale     |  12.8419180713568
comunale    |   155.13306294845
autostrada  |  1.00396374819259
vicinale    |  11.0392360640017
(6 rows)

In questo modo si ottiene la lunghezza distinta per classificazione di strade

Mapnik | un tiles cacher di dati OSM

Creare delle tiles a partire dal db OSM? Si può fare in locale. Come? Basta installare Mapnik, Postgresql con estensione spaziale postgis e scaricare un planet di OSM.

Ecco come ho fatto i miei test. Molto probabilmente non è la strada più diretta e corretta, ma a volte “smazzarsi” un po’ di codice e un po’ di errori aiuta a comprendere un po’ di più le cose. In questo/i post faccio riferimento a operazioni svolte con Debian (Lenny).

Partiamo dall’inizio:-

– installare Postgresql con estensione spaziale postgis (per questo rimando alle pagine relative);

– installare mapnik con

# apt-get install mapnik (oppure tramite “synaptic”);

– reperiamo i dati del planet che ci interessa: io ho scaricato il planet italiano da qui. Si ottine il file italy.osm.bz2.

– creare il database che riceverà i dati. Diventare utente postgres e creare il db con:

# createdb -E UTF8 -O sit osm

dove “osm” è il nome del db e “sit” è il nome dell’utente

– creare il linguaggio per il db:

# createlang plpgsql osm

– aggiungere le tabelle per fare in modo che sia un geodb:

# psql -d osm -f /usr/share/postgresql-8.3-postgis/lwpostgis.sql

– Fare in modo che le tabelle spaziali siano di proprietà dell’utente sit:

# echo “ALTER TABLE geometry_columns OWNER TO sit; ALTER TABLE spatial_ref_sys OWNER TO sit;” | psql -d osm

– popliamo il db creato tramite “osm2pgsql”

# osm2pgsql -m -d osm /home/sit/osm/data/italy.osm.bz2

– posizionarsi nella home directory e lanciare il comando:

$ svn checkout http://svn.openstreetmap.org/applications/rendering/mapnik

In questo modo reperiamo una serie di file e directory già strutturate per effettuare le operazioni di rendering. Viene creata una directory “mapnik”.

– Posizionarsi in “mapnik”

$ cd mapnik

– scaricare gli SHP di linee di costa e boundary:

$ wget http://tile.openstreetmap.org/world_boundaries-spherical.tgz

$ tar zxvf world_boundaries-spherical.tgz

$ wget http://hypercube.telascience.org/~kleptog/processed_p.zip

$ unzip processed_p.zip

$ mv coastlines/* world_boundaries/

$ rmdir coastlines

– spostarsi nella directory world_boundaries:

$ cd world_boundaries

$ wget http://tile.openstreetmap.org/shoreline_300.tar.bz2

$ tar xvjf shoreline_300.tar.bz2

– fare una copia del file set-mapnik-env e chiamarla, per esempio, z0-set-mapnik-env.

$ cp set-mapnik-env z0-set-mapnik-env

– editare questo file indicando il nome corretto del database postgresql da usare ed il nome corretto dell’utente che ha accesso al db stesso. Nell’header del file c’è una chiara e semplice spiegazione dei settaggi.

– lanciare il comando:

$ source ./z0-set-mapnik-env

– poi:

$ ./customize-mapnik-map >$MAPNIK_MAP_FILE

– creare una copia del file generate_tiles.py (chiamarla i.e. “z0_generate_tiles.py”) e modificarla adattando la bbox alla zona di interesse. Nel mio caso, dovendo operare in un’area ristretta della Provinica di Vicenza ho editato nel modo seguente (riporto un estratto della parte finale del file, l’unica modificata). Basta commentare le parti da omettere con un “#” seguito da uno spazio ” “.

—————————————————————————————————

# Change the following for different bounding boxes and zoom levels

#

# Start with an overview

# World

# bbox = (-180.0,-90.0, 180.0,90.0)

# bbox = (11.0,45.0, 12.0,46.0)

# render_tiles(bbox, mapfile, tile_dir, 0, 0, “World”)

# minZoom = 10

# maxZoom = 16

# bbox = (-2, 50.0,1.0,52.0)

# render_tiles(bbox, mapfile, tile_dir, minZoom, maxZoom)

# Montecchio Maggiore

bbox = (11.37,45.47, 11.45,45.56)

render_tiles(bbox, mapfile, tile_dir, 1, 12 , “Montecchio”)

# Muenchen

# bbox = (11.4,48.07, 11.7,48.22)

# render_tiles(bbox, mapfile, tile_dir, 1, 12 , “Muenchen”)

—————————————————————————————

– infine lanciare il comando che genera la tiles

$ ./z0_generate_tiles.py

Nella directory “tiles” vengono generate le tiles (appunto :-)).

Le immagini così generate (PNG) possono essere usate in locale in caso di mancanza di connessione alla rete o solo per caricare dati locali invece di doverli scaricare dai server OSM. A titolo di esempio riportiamo il caso di un applicativo basato su Openlayers. In questo caso basta indicare un nuovo layer (nella pagina HTML che visualizzerò i dati) con la seguente sintassi:

———————————————————————————————————————————————————————

var newLayer = new OpenLayers.Layer.OSM(“Mapnik@home”, “http://localhost/openlayer/tiles/”, {numZoomLevels: 19});

map.addLayer(newLayer);

———————————————————————————————————————————————————————

dove http://localhost/openlayer/tiles/” è il percorso locale per raggiungere le immagini PNG (questa direcotry deve essere accessibile all’utente www-data).

Sotto è riportato un esempio di render di dati OSM realizzato con mapnik; il tutto visualizzato con tramite Openlayers.

Esempio di render effettuato con Mapnik e visualizzato mediante Openlayers

Esempio di render effettuato con Mapnik e visualizzato mediante Openlayers

postgis | conteggio punti ricadenti all’interno di poligoni

Questo metodo consente di contare il numero di punti ricadenti all’interno di poligoni mediante instruzione SQL in postGIS.

Partiamo da un esempio: siamo in possesso di uno strato poligonale (i.e. una griglia a maglia quadrata di lato 100m) e di uno strato puntuale (i.e. i punti che individuano antenne dislocate sul territorio). Lo scopo è quello di contare quante antenne ricadono all’interno di ogni quadrato di 100m.

La procedura illustrata crea una nuova tabella con il conteggio dei punti cercati.

nome_datbase=# CREATE TABLE nome_tabella AS SELECT tabella_polygon.cat, COUNT(id) AS count FROM tabella_point,tabella_polygon WHERE tabella_point.the_geom && tabella_polygon.the_geom AND CONTAINS (tabella_polygon.the_geom, tabella_point.the_geom) GROUP BY tabella_polygon.cat;

dove:

tabella_polygon è la tabella che contiene le griglie;

tabella_point è la tabella che contiene le antenne;

tabella_polygon.cat rappresenta un campo id univoco (il cat proviene da una esportazione di dati da GRASS);

join tra layer postGIS (tabella geometrica) e tabella postgreSQL

Dato un layer postGIS con campo chiave “id” ed una tabella postgreSQL che contiene lo stesso campo chiave si può creare una VIEW (vista) tramite JOIN sul campo comune. In questo modo le informazioni geometriche degli oggetti vengono salvate su una tabella “leggera” mentre le informazioni alfanumeriche (attributi) vengono salvate su un’altra tabella. Es:

nome_database=# SELECT tabella_dati.campo1, tabella_dati.campo2, tabella_dati.campo3,…..,tabella_dati.campon, tabella_geom.id, tabella_geom.gid, tabella_geom.the_geom FROM tabella_geom JOIN tabella_dati ON tabella_geom.id=tabella_dati.id

postgresql | elencare tutti i valori (non ripetuti) di un campo

La parola chiave DISTINCT esclude dai risultati le righe duplicate.

Es: vogliamo elencare tutti i valori che sono contenuti nel campo “nome_via” di una tabella contenente i nomi di tutte le strade. Può succedere che esistano strade “spezzate” in più tratti ed in un database geometrico (PostGIS) siano memorizzati più archi di strada con lo stesso nome. DISTINCT consente di elencare i valori non ripetuti:

nome_database=# SELECT DISTINCT nome_via FROM nome_tabella_strade;

Nel caso volessimo elencare i nomi delle strade così distinte indicando anche la lunghezza totale dei tratti che hanno lo stesso nome:

nome_database=#SELECT DISTINCT ON (nome) nome,sum(lunghezza) FROM nome_tabella_strade GROUP BY nome;

e se volessimo esportare l’output della query in un file CSV:

– nel prompt di psql indicare:

nome_database=# \o /percorso/alt/file/nome_file_output.csv

– poi lanciare la query:

nome_database=#SELECT DISTINCT ON (nome) nome,sum(lunghezza) FROM nome_tabella_strade GROUP BY nome;

– In questo modo otteniamo un file CSV con il risultato.

PostGIS | creare una colonna che contenga i centroidi del poligoni (di un layer poligonale)

Per prima cosa creare la colonna geometrica che conterrà le coordinate dei centroidi:

nome_database=# SELECT ADDGEOMETRYCOLUMN (‘public’,’nome_tabella’, ‘centroid’, ‘3003’, ‘POINT’,2);

dove:
public indica lo schema da usare nel database;
centroid è il nome del campo da creare;
3003 è il codice EPSG del sistema di reiferimento da usare;
2 indica le dimensioni spaziali.

Poi calcolare i centroidi e popolare il nuovo campo (colonna) creato:

nome_database=# UPDATE nome_tabella SET centroid=centroid(the_geom);

Per creare una VIEW con i centroidi:

nome_database=# CREATE VIEW centroidi AS SELECT nome_campo1.tabella_poligoni, nome_campo2.tabella_poligoni,nome_campo_i.tabella_poligoni, centroid(the_geom) FROM tabella_poligoni;

unione di più geometrie con PostGIS

Metodo utilizzato nel caso si vogliano unire più oggetti di uno stesso strato PostGIS (stessa tabella PotgreSQL) che hanno valori uguali di un certo campo. Es. unire tutte le aste fluviali denominate “Adige”.

Ho seguito questo splendido post di Paolo Corti per completare la procedura.

La tabella unione deve essere create a priori inserendo, in seconda battuta, anche una colonna per memorizzare le informazioni geometriche (the_geom). Nel nostro caso:

SELECT AddGeometryColumn(”,’nome_tabella_unione’,’the_geom’,’-1′,’MULTILINESTRING’,2);

E’ importante impostare lo SRID a “-1” altrimenti viene riportato un errore di constraints (enforce_srid); inoltre lo strato viene caricato in Qgis ma non viene visualizzato.

Infine popoliamo la nuova tabella unione con i dati:

INSERT INTO nome_tabella_unione (the_geom,nome_campo1) SELECT astext(multi(ST_Union(the_geom))) AS the_geom,nome_campo1 FROM nome_tabella_originale  GROUP BY nome_campo1;