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@geos.refractions.net
http://geos.refractions.net/mailman/listinfo/geos-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
_______________________________________________
geos-devel mailing list
geos-devel@geos.refractions.net
http://geos.refractions.net/mailman/listinfo/geos-devel
