PgRouting: Porovnání verzí

Z GeoWikiCZ
VizuálníWikitext
mBez shrnutí editace
Řádek 24: Řádek 24:


Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.
Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.
Data stáhneme přes [http://wiki.openstreetmap.org/wiki/Downloading_data#API_map_request API OpenStreetMap]


== Testcase 2 ==
== Testcase 2 ==

Verze z 6. 4. 2011, 16:41

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 '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

Související články

Externí odkazy

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