|
|
(Není zobrazeno 125 mezilehlých verzí od stejného uživatele.) |
Řádek 1: |
Řádek 1: |
| {{Upravit}} | | {{freegiswiki|PgRouting}} |
| [[Image:pgrouting.png|125px|right]]
| |
| [http://pgrouting.postlbs.org 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 [[PostGIS#Vytvoření databáze|zde]].
| |
| | |
| Příklad nahrání funkcí pgRouting do databáze 'pgis_student'
| |
| | |
| psql pgis_student -f /usr/share/postlbs/routing_core.sql
| |
| psql pgis_student -f /usr/share/postlbs/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
| |
| | |
| <pre>
| |
| \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)
| |
| </pre>
| |
| | |
| Dále vytvoříme topologii sítě.
| |
| | |
| <source lang="sql">
| |
| ALTER TABLE ways ADD COLUMN source integer;
| |
| ALTER TABLE ways ADD COLUMN target integer;
| |
| SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');
| |
| </source>
| |
| | |
| Funkce <code>assign_vertex_id()</code> vytvoří tabulku s uzly ('vertices_tmp').
| |
| | |
| <pre>
| |
| \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)
| |
| </pre>
| |
| | |
| Doplníme indexy.
| |
| | |
| <source lang="sql">
| |
| 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);
| |
| </source>
| |
| | |
| <pre>
| |
| \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)
| |
| </pre>
| |
| | |
| == Vyhledání nejkratší cesty ==
| |
| | |
| === Dijkstra ===
| |
| | |
| Vyhledání nejkratší cesty na základě [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstrova algoritmu]. První implementovaný algoritmus pro PgRouting. Lze použít pro orientované či neorientované hrany. Vyžaduje pouze informace o uzlech.
| |
| | |
| <source lang="sql">
| |
| 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)
| |
| </source>
| |
| | |
| Nalezení nejkratší cesty z bodu '10' do bodu '20' (neorientované hrany, délka hrany).
| |
| | |
| <source lang="sql">
| |
| SELECT * FROM shortest_path(
| |
| 'SELECT gid as id,source,target,length as cost from ways',
| |
| 10, 20, false, false);
| |
| </source>
| |
| | |
| <pre>
| |
| 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
| |
| </pre>
| |
| | |
| Funkce <code>dijkstra_sp</code> vrací informaci o geometrii nejkratší cesty.
| |
| | |
| <source lang="sql">
| |
| SELECT gid, ST_AsText(the_geom) AS the_geom FROM dijkstra_sp('ways', 10, 20);
| |
| </source>
| |
| | |
| <pre>
| |
| 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))
| |
| </pre>
| |
| | |
| Nejkratší cestu vytvoříme dotazem.
| |
| | |
| <source lang="sql">
| |
| CREATE TABLE sp10_20 AS SELECT gid, the_geom FROM dijkstra_sp('ways', 10, 20);
| |
| SELECT Populate_Geometry_Columns('sp10_20'::regclass);
| |
| </source>
| |
| | |
| === A-Star ===
| |
| | |
| Vyhledání nejkratší cesty na základě [http://en.wikipedia.org/wiki/A*_search_algorithm A-Star algoritmu].
| |
| | |
| Tabulka hran musí obsahovat informace o souřadnicích počátečních a koncových uzlů.
| |
| | |
| <source lang="sql">
| |
| 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));
| |
| </source>
| |
| | |
| <source lang="sql">
| |
| 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)
| |
| </source>
| |
| | |
| <source lang="sql">
| |
| SELECT * FROM shortest_path_astar(
| |
| 'SELECT gid as id,source,target,length as cost,x1,y1,x2,y2 from ways',
| |
| 10, 20, false, false);
| |
| </source>
| |
| | |
| <pre>
| |
| 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
| |
| </pre>
| |
| | |
| === 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'.
| |
| | |
| <source lang="sql">
| |
| 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;
| |
| </source>
| |
| | |
| <source lang="sql">
| |
| 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)
| |
| </source>
| |
| | |
| <source lang="sql">
| |
| 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)
| |
| </source>
| |
| | |
| <pre>
| |
| 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
| |
| </pre>
| |
| | |
| == Související články ==
| |
| | |
| * [[SpatiaLite#Síťové analýzy|Síťové analýzy ve SpatiaLite]]
| |
| * [[GRASS GIS - Síťové analýzy]]
| |
| | |
| == Externí odkazy ==
| |
| | |
| * [http://pgrouting.postlbs.org pgRouting]
| |
| | |
| {{Databáze}}
| |
| {{GIS}}
| |
| {{GFOSS}}
| |