Suggestion: Looping resolution

[Alby1987]

Hi! I've read about the loop problem, and your idea about MappointX, MappointX+4, etc... I was thinking it would be better to divide the subtrack based on same points. For example instead of routing from A to B, you can route in pair A-B,C-D,etc...

If points are near (5m-10m-adjustable) and subsequent, treat them as one. In are near but not subsequent, like the drawing above, dividing the route should be OK. It's a good idea? :)

[karussell]

Yeah, that is basically the improved idea BUT the merging is not that easy :). Also you do not know up-front that B|E|C|D is the important junction so you'll have to divide your track based on a heuristic.

[Alby1987]

I'm not to good in GIS system, but it shouldn't be like having (for the track above) 5 different paths that you can use the matching algorithm? A->B, B->D, D->F,F->H,H->J .

The letters are joints, and B=C, D=E, F=G, and so on... Maybe, I just missing some GIS concepts I'll understand in the future, and connecting is not that easy :) !

For the division of the tracks, if you are working on a offline map matching (having the whole route loaded before starting calculations), it should be possible to do a for loop every time a joint is calculated, check if that joint was used before. If so, close that subpath, and create a new path.

I'll try explain:

Black is the calculated path, blue are junctions, red are waypoints

From start to waypoints 1 is okay (Fig.1), then it goes to waypoint 2 (Fig.2), then, going to waypoint 3, a particular junction is touched: this junction was passed before (Fig.3). So the algorithm goes backwards and creates 2 subpaths already calculated: Start->Important Junction, Important Junction->Waypoint touched before (1 and 2)->Important Junction, and then it start again Important Junction->Waypoint 3, and so on...

Is this a good idea? Many thanks :)

[karussell]

Hey, that approach is possible but it has to be implemented :). Also I see problems as the correct split is important and 'B->D' would not lead to the loop but instead GraphHopper would find a shorter path and use that. So the splitting should happen like in your example where one uses at least one support-point from the loop. The loop detection could be partially done upfront, but not always. So the simplest approach would be to split every path into N subpaths and merge them afterwards, again that isn't hard in theory just not implemented. Also other optimizations have to be done before this.

[Alby1987]

To do the loop, B->D, there should be inbetween points between B and D. It's ok! I'll clone the code and see what I can do :) Many thanks! :D

[karussell]

I'm currently investigating this and a loop detection is possible (real distance versus found distance), so that one has to do the search recursivly until no (big) loop is found. As this approach is a bit more complex and possibly also slower I will do the heuristical splitting into sub-tracks for now as a fix.

[karussell]

BTW: the work for this is done in the issue_1 branch

[chrissssss]

Hi! Good work, results are far better than before! I'm sorry, but I've tested master half an hour ago with the following http://www.gpsies.com/map.do?fileId=dcnjvydxcmwcpgoq on a small dataset around Berlin DGZ Ring with foot encoder. The check fails at doWork(), but even if I comment it out it the result is strange.

The upper loop seems to be missing.

EDIT: Just created a pull request to hand you over the junit test-stub. It has no asserts but creates a testfile for the result. Please leave me a comment if I can do something to help. BTW, which way did you choose to resolve the looping issue?

[karussell]

with the following http://www.gpsies.com/map.do?fileId=dcnjvydxcmwcpgoq

I get that the route is none-public (although I'm logged in)

The check fails at doWork(), but even if I comment it out it the result is strange.

Yeah, if the check passes the results should be reasonable.

Just created a pull request to hand you over the junit test-stub

That is very helpful! In case when I cannot reproduce this problem in my test area (leipzig) can I include the data set and the test you provided under the Apache License?

For now the looping issue is solved via partitioning the route into smaller parts, which solves this relative robust but still gives sometimes strange results at the merge location. And you have to provide the distance to do the split (separatedSearchDistance). In a later improvement the split could be done for the loop crossing (and one or two additional via points), but we need a proper loop detection and of course a 100% working simple solution before.

[chrissssss]

Hi Peter, the unit test already has your header included. The graph data is taken from OSM and the gpx you can do what you want with ;)

It's included in the Unit-Test. The problem is that the resulting gpx-file doesn't include the upper left loop

I'll give you a glance at what the gpx looks like

[karussell]

the unit test already has your header included

ok, just wanted to make it sure :)

If you decrease the search distance you get a good looking match:

MapMatching mapMatching = new MapMatching(graph, locationIndex, encoder);
mapMatching.setSeparatedSearchDistance(100);

Still I have a look into the problem that the check() method saying "dup edge etc" for the default distance

[karussell]

Okay, the duplicate edge is because of the beginning of the second loop is stored and the second search already finds GPS points back to the destination => the small beginning of Wilhem-Wagnenfeld-Straße is stored twice (u-turn). Currently we have to live with workarounds until a more solid solution is implemented (I know how, but would take me too much time). The workarounds are: decrease the separatedSearchDistance OR accept that sometimes loops are ignored and you specify a new forceRepair=true parameter where it tries to remove duplicate edges.

Suggestions are welcome the current improvements I plan are:

• forceRepair currently is limited. Instead of checking for edge duplicates we should check for missing GPX matches
• we need a proper loop detection and then
• recursively detect loops and insert them
• Or instead of this loop insert algorithm I can think of a guided routing algorithm with a steadily changing goal. (could time dependent weights solve this?)