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();