pgRouting

Changeset 234

Show
Ignore:
Timestamp:
09/22/08 20:13:37 (2 months ago)
Author:
daniel
Message:

workshop: astar and shootingstar chapter + little changes

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • branches/workshop/FOSS4G2008/Docs/01_introduction.chapter

    r227 r234  
    3737svn checkout http://pgrouting.postlbs.org/svn/pgrouting/branches/workshop/FOSS4G2008/ workshop 
    3838}}} 
     39 
     40== Further informations == 
     41 
     42 * pgRouting project website: http://pgrouting.postlbs.org 
     43 * MapFish project website: http://www.mapfish.org 

  • branches/workshop/FOSS4G2008/Docs/07_pgrouting.dijkstra.chapter

    r232 r234  
    1 = pgrouting with Dijkstra algorithm = 
     1= pgRouting with Dijkstra algorithm = 
    22 
    33Dijkstra algorithm was the first algorithm implemented in pgRouting.  
    …… 
    1515 
    1616Note:  
    17  * Source and target IDs are node IDs. 
     17 * Source and target IDs are vertex IDs. 
    1818 * Undirected graphs ("directed false") ignores "has_reverse_cost" setting 
    1919 
    …… 
    5454=== Wrapper WITHOUT bounding box === 
    5555 
    56 Wrappers can change the format and ordering of the result and they often set  
     56Wrappers can change the format and ordering of the result. They often set  
    5757default function parameters and make the usage of pgRouting more simple.  
    5858 
    …… 
    6565  gid   |                              the_geom       
    6666--------+--------------------------------------------------------------- 
    67   293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 
    68  4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) 
    69  4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) 
    70   ... | ... 
    71   762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 
    72   761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) 
     67    293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 
     68   4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) 
     69   4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) 
     70    ... | ... 
     71    762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 
     72    761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) 
    7373(62 rows) 
    7474}}} 
    …… 
    8383        FROM dijkstra_sp_delta('ways', 10, 20, 0.1); 
    8484}}} 
     85  gid   |                              the_geom       
     86--------+--------------------------------------------------------------- 
     87    293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 
     88   4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) 
     89   4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) 
     90    ... | ... 
     91    762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 
     92    761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) 
     93(62 rows) 
    8594 
    8695Note: The projection of OSM data is "degree", so we set a bounding box  
    87 containing start and end vertex plus a 0.1 degree buffer. 
     96containing start and end vertex plus a 0.1 degree buffer for example. 

  • branches/workshop/FOSS4G2008/Docs/08_pgrouting.astar.chapter

    r222 r234  
     1= pgRouting with A-Star algorithm = 
     2 
     3A-Star algorithm is another well-known routing algorithm. It adds geographical  
     4information to source and target of each network link. This enables the shortest  
     5path search to prefer links which are closer to the target of the search. 
     6 
     7== Prepare routing table for A-Star == 
     8 
     9For A-Star you need to prepare your network table and add latitute/longitude  
     10columns (x1, y1 and x2, y2) and calculate their values. 
     11 
     12{{{ 
     13ALTER TABLE ways ADD COLUMN x1 double precision; 
     14ALTER TABLE ways ADD COLUMN y1 double precision; 
     15ALTER TABLE ways ADD COLUMN x2 double precision; 
     16ALTER TABLE ways ADD COLUMN y2 double precision; 
     17}}} 
     18 
     19{{{ 
     20UPDATE ways SET x1 = x(startpoint(the_geom)); 
     21UPDATE ways SET y1 = y(startpoint(the_geom)); 
     22UPDATE ways SET x2 = x(endpoint(the_geom)); 
     23UPDATE ways SET y2 = y(endpoint(the_geom)); 
     24}}} 
     25 
     26Note: "endpoint()" function fails for some versions of PostgreSQL (ie. 8.2.5, 8.1.9).  
     27A workaround for that problem is using the "PointN()" function instead: 
     28 
     29{{{ 
     30UPDATE ways SET x1 = x(PointN(the_geom, 1)); 
     31UPDATE ways SET y1 = y(PointN(the_geom, 1)); 
     32UPDATE ways SET x2 = x(PointN(the_geom, NumPoints(the_geom))); 
     33UPDATE ways SET y2 = y(PointN(the_geom, NumPoints(the_geom))); 
     34}}} 
     35 
     36== Shortest Path A-Star core function == 
     37 
     38Shortest Path A-Star function is very similar to the Dijkstra function, though  
     39it prefers links that are close to the target of the search. The heuristics of  
     40this search are predefined, so you need to recompile pgRouting if you want to  
     41make changes to the heuristic function itself. 
     42 
     43{{{ 
     44shortest_path_astar( sql text,  
     45                   source_id integer,  
     46                   target_id integer,  
     47                   directed boolean,  
     48                   has_reverse_cost boolean )  
     49}}} 
     50 
     51Note:  
     52 * Source and target IDs are vertex IDs. 
     53 * Undirected graphs ("directed false") ignores "has_reverse_cost" setting 
     54 
     55=== Example of A-Star core function === 
     56 
     57{{{ 
     58SELECT * FROM shortest_path_astar(' 
     59                SELECT gid as id,  
     60                         source::integer,  
     61                         target::integer,  
     62                         length::double precision as cost,  
     63                         x1, y1, x2, y2 
     64                        FROM ways',  
     65                10, 20, false, false);  
     66}}} 
     67 
     68{{{ 
     69vertex_id | edge_id |        cost          
     70-----------+---------+--------------------- 
     71        10 |     293 |  0.0059596293824534 
     72         9 |    4632 |  0.0846731039249787 
     73      3974 |    4633 |  0.0765635090514303 
     74       ... |     ... |  ... 
     75        20 |      -1 |                   0 
     76(63 rows) 
     77}}} 
     78 
     79=== Wrapper function WITH bounding box === 
     80 
     81Wrapper functions extend the core functions with transformations, bounding box  
     82limitations, etc..  
     83 
     84{{{ 
     85SELECT gid, AsText(the_geom) AS the_geom  
     86        FROM astar_sp_delta('ways', 10, 20, 0.1); 
     87}}} 
     88 
     89{{{ 
     90  gid   |                              the_geom       
     91--------+--------------------------------------------------------------- 
     92    293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833)) 
     93   4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183)) 
     94   4633 | MULTILINESTRING((18.4077388 -33.9436183,18.4080293 -33.9429733)) 
     95    ... | ... 
     96    762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966)) 
     97    761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275)) 
     98(62 rows) 
     99}}} 
     100 
     101Note:  
     102 * There is currently no wrapper function for A-Star without bounding box, 
     103since bounding boxes are very useful to increase performance. If you don't need 
     104a bounding box Dijkstra will be enough anyway. 
     105 * The projection of OSM data is "degree", so we set a bounding box  
     106containing start and end vertex plus a 0.1 degree buffer for example. 

  • branches/workshop/FOSS4G2008/Docs/09_pgrouting.shootingstar.chapter

    r222 r234  
     1= pgRouting with Shooting-Star algorithm = 
     2 
     3Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. 
     4Its speciality is that it routes from link to link, not from vertex to vertex  
     5as Dijkstra and A-Star algorithms do. 
     6This makes it possible to define relations between links for example, and it  
     7solves some other vertex-based algorithm issues like "parallel links", which 
     8have same source and target but different costs. 
     9 
     10== Prepare routing table for Shooting-Star == 
     11 
     12For 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 
     14heuristic function, which prefers links closer to the target of the search. 
     15 
     16{{{ 
     17ALTER TABLE ways ADD COLUMN reverse_cost double precision; 
     18UPDATE ways SET reverse_cost = length; 
     19}}} 
     20 
     21{{{ 
     22ALTER TABLE ways ADD COLUMN to_cost double precision; 
     23ALTER TABLE ways ADD COLUMN rule text; 
     24}}} 
     25 
     26== Shortest Path Shooting-Star core function == 
     27 
     28Shooting-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{{{ 
     36shortest_path_shooting_star( sql text,  
     37                   source_id integer,  
     38                   target_id integer,  
     39                   directed boolean,  
     40                   has_reverse_cost boolean )  
     41}}} 
     42 
     43Note:  
     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 
     49Shooting* algorithm calculates a path from edge to edge (not from vertex to  
     50vertex). Column vertex_id contains start vertex of an edge from column edge_id. 
     51 
     52To 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}}} 
     58means 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}}} 
     64means that the cost of going from edge 14 to edge 12 through edge 4 is 1000. 
     65 
     66If you need multiple restrictions for a given edge then you have to add  
     67multiple 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}}} 
     74means 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{{{ 
     79SELECT * 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 
     103Wrapper functions extend the core functions with transformations, bounding box  
     104limitations, etc..  
     105 
     106{{{ 
     107SELECT 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 
     123Note:  
     124 * There is currently no wrapper function for A-Star without bounding box, 
     125since bounding boxes are very useful to increase performance. If you don't need 
     126a bounding box Dijkstra will be enough anyway. 
     127 * The projection of OSM data is "degree", so we set a bounding box  
     128containing start and end vertex plus a 0.1 degree buffer for example.