Creating a random lat/long coordinate that is positioned in a physically reachable location

I have an application that generates some number of tokens around the current location of the user using a certain distance radius. The user will then have to run to some of those locations. The problem is that some tokens can be created in a lake,forest,ocean, or some other physically unreachable location. As a quick fix I just generate extra tokens and increase the proximity distance that determines if a user reached a certain location. I now want to improve this so that each token is located at a reachable location.

The only solution I have been able to come up with is using the Google Directions API to determine a path from the user to the token and use the last coordinate in the polyline as the new reachable location of the token. My problem with this is that I potentially have to post up to 30 requests to the Directions service simultaneously and I am worried that I might hit the query rate limit. I have not found anything definite about query rate limit.

So my question is whether anyone knows of a better solution or can give any input on the Directions query rate li开发者_高级运维mit? Waiting 1 second between each request and forcing the user to wait up to 30 seconds is not a reasonable solution. Thanks.

UPDATE Using the solution that I described in the question does produces an OVER_QUERY_LIMIT, even if I wait 1 second between each request. Other then that the logic was sound and tokens that got a request thru were appearing in walk reachable locations.

---

You can calculate the distance between two lat/lon with Location.distanceBetween(). This is a static convenience API call. There's no limit on number of calulations.

---

Usage limits

Use of the Google Directions API is subject to a query limit of 2,500 directions requests per day. Individual directions requests may contain up to 8 intermediate waypoints in the request.

Google Maps Premier customers may query up to 100,000 directions requests per day, with up to 23 waypoints allowed in each request.

You might want to take a look into the Maps premier customer so you don't hit the limit too fast. If your app becomes popular I bet you can get an higher limit.

One way would be to see if you can see the elevation to see if it's a cliff or not. However just seeing if it's a lake or not seems to be quite hard. Might be some kind of gps lookup service out there except Google Maps.

If you just want to know the distance between locations just use Location.distanceTo() or static distanceBetween() Getting the info if it's a road or not is another question.

---

After some 8 hours I finally got something working. So using the fact that each request can have up to 8 waypoints I can technically ask directions to 9 locations in one request. Here's what I am doing now:

Generate 9 random locations at a time. Pass the locations to my DirectionsComputer which returns the polyline path that goes through all 9 coordinates as a list of coordinates. Then I pick 9 location from the path and set them as the locations of my tokens. Now all my tokens are semi-randomly generated, always appear on a road, and I only need to do 4 consecutive requests to generate 36 tokens.

There are some cases where a few tokens are bunched together. For example, the coordinates which are originally located in the ocean get moved to the same beach. But for the most part, all my tests showed the tokens spread apart and I could tweak the rest.