PgRouting
pgRouting je rozšíření pro PostGIS určené pro síťové analýzy.
- Vyhledání nejkratší cesty
- Problém obchodního cestujícího
- Dojezdová vzdálenost
Vytvoření geodatabáze, nahrání funkcí pgRouting
Informace ohledně vytvoření PostGIS geodatabáze najdete zde.
Příklad nahrání funkcí pgRouting do databáze 'routing'
psql routing -f /usr/share/pgrouting/routing_core.sql psql routing -f /usr/share/pgrouting/routing_core_wrappers.sql psql routing -f /usr/share/pgrouting/routing_topology.sql
Testcase 1
Tento text čerpá z FOSS4G routing with pgRouting tools, OpenStreetMap road data and GeoExt (2010). Příklady jsou upraveny město Praha.
Stažení OSM dat
Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.
Data stáhneme přes API OpenStreetMap
Testcase 2
Tento text čerpá z FOSS4G routing with pgRouting tools and OpenStreetMap road data (2008).
Nahrání testovacích dat
Testovací data jsou dostupná z
svn checkout http://pgrouting.postlbs.org/svn/pgrouting/branches/workshop/FOSS4G2008/ workshop
Nahrajeme testovací data.
cd workshop psql pgis_student -f Data/ways_without_topology.sql
\d ways
Table "public.ways"
Column | Type | Modifiers
----------+------------------+-----------
gid | integer | not null
length | double precision |
name | character(200) |
the_geom | geometry |
Indexes:
"ways_pkey" PRIMARY KEY, btree (gid)
Check constraints:
"enforce_dims_the_geom" CHECK (ndims(the_geom) = 2)
"enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
"enforce_srid_the_geom" CHECK (srid(the_geom) = 4326)
Dále vytvoříme topologii sítě.
ALTER TABLE ways ADD COLUMN source integer;
ALTER TABLE ways ADD COLUMN target integer;
SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');
Funkce assign_vertex_id() vytvoří tabulku s uzly ('vertices_tmp').
\d vertices_tmp
Table "public.vertices_tmp"
Column | Type | Modifiers
----------+----------+-----------------------------------------------------------
id | integer | not null default nextval('vertices_tmp_id_seq'::regclass)
the_geom | geometry |
Indexes:
"vertices_tmp_idx" gist (the_geom)
Check constraints:
"enforce_dims_the_geom" CHECK (st_ndims(the_geom) = 2)
"enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'POINT'::text OR the_geom IS NULL)
"enforce_srid_the_geom" CHECK (st_srid(the_geom) = 4326)
Doplníme indexy.
CREATE INDEX source_idx ON ways(source);
CREATE INDEX target_idx ON ways(target);
CREATE INDEX geom_idx ON ways USING GIST(the_geom GIST_GEOMETRY_OPS);
\d ways
Table "public.ways"
Column | Type | Modifiers
----------+------------------+-----------
gid | integer | not null
length | double precision |
name | character(200) |
the_geom | geometry |
source | integer |
target | integer |
Indexes:
"ways_pkey" PRIMARY KEY, btree (gid)
"geom_idx" gist (the_geom)
"source_idx" btree (source)
"target_idx" btree (target)
Check constraints:
"enforce_dims_the_geom" CHECK (ndims(the_geom) = 2)
"enforce_geotype_the_geom" CHECK (geometrytype(the_geom) = 'MULTILINESTRING'::text OR the_geom IS NULL)
"enforce_srid_the_geom" CHECK (srid(the_geom) = 4326)
Vyhledání nejkratší cesty
Dijkstra
Vyhledání nejkratší cesty na základě Dijkstrova algoritmu. První implementovaný algoritmus pro PgRouting. Lze použít pro orientované či neorientované hrany. Vyžaduje pouze informace o uzlech.
shortest_path(sql text, -- SQL dotaz
source_id integer, -- id počátečního uzlu
target_id integer, -- id koncového uzlu
directed boolean, -- orientovaný/neorientovaný graf
has_reverse_cost boolean -- náklady v opačném směru definovány/nededinovány)
Nalezení nejkratší cesty z bodu '10' do bodu '20' (neorientované hrany, délka hrany).
SELECT * FROM shortest_path(
'SELECT gid as id,source,target,length as cost from ways',
10, 20, false, false);
vertex_id | edge_id | cost
-----------+---------+---------------------
10 | 293 | 0.0059596293824534
9 | 4632 | 0.0846731039249787
4067 | 4633 | 0.0765635090514303
2136 | 4634 | 0.0763951531894937
1936 | 4635 | 0.0750311256021923
1867 | 4636 | 0.0724897276707373
4218 | 4637 | 0.00909269800649229
...
1806 | 762 | 0.0551912469872652
1805 | 761 | 0.0305298478239596
20 | -1 | 0
Funkce dijkstra_sp vrací informaci o geometrii nejkratší cesty.
SELECT gid, ST_AsText(the_geom) AS the_geom FROM dijkstra_sp('ways', 10, 20);
293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) 4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) 4634 | MULTILINESTRING((18.4080293 -33.9429733,18.4083191 -33.9423297)) 4635 | MULTILINESTRING((18.4083191 -33.9423297,18.4085881 -33.9416929)) 4636 | MULTILINESTRING((18.4085881 -33.9416929,18.4088787 -33.9410872)) 4637 | MULTILINESTRING((18.4088787 -33.9410872,18.4089132 -33.9410106)) ... 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))
Nejkratší cestu vytvoříme dotazem.
CREATE TABLE sp10_20 AS SELECT gid, the_geom FROM dijkstra_sp('ways', 10, 20);
SELECT Populate_Geometry_Columns('sp10_20'::regclass);
A-Star
Vyhledání nejkratší cesty na základě A-Star algoritmu.
Tabulka hran musí obsahovat informace o souřadnicích počátečních a koncových uzlů.
ALTER TABLE ways ADD COLUMN x1 double precision;
ALTER TABLE ways ADD COLUMN y1 double precision;
ALTER TABLE ways ADD COLUMN x2 double precision;
ALTER TABLE ways ADD COLUMN y2 double precision;
UPDATE ways SET x1 = x(startpoint(the_geom));
UPDATE ways SET y1 = y(startpoint(the_geom));
UPDATE ways SET x2 = x(endpoint(the_geom));
UPDATE ways SET y2 = y(endpoint(the_geom));
shortest_path_astar(sql text, -- SQL dotaz
source_id integer, -- id počátečního uzlu
target_id integer, -- id koncového uzlu
directed boolean, -- orientovaný/neorientovaný graf
has_reverse_cost boolean -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_astar(
'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2 from ways',
10, 20, false, false);
vertex_id | edge_id | cost
-----------+---------+---------------------
10 | 293 | 0.0059596293824534
9 | 4632 | 0.0846731039249787
4067 | 4633 | 0.0765635090514303
2136 | 4634 | 0.0763951531894937
1936 | 4635 | 0.0750311256021923
1867 | 4636 | 0.0724897276707373
4218 | 4637 | 0.00909269800649229
...
1806 | 762 | 0.0551912469872652
1805 | 761 | 0.0305298478239596
20 | -1 | 0
Shooting-Star
Vyhledání nejkratší cesty na základě Shooting-Star algoritmu. Tento algoritmus na rozdíl od Dijkstrova či A-Star algoritmu vypočítává nejkratší cestu ze spojnice hran nikoliv z uzlů. Tento přístup umožňuje zachytit vztahy mezi hranami, rovnoběžnost hran a pod.
Algoritmus vyžaduje existenci sloupce 'reverse_cost' a 'to_cost'.
ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;
ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;
shortest_path_shooting_star(sql text, -- SQL dotaz
source_id integer, -- id počátečního uzlu
target_id integer, -- id koncového uzlu
directed boolean, -- orientovaný/neorientovaný graf
has_reverse_cost boolean -- náklady v opačném směru definovány/nededinovány)
SELECT * FROM shortest_path_shooting_star(
'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2,rule,to_cost from ways',
293, 761, false, false)
vertex_id | edge_id | cost
-----------+---------+---------------------
5156 | 293 | 0.0059596293824534
5157 | 293 | 0.0059596293824534
5156 | 4632 | 0.0846731039249787
16346 | 4633 | 0.0765635090514303
12324 | 4634 | 0.0763951531894937
11972 | 4635 | 0.0750311256021923
11847 | 4636 | 0.0724897276707373
16692 | 4637 | 0.00909269800649229
...
11746 | 762 | 0.0551912469872652
11744 | 761 | 0.0305298478239596