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

Poznámky

Nahrání funkcí pgRouting to existující databáze.

psql pgis_student -f /usr/share/postlbs/routing_core.sql
psql pgis_student -f /usr/share/postlbs/routing_core_wrappers.sql
psql pgis_student -f /usr/share/postlbs/routing_topology.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)

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)

Externí odkazy

• pgRouting