The Haversine Formula in C# and SQL: Distance between two points

Storm was recently asked to create a local office finder for a client.  We used the Google Maps API to geo-locate the offices, storing their lat/lng co-ordinates in a database.  Each time a customer performs a search for their town or post code we use the same process to their lat/lng co-ordinates as well.  Now we have the information we need, but how you find out which offices is closest to the customer?  We use the Haversine Formula.

As you can see if you visit the WikiPedia page, it’s not a simple formula!  However, it is beautifully elegant and a very fast solution to the problem.

During the course of development we worked on two versions of the code. Our first iteration had the office co-ordinates stored in an SQL Server database, later we moved to keeping them in an in-memory List<T>. Below are both versions of the code to calculate the Haversine distance.

MS SQL Server

SELECT TOP 1 *, ( 3960 * acos( cos( radians( @custLat ) ) *
  cos( radians( Lat ) ) * cos( radians(  Lng  ) - radians( @custLng ) ) +
  sin( radians( @custLat ) ) * sin( radians(  Lat  ) ) ) ) AS Distance
FROM Offices
ORDER BY Distance ASC

@custLat and @custLng are the variable co-ordinates of the customer.  Lat and Lng are the fields of the database table in which we have stored the office co-ordinates.  The above code calculates the distance in miles, if you want the answer in kilometers you need to replace 3960 with 6371. This could be parameterised in a Stored Procedure if you were feeling adventurous – there are plenty of example of this on the web already.

C#

In the following C# example, we use a simple enum to specify the unit of distance. We also need to convert the latitude and longitude from degrees to radians. We created a simple extension method for the double type to do this conversion.

    /// <summary>
    /// Returns the distance in miles or kilometers of any two
    /// latitude / longitude points.
    /// </summary>
    /// <param name="pos1">Location 1</param>
    /// <param name="pos2">Location 2</param>
    /// <param name="unit">Miles or Kilometers</param>
    /// <returns>Distance in the requested unit</returns>
    public double HaversineDistance(LatLng pos1, LatLng pos2, DistanceUnit unit)
    {
        double R = (unit == DistanceUnit.Miles) ? 3960 : 6371;
        var lat = (pos2.Latitude - pos1.Latitude).ToRadians();
        var lng = (pos2.Longitude - pos1.Longitude).ToRadians();
        var h1 = Math.Sin(lat / 2) * Math.Sin(lat / 2) +
                      Math.Cos(pos1.Latitude.ToRadians()) * Math.Cos(pos2.Latitude.ToRadians()) *
                      Math.Sin(lng / 2) * Math.Sin(lng / 2);
        var h2 = 2 * Math.Asin(Math.Min(1, Math.Sqrt(h1)));
        return R * h2;
    }

    public enum DistanceUnit { Miles, Kilometers };

A simple helper class is used to pass around Longitude / Latitude co-ordinates:

    /// <summary>
    /// Specifies a Latitude / Longitude point.
    /// </summary>
    public class LatLng
    {
        public double Latitude { get; set; }
        public double Longitude { get; set; }

        public LatLng(){
        }

        public LatLng(double lat, double lng)
        {
            this.Latitude = lat;
            this.Longitude = lng;
        }
    }

To use the function to perform the search we grab an array of offices, loop over them calculating the distance to the customer and use LINQ to select the closest office.

    var Offices = GetMyOfficeList();
    for(int i = 0; i< Offices.Count; i++)
    {
        Offices[i].Distance = HaversineDistance(
                                coord,
                                new LatLng(Offices[i].Lat, Offices[i].Lng),
                                DistanceUnit.Miles);
    }

    var closestOffice = Offices.OrderBy(x => x.Distance).Take(1).Single();

By Adam Pope

Adam is our tech God, and it's not just his name that's holy - his knowledge of code borders on the supernatural, and whilst he doesn't like to brag, he finished top of his class at university. (Yep, the very top).

When he isn't crafting masterpieces on the web he is knocking them up in the kitchen, his legendary curry being an office mainstay here at Storm.

Adam was recently named as one of South West Business Insider's 42 under 42 for 2012.

stormconsultancy.co.uk →

6 comments

  1. Great!!! This article was very useful!!! I spent a hole week looking for this! Thank you!!!

  2. This article is amazing! Thank you for your wonderful help. I don’t mean to be rude, but could you help by putting together an example, with an example DB schema and data?

    :-)

  3. i am working on geolocation project and this article is very helpfull. if its possible could u share ur complete code about this article? i am mean where GetMyOfficeList come from? or u can send mail to me.thanks for your article.

  4. Hi Ben,

    GetMyOfficeList is not really in my code, it was just put in for the example. The idea is that you have a function which is querying your database and returns an array of Office objects. The Office class has to have Lat and Lng properties for the next line to work.

    Hope that helps
    Adam

  5. Thanks this snippet is extremely useful :D

    Do you know how to calculate the width and height (in degrees minutes) of a Google Static Maps image?

    I’ve found it extremely difficult. The only information you have is:
    - The centre of the image (at a Longitude Latitude coordinate)
    - The zoom level of the satellite (1 <- zoom <= 25)
    - The width and height of the image in pixels

    See this image for a visual explanation of the problem: http://i39.tinypic.com/nv8741.jpg

    And from this its very difficult to calculate the image dimensions in degrees minutes, mainly because the zoom level heights (in feet or metres) is not exposed by google AFAIK. If you could do a post about this problem I believe it would be extremely useful to people.