2008-03-30

Postal codes within a radius

My hobby MVC website allows people to place adverts. When searching for adverts I would like the user to be able to specify a UK postal code and radius to filter the adverts down to ones within travelling distance. The trick to this was to record a list of UK postal codes and their latitude/longitude.

The first step is to write a routine which will give a straight line distance between to coordinates:

public static class MathExtender
{
  public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude)
  {
    double theta = sourceLongitude - destLongitude;
    double distance =
      Math.Sin(DegToRad(sourceLatitude))
      * Math.Sin(DegToRad(destLatitude))
      + Math.Cos(DegToRad(sourceLatitude))
      * Math.Cos(DegToRad(destLatitude))
      * Math.Cos(DegToRad(theta));
    distance = Math.Acos(distance);
    distance = RadToDeg(distance);
    distance = distance * 60 * 1.1515;
    return (distance);
  }

  public static double DegToRad(double degrees)
  {
    return (degrees * Math.PI / 180.0);
  }

  public static double RadToDeg(double radians)
  {
    return (radians / Math.PI * 180.0);
  }
}


Additionally, on my PostalCode class I have a helper method like so:

public double GetDistanceTo(PostalCode destination)
{
  return MathExtender.GetDistanceBetweenPoints(Latitude, Longitude, destination.Latitude, destination.Longitude);
}


Now the next problem is that these routines are not selectable via SQL and therefore to find all postal codes within a radius of another I would have to load all postal codes into memory and then evaluate them, which I don’t want to do! The DB might be able to use SIN/COS/ACOS etc but if it does then it would be DB specific and I don’t want that either. My decision was to first look for postal codes within a square area, the square being just big enough to encompass the circle, and then to use the in-memory PostalCode.GetDistanceTo() method to whittle the postcodes down to the exact list of matching objects.
The problem remained that I would still need to establish whether Longitude/Latitude coordinates will be within this square. To overcome this I decided that if the world were divided up into a grid of squares each 1 mile in size I could then easily select postal codes within any size square by checking which 1 mile square it is within. So I decided to establish Longitude=0 Latitude=0 as 0,0 on my grid and work out every postal code’s distance from that point. I added two persistent "Double" properties to my postal code class named GridReferenceX and GridReferenceY which I set whenever the Longitude or Latitude is set:

public double GridReferenceX { get; private set; }
public double GridReferenceY { get; private set; }

public double Longitude
{
  get { ..... };
  set
  {
    ......;
    CalculateGridReference();
  }
}

public double Latitude
{
  get { ..... };
  set
  {
    ......;
    CalculateGridReference();
  }
}

private void CalculateGridReference()
{
  //Latitude distance only (X)
  GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0);
  //Longitude distance only (Y)
  GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude);
}


Now I have a grid reference for each postal code which really means nothing, but the advantage is that they can be compared to each other like so...

public IList<PostalCode> GetAllWithinRadius(PostalCode postalCode, double radiusInMiles)
{
  List<PostalCode> result = new List<PostalCode>();
  string criteria = string.Format("->select(gridReferenceX >= {0} and gridReferenceX <= {1} and gridReferenceY >= {2} and gridReferenceY <= {3})",
    postalCode.GridReferenceX - radiusInMiles,
    postalCode.GridReferenceX + radiusInMiles,
    postalCode.GridReferenceY - radiusInMiles,
    postalCode.GridReferenceY + radiusInMiles);

  IList<PostalCode> allPostalCodes = BusinessClassesHelper.SelectObjects<PostalCode>(ServiceProvider, "PostalCode", criteria);
  return
    (
      from selectedPostalCode in allPostalCodes
      where postalCode.GetDistanceTo(selectedPostalCode) <= radiusInMiles
      select selectedPostalCode
    ).ToList<PostalCode>();
}



This first uses SQL to exclude all postal codes which cannot possibly be within the radius, then a simple LINQ query returns only the postal codes that are actually within the radius of the specific postal code. Another benefit is that this will also work for postal codes anywhere in the world, I could quite easily check how far (in a straight line) it is from my UK postal code to a US zip code!

No comments: