1 | = pgRouting with Shooting-Star algorithm = |
---|
2 | |
---|
3 | Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. |
---|
4 | Its speciality is that it routes from link to link, not from vertex to vertex |
---|
5 | as Dijkstra and A-Star algorithms do. |
---|
6 | This makes it possible to define relations between links for example, and it |
---|
7 | solves some other vertex-based algorithm issues like "parallel links", which |
---|
8 | have same source and target but different costs. |
---|
9 | |
---|
10 | == Prepare routing table for Shooting-Star == |
---|
11 | |
---|
12 | For Shooting-Star you need to prepare your network table and add the |
---|
13 | "reverse_cost" and "to_cost" column. Like A-Star this algorithm also has a |
---|
14 | heuristic function, which prefers links closer to the target of the search. |
---|
15 | |
---|
16 | {{{ |
---|
17 | ALTER TABLE ways ADD COLUMN reverse_cost double precision; |
---|
18 | UPDATE ways SET reverse_cost = length; |
---|
19 | }}} |
---|
20 | |
---|
21 | {{{ |
---|
22 | ALTER TABLE ways ADD COLUMN to_cost double precision; |
---|
23 | ALTER TABLE ways ADD COLUMN rule text; |
---|
24 | }}} |
---|
25 | |
---|
26 | == Shortest Path Shooting-Star core function == |
---|
27 | |
---|
28 | Shooting-Star algorithm introduces two new attributes: |
---|
29 | * rule: a string with a comma separated list of edge IDs, which describes a |
---|
30 | rule for turning restriction (if you came along these edges, you can pass |
---|
31 | through the current one only with the cost stated in to_cost column) |
---|
32 | * to_cost: a cost of a restricted passage (can be very high in a case of turn |
---|
33 | restriction or comparable with an edge cost in a case of traffic light) |
---|
34 | |
---|
35 | {{{ |
---|
36 | shortest_path_shooting_star( sql text, |
---|
37 | source_id integer, |
---|
38 | target_id integer, |
---|
39 | directed boolean, |
---|
40 | has_reverse_cost boolean ) |
---|
41 | }}} |
---|
42 | |
---|
43 | Note: |
---|
44 | * Source and target IDs are link IDs. |
---|
45 | * Undirected graphs ("directed false") ignores "has_reverse_cost" setting |
---|
46 | |
---|
47 | === Example for Shooting-Star "rule" === |
---|
48 | |
---|
49 | Shooting* algorithm calculates a path from edge to edge (not from vertex to |
---|
50 | vertex). Column vertex_id contains start vertex of an edge from column edge_id. |
---|
51 | |
---|
52 | To describe turn restrictions: |
---|
53 | {{{ |
---|
54 | gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule |
---|
55 | -----+--------+--------+------+----+----+----+----+---------+------ |
---|
56 | 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14 |
---|
57 | }}} |
---|
58 | means that the cost of going from edge 14 to edge 12 is 1000, and |
---|
59 | {{{ |
---|
60 | gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule |
---|
61 | -----+--------+--------+------+----+----+----+----+---------+------ |
---|
62 | 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14, 4 |
---|
63 | }}} |
---|
64 | means that the cost of going from edge 14 to edge 12 through edge 4 is 1000. |
---|
65 | |
---|
66 | If you need multiple restrictions for a given edge then you have to add |
---|
67 | multiple records for that edge each with a separate restriction. |
---|
68 | {{{ |
---|
69 | gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule |
---|
70 | -----+--------+--------+------+----+----+----+----+---------+------ |
---|
71 | 11 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 4 |
---|
72 | 11 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 12 |
---|
73 | }}} |
---|
74 | means that the cost of going from either edge 4 or 12 to edge 11 is 1000. And then you always need to order your data by gid when you load it to a shortest path function.. |
---|
75 | |
---|
76 | === Example of Shooting-Star core function === |
---|
77 | |
---|
78 | {{{ |
---|
79 | SELECT * FROM shortest_path_shooting_star(' |
---|
80 | SELECT gid as id, |
---|
81 | source::integer, |
---|
82 | target::integer, |
---|
83 | length::double precision as cost, |
---|
84 | x1, y1, x2, y2, |
---|
85 | rule, to_cost |
---|
86 | FROM ways', |
---|
87 | 293, 761, false, false); |
---|
88 | }}} |
---|
89 | |
---|
90 | {{{ |
---|
91 | vertex_id | edge_id | cost |
---|
92 | -----------+---------+--------------------- |
---|
93 | 4232 | 293 | 0.0059596293824534 |
---|
94 | 3144 | 293 | 0.0059596293824534 |
---|
95 | 4232 | 4632 | 0.0846731039249787 |
---|
96 | ... | ... | ... |
---|
97 | 51 | 761 | 0.0305298478239596 |
---|
98 | (63 rows) |
---|
99 | }}} |
---|
100 | |
---|
101 | === Wrapper function WITH bounding box === |
---|
102 | |
---|
103 | Wrapper functions extend the core functions with transformations, bounding box |
---|
104 | limitations, etc.. |
---|
105 | |
---|
106 | {{{ |
---|
107 | SELECT gid, AsText(the_geom) AS the_geom |
---|
108 | FROM shootingstar_sp('ways', 293, 761, 0.1, 'length', true, true); |
---|
109 | }}} |
---|
110 | |
---|
111 | {{{ |
---|
112 | gid | the_geom |
---|
113 | --------+--------------------------------------------------------------- |
---|
114 | 293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) |
---|
115 | 293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) |
---|
116 | 4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) |
---|
117 | ... | ... |
---|
118 | 762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) |
---|
119 | 761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) |
---|
120 | (62 rows) |
---|
121 | }}} |
---|
122 | |
---|
123 | Note: |
---|
124 | * There is currently no wrapper function for A-Star without bounding box, |
---|
125 | since bounding boxes are very useful to increase performance. If you don't need |
---|
126 | a bounding box Dijkstra will be enough anyway. |
---|
127 | * The projection of OSM data is "degree", so we set a bounding box |
---|
128 | containing start and end vertex plus a 0.1 degree buffer for example. |
---|