PgRouting: Porovnání verzí
| Řádek 137: | Řádek 137: | ||
name | residential | name | residential | ||
</pre> | </pre> | ||
=== Vytvoření topologie === | === Vytvoření topologie === | ||
Verze z 15. 4. 2012, 15:14
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 'pgis2_routing'
psql pgis_routing -f /usr/share/pgrouting/routing_core.sql psql pgis_routing -f /usr/share/pgrouting/routing_core_wrappers.sql psql pgis_routing -f /usr/share/pgrouting/routing_topology.sql
Testcase 1
Tento text čerpá z FOSS4G routing with pgRouting tools, OpenStreetMap road data and GeoExt (2011). Příklady jsou upraveny město Praha.
Vstupní data
Můžeme stáhnout originální data z workshopu a nebo si připravit vlastní dataset, zde je příklad pro město Praha.
Stažení originálních dat workshopu
git clone https://github.com/pgRouting/workshop.git pgrouting-workshop cd pgrouting-workshop tar xvzf data.tar.gz
Následující příkaz vytvoří databázi 'pgrouting-workshop' jako kopii databáze 'template_routing' a nahraje do této databáze cvičná data.
psql template_routing -f data/sampledata_notopo.sql
psql pgrouting-workshop
SELECT * from geometry_columns;
f_table_catalog | f_table_schema | f_table_name | f_geometry_column | coord_dimension | srid | type --------------------+----------------+--------------+-------------------+-----------------+------+----------------- pgrouting-workshop | public | ways | the_geom | 2 | 4326 | MULTILINESTRING
Stažení OSM dat (Praha)
Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.
psql pgis_student -c"SELECT ST_Extent(ST_Transform(geom, 4326)) FROM gis1.obce WHERE nazev = 'Praha'"
st_extent ------------------------------------------------------------------------- BOX(14.2253523853741 49.9423178052737,14.7065714274832 50.177370950699) (1 row)
Data stáhneme přes API OpenStreetMap
wget --progress=dot:mega -O praha.osm \ http://www.informationfreeway.org/api/0.6/map?bbox=14.2253523853741,49.9423178052737,14.7065714274832,50.177370950699
Alternativně lze data stáhnout ze serveru 'Cloudmade'
wget --progress=dot:mega http://download.cloudmade.com/europe/eastern_europe/czech_republic/prague/prague.osm.bz2
Data naimportujeme do databáze pomocí aplikace osm2pgrouting
bzip2 -d prague.osm.bz2 osm2pgrouting -file prague.osm -conf /usr/share/osm2pgrouting/mapconfig.xml -dbname pgis_routing -clean -user postgis
psql pgis_routing
\d
List of relations
Schema | Name | Type | Owner
--------+-------------------+-------+----------
public | classes | table | postgis
public | geography_columns | view | postgres
public | geometry_columns | view | postgres
public | nodes | table | postgis
public | relation_ways | table | postgis
public | relations | table | postgis
public | spatial_ref_sys | table | postgres
public | types | table | postgis
public | way_tag | table | postgis
(10 rows)
Databáze obsahuje pouze jednu "feature-table"
SELECT f_table_name,type,srid FROM geometry_columns;
f_table_name | type | srid --------------+-----------------+------ ways | MULTILINESTRING | 4326 (1 row)
Náhled na data
SELECT gid,class_id,length,name,x1,y1,x2,y2,reverse_cost,rule,to_cost,osm_id,ST_GeometryType(the_geom),source,target
FROM ways LIMIT 1;
gid | 1 class_id | 110 length | 0.0117292616366281 name | Horáčkova x1 | 14.4363544 y1 | 50.0486718 x2 | 14.4363404 y2 | 50.0485667 reverse_cost | 0.0117292616366281 rule | to_cost | osm_id | 4947 st_geometrytype | ST_MultiLineString source | target |
SELECT * FROM classes WHERE id = 110;
id | 110 type_id | 1 name | residential
Vytvoření topologie
psql pgrouting-workshop
SELECT gid, class_id, length, name, st_geometrytype(the_geom) FROM ways LIMIT 1;
gid | class_id | length | name | st_geometrytype ------+----------+-------------------+------+-------------------- 1172 | 110 | 0.141962653471065 | | ST_MultiLineString
ALTER TABLE ways ADD COLUMN "source" integer;
ALTER TABLE ways ADD COLUMN "target" integer;
SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');
SELECT gid, class_id, length, name, st_geometrytype(the_geom),source,target from ways limit 1;
gid | class_id | length | name | st_geometrytype | source | target ------+----------+--------------------+------+--------------------+--------+-------- 1971 | 401 | 0.0284840167603594 | | ST_MultiLineString | 390 | 391
CREATE INDEX source_idx ON ways("source");
CREATE INDEX target_idx ON ways("target");
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
git clone https://github.com/pgRouting/workshop-2008.git workshop-2008
Nahrajeme testovací data.
cd workshop-2008 psql pgis2_routing -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
SELECT gid, AsText(the_geom) AS the_geom
FROM astar_sp_delta('ways', 10, 20, 0.1);
gid | the_geom ------+------------------------------------------------------------------ 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)) ... 6618 | MULTILINESTRING((18.4236514 -33.9182429,18.4237423 -33.9182966)) 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) (62 rows)
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
SELECT gid, AsText(the_geom) AS the_geom
FROM shootingstar_sp('ways', 10, 20, 0.1, 'length', true, true);