[OSM-dev] OT: Map Matching algorithm

Milo van der Linden mlinden at zeelandnet.nl
Fri Oct 19 15:51:18 BST 2007

Hello George,

I think that no such function is available in the OSM api at the moment. 
So this would involve some coding effort. What I would like to know is;

- what programming language do you use?
- Do you have a function to loop through the NMEA log allready?
- Are you using OGR/GDAL in the base of the application?

My main programming skills are focused on VB6, VB.NET and C#, so if this 
is your programming environment I might be able to help

Kind regards,

Milo van der Linden

George Ionescu schreef:
> 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
> 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.
> 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?
> Thanking you for your time,
> Sincerely,
> George Ionescu
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev



Milo van der Linden
skype: milovanderlinden <skype:milovanderlinden?add>
mlinden at zeelandnet.nl <mailto:mlinden at zeelandnet.nl>
milovanderlinden at gmail.com <mailto:milovanderlinden at gmail.com>
milo at 3dsite.nl <mailto:milo at 3dsite.nl>


De informatie in dit bericht reflecteert mijn persoonlijke mening en 
niet die van een bedrijf of instantie. Aan de informatie kunnen geen 
rechten worden ontleend. Indien dit bericht onderdeel is van een forum, 
mailing-list of community dan gelden automatisch de bij het betreffende 
medium behorende voorwaarden. The information in this message reflects 
my personal opinion and not that of a company or public body. All rights 
reserved.If this message is contained in a mailing-list or community, 
the rights on the medium are automatically adapted.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20071019/f9523eae/attachment.html>

More information about the dev mailing list