[OSM-dev] Routing over OSM data

Brandon Martin-Anderson badhill at gmail.com
Thu Oct 25 17:56:45 BST 2007


In case I don't get to fixing the python script quickly, here's the basics
of how it works:

The OSM dataset and .osm XML files are in a "topological" format, which
means that way-endings have an associated ID all ways that link at a
particular point have the same ending ID. pgRouting requires this
information to function: it builds a graph where OSM ways are edges and OSM
nodes are vertices.

ESRI Shapefiles are _not_ topological. Each shapefile linestring is simply a
string of cartesian points, with no indication of whether or not two
linestrings that end at the same cartesian point are actually linked. This
is a problem for several reasons. First, linestrings with the same endpoint
can appear linked even though they aren't: they could exist on different
levels, for instance. Second, and probably more pressing, is floating point
rounding errors can result into non-equal linestring endpoints which
actually are meant to be linked. Each shapefile->topology creator copes with
these in various different ways, but the conversion is always imperfect.

Now, there are tools to convert OSM files to Shapefiles, and then Shapefiles
to pgRouting graph tables, but the intermediate step is unnecessary and
bound to introduce errors.

The basics of an OSM->pgSQL format are very simple.

(1) Generate a list of "connected nodes" which join more than one way.
(2) Split every way into several sub-ways, using the connected nodes as
delimiters
(3) Compute the length of each sub-way.
(4) For each sub-way, enter the (from-node, to-node, and length) into a
table into a pgRouting database
(4a) For bonus points, test whether or not the sub-way is maked oneway:true
or oneway:yes and enter the tuple (from-node, to-node, distance,
reverse_distance=0) if the way is one-way

I hacked that out in the python script, but maybe someone with motivation
can run with it, or write something better in C, or something.

-B
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20071025/4bcf2006/attachment.html>


More information about the dev mailing list