Le blog de Jean David TECHER, un Réunionnais à Saint-Priest/Lyon

Aller au contenu | Aller au menu | Aller à la recherche


< 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 >

jeudi 24 juillet 2008

Bientôt les vacances...!

C'est pour bientôt! Encore une journée de boulot et demain soir c'est les vacances! Ca ne durera qu'une semaine mais c'est déjà ça!

Oh purée, j'ai hâte d'être à Montpellier revoir mon chat, mes amis, le Lez!

[PgRouting 1.02] Shooting star - usage example with turn restriction

This is my favorite function in PgRouting . Here we will see an example. For more info, please see http://pgrouting.postlbs.org/wiki/ShootingStar

Let's suppose that we have the following network with two roundabouts as shown in the following picture. The SQL file used here is available at http://www.davidgis.fr/download/pgrouting_wr.sql


The network
The associated table is named wr. The wr's content is
routing=# SELECT gid as id, source, target, cost, reverse_cost,x1, y1,x2, y2, rule, to_cost FROM wr order by id;
 id | source | target |       cost       |   reverse_cost   |        x1        |        y1         |        x2        |        y2         | rule | to_cost 
----+--------+--------+------------------+------------------+------------------+-------------------+------------------+-------------------+------+---------
  1 |      1 |      2 | 14.2572101668807 |             1000 | 76.7176891326003 |   33.775246780918 | 87.3962905382969 |  43.2217018705726 |      |        
  2 |      2 |      3 | 11.0893168443772 |             1000 | 87.3962905382969 |  43.2217018705726 | 87.3962905382969 |  54.3110187149498 |      |        
  3 |      3 |      4 | 13.9884637834871 |             1000 | 87.3962905382969 |  54.3110187149498 | 76.7176891326003 |  63.3467583659239 |      |        
  4 |      4 |      5 | 14.2572101668807 |             1000 | 76.7176891326003 |  63.3467583659239 | 67.2712340429456 |  52.6681569602273 |      |        
  5 |      5 |      6 | 10.6864968606796 |             1000 | 67.2712340429456 |  52.6681569602273 |  66.860518604265 |  41.9895555545307 |      |        
  6 |      6 |      1 | 12.8311604873812 |             1000 |  66.860518604265 |  41.9895555545307 | 76.7176891326003 |   33.775246780918 |      |        
  7 |      7 |      1 | 53.8753258085636 | 53.8753258085636 |               80 |               -20 | 76.7176891326003 |   33.775246780918 |      |        
  8 |      8 |      4 | 62.5380849791951 | 62.5380849791951 | 73.0212501844746 |  125.775505045381 | 76.7176891326003 |  63.3467583659239 |      |        
  9 |      7 |      9 |               40 |               40 |               80 |               -20 |              120 |               -20 |      |        
 10 |      9 |     10 | 33.4201752293529 | 33.4201752293529 |              120 |               -20 | 141.610728444141 | -45.4928328844451 |      |        
 11 |      9 |     11 |               60 |               60 |              120 |               -20 |              180 |               -20 |      |        
 12 |     11 |     12 | 25.9044654619518 | 25.9044654619518 |              180 |               -20 | 180.217979680121 | -45.9035483231257 |      |        
 13 |     12 |     10 | 38.6094358307609 | 38.6094358307609 | 180.217979680121 | -45.9035483231257 | 141.610728444141 | -45.4928328844451 |      |        
 14 |     13 |     12 | 29.5829181472758 | 29.5829181472758 | 181.039410557482 | -75.4750599081316 | 180.217979680121 | -45.9035483231257 |      |        
 15 |     13 |     14 | 39.4286821133412 | 39.4286821133412 | 181.039410557482 | -75.4750599081316 | 141.610728444141 | -75.4750599081316 |      |        
 16 |     14 |     10 | 29.9822270236865 | 29.9822270236865 | 141.610728444141 | -75.4750599081316 | 141.610728444141 | -45.4928328844451 |      |        
 17 |     15 |     13 | 39.2224758594282 | 39.2224758594282 |              220 |               -80 | 181.039410557482 | -75.4750599081316 |      |        
 18 |     15 |     16 | 38.0005743220152 |             1000 |              220 |               -80 | 251.682466010552 | -79.1714988562574 |      |        
 19 |     16 |     15 | 38.0539027874633 |             1000 | 251.682466010552 | -79.1714988562574 |              220 |               -80 |      |        
 20 |     17 |     16 | 48.3246366252935 | 48.3246366252935 |              300 |               -80 | 251.682466010552 | -79.1714988562574 |      |        
 21 |     11 |     18 |  115.27849852631 |  115.27849852631 |              180 |               -20 | 295.218302510699 | -23.7249146343713 |      |        
 22 |     18 |     17 | 56.4778705670458 | 56.4778705670458 | 295.218302510699 | -23.7249146343713 |              300 |               -80 |      |        
