The changelog is here – please read about the necessary changes to your config.properties and/or your Java code. Dowload the new version here. As the documentation has slightly improved we’d like your input here as well.
In the next release we expect bigger changes to come like one top secret 😉 and this exciting work from @devemux86 which continues the work from VTM (OpenScienceMap) and has OpenGL support, allows map rotation, iOS support and more, while keeping compatibility with the Mapsforge file format.
Today we are proud to release our Map Matching API as part of our Directions API. It is a web service based on one of our open source components. You can use it to snap measured GPS points to a digital road network to e.g. clean data or attach certain data to it like turn instructions for biking trials. Read more about map matching at Wikipedia. Our Map Matching API is powered by the Apache licensed hmm-lib from BMW Car IT. ‘hmm’ stands for hidden markov model and indicates the underlying algorithm.
In the following screenshot and in these live examples you can see the Map Matching API in action. The black line represents the original GPS track e.g. received from a smartphone’s GPS. The green line represents the matched result, i.e. the part of the digital network, the black line is matched to:
The Map Matching API works through tunnels, bridges, complex junctions etc. and can utilize different available vehicle profiles. Even more off-the-road examples will snap correctly – depending on the chosen GPS accuracy:
We are confident that it is another helpful routing tool that can be used in production for your web or mobile application. If you find any example where our Map Matching does not work as expected, please let us know in the forum.
Use this link to sign up and try the API for 2 weeks and let us know about your GPS tracks and questions!
On 13. July, Wednesday, from 16:00 to 17:30 we’ll hold the first GraphHopper meeting at Beuth University, Haus Bauwesen, room D 451.
We’ll have the following topics:
Introductory talk about the GraphHopper routing and current development
You are invited to show us your projects based on GraphHopper.
Hands on workshop, where one of the topics will be indoor navigation
All talks should be 20 slides and 20s max for every slide, currently all in German language. See PechaKucha at Wikipedia for more details. To make planning a bit simpler please send a short email to firstname.lastname@example.org
It was a great success having 5 talks of GraphHopper usages and all in all over 4 hours of discussion about the different topics like indoor routing, offline routing, map matching and traffic data integration.
speed up mode (Contraction Hierarchies) can be disabled per request making several flexibility mode features available like alternative routes, round trips, weighting changes, heading settings or even turn restrictions which required a bit of refactoring
The next release 0.8 will focus on more flexibility. Furthermore we would like to use the chance and point to the new work of our map matching component, which is now based on a more precise algorithm and often results in better matchings. It includes work from Michael (MATSim) and Stefan Holder (BMW Car IT). Please try it out here and give us feedback so we can include safely it in the next release or even replace the current algorithm.
As always our GraphHopper Directions API consumes these changes and makes it possible to use alternative routes, round trip calculations, heading indication, shortest path calculation and turn restrictions for the Routing API – read here for more details.
The roads to rome project from Moovel Labs is a nice visualization of the possibilities with GraphHopper. And it is only the start. While investigating and debugging the quality of alternative routes – a new feature from GraphHopper – we stumbled over the necessity to do a very similar visualizations. The visualization of the so called shortest path tree.
What is a shortest path tree?
The shortest path tree (SPT) contains the ‘best ways’ from a root location to any other point in the network. ‘Best way’ can mean for example the ‘shortest’, ‘fastest’ or the ‘most beautiful’ path. The SPT is unique for each root location and transportation mode (e.g. “car”). It is easy to calculate with the Dijkstra algorithm, but it is hard to make it working on large networks such as the European road network. GraphHopper can do this.
We can create similar – but easier to gather – visualizations with our MiniGraphUI, a very simplistic Java Swing UI built just for development a few years ago:
Shortest Path Tree Visualizations
For the visualization we made the line thickness dependent on the number of reachable leafs of the SPT. Let us change the transportantion mode to ‘walking’ instead of car (ferries included but not visualized):
A further step to make the visualization more powerful is to use different colours for different road speeds:
Alternatively, we can colour-encode the distance from the origin Rome:
Of course the flag colours green, white and red must be tried too, click to zoom 🙂
As well as for Germany and France:
All images are via OpenStreetMap (c) contributors.
Many changes would be possible to make the visualizations better looking like with a background map or better colours, but we left this task to the reader, just showing the possibilities here.
When ‘time’ is used as the ‘distance measure’ as in our examples, then these visualizations are the so called isochrone maps – see our Isochrone API for this task.
Create your own shortest path trees
Although the visualizations from Moovel are also done with GraphHopper, within the MiniGraphUI we have direct access to all the underlying graph properties, so that a SPT through full Germany with millions of nodes takes only half a minute to draw on an aged laptop after importing the data which took under 10 minutes for Italy. We can even zoom in and out. For larger areas probably some further speed tuning could be necessary. You can download GraphHopper here then replace the MiniGraphUI with this snippet, specify your OSM file, then edit config.properties and set prepare.chWeighting=no and finally run:
And we could do animations like done in an older post here or compare with old versions of OSM.
What have shortest path trees to do with alternative route finding?
As we mentioned in the intro we have stumbled over the necessity to visualize the SPT to improve the quality of alternative path search. The work for this is currently still under development.
These SPTs can be made from any origin A (‘source SPT’) as well as towards any destination B (‘sink SPT’). And with the help of those two SPTs we can find out ‘overlapping areas’ in the middle. These areas are called plateaus – if we use a bidirectional Dijkstra and extend the normal finish condition to actually make these two Dijkstras really overlap each other. And the larger these plateaus are, the better is the alternative. For example, the best path is also the best alternative with a 100% overlapping path reaching from A to B in the source SPT and backward from B-A in the sink SPT. Apart from the optimal path, these plateaus are often not too large and we need to use other properties to select good alternatives. This can be done for example with a property called ‘sharing’ which calculates the distance an alternative route shares with the best one. After several necessary tweaks with the help of zoomable and debuggable visualizations like this one:
we got surprisingly good alternatives e.g. from Rome to Perugia: