Hi,

I imported a large area from "planet.osm" file into a postgresql database using Osmosis.
Now, I want to implement a routing algorithm based on two locations entered by a user.

Is not really clear for me where in my database structure I should search for this two points. For example if a user enters as starting point "London, UK" and as end point "Paris, France" where should I search for this two locations so I can start implementing my routing algorithm.

My database structure as created by Osmosis contains the following tables: nodes, relation_members, relations, users, way_nodes and ways.

I need some clear information on how the database is structured because I can not figure out where to start building my graph so I can implement A* algorithm. This routing algorithm is a part of my thesis so I can not use an allready built service.

Thank you,
Radu-Stefan

asked 13 Jun '13, 08:50

raduzugravu's gravatar image

raduzugravu
316610
accept rate: 0%


The Snapshot database structure populated by Osmosis is very unsuitable for routing, at least in part because geometry for ways might not exist or be unsuitable and there is no geometry for relations. You really need to transform the data into a more suitable format. This data is really for people who want a pretty much exact copy of current data from the planet database for an area.

I would start by reading the wiki.

permanent link

answered 13 Jun '13, 10:18

SK53's gravatar image

SK53 ♦
22.9k46234360
accept rate: 20%

But how can I retrive my start and end locations from the list of nodes? Right now I do a search through the hsotore tags and compare name keys with the values introducted by the user. This is really slow. Is there a way to make a search through hstore keys faster? My database implementation uses Postgis functionality. My problem is in retrieving the start and end locations. Once I find my start and end points routing should be done easy using Postgis functions.

(13 Jun '13, 11:45) raduzugravu

Then you probably need a nameserver like Nominatim, but I'm sceptical that you can use a raw snapshot schema. It's basically a Postgres schema not a PostGIS one (really only the nodes have location).

(13 Jun '13, 12:14) SK53 ♦

OpenStreetMap data can be converted into many database structures, for many different purposes. You should decide the database structure that you require first, and then import the data into your chosen structure.

By picking a schema without checking that it's suitable, then you're almost guaranteed to fail. It's like cementing bricks to one another, and then designing the house afterwards.

Of course, if you don't want to design the database structure, then you can use one that's already designed for routing, and already has an importer, like osm2pgrouting - but that might not be the point of the exercise.

permanent link

answered 13 Jun '13, 14:15

Andy%20Allan's gravatar image

Andy Allan
11.8k23121144
accept rate: 30%

There is no good way to do performant geocoding with a pgsnapshot database. If you do suitable partial indexes on (lower(tags -> 'name')) (lower(tags -> 'alt_name')) and similar tags you might be able to get some results, but writing a geocoder is a thesis in itself.

pgsnapshot is written to preserve full OSM data, which is not what you want for routing.

In any case, the three main tables are nodes, ways and relations. They contain the nodes, ways and relations imported into the DB with one row per object. Most of the columns for these are self-evident from the names, but tags is a hstore with the object tags.

The table-specific columns are

  • in nodes geom is the node location stored as a PostGIS POINT
  • in ways nodes is a bigint[] with a list of node IDs. Note that using this to find which ways are "parents" of a node is slow operation, even with a GIN index
  • The optional bbox and linestring columns on ways have the way bbox or linestring respectively. These probably won't help you with forming the graph as linestrings have no notion of connectivity.

The way_nodes and relation_members store membership in ways and relations and allow you to find the "parent" ways or relations for a node or other object.

I suggest you decide if you're trying to write a geocoder or trying to write a routing engine. In either case, pgsnapshot is probably not the place to start.

permanent link

answered 14 Jun '13, 10:13

pnorman's gravatar image

pnorman
2.4k52140
accept rate: 19%

Hi,

Thank you for your answer. What I am trying to write is a routing engine. I need to geocode start and end locations in order to know coordinates for locations introduced by the user. To obtain this coordinates I could make a request to nominatim.

Theoretically it should be possible to write an A* algorithm on this set of data after I get my start and end coordinates, right?

(14 Jun '13, 11:09) raduzugravu
1

yes but whether it will complete before heat-death of the universe is another matter

(14 Jun '13, 11:22) SK53 ♦

Time is not that important. Of course it shouldn't take days to complete. I think somewhere under 1-2 minutes for locations not too far away one from another should be ok.

I have one more question. In order to write my routing algorithm my start and end nodes should be part of a way, right?

(14 Jun '13, 11:32) raduzugravu

I mean if someone introduces as starting node a cultural objective (for example the name of a museum) which is not part of a way then I have to find the closest node to that starting node which is part of a way. That can be done using postgis geometry functions?

(16 Jun '13, 07:28) raduzugravu
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×255
×219

question asked: 13 Jun '13, 08:50

question was seen: 8,934 times

last updated: 16 Jun '13, 07:28

powered by OSQA