(22 rows)

I. Roundabouts

We have two roundabouts. First done with (1,2,3,4,5,6) and secund done with (18,19). So that is the reason why reverse_cost is enough expensive: reverse_cost=1000

In a first time, we want the path from edge=20 to edge=8. Using shooting_star, we have
routing=# SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, reverse_cost,x1, y1,x2, y2, rule, to_cost FROM wr order by id',20,8,true,true);
 vertex_id | edge_id |       cost       
-----------+---------+------------------
        31 |      20 | 48.3246366252935
        29 |      19 | 38.0539027874633
        27 |      17 | 39.2224758594282
        23 |      14 | 29.5829181472758
        21 |      13 | 38.6094358307609
        17 |      10 | 33.4201752293529
        15 |       9 |               40
        12 |       7 | 53.8753258085636
         1 |       1 | 14.2572101668807
         2 |       2 | 11.0893168443772
         4 |       3 | 13.9884637834871
         6 |       8 | 62.5380849791951
(12 rows)
We have

Shortest path using shooting star from edge=20 to 8

II. Turn restrictions

Let's suppose now that we have following restrictions:

  1. from edge from 17 to 14 ;
  2. from edge from 16 to 10;
You can' tgo from 17 to 14 and from 16 to 10. The restricted edges are shown on the following picture


Restricted edges: You can't go from 17 to 14 and from 16 to 10

So we have to do

routing=# update wr set to_cost=100,rule='17' where gid=14;
UPDATE 1
routing=# update wr set to_cost=100,rule='16' where gid=10;

So we have
routing=# 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 wr order by id',20,8,true,true);
 edge_id 
---------
      20
      19
      17
      15
      16
      13
      12
      11
       9
       7
       1
       2
       3
       8
(14 rows)
Beautifull...The final result is

Shortest path from edge=20 to 8

mardi 22 juillet 2008

Shooting star and bridge - Usage example

We have the following roads. See the following image

The table test has the following content
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-versa
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',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)

[PgRouting 1.02]Using Shooting star with a clause where

Let's suppose that we are at Montpellier in France. (the one of the most beautifull towns in South France !). We want to go from "Avenue du Fès" to "Rue de Casseyrols", i.e.
  • start point := "Avenue du Fès";
  • end point := "Rue de Casseyrols".

Everything is shown in the following picture


start point and and point

In order to manage the street, we had the following column to hour table. If the status field is yes, then the street is available.

ALTER TABLE routing add column status text default 'yes';
We use
SELECT the_geom FROM routing r JOIN 
           (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 routing WHERE status='::text||'''yes'''::text,
           426515,
          404982, true, true)) AS  x(e)
     ON x.e = r.gid;
Then we have
We go through the street "Avenue du Père Soulas". Suppose now that the street is not available.
We do
 UPDATE routing SET status='no' WHERE name='Avenue du Père Soulas';
We have