Changeset 75
- Timestamp:
- 02/04/2012 01:51:17 (13 years ago)
- Location:
- trunk/workshop-routing-foss4g/chapters
- Files:
-
- 2 edited
-
introduction.rst (modified) (1 diff)
-
shortest_path.rst (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/workshop-routing-foss4g/chapters/introduction.rst
r64 r75 5 5 .. rubric:: Résumé 6 6 7 `pgRouting <http://www.pgrouting.org>`_ ajoute les fonctionalité de routage à `PostGIS <http://www.postgis.org>`_. Ces travaux pratiques d'introduction va vous présenter comment. Il présente un exemple pratique de comment utiliser pgRouting avec les données du réseau routier d'`OpenStreetMap <http://www.openstreetmap.org>`_. Il explique les étapes permettant la préparation des données, effectuer des requêtes de routage, l'assignation des coûts et l'utilisation de `GeoExt <http://www.geoext.org>`_ pour présenter les chamins depuis une application de web-mapping.7 `pgRouting <http://www.pgrouting.org>`_ ajoute les fonctionalités de routage à `PostGIS <http://www.postgis.org>`_. Ces travaux pratiques d'introduction va vous présenter comment. Il présente un exemple pratique de comment utiliser pgRouting avec les données du réseau routier d'`OpenStreetMap <http://www.openstreetmap.org>`_. Il explique les étapes permettant la préparation des données, effectuer des requêtes de routage, l'assignation des coûts et l'utilisation de `GeoExt <http://www.geoext.org>`_ pour présenter les chamins depuis une application de web-mapping. 8 8 9 9 La navigration dans un réseau de routes nécessite des algorithmes de routage complex qui supportent la restriction des virages utilisables et même des attributs dépendant du temps. pgRouting est une librairie OpenSource qui peut être étendue qui fournit une grande variété d'outils pour la recherche de plus courts chemins comme une extension de PortgreSQL et de PostGIS. Ces travaux pratiques vont expliquer la recherche de plus courts chemin avec pgRouting dans un réseau routier réel et comment la structure des données est importante pour obtenir des résultats plus rapidement. Vous apprendrez aussi les difficultés et le limitations de pgRouting dans le cadre d'application SIG. -
trunk/workshop-routing-foss4g/chapters/shortest_path.rst
r73 r75 77 77 78 78 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 79 Wrapper 80 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 81 82 .. rubric:: Wrapper WITHOUT bounding box83 84 Wrapper functions extend the core functions with transformations, bounding box limitations, etc.. Wrappers can change the format and ordering of the result. They often set default function parameters and make the usage of pgRouting moresimple.79 Enveloppe 80 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 81 82 .. rubric:: Enveloppe SANS limite d'étendue 83 84 les 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. 85 85 86 86 .. code-block:: sql … … 103 103 .. note:: 104 104 105 I t's possible to show the route in QGIS. It works for shortest path queries that return a geometry column.106 107 * Cr eate a database connection and add the "ways" table as a background layer.108 * A dd another layer of the "ways" table but select ``Build query`` before adding it.109 * Type ``"gid" IN ( SELECT gid FROM dijkstra_sp('ways',5700,6733))`` into the **SQL where clause** field.110 111 ``SQL query`` can be also selected from the layer context menu.112 113 114 .. rubric:: Wrapper WITH bounding box115 116 You can limit your search area by adding a bounding box. This will improve performance especially for large networks.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. 106 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**. 110 111 ``SQL query`` peut aussi être sélectionné depuis le menu contextuel de la couche. 112 113 114 .. rubric:: Enveloppe AVEC une étendue limite 115 116 Vous 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. 117 117 118 118 .. code-block:: sql … … 134 134 .. note:: 135 135 136 The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a ``0.1`` degree buffer for example.137 138 139 ------------------------------------------------------------------------------------------------------------- 140 A- Star141 ------------------------------------------------------------------------------------------------------------- 142 143 A-Star algorithm is another well-known routing algorithm. It adds geographical information to source and target of each network link. This enables the shortest path search to prefer links which are closer to the target of the search.144 145 .. rubric:: Pr erequisites146 147 For A-Star you need to prepare your network table and add latitute/longitude columns (``x1``, ``y1`` and ``x2``, ``y2``) and calculate their values.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. 137 138 139 ------------------------------------------------------------------------------------------------------------- 140 A-Ãtoile 141 ------------------------------------------------------------------------------------------------------------- 142 143 L'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. 144 145 .. rubric:: Prérequis 146 147 Pour 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. 148 148 149 149 .. code-block:: sql … … 168 168 .. Note:: 169 169 170 ``endpoint()`` function fails for some versions of PostgreSQL (ie. 8.2.5, 8.1.9). A workaround for that problem is using the ``PointN()`` function instead:171 172 173 .. rubric:: F unction with parameters174 175 Shortest Path A-Star function is very similar to the Dijkstra function, though it prefers links that are close to the target of the search. The heuristics of this search are predefined, so you need to recompile pgRouting if you want to make changes to the heuristic function itself.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: 171 172 173 .. rubric:: Fonction avec paramÚtres 174 175 La 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. 176 176 177 177 .. code-block:: sql … … 184 184 185 185 .. note:: 186 * Source and target IDs are vertexIDs.187 * Undirected graphs ("directed false") ignore "has_reverse_cost" setting188 189 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 190 Core 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" 188 189 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 190 Bases 191 191 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 192 192 … … 215 215 216 216 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 217 Wrapper 218 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 219 220 .. rubric:: Wrapper function WITH bounding box 221 222 Wrapper functions extend the core functions with transformations, bounding box limitations, etc.. 217 Enveloppe 218 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 219 220 .. rubric:: Fonction envelopper AVEC cadre limite 223 221 224 222 .. code-block:: sql … … 241 239 .. note:: 242 240 243 * There is currently no wrapper function for A-Star without bounding box, since bounding boxes are very useful to increase performance. If you don't need a bounding box Dijkstra will be enough anyway. 244 * The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example. 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. 245 242 246 243 … … 249 246 ------------------------------------------------------------------------------------------------------------- 250 247 251 Shooting-Star algorithm is the latest of pgRouting shortest path algorithms. Its speciality is that it routes from link to link, not from vertex to vertex as Dijkstra and A-Star algorithms do. This makes it possible to define relations between links for example, and it solves some other vertex-based algorithm issues like "parallel links", which have same source and target but different costs.252 253 .. rubric:: Pr erequisites254 255 For Shooting-Star you need to prepare your network table and add the ``rule`` and ``to_cost`` column. Like A-Star this algorithm also has a heuristic function,which prefers links closer to the target of the search.256 257 .. code-block:: sql 258 259 -- A dd rule and to_cost column248 L'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. 249 250 .. rubric:: Prérequis 251 252 Pour 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. 253 254 .. code-block:: sql 255 256 -- Ajouter les colonnes rule et to_cost 260 257 ALTER TABLE ways ADD COLUMN to_cost double precision; 261 258 ALTER TABLE ways ADD COLUMN rule text; 262 259 263 .. rubric:: Shooting-Star algorithm introduces two new attributes260 .. rubric:: L'algorithme Shooting-Star introduit deux nouveaux attributs 264 261 265 262 .. list-table:: 266 263 :widths: 10 90 267 264 268 * - **Attribut e**269 - **D escription**265 * - **Attribut** 266 - **Déscription** 270 267 * - rule 271 - a string with a comma separated list of edge IDs, which describes a rule for turning restriction (if you came along these edges, you can pass through the current one only with the cost stated in to_cost column)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) 272 269 * - to_cost 273 - a cost of a restricted passage (can be very high in a case of turn restriction or comparable with an edge cost in a case of traffic light)274 275 .. rubric:: F unction with parameters270 - 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) 271 272 .. rubric:: Fonction avec paramÚtres 276 273 277 274 .. code-block:: sql … … 285 282 .. note:: 286 283 287 * Source and target IDs are link IDs.288 * Undirected graphs ("directed false") ignores "has_reverse_cost" setting289 290 To describe turn restrictions: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" 286 287 Pour décrire une interdiction de tourner : 291 288 292 289 .. code-block:: sql … … 296 293 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14 297 294 298 ... means that the cost of going from edge 14 to edge 12 is 1000, and295 ... signifie que le coût pour aller du tronçon 14 au tronçon 12 est de 1000, et 299 296 300 297 .. code-block:: sql … … 304 301 12 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 14, 4 305 302 306 ... means that the cost of going from edge 14 to edge 12 through edge 4 is1000.307 308 If you need multiple restrictions for a given edge then you have to add multiple records for that edge each with a separate restriction.303 ... signifie que le coût pour aller du tronçon 14 au tronçon 12 via le tronçon 4 est de 1000. 304 305 Si 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. 309 306 310 307 .. code-block:: sql … … 315 312 11 | 3 | 10 | 2 | 4 | 3 | 4 | 5 | 1000 | 12 316 313 317 ... 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..318 319 320 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 321 Core 322 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 323 324 An example of a Shooting Star query may look like this: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... 315 316 317 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 318 Bases 319 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 320 321 Un exemple d'utilisation de l'algorithme Shooting Star : 325 322 326 323 .. code-block:: sql … … 349 346 .. warning:: 350 347 351 Shooting Star algorithm calculates a path from edge to edge (not from vertex to vertex). Column vertex_id contains start vertex of an edge from column edge_id. 352 353 354 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 355 Wrapper 356 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 357 358 Wrapper functions extend the core functions with transformations, bounding box limitations, etc.. 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. 349 350 351 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 352 Envelopper 353 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 359 354 360 355 .. code-block:: sql … … 376 371 .. note:: 377 372 378 There is currently no wrapper function for Shooting-Star without bounding box, since bounding boxes are very useful to increase performance. 379 380 .. warning:: 381 382 The projection of OSM data is "degree", so we set a bounding box containing start and end vertex plus a 0.1 degree buffer for example. 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 TracChangeset
for help on using the changeset viewer.
