Distrează-te creând rute - PgRouting
de Cristina Mavriche
1. Ce reprezintă pgRouting?
Dacă vrei sa le arăți prietenilor tăi calea cea mai scurtă de la gară până în complexul studențesc, poți face asta pe propriul calculator :) prin intermediul pgRouting.
PgRouting reprezintă o extensie a PostGIS, fiind un proiect open-source; predecesorul pgRouting – pgDijkstra, scris de către Sylvain Pasche de la Camptocamp (Franța/Suedia) a fost extins de către Orkney (Japonia) și redenumit pgRouting (proiectul PostLBS), momentan fiind menținut de către Georepublic (Germania/Japonia).
Procesarea datelor se poate face prin:
- Shortest Path Dijkstra — rutare cu heuristics
- Shortest Path A* (A-Star) — rutare pentru seturi mari de date (cu heuristics)
- Shortest Path Shooting Star — rutare cu restricții de virare
- Traveling Sales person Problem solver (TSP) — utilizează distanța euclidiană între noduri
- Driving Distance calculation — ține cont de distanța de condus
Acesta pune la dispoziție funcționalități avansate de rutare, ce pot fi extinse și la nivel web, accesarea datelor din PostgreSQL și vizualizarea rezultatelor în QGis sau uDig.
Tutorialul de față ne va ajuta să facem primul pas către pgRouting. Vom încerca să importăm un shapefile de străzi într-o bază de date creată în PostgreSQL /PostGis, să creăm un shortest_path după algoritmul lui Dijkstra, și să simbolizăm rutele interactiv în QGis. Desigur, pentru un rezultat corect vom parcurge câteva etape:
- pregătirea datelor: eliminarea coordonatelor 3D cu ajutorul FwTools , explodarea poliliniilor de stradă la intersecții cu ajutorul funcției Clean din gvSIG
- instalare PostgreSQL și PostGIS
- crearea unei baze de date după template-ul PostGIS, instalare pgRouting și importul datelor
- crearea rutelor cu ajutorul algoritmului Dijkstra
- vizualizarea rutelor în QGIS , prin intermediul Fast SQL Layer
1. Pregătirea datelor
Am downloadat pentru exemplificare un shapefile mai detaliat de străzi (municipiul Câmpulung Moldovenesc) din Seturi de date geospațiale locale de pe geo-spatial.org , precum și layer-ul de puncte de interes .
- Navigăm în fișierul unde se află shapefile-ul de străzi și executăm comanda:
- Deschidem gvSIG, deschidem shapefile-ul strazi_line.shp, apoi de la View -> Geoprocessing Tools -> Topology -> Clean corectăm erorile topologice și segmentăm străzile în locurile unde se intersectează.
Figura 1.
2. Instalare PostgreSQL 8.4 și PostGIS 1.5.3
Pentru instalarea PostgreSQL, PostGis, crearea unei baze de date, importul datelor și accesarea acestora în QGis, se pot consulta următoarele materiale de pe geospatial.org:
- Utilizare PostGIS. Partea I: Instalare PostgreSQL + PostGIS , de Ion Nedelcu.
- Importul unui set de date vectorial din format ESRI Shapefile în PostGIS și vizualizarea/interogarea acestuia folosind QGIS, uDig și GeoServer , de Florin Iosub.
O alternativă, prin intermediul terminalului în Ubuntu 10.10 (Maverick Meerkat), este prezentată in cele ce urmează:
3. Crearea bazei de date, instalarea pgRouting 1.0.3 și importul datelor
Windows:
- PgRouting de downloadează de aici . Din directorul downloadat, fișierele din lib se copiază în directorul lib din PostGIS.
- Se pornește pgAdmin, se creează o nouă bază de date, având ca template baza de date PostGis.
- Se pornește o sesiune nouă Sql și se execută cele trei fișiere .sql din directorul Share/Contrib/
Linux:
Suntem gata să importăm fișierele shapefile in baza de date nou creată. Se poate folosi și ogr2ogr . Trecem calea completă către shapefile sau ne poziționăm în directorul în care se află acestea.
.. vom folosi shp2pgsql prin interfața grafică sau în terminal, și vom importa străzile inițiale(pentru comparație), cele curățate și punctele de interes:
Figura 2.
4. Crearea rutelor cu ajutorul algoritmului Dijkstra
După import, în interfața Sql din pgAdmin putem face câteva interogări să vedem tipurile de geometrie. Coloana de geometrie am lasat-o cu numele default the_geom și este stocată intern de PostGis în formatul binar WKB (Well Known Binary) pentru o performanță mai bună.
Odată ajunși în acest punct, putem sa ne imaginăm că am ajuns la un loc de belvedere și putem lua o pauză, să admirăm liniștiți priveliștea :) și să experimentăm manevrarea geometriilor cu ajutorul nenumăratelor instrumente spațiale din PostGis.
SELECT DISTINCT ST_NDims(the_geom) from strazi_2d; SELECT DISTINCT geometrytype(the_geom) from strazi_2d;
Facem primul pas către funcționalitățile pgRouting. Shortest-path se poate obține în modul cel mai ușor utilizând algoritmul Dijkstra . Pentru aceasta trebuie ca rețeaua de străzi să fie rutabilă:
ALTER TABLE strazi_2d ADD COLUMN source integer;
ALTER TABLE strazi_2d ADD COLUMN target integer;
ALTER TABLE strazi_2d ADD COLUMN length double precision;
UPDATE strazi_2d SET length = length(the_geom);
SELECT assign_vertex_id('strazi_2d', 0.0001, 'the_geom', 'gid');
- Prin funcția assign_vertex_id se vor crea punctele de inceput și sfârșit ale segmentelor de străzi, din care se vor extrage nodurile unice ale rețelei, vertices_tmp, apoi id-urile acestora vor fi trecute în fișierul original strazi_2d în campurile source și _target.
Funcția propriu-zisă ia ca parametri:
shortest_path ( sql text,
source_id integer,
target_id integer,
directed boolean,
has_reverse_cost boolean )
- Source_id și target_id reprezintă id-urile nodurilor de rețea.
Astfel, dacă vrem să aflăm calea cea mai scurtă între nodurile 61 și 750 ale rețelei:
SELECT * FROM shortest_path
('SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM strazi_2d',
61,
750,
false,
false);
Figura 3.
- Parametrii directed și has_reverse_cost se pot folosi dacă vrem să ținem cont de orientare (mărim costul segmentului cu one way astfel încât rutarea să îl evite).
ALTER TABLE strazi_2d ADD COLUMN reverse_cost double precision;
UPDATE strazi_2d SET reverse_cost = length;
UPDATE strazi_2d SET reverse_cost = reverse_cost + 1000000 WHERE one_way = 1;
SELECT gid, one_way, length, reverse_cost, source,target FROM strazi_2d ORDER BY gid;
SELECT * FROM shortest_path
('SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost,
reverse_cost::double precision AS reverse_cost
FROM strazi_2d',
1363,
508,
true,
true);
Figura 4.
- Se poate simplifica prin înlocuirea selecției sql direct cu numele shapefile-ului de străzi(se selectează tot tabelul), iar căutarea poate fi limitată prin folosirea unui bounding-box.
SELECT gid, AsText(the_geom) AS the_geom
FROM dijkstra_sp('strazi_2d', 1363, 508);
SELECT gid, AsText(the_geom) AS the_geom
FROM dijkstra_sp_delta('strazi_2d', 1363, 508, 500);
- Alte exemple de algoritmi pentru shortest_path: A-Star și Shooting-Star .
A-Star adaugă coordonate geografice la start-node si end-node pentru fiecare segment de rețea (nu se folosesc doar nodurile unice de intersecție), astfel este optimizată operația de rutare.
5. Vizualizarea rutelor în QGis prin intermediul Fast SQL Layer
In acest moment putem deja vizualiza rezultatul query-ului nostru în QGis 1.7.0 . Acesta se poate instala astfel:
Mergem la Add PostGis Table -> New ,creăm o nouă conexiune la baza de date din PostGis și deschidem shapefile-ul străzi_2d.
Pentru a face și în cadrul QGis interogarea din pgAdmin prin care sunt selectate rutele, vom folosi plugin-ul Fast SQL Layer .
Figura 5.
Dupa instalare, mergem la Plugins -> Manage Plugins și îl activăm. Acum va apărea o fereastra în care putem scrie query-ul pentru shortest_path, setăm coloanele de id și geometrie (gid, the_geom), dăm Run și un nou layer reprezentând ruta va fi creat. Astfel putem schimba nodurile între care vrem să fie procesată ruta și vedem rezultatul imediat.
SELECT *
FROM strazi_2d
JOIN
(SELECT * FROM shortest_path
('SELECT gid as id,
source::integer,
target::integer,
length::double precision as cost
FROM strazi_2d',
61,
750,
false,
false
)
) AS route
ON strazi_2d.gid = route.edge_id
Figura 6.
Putem să studiem și cazul străzilor cu o singură direcție de parcurgere (cost, respectiv reverse cost):
Figura 7.
Figura 8.
Pentru a ne ajuta la vizualizare, putem face un layer numit repere, prin care profităm de punctele de interes(poi). Selectam cel mai apropiat nod de rețea(vertices_tmp) de fiecare poi, apoi, daca un nod este alocat la mai multe poi-uri, il alegem pe cel care se află la distanța cea mai mică de un poi.
Figura 9.
Deschidem și layer-ul repere în QGis, alegem punctele de interes între care vrem să creăm ruta, scriem id-urile în query-ul din fereastra Fast Sql Layer și rulăm. Pentru automatizarea procesului în mediul web de exemplu, se poate folosi o metodă programatică.
Figura 10.
Figura 11.
Am ales Shortest Path Search pentru a face cunoștință cu pgRouting, puteți încerca funcții mai avansate de rutare experimentând aplicațiile din pgRouting Workshop .
Figura 12.
- Avantaje: se poate experimenta interactiv crearea de rute, și în același timp înțelege mecanismul din background; se poate implementa cu succes într-un mediu web și dispune de resurse care permit analiza avansată a rețelelor (Weighted costs, Restricted access).
- Dezavantaje: shapefile-urile trebuie să fie validate, instalarea pachetelor de programe trebuie făcută cu grijă – se pot ivi probleme dacă lipsesc diverse module/biblioteci.
