[geos-devel] Map matching algorithm

[Martin Davis]

You could try looking at RoadMatcher:  
http://www.jump-project.org/project.php?PID=RM&SID=OVER

Frechet distance is nice, but very computationally intensive (plus no 
available code that I've found).  I used a thing I call VertexHausdorff 
distance in RM - it's the Hausdorff distance computed at vertices only, 
to make it simple to code.  It works well.

You'd have to embed that in an algorithm to choose potential road 
candidates to test for matches.  I usually do this by simply loading the 
candidate roads into a spatial index, and just looking at all those 
within a given distance tolerance.  You can weed out non-candidates 
pretty quickly using various heuristics.

Once you have decide on a match, snapping is simply determining the 
closest point on the candidate road.

Of course, if you want to match across multiple road sections, the 
problem gets quite a bit harder.  At that point you might as well just 
use RoadMatcher. 


George Ionescu wrote:
> 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/
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net
> http://geos.refractions.net/mailman/listinfo/geos-devel
>

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022