Google Maps: Given a point, how to find all points at a given road distance?

Question

In my app, the GPS picks the location of the vehicle. It is then supposed to put markers at all points where the vehicle could be if it drives for 1 KM in any direction (note that the roads may fork many times within his 1KM reach).

Can someone suggest me how to do this? Thanks in advance.

Answer 1

This is a very tricky problem to solve with the Google Maps API. The following is one method that you may want to consider:

1. You can easily calculate a bounding circle of 1km around your GPS point, and it is also easy to calculate points that fall on the circumference of this circle, for any angle. This distance will be "as the crow files" and not the actual road distance, but you may want to check out the following Stack Overflow post for a concrete implementation of this:

   How to calculate the latlng of a point a certain distance away from another?

   Screenshot with markers at 20 degree intervals on a bounding circle with a 1km radius:

removed dead ImageShack link - How to calculate the latlng of a point a certain distance away from another?

2. There is also a trick to snap these points to the nearest street. You can check out Mike Williams' Snap point to street examples for a good implementation of this.

   Calculating the road distance from your GPS point to each snapped road point could be done with the directions service of the Google Maps API. Note that this will only work in countries that support directions in Google Maps, but more importantly, the road distance will almost always be greater than 1km, because our bounding circle has a 1km radius "as the crow flies". However if you can work with approximate information, this may already be one possible solution.

3. You can also consider starting with the above solution (1km bounding circle, calculate x points on the circumference, and snap them to the closest road), then calculate the road distance of each path (from your GPS point to each snapped point), and then you can repeat this this recursively for each path, each time using a smaller bounding circle, until you reach a road distance close to 1km. You can decrease the bounding circle in each recursion, in proportion to the error margin, to make your algorithm more efficient.

---

UPDATE:

I found a very neat implementation which appears to be using a similar method to the one I described above:

• Driving Radius (Multiple destinations)

Note how you can change the interval of degrees from the top. With a wide interval you'll get fast results, but you could easily miss a few routes.

Screenshot:

removed dead ImageShack link - Driving Radius