Avoid unnecessary u-turns

[karussell]

Sometimes u-turn artifacts are introduced. A good description with data and screenshots is available in the forum

[kodonnell]

Sure. In computeTransistionProbabilities:

System.out.println("query result: " + to.getQueryResult());
System.out.println("closest node: " + to.getQueryResult().getClosestNode());
System.out.println("closest node is virtual: " + queryGraph.isVirtualNode(to.getQueryResult().getClosestNode()));
System.out.println("closest edge: " + to.getQueryResult().getClosestEdge());
System.out.println("closest edge is virtual: " + queryGraph.isVirtualEdge(to.getQueryResult().getClosestEdge().getEdge()));
System.out.println("closest edge base node: " + to.getQueryResult().getClosestEdge().getBaseNode());
System.out.println("closest edge adj node: " + to.getQueryResult().getClosestEdge().getAdjNode());  

Running the testSmallSeparatedSearchDistance[non-CH] test (i.e. using the test map/graph) the last candidate output is:

query result: 5590-5589  null
closest node: 31448
closest node is virtual: true
closest edge: 6515 5590-5589
closest edge is virtual: false
closest edge base node: 5590
closest edge adj node: 5589

[karussell]

Ah, now I understand the underlying reason: the lookup procedure works as follows:

• call LocationIndexTree.findClosest for every input point and return a QueryResult with a real edge and a real node (one of the closest nodes is picked)
• create QueryGraph and call QueryGraph.lookup with the previously calculated list of QueryResults.
  • Inside this call change the closestEdge if stored in 'wrong' direction - still the edge is 'real', also call queryResult.setWayIndex if it was the 'wrong' direction. (We define a direction here to make handling of multiple points per edge easier).
  • Then call queryGraph.setClosestNode(virtualNode) if the query is not on a junction.
  • Then create the necessary virtual edges and hide the real edge from the edgeIterator but leave the queryResult.closestEdge unchanged ('real') as we do not know which of the two virtual edges to pick

So, long story short: getClosestEdge is currently always real and getClosetNode is virtual or rarely real (if directly on a junction). Either we need to fix this discrepancy of real vs. virtual or better document this I fear.

[kodonnell]

... the underlying reason ...

That fits with what I was seeing (and tried to hack).

Either we need to fix this discrepancy of real vs. virtual or better document this I fear.

@karussell will this have wider implications? E.g. if an inner-link U-turn does actually occur, do we need virtual edges to correctly display it?

Can we get around the issue too? E.g. is there a way to get the virtual edges by using the virtual node? I tried EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(to.getQueryResult().getClosestNode()) but then e.g. iter.getEdge() fails if it's a virtual node.

[karussell]

E.g. if an inner-link U-turn does actually occur, do we need virtual edges to correctly display it?

Yes. But I wouldn't expose them somehow. That is the exact problem we have to solve: return e.g. just the geometry and potentially the more stable OSM nodes, but not our nodes and NEVER the virtual nodes or edges.

Can we get around the issue too?

Your way falls short if there are multiple nodes per edge (not uncommon for map matching)

[stefanholder]

I tried EdgeIterator iter = queryGraph.createEdgeExplorer().setBaseNode(to.getQueryResult().getClosestNode()) but then e.g. iter.getEdge() fails if it's a virtual node.

But this way always seems to work here, or am I missing something?

[kodonnell]

am I missing something?

Nope - turns out I was just the missing .next().

[kodonnell]

I've had a hack with directed candidates, but haven't resolved the original issue. To be frank, I'm just guessing how some of this direction/enforcement stuff works anyway - I think it needs someone with a greater appreciation of GH internals.

@karussell - what's the plan? @stefanholder has proposed a solution (and has a better idea than me of how to implement it!), but you didn't seem happy progressing it. So where to from here?

[stefanholder]

So where to from here?

I can try to do an initial implementation in the next few days, which we can then improve together.

[kodonnell]

I've dumped my stuff here if it's useful. It runs through, but something is clearly wrong.

Things I learned:

• this
• you need to get all candidates first, then look them up, then create time steps from them, hence the layout I have. Initially I tried to e.g. create the virtual edges in createTimeSteps, but that fails as you need to lookup first (and you can only lookup once).
• I think you only need two candidates (e.g. in A---X---B, then A->X and B->X), not four (i.e. A->X and X->A). You just chose incoming/outgoing as appropriate when routing the transitions.

