3

I'm trying to create a web application that given two points : S(lat,long) and D(lat,long), find the shortest path between them.

My problem is : I do not know how to use A* or other AI algorithm to find the shortest path given the nodes and ways from here : "http://overpass.osm.rambler.ru/cgi/interpreter?" and after that reconstruct the solution, building the path in the map. I'm using Overpass API to get the nodes and ways, using an approach by "rectangle" between the geo points(i know this is bad, because you can have a shortest path the is not in this rectangle, but i do not see a better solution with this API).

Anyone could give me some advice on how to proceed? I can post my code here if you guys want.

Improve this question
5
  • Any reason you are not using one of the many online routers for OSM? And what exactly is your problem about not being able to implement a routing algorithm on top of OSM?
    – scai
    Commented Apr 15, 2015 at 6:45
  • @scai , my problem is that I'm supposed to implement this from scratch. This is a paper from AI course in my university. I'm having trouble about getting the info in the right way. Today I had an idea to get all nodes that are in the intersection between ways and start the A* algorithm, but I can't do this because given a node I do not know how to determine it's exactly next node, i think. And another problem, what nodes I'm going to take given a start and destination points? All the nodes and ways inside a boundary circle that contains both start and destination? I'm so confused.
    – Mixxer
    Commented Apr 15, 2015 at 16:35
  • 2
    For determining previous and next node(s) you have to look at the way. Please take a look at How can I convert an OSM XML file into a graph representation?. Also note that there are already many routers for OSM. Lots of them are Open Source, for example GraphHopper and OSRM.
    – scai
    Commented Apr 15, 2015 at 18:47
  • @scai , i understand, but they do not mention how to get specific nodes and ways given a start point and destination. As I said before, right now I'm getting the rectangle boundary between them(and all nodes and ways inside it), so if two points are in the same line, i will not get any nodes and ways. Do you have a better idea?
    – Mixxer
    Commented Apr 15, 2015 at 19:37
  • You have to process more data than just the rectangle containing the start and end node. The shortest path must not necessary be located inside this rectangle. This is a thing you have to play a little around yourself until finding a good estimate.
    – scai
    Commented Apr 15, 2015 at 20:10
Related questions
0
Routing Engine Using OpenStreetMap Data
1
Find intersections of Ways without Nodes
2
Calculating shortest path on maps (Google Maps, Openstreetmaps, etc)
Load 7 more related questions Show fewer related questions

0

Reset to default