GraphHopper.com | Forum | GitHub | Maps | Blog

Wrong edge returned in map matching result


#1

Hi forum,
I have an input data set with sparse points and am seeing incorrect edges snapped to a point returned in MatchResult. The line color corresponds to the way id that is associated with each snapped point. I’ve highlighted the incorrect edge in black.

image

Here is another example (point was snapped to way in orange where, based on the sequence of points, it should have been snapped to the way in green):

This is the logic I am using to get the snapped points.

for (em <- mr.getEdgeMatches) {

  val gpxExtensions = em.getGpxExtensions

  if (gpxExtensions.size()>0) {
    for (gpxExtension <- gpxExtensions) {

      val res = gpxExtension.getQueryResult
      val edgeState = res.getClosestEdge

      // get way id of closest edge
      val wayId = GraphhopperFactory.getOSMInfo(edgeState)

      // get snapped point
      val snappedPoint = res.getSnappedPoint

,

When I inspect the edge match in MatchResult, both incoming and outgoing edges are null. Should I be filtering out these edges?

Also I don’t know what the difference is between the edges returned by:
val mergedPath = mr.getMergedPath.calcEdges

vs

mr.getEdgeMatches

I need the original timestamps in order to interpolate points on edges for which no GPX entry exists, and this it the reason why I’m using the later in order to navigate to the points in GPXExtensions which have timestamp information.

Any help would be greatly appreciated!

Thanks,
Trang


#2

Can you post the relevant GPX file and extract to the minimal number of locations where you can reproduce the issue?


#3

I’ve attached the points used in the map matching in .txt format - hope that’s ok. There are a few incorrectly snapped edges. You can take a look at points 9, 10 and 49 in the file. Thanks.device_9fcf690c23539594b1c3dbdedd8c04b2.txt (2.2 KB)

Map layer is http://download.geofabrik.de/europe/great-britain/england/greater-manchester.html
Alg options used:
val weightingOpt = new FastestWeighting(encoder)
val encoder: CarFlagEncoder = new CarFlagEncoder(5, 5, 1)
flexAlgOptions = AlgorithmOptions.start
.algorithm( Parameters.Algorithms.DIJKSTRA_BI)
.weighting(weightingOpt)
.hints(new PMap()
.put(Parameters.CH.DISABLE, true))
.build
Map matching measurement error tolerance: 40m


#4

Would you mind to print the output of GPXFile.doExport? This way I can easily POST it to our production servers without any local installation :slight_smile:


#5

Sure, attached. Thanks!
device_9fcf690c23539594b1c3dbdedd8c04b2.gpx (5.0 KB)


#6

Have uploaded it and it seems it is working - at least I don’t see any artifacts

We are using the latest master that has also a significant speed up for certain use cases.


#7

Thanks Peter for running the points through. I am using retrieving the snapped edges using GPX extensions and the way id that it maps to results in the extraneous one shown in orange
for (em <- mr.getEdgeMatches) {

val gpxExtensions = em.getGpxExtensions

if (gpxExtensions.size()>0) {
for (gpxExtension <- gpxExtensions) {

val res = gpxExtension.getQueryResult
val edgeState = res.getClosestEdge

Sequence of OSM way ids:
|29|28|37119981|
|30|29|218462545|
|31|30|124104239|
|32|31|41862197|

Is this the correct way to get to the mapped edges?
There is also a getMergedPath.calcEdges method that can be invoked on the map matching result. It returns a different set of edges compared to getEdgeMatches. Could you explain what this returns? I needed GPX extensions in order to interpolate timestamps.


#8

Attaching the list of internal edges viewed from a debugger. Highlighted is the incorrect edge.


#9

The way to get the Path is shown here: https://github.com/graphhopper/map-matching/blob/master/matching-web-bundle/src/main/java/com/graphhopper/matching/http/MapMatchingResource.java#L129

Getting interpolated timestamps is not yet supported but in the forum I saw someone that had a workaround.


#10

So it looks like the UI is using the merged path to get to the map matched points.
What is mr.getEdgeMatches returning compared to mr.getMergedPath?

Since getMergedPath.calcPoints don’t have any time association, we would need to perform a closest point search across the input GPX entries and is tricky if there are loops in the trajectory. I haven’t yet tried this in a full run but it would seem expensive over a large data set.
Is there a better way to associate gpxExtensions with the edges returned by mr.getMergedPath?


#11

There’s a second (inofficial, contributed, subject to change) output format, called “extended_json”, which appears to be something close to the edgeMatches. See MapMatchingResource.java. (Request it with “?type=extended_json”). Maybe when you do requests with both types, you have all information you need?


#12

More specifically, the edge you are looking for is, I think, edgeMatch.getEdgeState, not gpxExtension.getQueryResult.getClosestEdge.

That still doesn’t map the observation to a point on that edge, but at least it should give you the right edge.


#13

Good question indeed. Yes, in the Path we have something like “internal” edge ids, which are used by the algorithm and encode the direction on the link. In the matchResult, we filter these out and convert them to real edge ids. In the Path, we apparently didn’t bother, because where it is used, the edge ids do not matter (it is used by the web API to create a chain of driving instructions and a LineString of coordinates).

If you want edge ids, use those on the matchResult. If those are wrong, we have a problem.


#14

michaz - thanks so much for the explanation. Just need a few additional clarifications to your responses:
gpxExtension.getQueryResult.getClosestEdge -> does this return the closest edge snapped to the original coordinates vs the corrected list of ordered edges determined by the map matching result?

Are you saying that matchResult.getMergedPath returns internal edge ids and it should be sufficient to examine the edges in matchResult.getEdgeMatches?

Currently we’ve built a workaround by using a snapped point for timestamp information only if its closest edge is included in the list of edges returned by matchResult.getMergedPath …

Also some background: previously when we didn’t lookup the closest edge associated with a GPX entry, we were seeing strange results, where a point appeared to be snapped to the wrong edge thought the route was correctly identified.
Note: the point colors associate a point to the wayId it is mapped to
image


#15

That’s what I think, yes. But the only result that is really “public” or “supported” is the path itself (the chain of coordinates), as returned by the API.

As you may have guessed, when we wrote this, we didn’t consider edge ids to be public at all. That somehow crept in (and we understand the need for it). We’ll definitely look at this again and make it more consistent and clear, but I can’t promise a timeline.

I am not so sure what exactly the x,y,timestamp fields in the “extended_json” mean or whether they are correct.

I would say there is no reliable source of identifying the snapped equivalents of input points on the output path at the moment. Yes, it’s all there, but I don’t want to make any claims before looking at it in detail again.


#16

One more suggestion:

When you further look into this, maybe look directly at the List<SequenceState<GPXExtension, GPXEntry, Path>> that goes into computeMatchResult, which should probably be renamed.

That is actually the most direct and informative representation of the map matching result, except that the edge ids used everywhere are “internal”. If it isn’t in there, it isn’t anywhere. Maybe something you need is lost or changed within that conversion method.


#17

Or more specifically: I would look at

  • the “extended_json” (and check whether it is correct and what you need)
  • the List<SequenceState<GPXExtension, GPXEntry, Path>> (if it isn’t, and see if you can get it from there).

Not so much at things in between.


#18

Thanks, I’ll take a look at your suggestions.


#19

I took a look at the extended_json logic and it is similar to what we are doing except that we use the closest edge to lookup way ids associated with a snapped point.

Looking at the computeMatchResult logic, the associate of gpx points to a matched edge is done whenever an edge transition is detected in the edge match result (without examining the closest edge in the query result):
if (currentEdge == null || !equalEdges(directedRealEdge, currentEdge)) {
EdgeMatch edgeMatch = new EdgeMatch(directedRealEdge, gpxExtensions);
edgeMatches.add(edgeMatch);
gpxExtensions = new ArrayList<>();
currentEdge = directedRealEdge;
}’

I’m not sure why (perhaps this is intentional?) but this would explain why we were seeing thg “shift” in the above image, where some snapped points appear to be associated with the wrong edge if you plot this on a map.


#20

I’ve found another case in which the GPX extension returned for an edge match is wrongly associated with the edge match. Gpx extension 0 below is closest to edge id 50505 but is returned in the match result as a child element to edge 50506. Should I submit a JIRA for this issue?

Thanks,
Trang