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