[stefanholder]

@kodonnell's code looks already pretty good.

Some remarks:

• I would rename GPXExtension to MapMatchCandidate and instead of storing QueryResult there, I would store queryDistance, snappedPoint and closestNode directly in MapMatchCandidate. This also makes this code less dependent on Graphhopper internals.
• I would assert here that there are exactly two virtual edges. If this is not always true, it would be interesting to find out why.

Seems that Graphhopper #885 is now the main blocker for this issue.

I think it makes sense that @kodonnell creates a pull request of his code to an experimental graphhopper map-matching branch, e.g. issue_70. This makes it easier to work on this together. @karussell, can you please create such a branch?

[karussell]

Added you both as contributor with write access (you should be able to create a new branch).

@karussell - what's the plan?

The plan is to trust our new contributors ;) ... I'm currently involved in other parts too much, so I can only help to improve documentation or concepts/architecture.

[stefanholder]

Thanks @karussell.

Can you please briefly comment on Graphhopper #885? Should @kodonnell and I try to fix this ourselves?

[karussell]

Re 885 - yes, please. This is probably just a missing if around the two setUnfavored calls (but I might have missed the core essence)

[kodonnell]

I would rename GPXExtension to MapMatchCandidate

I initially created my own candidate class, but then realised that's what GPXExtension was being used for. Agreed that we should tidy it up to make the code a bit more obvious to understand (there are a few other issues too). That said, in the interests of clarity of commit history etc., I'm tempted to implement the feature using this API first, then tidy it up later.

I would assert ...

Indeed - there are probably a few other assumptions too. Off the top of my head, I think I did see more than two virtual candidates once. Maybe that's what @karussell was referring to here.

I think it makes sense that @kodonnell ...

Yus! I'm very green to open source contributing, so I'm tickled pink to help. Let us ride the wave of my enthusiasm as long as we can = ) I'll work on something this morning (NZ time).

Re 885 - yes, please

@stefanholder I'll work on it now, then do the rest of the map-matching stuff. Still not sure how to get it actually working, so may have to tap out for a bit.

[stefanholder]

I'm tempted to implement the feature using this API first, then tidy it up later.

Sure.

Maybe that's what @karussell was referring to here.

I think @karussell meant that for the final map matching output we need to translate virtual nodes to pillar nodes or to the OSM way geometry if there is no pillar node nearby. However, preventing inner-link U-turns should eliminate this problem except for the first and last GPS position.

I'll work on it now, then do the rest of the map-matching stuff

Great, go ahead. When you're finished (even if it's WIP), please create a pull request to branch issue_70 (you could also just push your changes but it's easier to discuss a pull request). The branch is based on the same commit as your "play code", so there should be no problems.

[kodonnell]

Done, except I did it on issue70 branch instead of issue_70 - the issue_70 seemed to be old, and didn't have my play code in it, so I wasn't sure about it. If you created issue_70, maybe delete it (I don't want to as I didn't create it etc). Let's carry on the discussion at PR #83.

[stefanholder]

Sorry, my mistake. I created issue_70 based on the last commit in the master of @kodonnell's forked map matching repository but this was the wrong one. I just deleted issue_70.

[karussell]

Can we close here now that #88 is merged or is there still room for improvement?

[kodonnell]

Can we close here now that #88 is merged

At this stage it's pretty untested (both in unit tests and by users). However, it looks good to me, so I'd probably prefer to close this and then re-open it (or start a new issue) if it arises. Not sure what's standard practice though.

is there still room for improvement?

I think #88 closes this issue well, and the only improvements are probably performance/API related or the like, which I think are separate.

[karussell]

At this stage it's pretty untested (both in unit tests and by users).

Why do you think it is untested by unit tests? All previous stuff works. And as we'll deploy this soon into production we'll get back user reports quickly.

[karussell]

However, it looks good to me, so I'd probably prefer to close this and then re-open it (or start a new issue) if it arises. Not sure what's standard practice though.

Yes, lets keep every issue as small as possible and reopen it later or similar.