From my understanding of the current map matching implementation it uses node-based traversal during path finding. There is a comment in the source:
// TODO initialization of start values for the algorithm is currently done explicitely via node IDs! // To fix this use instead: traversalMode.createTraversalId(iter, false); // this.traversalMode = graph.getExtension() instanceof TurnCostExtension // ? TraversalMode.EDGE_BASED_2DIR : TraversalMode.NODE_BASED;
My understanding is that if this change was made it would only support bi-directional edge based traversal. For u-turn support the traversal mode would have to be EDGE_BASED_2DIR_UTURN. But I am dubious of making such a change because of the ominous comment about this traversal mode:
Not recommended as it leads to strange routes that outsmart the turn costs.
To achieve map matching of trails with u-turns I am thinking of making the GPX sub-list extraction in doWork(List<GPXEntry> gpxList) split on u-turns also.
What are your thoughts on supporting map matching for trails with u-turns?
Following U-turns in a GPX track would be also supported if you just enable edge base traversal, no need for the _UTURN thing. But moving map matching from node based to edge based is currently not a simple thing and also our algorithm is not really suited for matching u-turns. Of course, we have ideas and working on an improved algorithm which could then be used for this as well. Also we always welcome improvements from our community
Thanks for the fast reply. I am interested that you are “working on an improved algorithm which could then be used for this as well”. If you don’t mind me asking, can you elaborate a bit more on this? Also, in the meantime, do you think my idea of detecting u-turns and splitting on them would work?
If you don’t mind me asking, can you elaborate a bit more on this?
Currently we use a rather simple and very fast heuristic but we want to improve regarding quality and therefor play with established map matching algorithms.
Yes, that is roughly how we are currently doing it for circles.
