[GIS] Doubts about how pgRouting topology is built and how flexible it is

pgroutingtopology

I'm learning pgRouting, to validate if it can be used in a project. I have several doubts. Mostly related with how could I "fill the gap" between the "bricks" it provides and the real world applications based on routing I normally use. I will summarize the questions in a few ones. Sorry if they're too silly. I have little experience with topology.

EDIT: PolyGeo wisely suggests that I focus this question in one important topic, and leave the rest for different questions. I will reformulate my doubts to create a general question important for me. The already existent responses will still make sense. Anyway, I keep the original questions at the end.

My general doubt is about the topology creation process and how flexible is.

If my data consists in a bunch of lines, and I tell pgRouting to create a topology from that, is a node created at any intersection, apart from the nodes created at the beginning and end of any line? And what about intersections at different level? (for example: a bridge above a motorway: http://goo.gl/pVeE4j, that's not really an intersection) How are these handled? –> EDIT: I've already found this http://goo.gl/ojGmuH. I think it is a response. I need to investigate it.

Once the topology has been built, what do I do if I need new nodes for a query? Example: I want the shortest path from any arbitrary point in my route to another arbitrary point, not just from one existent node to another one (example: the Google Maps feature "give me directions from my current location to this marker I've just put in the map")

Regarding the topology, my last doubt is if the PostGIS topology and the pgRouting topology are related in any sense.

These are the original 6 questions I made:

About creating the topology: you feed the engine with a few lines, as the base of the topology. I guess a new vertex is created every time two of these lines intersect, apart from the vertex created at the beginning and the end of each line. Am I right?
When two lines intersect at different level, how is it handled? (if it's really handled). For example, a bridge above a motorway. Something like this: http://goo.gl/pVeE4j
I've seen several examples using really simple data: a few lines forming a simple network. I've also seen examples using OSM data imported with osm2po or osm2pgrouting. OSM data is great, and complex. But what if I want an intermediate point? Not as simple as a single table with a few dozens of prepared linestrings and not as complex as OSM datasets. Sometimes, we need to work with data provided by public institutions (old digitized maps, cadastre datasets, etc). Is there any way to integrate data from different sources? Any method to ease the compliance of my data with the minimum requisites for pgRouting to create a topology based on it? So, to go from chaos (different sources, different methods to obtain the data…) to a polished set of PostgreSQL tables, ready to work with?
The minimum path algorithms always need two nodes (from A to B). No problem if those points are actual vertices of my topology. But, what if I want to calculate a path from this exact point where I am right now to another arbitrary point? Like the Google Maps calculation: "give me the path from my current location to X". Creating new vertices every time an arbitrary path is requested and rebuilding the topology sounds like nonsense for me.
About the turn restrictions, I find the underlying logic difficult to understand. What do the parameters of restriction SQL mean? In the example, a restrictions table is created. Why those fields?
Do pgRouting topology and PostGIS topology know each other? If not, are they planning to converge/collaborate in any point?

So, summarizing, in my opinion pgRouting looks like a really great framework, but I think there are a lot of things to learn, understand and build in order to construct a routing engine using it.

Best Answer

I'm trying to give a brief reply to your questions:

The topology function assigns a source and a vertex ID for each road segment. To do this a vertex table is created, which contains all source and target IDs. You can use this vertex table, but it's not required.
If there is no shared node at an intersection, then the topology script will not connect these 2 roads.
You can use any network data you want.
You need to handle intermediate points yourself. PostGIS provides various functions to find nearest roads and split them, see ST_LineLocatePoint or ST_LineSubstring. pgRouting is a set of basic functions, which add routing or network analysis functionality.
Turn restrictions are complex. You should first start with something simple.
PostGIS and pgRouting topology functions are different. pgRouting cares about a valid "network".

You probably best start with the pgRouting workshop.

Related Solutions

[GIS] What does ‘building topology’ mean for pgRouting

Routing is a graph problem, not a pure geometry problem per se (I am using a bit loose terms here for the sake of clarity). What that means is that you have to grab the original geometries from your features - potentially from various different spatial tables (aka Feature Classes in ESRI speak) and build a graph representation (aka Network Topology ) that is suitable for traditional routing algorithms like A*, traditional Dijkstra, etc. You have to think that, depending on the problem you are solving, you may choose different weights assigned to traversing the edges (is cost traversal based on geometric length, or some attribute like speed limit?), put restrictions on turns around edges (is a left or u-turn allowed?), assign different classes to the edges (residential, freeway, toll bridge, whatever), etc etc. Heck, you even have a choice to do node-to-node routing or edge-to-edge which gives different results.

The process of extracting the necessary information from your spatial tables is referred to as "building network topology" and the tables are where they are stored on the db. With the information I gave you, hopefully now the become obvious :)

pgRouting – Creating Network Topology with Grade Separation

When loading data to PostGIS, there's no topology information associated with them. To create a useful topology the data needs to be “noded”. This means that where two or more roads form an intersection there it needs to be a node at the intersection and all the road segments need to be broken at the intersection, assuming that you can navigate from any of these segments to any other segment via that intersection. (Extract from pgrouting 2.0 documentation).

In your case, it seems that some nodes are common between bridges over roads and underneath roads. I don't know if those nodes were given in the ITN data or if you created them.

So you have to pass a clean network to pgrouting :

Let's say you have a bridge (A-B-C) and a road underneath (D-B-E) :

Network example

The table you pass to pgRouting is like :

source | target | geometry           | cost
   A   |   B    | LINESTRING (A,B)   | cost_ab
   B   |   C    | LINESTRING (B,C)   | cost_bc
   D   |   B    | LINESTRING (D,B)   | cost_db
   B   |   E    | LINESTRING (B,E)   | cost_be

You have to modify it to

source |target | geometry            | cost
   A   |   C   | LINESTRING (A,B,C)  | cost_ab+cost_bc
   D   |   E   | LINESTRING (D,B,E)  | cost_db+cost_be

You can create a temporary table and use some case statements to fill columns/filter your grade and generate the modified network.

Note that pgRouting 2.0 documentation gives an example (but with new methods) : pgRouting 2.0 Routing topology

Best Answer

Related Solutions

[GIS] What does ‘building topology’ mean for pgRouting

pgRouting – Creating Network Topology with Grade Separation

Related Question