PgRouting

Z GeoWikiCZ

Tento článek není dokončen nebo potřebuje upravit


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 pgis2_routing -f /usr/share/pgrouting/routing_core.sql
psql pgis2_routing -f /usr/share/pgrouting/routing_core_wrappers.sql
psql pgis2_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í originálních dat workshopu

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.2263458866547 49.9430072212568,14.7076337904321 50.1780875601954)
(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.2263458866547,49.9430072212568,14.7076337904321,50.1780875601954

Poznámka: Stažení dat přes API OSM je poměrně časově náročné, snapshot dat z 6.6.2011 můžete stáhnout zde.

A naimportujeme do databáze pomocí aplikace osm2routing 

osm2pgrouting -file praha.osm -conf mapconfig.xml -dbname routing -clean -user <me> -passwd <mypassword>

psql routing

\d

              List of relations
 Schema |       Name        | Type  | Owner  
--------+-------------------+-------+--------
 public | classes           | table | martin
 public | geography_columns | view  | martin
 public | geometry_columns  | table | martin
 public | nodes             | table | martin
 public | relation_ways     | table | martin
 public | relations         | table | martin
 public | spatial_ref_sys   | table | martin
 public | types             | table | martin
 public | way_tag           | table | martin
 public | ways              | table | martin
(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             | 109866
class_id        | 119
length          | 0.0663025843260471
name            |                                                                                                                                                                                                         
x1              | 14.3788716
y1              | 50.0331236
x2              | 14.379455
y2              | 50.0335874
reverse_cost    | 0.0663025843260471
rule            | 
to_cost         | 
osm_id          | 60592717
st_geometrytype | ST_MultiLineString
source          | 
target          | 

SELECT * FROM classes WHERE id = 119;

id      | 119
type_id | 1
name    | footway

SELECT assign_vertex_id('ways', 0.0000001, 'the_geom', 'gid');

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

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

Související články

Externí odkazy

Citováno z „https://geo.fsv.cvut.cz/index.php?title=PgRouting&oldid=20071“