OverviewFirst of all I would like to say sorry for not blogging in the last month.
I had to do a lot of not gsoc stuff, but this is not a good excuse... so just sorry and let's start with the report! :)
Interface with GraphHopper now supports viapointsI created a patch for supporting viapoints in maps. The patch is now in review. You can have more info here.
Dependency fixedI have been a bit stucked in Maps because I was waiting for two jobs to get done: first implementation of sidebar and new markers.
In these weeks Mattias and Damiàn made a great work and both jobs are now in review (more info on bugzilla here and here and on Damiàn blog).
|New markers by Damiàn Nohales||New sidebar by Mattias Bengtsson|
GraphHopper best approach for alternative paths issueIn my last report I said I was studying the best algorithm for solving alternative paths problem. You can have a good overview of my research here and below a short resume:
- k-shortest path: not feasible
- pareto optimality: not feasible
- penalty approach: good option for simple Dijkstra-like algorithms. It adds an overhead to the computation (for updating penalties). So if there will be time, it will be implemented just for this category of algorithms.
- plateau method: best option for bidirection Dijkstra-like algorithms. This algo should not create a lot of problems when activating Contraction Hierarchies but I'll know more about this later after some tests.
Together with Peter Karich, I decided to start working on the plateau method.
GraphHopper: implementing alternatives pathsI wrote a first implementation of plateau method and two small unit tests. The algo was working fine in these tests, so I decide to test in a real world environment.... and I had some troubles.
After a bit, I realize that I have to work on the goodness function.
In detail, I should consider two more conditions for selecting a good alternative: similarity and optimality rate.
|Red alternative is good|
Yellow one not too much
What's next? (Gnome maps)
- Fix the sidebar for working with viapoints.
- Add the feature to add, remove and sort viapoints directly from the sidebar.
- New turning point markers on the map.
What's next? (GraphHopper)
- Change alternatives goodness function.
- Optimize code (Peter gave to me a good hint).
- Test activating Contraction Hierarchies (crossing fingers mode ON XD ).