# [OSM-dev] OT: Map Matching algorithm

George Ionescu geoionescu at gmail.com
Fri Oct 19 10:12:31 BST 2007

```Hello dear OSM developers,

sorry for the Off-Topic, but I'm almoust out of hope for my problem
and I really think you can help, mostly because of the new Routing
engine being developed which, hopefully, needs this problem solved.

I'm currently involved in developing a software which involves
matching road-collected GPS data onto a vectorial map. If you don't
mind the 5-minute reading, the project description is below:

We have a basic in-house developed GIS system which does only one thing for
the moment: loads an ESRI shape file and a NMEA log (recorded by a DGPS
corrected GPS) and draws them on the screen. We're not aiming (nor needing)
a navigation system, but we do need to match the points from the NMEA log on
the roads from the shape file.

Although the GPS is quite accurate (e.g. at most 3m HDOP), the
field-collected points almost never match the roads ( e.g. are not on the

I'm looking for a way to snap the points on the road, knowing that basic
snapping (e.g. snap a point to the nearest line) won't do the trick.

While searching I found out that Frechet distance may help a little
but I can only figure that this would be the verification method, not the
matching one.

I guess that the mathematics problem would be something like: given a known
finite set of polylines SP and a known finite set of points P, find the
subset of polylines which has the minimum Frechet distance from the polyline
defined by P and the translation matrix for each point P to fit the
polylines found.

I know that this is quite computationally intesive, but fortunately I don't
need real-time calculations.

I asked this question on some mailing lists and got a response on GEOS
mailing list which you can read at:
http://geos.refractions.net/pipermail/geos-devel/2007-October/003065.html

The author suggested that Hausdorff distance might do the trick.

So, after such a long description, here goes my question:

Does such a map-matching algorithm exist somewhere hidden in
OpenStreetMap source repository or do I have to code one myself? If it
doesn't, will it be implemented soon given that the Routing engine
might need this?