|
|
| (Není zobrazeno 19 mezilehlých verzí od stejného uživatele.) |
| Řádek 1: |
Řádek 1: |
| − | [[Image:pgrouting.png|175px|right]]
| + | {{freegiswiki|PgRouting}} |
| − | [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 'template_routing'
| |
| − | | |
| − | psql template_routing -f /usr/share/pgrouting/routing_core.sql
| |
| − | psql template_routing -f /usr/share/pgrouting/routing_core_wrappers.sql
| |
| − | psql template_routing -f /usr/share/pgrouting/routing_topology.sql
| |
| − | | |
| − | == Testcase 1 ==
| |
| − | | |
| − | Tento text čerpá z [http://workshop.pgrouting.org/ FOSS4G routing with pgRouting tools, OpenStreetMap road data and GeoExt] (2011). Příklady jsou upraveny město Praha.
| |
| − | | |
| − | === Vstupní data ===
| |
| − | | |
| − | Můžeme stáhnout originální data z workshopu a nebo si připravit vlastní dataset, zde je příklad pro město Praha.
| |
| − | | |
| − | ==== Stažení originálních dat workshopu ====
| |
| − | | |
| − | git clone https://github.com/pgRouting/workshop.git pgrouting-workshop
| |
| − | cd pgrouting-workshop
| |
| − | tar xvzf data.tar.gz
| |
| − | | |
| − | Následující příkaz vytvoří databázi 'pgrouting-workshop' jako kopii databáze 'template_routing' a nahraje do této databáze cvičná data.
| |
| − | | |
| − | psql template_routing -f data/sampledata_notopo.sql
| |
| − | | |
| − | psql pgrouting-workshop
| |
| − | <source lang=sql>
| |
| − | SELECT * from geometry_columns;
| |
| − | </source>
| |
| − | <pre>
| |
| − | f_table_catalog | f_table_schema | f_table_name | f_geometry_column | coord_dimension | srid | type
| |
| − | --------------------+----------------+--------------+-------------------+-----------------+------+-----------------
| |
| − | pgrouting-workshop | public | ways | the_geom | 2 | 4326 | MULTILINESTRING
| |
| − | </pre>
| |
| − | | |
| − | ==== Stažení OSM dat (Praha) ====
| |
| − | | |
| − | Nejprve zjistíme minimální ohraničující obdélník (bbox) Prahy.
| |
| − | | |
| − | psql pgis_student -c"SELECT ST_Extent(ST_Transform(geom, 4326)) FROM gis1.obce WHERE nazev = 'Praha'"
| |
| − | | |
| − | <pre>
| |
| − | st_extent
| |
| − | -------------------------------------------------------------------------
| |
| − | BOX(14.2253523853741 49.9423178052737,14.7065714274832 50.177370950699)
| |
| − | (1 row)
| |
| − | </pre>
| |
| − | | |
| − | Data stáhneme přes [http://wiki.openstreetmap.org/wiki/Downloading_data#API_map_request API OpenStreetMap]
| |
| − | | |
| − | wget --progress=dot:mega -O praha.osm \
| |
| − | http://www.informationfreeway.org/api/0.6/map?bbox=14.2253523853741,49.9423178052737,14.7065714274832,50.177370950699
| |
| − | | |
| − | Alternativně lze data stáhnout ze serveru 'Cloudmade'
| |
| − | | |
| − | wget --progress=dot:mega http://download.cloudmade.com/europe/eastern_europe/czech_republic/prague/prague.osm.bz2
| |
| − | | |
| − | Data naimportujeme do databáze pomocí aplikace [http://www.pgrouting.org/docs/tools/osm2pgrouting.html osm2pgrouting]
| |
| − | | |
| − | bzip2 -d prague.osm.bz2
| |
| − | osm2pgrouting -file prague.osm -conf /usr/share/osm2pgrouting/mapconfig.xml -dbname pgis_routing -clean -user postgis
| |
| − | | |
| − | === Přístup k datům ===
| |
| − | | |
| − | Cvičná data jsou také součástí [[Cvičná databáze PostGIS|cvičné databáze PostGIS]] <tt>pgis_student</tt>, schéma 'routing'.
| |
| − | | |
| − | <source lang=sql>
| |
| − | SET search_path TO routing,public;
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | \dt routing.
| |
| − | List of relations
| |
| − | Schema | Name | Type | Owner
| |
| − | ---------+---------+-------+-------
| |
| − | routing | classes | table | landa
| |
| − | routing | types | table | landa
| |
| − | routing | ways | table | landa
| |
| − | (3 rows)
| |
| − | </pre>
| |
| − | | |
| − | Databáze obsahuje pouze jednu "feature-table"
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT f_table_name,type,srid FROM geometry_columns WHERE f_table_schema = 'routing';
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | f_table_name | type | srid
| |
| − | --------------+-----------------+------
| |
| − | ways | MULTILINESTRING | 4326
| |
| − | (1 row)
| |
| − | </pre>
| |
| − | | |
| − | Náhled na data
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid,class_id,length,name,st_geometrytype(the_geom) FROM ways LIMIT 1;
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | gid | class_id | length | name | st_geometrytype
| |
| − | -----+----------+--------------------+------+--------------------
| |
| − | 302 | 102 | 0.0714603355500818 | | ST_MultiLineString
| |
| − | </pre>
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT * FROM classes WHERE id = 102;
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | id | 102
| |
| − | type_id | 1
| |
| − | name | motorway_link
| |
| − | cost |
| |
| − | </pre>
| |
| − | | |
| − | === Vytvoření topologie sítě ===
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, class_id, length, name, st_geometrytype(the_geom) AS type from ways limit 1;
| |
| − | </source>
| |
| − | <pre>
| |
| − | gid | 302
| |
| − | class_id | 102
| |
| − | length | 0.0714603355500818
| |
| − | name |
| |
| − | type | ST_MultiLineString
| |
| − | </pre>
| |
| − | | |
| − | <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');
| |
| − | CREATE INDEX source_idx ON ways("source");
| |
| − | CREATE INDEX target_idx ON ways("target");
| |
| − | </source>
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, class_id, length, name, st_geometrytype(the_geom) AS type,source,target,x1,y1,x2,y2,to_cost,rule from ways LIMIT 1;
| |
| − | </source>
| |
| − | <pre>
| |
| − | gid | 302
| |
| − | class_id | 102
| |
| − | length | 0.0714603355500818
| |
| − | name |
| |
| − | type | ST_MultiLineString
| |
| − | source | 212
| |
| − | target | 213
| |
| − | x1 | -104.9792332
| |
| − | y1 | 39.7786848
| |
| − | x2 | -104.9786416
| |
| − | y2 | 39.779139
| |
| − | to_cost |
| |
| − | rule |
| |
| − | </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 | 14701 | 0.133961657579708
| |
| − | 1034 | 974 | 0.0433580404548831
| |
| − | ...
| |
| − | 6749 | 8014 | 0.0518861583127315
| |
| − | 6750 | 8015 | 0.0518860343451018
| |
| − | 20 | -1 | 0
| |
| − | (50 rows)
| |
| − | </pre>
| |
| − | | |
| − | Alternativně lze použít funkci <code>dijkstra_sp</code> (wrapper pro <tt>shortest_path</tt>).
| |
| − | | |
| − | <source lang="sql">
| |
| − | SELECT gid, ST_AsText(the_geom) AS geom FROM dijkstra_sp('ways', 10, 20);
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | 974 | MULTILINESTRING((-104.9740756 39.7255831,-104.9740817 39.7251932))
| |
| − | 973 | MULTILINESTRING((-104.9740814 39.7272791,-104.9740756 39.7255831))
| |
| − | 11107 | MULTILINESTRING((-104.9781265 39.7520022,-104.9781346 39.7526951))
| |
| − | 11108 | MULTILINESTRING((-104.9781346 39.7526951,-104.9781265 39.7531137))
| |
| − | 8012 | MULTILINESTRING((-104.981101 39.7571413,-104.981529 39.7574721))
| |
| − | (49 rows)
| |
| − | </pre>
| |
| − | | |
| − | Nejkratší cestu vytvoříme dotazem.
| |
| − | | |
| − | <source lang="sql">
| |
| − | CREATE TABLE sp10_20 AS SELECT gid, the_geom FROM dijkstra_sp('ways', 10, 20);
| |
| − | </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(st_startpoint(the_geom));
| |
| − | UPDATE ways SET y1 = y(st_startpoint(the_geom));
| |
| − | UPDATE ways SET x2 = x(st_endpoint(the_geom));
| |
| − | UPDATE ways SET y2 = y(st_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 | 14701 | 0.133961657579708
| |
| − | 1034 | 974 | 0.0433580404548831
| |
| − | ...
| |
| − | 6749 | 8014 | 0.0518861583127315
| |
| − | 6750 | 8015 | 0.0518860343451018
| |
| − | 20 | -1 | 0
| |
| − | </pre>
| |
| − | | |
| − | Alternativně lze použít funkci <tt>astar_sp_delta</tt> (wrapper pro <tt>shortest_path_astar</tt>).
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, ST_AsText(the_geom) AS the_geom
| |
| − | FROM astar_sp_delta('ways', 10, 20, 0.1);
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | </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>
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, ST_AsText(the_geom) AS the_geom
| |
| − | FROM shootingstar_sp('ways', 10, 20, 0.1, 'length', true, true);
| |
| − | </source>
| |
| − | | |
| − | == Testcase 2 ==
| |
| − | | |
| − | Tento text čerpá z [http://www.pgrouting.org/docs/foss4g2008/index.html FOSS4G routing with pgRouting tools and OpenStreetMap road data] (2008).
| |
| − | | |
| − | === Vstupní data ===
| |
| − | | |
| − | Testovací data jsou dostupná z
| |
| − | | |
| − | git clone https://github.com/pgRouting/workshop-2008.git workshop-2008
| |
| − | | |
| − | Nahrajeme testovací data.
| |
| − | | |
| − | cd workshop-2008
| |
| − | psql pgis2_routing -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>
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, AsText(the_geom) AS the_geom
| |
| − | FROM astar_sp_delta('ways', 10, 20, 0.1);
| |
| − | </source>
| |
| − | | |
| − | <pre>
| |
| − | gid | the_geom
| |
| − | ------+------------------------------------------------------------------
| |
| − | 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))
| |
| − | ...
| |
| − | 6618 | MULTILINESTRING((18.4236514 -33.9182429,18.4237423 -33.9182966))
| |
| − | 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966))
| |
| − | 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))
| |
| − | (62 rows)
| |
| − | </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>
| |
| − | | |
| − | <source lang=sql>
| |
| − | SELECT gid, AsText(the_geom) AS the_geom
| |
| − | FROM shootingstar_sp('ways', 10, 20, 0.1, 'length', true, true);
| |
| − | </source>
| |
| − | | |
| − | == 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]
| |
| − | * [http://workshop.pgrouting.org/ pgRouting Workshop Manual]
| |
| − | * [http://www.pgrouting.org/docs/tools/osm2pgrouting.html osm2pgrouting]
| |
| − | | |
| − | {{Databáze}}
| |
| − | {{GIS}}
| |
| − | {{GFOSS}}
| |
