I've experimented with using pgRouting's shortest_path function to compute routes using the hiking trails defined in the OpenStreetMap data set.
In the OSM model as created by osm2pgsql, the relations table models a hiking trail based on a set of members (each member a LINESTRING geometry from the planet_osm_line table).
The problem is you cannot build a topology based solely on the start and end points of each trail segment, because more often then not, trail segment intersect mid-way:
So I used the relations table to build the topology where each trail segment is split based on the POINTS that are part of its LINESTRING geometry. This means that every point from the trail segment becomes a node in our topology (this is very inefficient, but I could not find a faster way of not missing mid-trail intersections).
I've built the topology using the following SQL code:
Once the topology has been created, I called assign_vertex_id() to compute source and target values (for some reason, probe_geometry_columns does not work on my machine so I had to fill in my topology table's geometry column data by hand):
The first thing required is finding topology nodes close to the POI's that represent departure and arrival points.
In this example, we will compute a route between Cabana Piscul Negru and Negoiu:
there are two edges in close proximity to Piscul Negru (94 meters away). They share source and target nodes because they are in fact over a segment shared between the two different trails.
We repeat the query to find out the node for Negoiu:
Now that we've got the start (17684) and end (18832) nodes, we can ask pgRouting to compute the route:
If we retrieve a summary of the involved trails, we get:
While the choice of the blue cross trail might look weird, it happens because in this particular section, the blue cross trail shares the same path as the blue triangle trail. From the routing engine's point of view, they are perfectly equivalent but a human might argue that the correct trail sequencing would be "Piscu Negru - Refugiul Caltun" following the blue triangle and then the ridge trail following the red stripe up to Negoiu.
You can also use the driving distance functions from pgRouting.
This is a colormap showing a classification of reachable places starting from Cabana Piscul Negru:
Building the topology
In the OSM model as created by osm2pgsql, the relations table models a hiking trail based on a set of members (each member a LINESTRING geometry from the planet_osm_line table).
The problem is you cannot build a topology based solely on the start and end points of each trail segment, because more often then not, trail segment intersect mid-way:
So I used the relations table to build the topology where each trail segment is split based on the POINTS that are part of its LINESTRING geometry. This means that every point from the trail segment becomes a node in our topology (this is very inefficient, but I could not find a faster way of not missing mid-trail intersections).
I've built the topology using the following SQL code:
drop table if exists trail_network;
create table trail_network(gid serial, osm_id integer, name varchar, symbol varchar, the_geom geometry, source integer, target integer, length float);
CREATE OR REPLACE FUNCTION compute_trail_network() RETURNS text as $$
DECLARE
relationRecord record;
partIndex integer;
lineRecord record;
wayRecord record;
geomFragment record;
BEGIN
FOR relationRecord in select id, parts, tags from planet_osm_rels where tags @> '{osmc:symbol}' and tags @> '{hiking}' LOOP
FOR partIndex in array_lower(relationRecord.parts, 1)..array_upper(relationRecord.parts, 1) LOOP
SELECT name, highway, way from planet_osm_line where osm_id = relationRecord.parts[partIndex] into lineRecord;
SELECT * from planet_osm_ways where id = relationRecord.parts[partIndex] into wayRecord;
FOR pointIndex in 1..ST_NPoints(lineRecord.way)-1 LOOP
select st_makeline(st_pointn(lineRecord.way, pointIndex), st_pointn(lineRecord.way, pointIndex+1)) as way into geomFragment;
INSERT into trail_network(osm_id, name, symbol, the_geom, length) values(relationRecord.parts[partIndex], substring(array_to_string(relationRecord.tags, '#'), '#name#([^#]*)#?$'), substring(array_to_string(relationRecord.tags, '#'), '(red_cross|blue_cross|red_triangle|blue_triangle|red_dot|blue_dot|red_stripe|blue_stripe|yellow_stripe|yellow_triangle|yellow_cross)'), geomFragment.way, st_length(geomFragment.way));
END LOOP;
END LOOP;
END LOOP;
return 'Done';
END;
$$ LANGUAGE 'plpgsql';
select * from compute_trail_network();
Once the topology has been created, I called assign_vertex_id() to compute source and target values (for some reason, probe_geometry_columns does not work on my machine so I had to fill in my topology table's geometry column data by hand):
insert into geometry_columns(f_table_catalog, f_table_schema, f_table_name, f_geometry_column, coord_dimension, srid, type) values('', 'public', 'trail_network', 'the_geom', 2, 900913, 'LINESTRING');
SELECT assign_vertex_id('trail_network', 2, 'the_geom', 'gid');
Computing a route
The first thing required is finding topology nodes close to the POI's that represent departure and arrival points.
In this example, we will compute a route between Cabana Piscul Negru and Negoiu:
osm=# select t.gid, t.source, t.target, t.osm_id, t.name, st_distance(p.way, t.the_geom) from trail_network t, planet_osm_point p where st_buffer(p.way, 100) && t.the_geom and p.name='Cabana Piscul Negru' order by st_distance(p.way, t.the_geom) asc limit 5;
gid | source | target | osm_id | name | st_distance
-------+--------+--------+----------+--------------------------------+------------------
41354 | 17684 | 17685 | 73964460 | Piscu Negru - Refugiul Călțun | 94.9336094118476
41532 | 17684 | 17685 | 73964460 | Piscul Negru - Șaua Paltinului | 94.9336094118476
(2 rows)
there are two edges in close proximity to Piscul Negru (94 meters away). They share source and target nodes because they are in fact over a segment shared between the two different trails.
We repeat the query to find out the node for Negoiu:
osm=# select t.gid, t.source, t.target, t.osm_id, t.name, st_distance(p.way, t.the_geom) from trail_network t, planet_osm_point p where st_buffer(p.way, 100) && t.the_geom and p.name='Negoiu' order by st_distance(p.way, t.the_geom) asc limit 5;
gid | source | target | osm_id | name | st_distance
-------+--------+--------+----------+----------------+------------------
42688 | 18832 | 18833 | 27182093 | Traseu creasta | 2.03276684697733
42687 | 18831 | 18832 | 27182093 | Traseu creasta | 2.18879960182101
42686 | 18830 | 18831 | 27182093 | Traseu creasta | 13.9052808592012
42685 | 18829 | 18830 | 27182093 | Traseu creasta | 35.2142772300472
42684 | 18828 | 18829 | 27182093 | Traseu creasta | 63.933925517158
(5 rows)
Now that we've got the start (17684) and end (18832) nodes, we can ask pgRouting to compute the route:
osm=# select tn.name, p.edge_id, tn.symbol from trail_network tn, (select edge_id from shortest_path('
osm'# SELECT gid as id,
osm'# source,
osm'# target,
osm'# length as cost
osm'# FROM trail_network',
osm(# 17684, 18832,false,false)) p
osm-# where p.edge_id = tn.gid;
name | edge_id | symbol
-------------------------------------+---------+---------------
Piscu Negru - Refugiul Călțun | 41343 | blue_triangle
Piscu Negru - Refugiul Călțun | 41341 | blue_triangle
Piscu Negru - Refugiul Călțun | 41338 | blue_triangle
Piscu Negru - Refugiul Călțun | 41335 | blue_triangle
[..]
If we retrieve a summary of the involved trails, we get:
osm=# select max(tn.name), max(tn.symbol) from trail_network tn, (select edge_id from shortest_path('
osm'# SELECT gid as id,
osm'# source,
osm'# target,
osm'# length as cost
osm'# FROM trail_network',
osm(# 17684, 18832,false,false)) p
osm-# where p.edge_id = tn.gid group by tn.name;
max | max
-------------------------------------+---------------
Piscu Negru - Refugiul Călțun | blue_triangle
Lacul Călțun - Tunel Transfăgărășan | blue_cross
Traseu creasta | red_stripe
(3 rows)
While the choice of the blue cross trail might look weird, it happens because in this particular section, the blue cross trail shares the same path as the blue triangle trail. From the routing engine's point of view, they are perfectly equivalent but a human might argue that the correct trail sequencing would be "Piscu Negru - Refugiul Caltun" following the blue triangle and then the ridge trail following the red stripe up to Negoiu.
You can also use the driving distance functions from pgRouting.
This is a colormap showing a classification of reachable places starting from Cabana Piscul Negru:
