search

graphhopper / map-matching

The map matching functionality is now located in the main repository https://github.com/graphhopper/graphhopper#map-matching
https://www.graphhopper.com/open-source/
Apache License 2.0
785 stars 273 forks source link

missing long edges #84

Closed kodonnell closed 6 years ago

kodonnell commented 7 years ago

I've come across an issue where LocationIndexMatch isn't finding long edges. I am using a modified form of it, but I think the underlying issue may persist.

My (naive) understanding is XFirstSearchCheck basically is looping through nodes, and calculating the distance of the node to the query point, and this is then passed on to XFirstSearchCheck.check (which is where we do our thing). My concern is what happens on edges where there is a long separation between pillar nodes. For example

-----P1-----( ... N ... )-----P2-----

where the bracketed N is a search region around N, and P1/P2 are consecutive pillar nodes on an edge passing through the search region. In this case, neither P1 nor P2 are in the search region, and hence the edge won't (??) be included?

That all said ... I tried to create a test case for this, but it worked (i.e. the above didn't happen). I'm not sure whether it was just a bad test case, so I'm raising this 'issue' as more of a 'could be an issue if someone who knows more thinks it is'.

karussell commented 7 years ago

This should still work as we use BresenhamLine.calcPoints to fill in nodes if necessary and the two pillar nodes would be too far away. See some complex stuff with this discussed in https://github.com/graphhopper/graphhopper/pull/221 and https://github.com/graphhopper/graphhopper/issues/232 and http://stackoverflow.com/q/24679963/194609

hbruch commented 6 years ago

ProbabIy the issue I ran into is such a long edge issue. When trying to match a short track (with PR #109 applied). The red track in the image below with coords LINESTRING[8.576946438529065 48.942270883048046, 8.577063654245032 48.942225069201065] is not matched. The blue lines represent the edges visited via XFirstSearchCheck.checkAdjacent. However, the long primary B10 road is not visited.

matching
karussell commented 6 years ago

Thanks for the visual report. This is probably a bug in the feeding mechanism of the location index that works via the bresenham mechanism (as described in the linked issues), probably happens only under rare conditions.

hbruch commented 6 years ago

Ouch. In my case the road was tagged with access=no due to temporary road works. Sorry for hijacking this issue...