Bienvenue sur PostGIS.fr

Bienvenue sur PostGIS.fr , le site de la communauté des utilisateurs francophones de PostGIS.

PostGIS ajoute le support d'objets géographique à la base de données PostgreSQL. En effet, PostGIS "spatialise" le serverur PostgreSQL, ce qui permet de l'utiliser comme une base de données SIG.

Maintenu à jour, en fonction de nos disponibilités et des diverses sorties des outils que nous testons, nous vous proposons l'ensemble de nos travaux publiés en langue française.

source: trunk/workshop-routing-foss4g/chapters/shortest_path.rst @ 75

Revision 75, 15.7 KB checked in by djay, 10 years ago (diff)

Traduction du chapitre 6

RevLine 
[63]1==============================================================================================================
[73]2Plus courts chemins
[63]3==============================================================================================================
4
[73]5pgRouting été initialement appelé *pgDijkstra*, puisque il implémentait seulement la recherche de plus court chemin à l'aide de l'agorithme de *Dijkstra*. Plus tard, d'uatres fonctions se sont ajoutées et la bibliotÚque fut renommée.
[63]6
7.. image:: images/route.png
8        :width: 250pt
9        :align: center
10       
[73]11Ce chapitre explique les trois différents algorithmes et les attributs nécessaires.
[63]12
13
14.. note::
15
[73]16        Si vous lancez l'outils :doc:`osm2pgrouting <osm2pgrouting>` pour importer des données *OpenStreetMap*, la table des chemins (``ways``) contient déjà tout les attributs nécessaires pour utiliser les fonctions de recherche de plus court chemins. Au contraire, la table ``ways`` de la base de données ``pgrouting-workshop`` du :doc:`chapitre précédent <topology>` manque d'un certain nombre d'attributs, qui sont présentés dans ce chapitre dans les **Prérequis**.
[63]17
18
19-------------------------------------------------------------------------------------------------------------
20Dijkstra
21-------------------------------------------------------------------------------------------------------------
22
[73]23L'algorithme de Dijkstraa été la premiÚre implémentation disponible dans pgRouting. Il ne nécessite pas d'autre attributs que les champs ``source`` et ``target``, les attributs ``id`` et ``cost``. Il peut être utilisé sur des graphes orientés ou non. Vous pouvez spécifier que votre réseau à un coût de ``parcours inverse`` (``reverse cost``) ou non.
[63]24
[73]25.. rubric:: Prérequis
[63]26
[73]27Pour être en mesure d'utiliser un coût de parcuors invers, vous devez ajouter une colonne de coût. Nous pouvons affecter la longuer au coût de parcours inverse.
[63]28
29.. code-block:: sql
30
31        ALTER TABLE ways ADD COLUMN reverse_cost double precision;
32        UPDATE ways SET reverse_cost = length;
33
[73]34.. rubric:: Fonction avec paramÚtres
[63]35
36.. code-block:: sql
37
38        shortest_path( sql text,
39                           source_id integer,
40                           target_id integer,
41                           directed boolean,
42                           has_reverse_cost boolean )
43
44.. note::
45
[73]46        * Les identifiant pour source et target sont les identifiant des noeuds.
47        * Graphes non-orientés ("directed=false") implique que le paramÚtre "has_reverse_cost" est ignoré
[63]48
49
50^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[73]51Bases
[63]52^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
53
[73]54Chaque algorithme a une fonction de *base*.
[63]55
56.. code-block:: sql
57
58        SELECT * FROM shortest_path('
59                        SELECT gid as id,
60                                 source::integer,
61                                 target::integer,
62                                 length::double precision as cost
63                                FROM ways',
64                        5700, 6733, false, false);
65
66.. code-block:: sql
67
68         vertex_id | edge_id |        cost         
69        -----------+---------+---------------------
70              5700 |    6585 |   0.175725539559539
71              5701 |   18947 |   0.178145491343884
72              2633 |   18948 |   0.177501253416424
73               ... |     ... |                 ...
74              6733 |      -1 |                   0
75         (38 rows)
76
77
78^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[75]79Enveloppe
[63]80^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
81
[75]82.. rubric:: Enveloppe SANS limite d'étendue
[63]83
[75]84les fonctions enveloppes sont des fonctions qui étendent les fonctions de bases en y ajoutant des transformations, ajoutant des limites de l'étendue géograhpique de la recherhe, etc.. Les enveloppes peuvent changer le format et l'ordre des résultats. Il affectent aussi automatiquement certains paramÚtre et rend l'utilisation de pgRouting encore plsu simple.
[63]85
86.. code-block:: sql
87
88        SELECT gid, AsText(the_geom) AS the_geom
89                FROM dijkstra_sp('ways', 5700, 6733);
90               
91.. code-block:: sql
92               
93          gid   |                              the_geom     
94        --------+---------------------------------------------------------------
95           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
96           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
97           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
98            ... | ...
99          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
100        (37 rows)
101
102
103.. note::
104
[75]105        Il est possible de visualiser le chemin dans QGIS. Cela fonctionne pour la requête de recherche du plus court chemin qui retourne une colonne géométrique.
[63]106
[75]107        * Créer la connexion à la base de données et ajoutez la table route comme couche de fond.
108        * Ajoutez une autre couche de la table "ways" mais selectionnez l'option ``Build query`` avant de l'ajouter.
109        * Saissez ``"gid"  IN ( SELECT gid FROM dijkstra_sp('ways',5700,6733))`` dans le champ **SQL where clause**.
[63]110       
[75]111        ``SQL query`` peut aussi être sélectionné depuis le menu contextuel de la couche.
[63]112
113       
[75]114.. rubric:: Enveloppe AVEC une étendue limite
[63]115
[75]116Vous pouvez limiter votre recherche à une zone précise en ajoutant un cadre limite. Cela améliorera les performances tout spécialement pour les réseaux volumineux.
[63]117
118.. code-block:: sql
119
120        SELECT gid, AsText(the_geom) AS the_geom
121                FROM dijkstra_sp_delta('ways', 5700, 6733, 0.1);
122               
123.. code-block:: sql
124
125          gid   |                              the_geom     
126        --------+---------------------------------------------------------------
127           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
128           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
129           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
130            ... | ...
131          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
132        (37 rows)
133
134.. note:: 
135
[75]136        La projection des données OSM est en "degrés", donc nous définirons un cadre limite contenant le point de départ et celui d'arrivée plus une zone tampon de ``0.1`` degrés par exemple.
[63]137
138
139-------------------------------------------------------------------------------------------------------------
[75]140A-Étoile
[63]141-------------------------------------------------------------------------------------------------------------
142
[75]143L'algortihme A-Étoile est un autre algrithme bien connu. Il ajoute l'information de la position géographique du début et la fin de chaque tronçon. Cela permet une recherche privilégiant les tronçons proches du point d'arrivée de la recherche.
[63]144
[75]145.. rubric:: Prérequis
[63]146
[75]147Pour A-* vous avez besoin de préparer votre table de réseau et d'y ajouter les colonnes latitute/longitude (``x1``, ``y1`` et ``x2``, ``y2``) et de calculer leur valeurs.
[63]148
149.. code-block:: sql
150
151        ALTER TABLE ways ADD COLUMN x1 double precision;
152        ALTER TABLE ways ADD COLUMN y1 double precision;
153        ALTER TABLE ways ADD COLUMN x2 double precision;
154        ALTER TABLE ways ADD COLUMN y2 double precision;
155       
156        UPDATE ways SET x1 = x(ST_startpoint(the_geom));
157        UPDATE ways SET y1 = y(ST_startpoint(the_geom));
158       
159        UPDATE ways SET x2 = x(ST_endpoint(the_geom));
160        UPDATE ways SET y2 = y(ST_endpoint(the_geom));
161       
162        UPDATE ways SET x1 = x(ST_PointN(the_geom, 1));
163        UPDATE ways SET y1 = y(ST_PointN(the_geom, 1));
164       
165        UPDATE ways SET x2 = x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
166        UPDATE ways SET y2 = y(ST_PointN(the_geom, ST_NumPoints(the_geom)));
167
168.. Note:: 
169
[75]170        La fonction ``endpoint()`` ne fonctionne pas avec certaines versions de PostgresQL (par exemple les version 8.2.5 et 8.1.9). Un moyen de résoudre ce problÚme consiste à utiliser la fonction ``PointN()`` Ã  la place:
[63]171
172
[75]173.. rubric:: Fonction avec paramÚtres
[63]174
[75]175La fonction de recherche de plus court chemin A-* est trÚs semblable à la fonction Dijkstra, bien qu'elle préfÚre les tronçons qui sont plus proche du point d'arrivée de la recherche. Les heuristiques de cette recherche sont prédéfinis, donc vous aurez besoin de recompiler pgRouting si vous souhaitez modifier ces heuristiques.
[63]176
177.. code-block:: sql
178
179        shortest_path_astar( sql text,
180                           source_id integer,
181                           target_id integer,
182                           directed boolean,
183                           has_reverse_cost boolean )
184
185.. note::
[75]186        * Les identifiants source et target sont les identifiant des sommets IDs.
187        * Graphes non-orienté ("directed=false") ne prennent pas en compte le paramÚtre "has_reverse_cost"
[63]188
189^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[75]190Bases
[63]191^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
192
193.. code-block:: sql
194
195        SELECT * FROM shortest_path_astar('
196                        SELECT gid as id,
197                                 source::integer,
198                                 target::integer,
199                                 length::double precision as cost,
200                                 x1, y1, x2, y2
201                                FROM ways',
202                        5700, 6733, false, false);
203               
204.. code-block:: sql
205               
206         vertex_id | edge_id |        cost         
207        -----------+---------+---------------------
208              5700 |    6585 |   0.175725539559539
209              5701 |   18947 |   0.178145491343884
210              2633 |   18948 |   0.177501253416424
211               ... |     ... |                 ...
212              6733 |      -1 |                   0
213         (38 rows)
214
215
216^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[75]217Enveloppe
[63]218^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
219
[75]220.. rubric:: Fonction envelopper AVEC cadre limite
[63]221
222.. code-block:: sql
223
224        SELECT gid, AsText(the_geom) AS the_geom
225                FROM astar_sp_delta('ways', 5700, 6733, 0.1);
226
227.. code-block:: sql
228
229          gid   |                              the_geom     
230        --------+---------------------------------------------------------------
231           5534 | MULTILINESTRING((-104.9993415 39.7423284, ... ,-104.9999815 39.7444843))
232           5535 | MULTILINESTRING((-104.9999815 39.7444843, ... ,-105.0001355 39.7457581))
233           5536 | MULTILINESTRING((-105.0001355 39.7457581,-105.0002133 39.7459024))
234            ... | ...
235          19914 | MULTILINESTRING((-104.9981408 39.7320938,-104.9981194 39.7305074))
236        (37 rows)
237
238       
239.. note::
240
[75]241        * Il n'y a pas actuellement de fonction pour a-* sans cadre limite, étant donnée que le cadre limite permet d'améliorer grandement les performances. Si vous n'avez pas besoin de cadre limite, Dijkstra sera suffisant.
[63]242
243
244-------------------------------------------------------------------------------------------------------------
245Shooting-Star
246-------------------------------------------------------------------------------------------------------------
247
[75]248L'algorithme Shooting-Star est le dernier algorithme de recherche de plus court chemin. Sa spécialité c'est qu'il recherche un parcours d'un tronçon à un autre, pas d'un sommet à un sommet comme les agorithmes de Dijkstra et A-Star le font. Cela rend possible la définition de relations entre les tronçons par exemple, et cela résoud certains problÚmes liés aux recherches d'un sommets à un autre comme les "tronçons parallÚles", qui ont les même sommet de début et de fin mais des coût différents.
[63]249
[75]250.. rubric:: Prérequis
[63]251
[75]252Pour Shooting-Star vous avez besoin de préparer votre table de réseau et d'ajouter les colonnes ``rule`` et ``to_cost``. Come l'algorithme A-* il a aussi un fonction heuristique, qui favorise les tronçons plus proche du point d'arrivée.which prefers links closer to the target of the search.
[63]253
254.. code-block:: sql
255
[75]256        -- Ajouter les colonnes rule et to_cost
[63]257        ALTER TABLE ways ADD COLUMN to_cost double precision;   
258        ALTER TABLE ways ADD COLUMN rule text;
259
[75]260.. rubric:: L'algorithme Shooting-Star introduit deux nouveaux attributs
[63]261
262.. list-table::
263   :widths: 10 90
264
[75]265   * - **Attribut**
266     - **Déscription**
[63]267   * - rule
[75]268     - une chaine de caractÚres contenant une liste d'identifiants de tronçno séparés par une virgule, qui décrivent le sens giratoir (si vous venez de cet tronçon, vous pouvez rejoindre le suivant en ajoutant un coût défini dans la colonne to_cost)
[63]269   * - to_cost
[75]270     - un coût pour passer d'un tronçon à un autre (peut être trÚs élevé s'il est interdit de trouner vers ce tronçon ce qui est comparable au coût de parcours d'un tronçon en cas de feu de signalisation)
[63]271
[75]272.. rubric:: Fonction avec paramÚtres
[63]273
274.. code-block:: sql
275
276        shortest_path_shooting_star( sql text,
277                           source_id integer,
278                           target_id integer,
279                           directed boolean,
280                           has_reverse_cost boolean )
281
282.. note::
283
[75]284        * Identifiant du départ et de l'arrivée sont des identifiants de tronçons.
285        * Graphes non-orientés ("directed=false") ne prennent pas en compte le paramÚtre "has_reverse_cost"
[63]286
[75]287Pour décrire une interdiction de tourner :
[63]288
289.. code-block:: sql
290
291         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
292        -----+--------+--------+------+----+----+----+----+---------+------
293          12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14
294 
[75]295... signifie que le coût pour aller du tronçon 14 au tronçon 12 est de 1000, et
[63]296
297.. code-block:: sql
298
299         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
300        -----+--------+--------+------+----+----+----+----+---------+------
301          12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14, 4
302
[75]303... signifie que le coût pour aller du tronçon 14 au tronçon 12 via le tronçon 4 est de 1000.
[63]304
[75]305Si vous avez besoin de plusieurs restrictions pour une arrête donnée you devez ajouter plusieurs enregistrements pour ce tronçon avec un restriction particuliÚre.
[63]306
307.. code-block:: sql
308
309         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
310        -----+--------+--------+------+----+----+----+----+---------+------
311          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
312          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12
313
[75]314... signifie que le coût pour aller soit du tronçon  4 soit du 12 au 11 est de 1000. Et donc vous devez ordoner vos données par gid lorsque vous chargez vos données dans la fonction de recherche de plus court chemin...
[63]315
316
317^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[75]318Bases
[63]319^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
320
[75]321Un exemple d'utilisation de l'algorithme Shooting Star :
[63]322
323.. code-block:: sql
324
325        SELECT * FROM shortest_path_shooting_star('
326                        SELECT gid as id,
327                                 source::integer,
328                                 target::integer,
329                                 length::double precision as cost,
330                                 x1, y1, x2, y2,
331                                 rule, to_cost
332                                FROM ways',
333                        6585, 8247, false, false);
334
335.. code-block:: sql
336
337         vertex_id | edge_id |        cost
338        -----------+---------+---------------------
339             15007 |    6585 |   0.175725539559539
340             15009 |   18947 |   0.178145491343884
341              9254 |   18948 |   0.177501253416424
342               ... |     ... |   ...
343              1161 |    8247 |   0.051155648874288
344         (37 rows)
345
346.. warning::
347
[75]348        L'lgorithme Shooting Star calcul un chemin d'un tronçon à un autre (pas d'un sommet à un autre). La colonnes vertex_id contienr le point de départ du tronçon de la colonne edge_id.
[63]349
350
351^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[75]352Envelopper
[63]353^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
354
355.. code-block:: sql
356
357        SELECT gid, AsText(the_geom) AS the_geom
358                FROM shootingstar_sp('ways', 6585, 8247, 0.1, 'length', true, true);
359
360.. code-block:: sql
361
362          gid   |                              the_geom     
363        --------+---------------------------------------------------------------
364           6585 | MULTILINESTRING((-104.9975345 39.7193508,-104.9975487 39.7209311))
365          18947 | MULTILINESTRING((-104.9975487 39.7209311,-104.9975509 39.7225332))
366          18948 | MULTILINESTRING((-104.9975509 39.7225332,-104.9975447 39.7241295))
367            ... | ...
368           8247 | MULTILINESTRING((-104.9978555 39.7495627,-104.9982781 39.7498884))
369        (37 rows)
370
371.. note::
372
[75]373        Il n'y a actuellement pas de fonction enveloppe pour Shooting-Star sans cadre limite, puisque le cadre limite améliore grandement les performances.
Note: See TracBrowser for help on using the repository browser.