Hi

I need a fast algorithm and input data to it to calculate for user what cities and villages are on the track from one city to another.

I realized that this is not simple especialy if speed of the calculation is crucial. I was thinking about fetching OSM data for one country and transform it to the graph with nodes and edges. Let's name this graph IG - Input Graph.

Now I would like to proces this IG to OG (output graph) that contains only cities/villages nodes and edges that are calculated based on IG roads. In simple words I need a graph that let me calculate in fast way the answer to question: If I start from city nr 3 and want to drive to city nr 7 what city/village will I be passing? The answers are:

  1. You will be passing cities/villages: 5, 6, 7
  2. You will be passing cities/villages: 2, 4, 6, 7
  3. You will be passing cities/villages: 5, 4, 6, 7

The city / village nodes are retrieved from OSM file. The Output Graph edges should have weight calculated based on the Input Graph edges. The measure of the weight is in general distance in meters from one node to the next.

My question is. Does somebody was working on something like this. I don't want to duplicate somebodys work. Ofcourse everybody are welcome to help me do it in right way.

Idea

asked 01 Apr '12, 10:35

Kapuch's gravatar image

Kapuch
11112
accept rate: 0%


My advice: contact the developers of the many Openstreetmap routing services.

( http://wiki.openstreetmap.org/wiki/Routing )

Within their software developments they definitely will have dealt with the kind of graph decisions that you are thinkng about here.

H.

permanent link

answered 01 Apr '12, 16:56

Herve5's gravatar image

Herve5
5681911
accept rate: 13%

edited 01 Apr '12, 16:56

... or leave a message to the Routing mailinglist that can be found here:

http://wiki.openstreetmap.org/wiki/Mailing_lists

(01 Apr '12, 18:57) stephan75

Thank You for advice. I just post them an email.

(01 Apr '12, 19:54) Kapuch
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:

×532
×249
×154
×16
×8

question asked: 01 Apr '12, 10:35

question was seen: 4,567 times

last updated: 01 Apr '12, 19:54

powered by OSQA