OpenStreetMap routing - Java Swing Application

Question

I am very new to OSM. I have to build an Java App for my MSc project. In this project, my app need to download raw data from OSM (XML format), parse to display it on my app. After that, I have to deploy routing service on my app. To be honest, I have never done it before so I am very confused now. Do you guys have any ideas or source code that can help me? Could you please help me?

Thank a lot.

Answer 1

You could use a 2d drawing framework like piccolo2d to render the map. And for the routing, you will need to build a graph describing the roads/ways on the maps, how they join and the distances represented. Having chosen a start point and an end point on the map an algorithm such as A star will then help you find the shortest path between the points.

Some more detail:

OSM XML dumps consist (it's more complicated than this: see the official docs for the full detail) of three classes of entities:

• Nodes: representing single points on the map, defined by longitude and latitude. These either represent notable features (a huge variety, but, for example: a shop, an ancient monument, a gate on a path etc) or are part of a way.
• Ways: representing polygons on the map. These are built up of an ordered list of nodes (referenced by id) and can represent linear things such as roads and paths (relevant to your routing problem) but also bounded areas such as field or forest boundaries, the shapes of urban areas, lakes, rivers etc.
• Relations: which I won't address here, but you can find more about these in the official docs.

Each of the above three node types will have additional data associated with them in the form of 'tags' which are key-value (string) pairs specifying the type of entity represented by the node/way. A general list can be found here and a list for routing here. An example drawn from the OSM website representing a small local road (in this case in Germany):

<!-- The nodes representing points along the way -->
<node id="298884269" lat="54.0901746" lon="12.2482632" ... />
<node id="261728686" lat="54.0906309" lon="12.2441924" ... />
...
<node id="298884272" lat="54.0901447" lon="12.2516513" ... />

<!-- A way, built of the points above, with a tag
     declaring it to be an unclassified road -->
<way id="26659127" ...>
    <nd ref="292403538"/>
    <nd ref="298884289"/>
    ...
    <nd ref="261728686"/>
    <tag k="highway" v="unclassified"/>
</way>

Where two ways intersect (e.g. when two roads cross) they will share a node in common at the crossing point.

To filter down to the data required to generate a routing graph, you need to:

• Read the XML for the area of interest, reading at least the nodes and ways.
• Filter out, leaving only the ways you want based on their tags (for instance where k="highway" etc).
• Filter out all nodes but the ones referenced by the remaining relevant ways.

Having isolated only the information you require, you then need to transform from the OSM format to something more suitable for routing. Although the OSM graph as described can be used for routing, it is more efficient to represent the map as a set of nodes for the start and end of each way, and any intersection points between ways and a set of edges representing the path between intersections, along with their lengths.

For example, you might want to transform the following (with intersecting ways a-b, c-d, e-f):

to something more like:

Where only the end nodes and the intersecting nodes remain. In this representation you would have transformed from 3 ways to 8 edges in your routing graph (a-x, c-x, x-e, e-d, x-y, e-y, y-f, y-b) each edge with an associated distance that you calculated by stepping along the nodes in the way, accumulating distance as you go: (e.g. a-x: 200m, e-y: 350m etc). Note that you will be needing to calculate distances between adjacent points in longitude/latitude space for which you can find a formula here.

You could represent this data using your own datastructure or using a third-part graph library such as JGraphT or Jung. From here, routing is (crudely, and assuming for simplicity that the set of nodes you have remaining are adequately fine-grained to represent all required start/end points) a matter of choosing the node representing the start of your journey, the node representing the end and using an algorithm such as A-star (as mentioned above) to calculate the shortest path.

The only catch is that, as far as I can remember, neither of the two libraries I mention have an implementation of A-star. But you can get the correct result by running Dijkstra's shortest path (present in both libraries) at lower speed - and then implement A-star yourself when you're more confident with the concepts.

To make all of this more interesting: instead of using distances you could route on estimated travel time (taking the average speed on the road into account). Or you could modify the distance based on the desirability of the route: e.g. for cycling, down-weight the distance on roads with less traffic in order to select longer but safer routes. Alternatively for hiking, downweight the distance for paths that pass through particularly scenic areas or near a landmark such as an ancient monument or a pub.

Given that there are decent existing routing services for OSM data (e.g from Cloudmade) the main reason you would want to do something like this is in order to use your own custom distance metric...

Answer 2

Alex answer contains the important parts. Especially to reduce the nodes to only the necessary ones!!

If you are interested: I've developed all this stuff in Java in my GraphHopper project, with a very rough Swing UI.

Also Dijkstra, bidirectional dijkstra and astar are implemented. In my tests a star is 30% slower than the dijkstra when forcing it to return no approximation for the route. In the future I'll experiment to allow approximation, but in the mean time you can use the bidirectional dijkstra which is ~50% faster than the normal dijkstra ;) and works like this: