Shooting star and bridge - Usage example
Par david techer, mardi 22 juillet 2008 à 16:31 :: PostGIS et PostgreSQL :: #348 :: rss
We have the following roads. See the following image
routing_db=# SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test order by gid; id | source | target | cost | reverse_cost | x1 | y1 | x2 | y2 | rule | to_cost ----+--------+--------+------------------+------------------+----+------+-----+------+------+--------- 1 | 1 | 2 | 27.5 | 27.5 | 60 | 87.5 | 60 | 115 | | 2 | 2 | 3 | 25.4950975679639 | 25.4950975679639 | 60 | 115 | 85 | 120 | | 3 | 1 | 4 | 62.5 | 1000 | 60 | 87.5 | 60 | 25 | | 4 | 5 | 6 | 29.0688837074973 | 29.0688837074973 | 1 | 1 | 20 | 23 | | 5 | 6 | 4 | 40.0499687890016 | 40.0499687890016 | 20 | 23 | 60 | 25 | | 6 | 4 | 7 | 27.3130005674953 | 27.3130005674953 | 60 | 25 | 85 | 36 | | 7 | 8 | 1 | 59 | 59 | 1 | 87.5 | 60 | 87.5 | | 8 | 1 | 9 | 25 | 25 | 60 | 87.5 | 85 | 87.5 | | 9 | 9 | 10 | 65 | 65 | 85 | 87.5 | 150 | 87.5 | | 10 | 11 | 3 | 15 | 15 | 85 | 135 | 85 | 120 | | 11 | 3 | 9 | 32.5 | 32.5 | 85 | 120 | 85 | 87.5 | | 12 | 9 | 7 | 51.5 | 51.5 | 85 | 87.5 | 85 | 36 | | 13 | 7 | 12 | 35 | 35 | 85 | 36 | 85 | 1 | | (13 lignes)Suppose now that we have build a bridge from edge=8 to edge=9 and a one-way street. We have the following image
Question: How to use shooting start in order to taking account the bridge?
First we have to update the fields rule and to_cost for edge in (8,9,11,12) and add required tuples. Then we have the following content.Notice: Edge 3 is a one-way street. so reverse_cost=1 000 000
routing_db=# select gid,astext(the_geom),source,target,x1,y1,x2,y2,cost,reverse_cost,rule,to_cost from test order by 1; gid | astext | source | target | x1 | y1 | x2 | y2 | cost | reverse_cost | rule | to_cost -----+-------------------------------------+--------+--------+----+------+-----+------+------------------+------------------+------+--------- 1 | MULTILINESTRING((60 87.5,60 115)) | 1 | 2 | 60 | 87.5 | 60 | 115 | 27.5 | 27.5 | | 2 | MULTILINESTRING((60 115,85 120)) | 2 | 3 | 60 | 115 | 85 | 120 | 25.4950975679639 | 25.4950975679639 | | 3 | MULTILINESTRING((60 87.5,60 25)) | 1 | 4 | 60 | 87.5 | 60 | 25 | 62.5 | 1000000 | | 4 | MULTILINESTRING((1 1,20 23)) | 5 | 6 | 1 | 1 | 20 | 23 | 29.0688837074973 | 29.0688837074973 | | 5 | MULTILINESTRING((20 23,60 25)) | 6 | 4 | 20 | 23 | 60 | 25 | 40.0499687890016 | 40.0499687890016 | | 6 | MULTILINESTRING((60 25,85 36)) | 4 | 7 | 60 | 25 | 85 | 36 | 27.3130005674953 | 27.3130005674953 | | 7 | MULTILINESTRING((1 87.5,60 87.5)) | 8 | 1 | 1 | 87.5 | 60 | 87.5 | 59 | 59 | | 8 | MULTILINESTRING((60 87.5,85 87.5)) | 1 | 9 | 60 | 87.5 | 85 | 87.5 | 25 | 25 | 11 | 2000 8 | MULTILINESTRING((60 87.5,85 87.5)) | 1 | 9 | 60 | 87.5 | 85 | 87.5 | 25 | 25 | 12 | 2000 9 | MULTILINESTRING((85 87.5,150 87.5)) | 9 | 10 | 85 | 87.5 | 150 | 87.5 | 65 | 65 | 10 | 2000 9 | MULTILINESTRING((85 87.5,150 87.5)) | 9 | 10 | 85 | 87.5 | 150 | 87.5 | 65 | 65 | 11 | 2000 9 | MULTILINESTRING((85 87.5,150 87.5)) | 9 | 10 | 85 | 87.5 | 150 | 87.5 | 65 | 65 | 12 | 2000 10 | MULTILINESTRING((85 135,85 120)) | 11 | 3 | 85 | 135 | 85 | 120 | 15 | 15 | | 11 | MULTILINESTRING((85 120,85 87.5)) | 3 | 9 | 85 | 120 | 85 | 87.5 | 32.5 | 32.5 | 8 | 1000 11 | MULTILINESTRING((85 120,85 87.5)) | 3 | 9 | 85 | 120 | 85 | 87.5 | 32.5 | 32.5 | 9 | 1000 12 | MULTILINESTRING((85 87.5,85 36)) | 9 | 7 | 85 | 87.5 | 85 | 36 | 51.5 | 51.5 | 8 | 1000 12 | MULTILINESTRING((85 87.5,85 36)) | 9 | 7 | 85 | 87.5 | 85 | 36 | 51.5 | 51.5 | 9 | 1000 13 | MULTILINESTRING((85 36,85 1)) | 7 | 12 | 85 | 36 | 85 | 1 | 35 | 35 | | (18 lignes)
Notice: for more informations, please see http://pgrouting.postlbs.org/
Let's now do a few tests
Example 1
Find the path from edge=7 to edge=13
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',7,13, true,true);
edge_id
---------
7
3
6
13
For the reversed path (from 13 to 7), we have
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',13,7, true,true);
edge_id
---------
13
13
12
11
2
1
7
Example 2
Find the path from edge=9 to edge=13
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,13, true,true);
edge_id
---------
9
9
8
3
6
13
If start is 13 and stop is 9 then we have
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',13,9, true,true);
edge_id
---------
13
13
12
11
2
1
8
9
Example 3
Find the path from edge=12 to edge=9
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',12,9, true,true);
edge_id
---------
12
12
11
2
1
8
9
From 9 to 12, we have
routing_db=# SELECT edge_id FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,12, true,true);
edge_id
---------
9
9
8
1
2
11
12
Example 4
From 9 to 10 and vice-versarouting_db=# SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',9,10, true,true);
vertex_id | edge_id | cost
-----------+---------+------------------
8 | 9 | 65
12 | 9 | 65
8 | 8 | 25
6 | 1 | 27.5
18 | 2 | 25.4950975679639
16 | 10 | 15
(6 lignes)
routing_db=# SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM test',10,9, true,true);
vertex_id | edge_id | cost
-----------+---------+------------------
15 | 10 | 15
16 | 2 | 25.4950975679639
18 | 1 | 27.5
6 | 8 | 25
8 | 9 | 65
(5 lignes)
Commentaires
Aucun commentaire pour le moment.
Ajouter un commentaire