8

Imagine you have a list of points (latitude + longitude) you have previously recorded with a GPS receiver. Now, you need to convert it to a textual representation of the route you followed. Example:

  1. Start at Redmond Avenue 12
  2. Walk 200 m
  3. Turn left to Another St.
  4. Walk 100 m
  5. Stop at Another St. 10
  6. End

It doesn't really need to be very detailed. The first idea that comes to my mind is to use an external service (google, yahoo...) to reverse geocode each point. Then apply a simple algorithm to write the route when I detect a change in the street name.

Any tip about what is the best algorithm to use or any existing (open) implementation is welcome. It does not seem to be trivial.

R.K.
  • 17,405
  • 3
  • 59
  • 110
Guido
  • 183
  • 7
  • 1
    Is it worth pointing out that if I'm told to Start at Redmond Avenue 12 and Walk 200 m I won't know which direction to walk? Sorry for nitpicking. – fmark Aug 06 '10 at 11:57
  • @fmark, thank you. You are rigth but it is not important in this case. The instructions are shown before the points have been recorded, as part of an internal auditory system. The level of detail is not as important as allowing other people to know the aproximate route that was followed. – Guido Aug 06 '10 at 18:05

1 Answers1

4

If you can use an external service, the Google Directions API provides this functionality directly. It supports waypoints along the path, so you could do:

http://maps.google.com/maps/api/directions/json?origin=Redmond+Avenue+12,01864
&destination=Concord,MA&waypoints=lat1,long1|lat2,long2|lat3,long3&sensor=true

This will return a JSON document with steps for each direction.

If you want to do this yourself, you have a few steps to start processing directions: you'll need a dataset for routing the paths, such as OSM, and a routing engine such as pgRouting. Something like OSM2PostGIS provides the necessary heavy lifting to get a setup like this running. You'll then want to reposition each of your points onto the nearest edge, which can be done in PostGIS with ST_Line_Locate_Point (documentation). Between the linear referencing in PostGIS and pgRouting, you should be able create reasonable enough directions.

scw
  • 16,391
  • 6
  • 64
  • 101
  • 1
    Thank you. I know that service provided by Google, but it only allows 25 points along the path. The GPS saves a point every 10 seconds, so I would reach the limit in less than 5 minutes. – Guido Aug 06 '10 at 12:11
  • 2
    Right, it would limit you to 25 points, but you could probably use less resolution since the paths will follow the edges in Google's base data for the majority of the route. Alternatively, you could send multiple queries for a single route, and then parse the results back together (there's also an example in the API for this). – scw Aug 09 '10 at 23:20