{"action":"created","issue":{"url":"https://api.github.com/repos/graphhopper/map-matching/issues/83","repository_url":"https://api.github.com/repos/graphhopper/map-matching","labels_url":"https://api.github.com/repos/graphhopper/map-matching/issues/83/labels{/name}","comments_url":"https://api.github.com/repos/graphhopper/map-matching/issues/83/comments","events_url":"https://api.github.com/repos/graphhopper/map-matching/issues/83/events","html_url":"https://github.com/graphhopper/map-matching/pull/83","id":191599074,"number":83,"title":"WIP: prevent inner-link U-turns","user":{"login":"kodonnell","id":8204904,"avatar_url":"https://avatars.githubusercontent.com/u/8204904?v=3","gravatar_id":"","url":"https://api.github.com/users/kodonnell","html_url":"https://github.com/kodonnell","followers_url":"https://api.github.com/users/kodonnell/followers","following_url":"https://api.github.com/users/kodonnell/following{/other_user}","gists_url":"https://api.github.com/users/kodonnell/gists{/gist_id}","starred_url":"https://api.github.com/users/kodonnell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kodonnell/subscriptions","organizations_url":"https://api.github.com/users/kodonnell/orgs","repos_url":"https://api.github.com/users/kodonnell/repos","events_url":"https://api.github.com/users/kodonnell/events{/privacy}","received_events_url":"https://api.github.com/users/kodonnell/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"stefanholder","id":12279136,"avatar_url":"https://avatars.githubusercontent.com/u/12279136?v=3","gravatar_id":"","url":"https://api.github.com/users/stefanholder","html_url":"https://github.com/stefanholder","followers_url":"https://api.github.com/users/stefanholder/followers","following_url":"https://api.github.com/users/stefanholder/following{/other_user}","gists_url":"https://api.github.com/users/stefanholder/gists{/gist_id}","starred_url":"https://api.github.com/users/stefanholder/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefanholder/subscriptions","organizations_url":"https://api.github.com/users/stefanholder/orgs","repos_url":"https://api.github.com/users/stefanholder/repos","events_url":"https://api.github.com/users/stefanholder/events{/privacy}","received_events_url":"https://api.github.com/users/stefanholder/received_events","type":"User","site_admin":false},"assignees":[{"login":"stefanholder","id":12279136,"avatar_url":"https://avatars.githubusercontent.com/u/12279136?v=3","gravatar_id":"","url":"https://api.github.com/users/stefanholder","html_url":"https://github.com/stefanholder","followers_url":"https://api.github.com/users/stefanholder/followers","following_url":"https://api.github.com/users/stefanholder/following{/other_user}","gists_url":"https://api.github.com/users/stefanholder/gists{/gist_id}","starred_url":"https://api.github.com/users/stefanholder/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefanholder/subscriptions","organizations_url":"https://api.github.com/users/stefanholder/orgs","repos_url":"https://api.github.com/users/stefanholder/repos","events_url":"https://api.github.com/users/stefanholder/events{/privacy}","received_events_url":"https://api.github.com/users/stefanholder/received_events","type":"User","site_admin":false}],"milestone":null,"comments":52,"created_at":"2016-11-24T22:42:39Z","updated_at":"2016-12-06T21:25:01Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/graphhopper/map-matching/pulls/83","html_url":"https://github.com/graphhopper/map-matching/pull/83","diff_url":"https://github.com/graphhopper/map-matching/pull/83.diff","patch_url":"https://github.com/graphhopper/map-matching/pull/83.patch"},"body":"See #70 \r\n\r\nWIP. Things to note (@stefanholder)\r\n\r\n- until [here](https://github.com/graphhopper/graphhopper/issues/885#issuecomment-262829335) is resolved I just manually set unfavored statuses\r\n- not sure whether what I've done is correct (e.g. use of edges and direction).\r\n- MapMatchingTest2 includes the example original in #70, plus a failing test. Most of the other tests fail (I think I know why, but we can worry about that later)\r\n\r\nI'm still not sure how the logic is going to work. To clarify, consider\r\n\r\n```\r\n     v1    v2 \r\n A------X------B\r\n```\r\nwith nodes A,B and a GPX position at X (i.e. the virtual node), and virtual edges v1 and v2. What is being done in this PR is creating two candidates for this GPX point: both with closestNode = X, but one with incoming=v1 and outgoing=v2, and the other with that reversed. When we route, we simply unfavor the incoming/outgoing edge to force the other to be used. E.g. if X is the `from` candidate, then we'd have\r\n\r\ncandidate 1: incoming=v1 (unfavored), outgoing=v2 \r\n```\r\n     v1    v2 \r\n AxxxxxxX--->--B\r\n```\r\n\r\ncandidate 2: incoming=v2 (unfavored), outgoing=v1 \r\n```\r\n     v1    v2 \r\n A--<---XxxxxxxB\r\n```\r\n\r\nWe can do similar for the `to` candidate but unfavor the outgoing edge.\r\n\r\nHowever, how do we actually prevent inner-link U-turns with this? When X is the `to` timestep, we have a candidate\r\n\r\n```\r\n     v1    v2 \r\n A-->---XxxxxxxB\r\n```\r\n\r\nand when it's the `from` timestep we have a candidate\r\n\r\n```\r\n     v1    v2 \r\n A--<---XxxxxxxB\r\n```\r\n\r\nin other words the inner-link U-turn is still possible:\r\n\r\n```\r\n A-->---XxxxxxxB\r\n A--<---XxxxxxxB\r\n```\r\n\r\n@stefanholder - how were you planning to get around this when you said:\r\n\r\n> If a candidate is a virtual node + direction, we can enforce the direction during routing with QueryGraph.enforceHeadingByEdgeId. We can store the direction as the outgoing virtual edge id.\r\n\r\nSince we don't know the direction of the 'right' `to` candidate we can't enforce the 'right' direction to start with.\r\n\r\nIf you agree it's not resolvable, then I think an 'online' (i.e. step by step) solution might be best: we calculate the best sequence up to the give point, and the we can enforce that as the direction at the start of the route to all other candidates. "},"comment":{"url":"https://api.github.com/repos/graphhopper/map-matching/issues/comments/265277041","html_url":"https://github.com/graphhopper/map-matching/pull/83#issuecomment-265277041","issue_url":"https://api.github.com/repos/graphhopper/map-matching/issues/83","id":265277041,"user":{"login":"kodonnell","id":8204904,"avatar_url":"https://avatars.githubusercontent.com/u/8204904?v=3","gravatar_id":"","url":"https://api.github.com/users/kodonnell","html_url":"https://github.com/kodonnell","followers_url":"https://api.github.com/users/kodonnell/followers","following_url":"https://api.github.com/users/kodonnell/following{/other_user}","gists_url":"https://api.github.com/users/kodonnell/gists{/gist_id}","starred_url":"https://api.github.com/users/kodonnell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kodonnell/subscriptions","organizations_url":"https://api.github.com/users/kodonnell/orgs","repos_url":"https://api.github.com/users/kodonnell/repos","events_url":"https://api.github.com/users/kodonnell/events{/privacy}","received_events_url":"https://api.github.com/users/kodonnell/received_events","type":"User","site_admin":false},"created_at":"2016-12-06T21:25:01Z","updated_at":"2016-12-06T21:25:01Z","body":"> with smaller node ID\r\n\r\nFYI issue-70.osm.gz is just an export from OSM of the region directly surrounding the relevant route. So, while it's locally the same network, the actual use in GH may differ, and effect the results. (For example, the edges are likely to experience different contraction, etc.)\r\n\r\n> can you please explain to me how to use the same routing settings in MapMatchingMain.java as in testIssue70\r\n\r\nI haven't used main before, but [the setup](https://github.com/graphhopper/map-matching/blob/0f3fafc01dac907d84752ec418ee9621981f7782/matching-core/src/main/java/com/graphhopper/matching/MapMatchingMain.java#L71-L93) is quite different to that of [the test](https://github.com/graphhopper/map-matching/blob/0f3fafc01dac907d84752ec418ee9621981f7782/matching-core/src/test/java/com/graphhopper/matching/MapMatching2Test.java#L68-L76). "}}
{"actor":{"display_login":"kodonnell"}}