[geos-devel] Map matching algorithm

[George Ionescu]

Hello GEOS users,

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 
road).

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.

Does such an algorithm exist out of the box in GEOS or do I have to code one 
myself? 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.

Any pointers, links, suggestions appreciated.
Thanks.
George Ionescu.

_________________________________________________________________
Don't just search. Find. Check out the new MSN Search! 
http://search.msn.com/