PgRouting: Porovnání verzí

Z GeoWikiCZ
VizuálníWikitext
Řádek 11: Řádek 11:
Informace ohledně vytvoření PostGIS geodatabáze najdete [[PostGIS#Vytvoření databáze|zde]].
Informace ohledně vytvoření PostGIS geodatabáze najdete [[PostGIS#Vytvoření databáze|zde]].


Příklad nahrání funkcí pgRouting do databáze 'pgis_student'
Příklad nahrání funkcí pgRouting do databáze 'routing'


  psql pgis_student -f /usr/share/pgrouting/routing_core.sql
  psql routing -f /usr/share/pgrouting/routing_core.sql
  psql pgis_student -f /usr/share/pgrouting/routing_core_wrappers.sql
  psql routing -f /usr/share/pgrouting/routing_core_wrappers.sql


== Nahrání testovacích dat ==
== Nahrání testovacích dat ==

Verze z 6. 4. 2011, 16:03

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

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=20021“