How do I implement a "find nearest" type functionality ?

Question

HI, I was wondering if anyone had any ideas about how to implement functionality where given an array of locations ( for e.g. branches) it will list the nearest one or list all withing a 5 mile radius etc?

Answer 1

When you say "locations", what do you mean exactly? Street addresses? GPS coordinates?

If you have GPS coordinates (or can convert an address to coords), you can always calculate the Euclidean distance or the (more accurate) great-circle distance between two points. Caculate the distance between the current location and each potential destination, then sort the list by shortest distance.

You didn't mention if you were using the Google Maps API, but here's some additional info in case you are. You can store two points as objects of type GLatLng and use object1.distanceFrom(object2) to calculate this. You can also create a GLatLngBounds object representing a rectangular region on the map and use GLatLngBounds.containsLatLng(latlng:GLatLng) to see if a geographical point lies within that region.

Edit: What typically happens in the case you mention below is when a user enters a post code, the "current location" is taken to be the geographic center of that post code (you would probably have to get this info from the authority who assigns post codes in your area). If you are in the UK, this site has a free list of postcodes and their coordinates. Searching for a postal code in Google Maps will take you to the center of that postcode; if you need to build your own list of post codes and coordinates, you can probably create a script that will iterate through all valid post codes and use Google maps to look them up and turn them into GPS coordinates.

To turn an address into coordinates, you want to do what is called geocoding. Google Maps has an API for this, and there are other resources that can provide you this functionality. For some examples, try this page. What resource you use largely depends on where you are, as most of this information is localized. You didn't mention much about your project (platform, language, etc), but at the bottom of that page is a section called "Geocoding Helper Libraries" that may have the functionality you need rolled into a pre-built package. In particular the GeoKit library (Ruby language) has a handful of examples on the front page of their website, including several that look like they do exactly what you are wanting to do.

EDIT: I got the following code from the code generator at WebRPC:

/**
 * Copyright WebRPC
 * available under the GNU GENERAL PUBLIC LICENSE Version 2, June 1991
 * http://www.gnu.org/licenses/gpl.txt
 */
public class Client
{
    public static void Main(string[] args)
    {
        // make the call
        XPathDocument doc = new XPathDocument(@"http://maps.google.com/maps/geo?q=New+York&output=xml&key=ABQIAAAAuXdMTY5VIU1FvkgOOP1dNBTsILMTMKRV-aJhd94IQkaJhVJ0YBS2qNSZGm8TaefqbXBT6lUXeMZ6tA");

        // print the outputs
        XPathNavigator nav = doc.CreateNavigator();
        XPathNodeIterator coord = nav.Select( "/kml/Response/Placemark/Point/coordinates" );
        while ( coord.MoveNext() )
            System.Console.WriteLine( coord.Current );
        XPathNodeIterator accuracy = nav.Select( "/kml/Response/Placemark/AddressDetails/@Accuracy" );
        while ( accuracy.MoveNext() )
            System.Console.WriteLine( accuracy.Current );
    }
}

You should be able to modify this C# code to suit your needs. Specifically, in the call to new XPathDocument, change the part of the string that reads ?q=New+York to whatever address or postal code you need (for example, using ?q=1060+West+Addison%2C+Chicago%2C+IL will retrieve information for Wrigley Field in Chicago, or using ?q=LS11+0ES%2C+UK will get info for a postal code in Leeds). To format an address from a regular text string, change spaces to '+' and turn all other non-alphanumeric characters into their ASCII equivalent (such as '%2C' for a comma).

The next few lines retrieve the information from the server and parse it in various ways. Of interest here is the field /kml/Response/Placemark/Point/coordinates in the returned data. This string will contain your latitude and longitude coordinates for the location you specified above.

Now, this should give you enough information to create a C# function that is able to turn an address or post code into a pair of coordinates. The hard part is done, but two steps remain. First, you will want to use this to generate coordinates for each address in your database (store these in the database with the addresses for best results). Now, when a user enters an address, call your C# function again to generate a set of coordinates for her location. Now that you have coordinates for everything, you can find the distance between two coordinates by using one of the two distance-calculating functions I linked to at the top of the post. Run down your list of branches, calculate the distance from the user to each, and sort that list to find the branches with the shortest distance values.