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

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 t开发者_如何学Pythono do this? Thanks in advance.

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

Natural brute force algorithm is to build a list of all possible nodes taking into account each possible decision on every crossroad.

I doubt that within 1km you would get more then 10 crossroads on average and assuming avg of 3 choices on a crossroad you would end up with 3^10 - around 59,049 end nodes (notice that you need to have 10 crossroads on every branch of the road to reach the full number).

In reality the number would go down and I would assume getting to the same node by different route would not be uncommon, especially in cities.

This approach would give you an exact answer (providing you have good street map as input). It is potential time, but the n does not seem to be that high, so it might be practical.

Further improvements and optimizations might be possible depending on what do you need these nodes for (or which kind of scenarios you would consider similar enough to prune them).

Elaborating a bit on Daniel's approach above, you want to first find all the point within a straight line radius from your origin. That's your starting set of nodes. Now include ALL edges incident to those nodes and other nodes in your starting set. Now check that the nodes are connected and that there aren't any nodes out there floating around that you can't reach. Now create a "shortest path tree" starting from your vehicle node.

The tree will give you the shortest paths from your starting node to all other nodes. Note that if you start by creating paths at the furthest nodes, any sub-paths are also shortest paths to those nodes along the way. Make sure to label those nodes on sub-paths as you continue so you don't need to compute them. Worst case scenario, you need to develop a shortest path for all nodes, but in practice this should take much less time.

1. List all possible nodes taking into account each possible decision on every crossroad (But how to do it automatically?
2. Use Dijkstra`s algorithm to find closes route to all points.
3. Visualize data. (That is a little bit tricky, because there can be an unreachable areas inside reachable area.