Geographic grid search algorithm

Question

Many of the location based services provide APIs for finding places/venues/spots around a given latitude longitude pair. I'm looking into how I can search for these places across an entire city.

I can build a grid for a city by getting its bounds from the Google Maps Geocoder and then incrementing the lat/longs to lay down points to form the grid. I've prototyped this grid (click the Fill Grid button to see all of the points) to visualize this idea.

// gather a collection of lat/long pairs that represents a grid of the city
    var latIncrement = .04;
    var lngIncrement = .04;
    var newLat = nw.lat();
    while(newLat >= sw.lat()) {
      var newLng = nw.lng();
      while(newLng <= ne.lng()) {
        // western and northern border as well as grid infill
        addMarker(new google.maps.LatLng(newLat, newLng));
        newLng += lngIncrement;
      }

      // eastern border
      addMarker(new google.maps.LatLng(newLat, ne.lng()));
      newLat -= latIncrement;
    }

    // southern border
    var newLng = sw.lng();
    while(newLng <= se.lng()) {
      addMarker(new google.maps.LatLng(sw.lat(), newLng));
      newLng += lngIncrement;
    }
    addMarker(se);

I can then take all of these points and run searches for them against the LBS APIs.

My question is, are there more scientific ways/algorithms to establish this grid? I'd like to learn more about them. I'm just arbitrarily incrementing the lat/lngs until I reach the border of the grid. The density of places is going to vary wildly by city and area of a city, so sometimes the increment will be too small, and sometimes too large. I'm looking for ideas about how to tune this a little better?

Answer 1

A perhaps more efficient/clean way would be to find the bounding rectangle of the city, which is the rectangle with each edge being the extreme cardinal points between the city border points, if you can find them, and then filling them in iteratively. But that is basically what you are already doing, anyway.

As for place density, do you have a specific API that you are going to be using this with? If you know the "reach" of the your API's points when detecting places, you ever only have to have grid points as close as their radius.

That being said, have you looked into seeing perhaps if the API directly supports searching for places within a border? That might be your best and cleanest bet.

---

After reading your comment, here is a possibly inefficient way that I'm going to think over and refine in the future, but it might help you get started.

Place a point in the center of your city, and observe all locations detected. Find the convex hull of your locations, and place a new point on each location on the convex hull. Then, add to your list of locations all locations that fall within reach of these newly added points.

Then, find the convex hull of those, and repeat the same process.

This might actually reduce your amount of points for sparsely populated cities. For dense ones, it might be less than optimal, but it might get you started on a working track.