valhalla / valhalla/valhalla

Time component to map matching?

Open
#1,495 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
6.2k
Forks
981
Avg merge
2d 14h
Merged PRs (30d)
14

Description

Hi Valhalla folks -- thanks for the great project. I'm using the map matching service and for my application it's important that the matched polyline closely approximate the original polyline in terms of overall length. So I'm wondering if it's possible to make the map matching algorithm less generous with the paths it generates.

Exhibit A:
GPS trace:
![image](https://user-images.githubusercontent.com/3200608/44828959-48fb6f00-abe8-11e8-97ef-062d6ac5641e.png)

matched polyline:
![image](https://user-images.githubusercontent.com/3200608/44828980-629cb680-abe8-11e8-8576-336149cf085d.png)

So the user turned left off of Monroe, turned right on to Golf Circle, noticed a (off-map) cut-through alley, and made a U-turn so that they could travel that way instead. The matched polyline just has them traveling the entirety of Golf Circle.

I understand why the matching algorithm came up with this: it sees two GPS points on each side of Golf Circle, several points in the middle of Golf Circle that are unmatched and ignored, and it deduces that you must have traveled the entire length of Golf Circle. The problem is that this didn't happen and the matched route is a fair bit longer than the original, especially when these errors accumulate.

Is there a way to get a matched polyline that more closely resembles the original route? I feel like the hidden markov model is ignoring a time component of the polyline in assigning its probabilities: if you assume all the gps points are equally spaced in time (or were able to provide this information), then traveling the route suggested by the map matching algorithm would require traveling at superhuman/illegal speeds.

Exhibit B:
GPS trace:
![image](https://user-images.githubusercontent.com/3200608/44829585-89102100-abeb-11e8-92b6-138c59308694.png)

matched polyline:
![image](https://user-images.githubusercontent.com/3200608/44829614-ab09a380-abeb-11e8-98f5-e9f910439ef2.png)

Similar situation here: the user did a U-turn on 26th St, but did not travel all the way to the end of it before doing so.

It seems like if there were a way to provide something like a `gps_interval` parameter to the map matcher then it might help inform some of the choices it makes and could potentially tie in with the costing mode. Like if you were using `pedestrian` costing and a 1 Hz GPS interval, then you'd expect each successive point in the trace to change in distance by 1-4 m and could perhaps be more skeptical about points that varied more than this.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.