Geotag-Geopoint your Entities using Azure Mobile Services

Associating your data with geo-location information could unlock powerful and highly useful scenarios for your application.  In this blog post, I will discus how you can associate, persist and use geo-location data with your entities.  The usage scenario I will be covering is how you can retrieve entities closest to a geo-point.

But first, let’s review a few key concepts about geo-locations and calculation of distances.

News: The Earth isn’t flat!

If you think of the values of longitude and latitude as a Cartesian coordinate system (in 2 dimensions) calculating distances between two points is a simple calculation - thank you Pythagoras.

 

image

But as early Greeks correctly deducted, the Earth’s shape resembles a sphere –although not a perfect one, it’s more of a flattened sphere. So if we use a trigonometric approach to  calculate the distance between two points, we’ll be off as the distance between two geo points is not a straight line but an arc segment on the Earth’s curvature.  In mathematics this is called a great-circle distance.

 

image

A good computational approach to calculate the great-circle distance consists of using the Haversine formula.  This formula provides acceptable accuracy and is less susceptible to  computational rounding errors when compared to other mathematically correct approaches such as the spherical law of cosines. 

 

Note: The actual Earth’s shape is elliptical, dented at the poles, so although the Haversine formula assumes a perfect sphere, the results are acceptable for most cases. 

 

For the implementation, I will use the Haversine formula in combination with a trigonometric approach, that I will introduce for optimization reasons.

 

Enough of Math and Theory, show me the code

 

First I need to create a GeoPoint entity and associate it to my data entity.  In this example, I will be using the default template for Azure Mobile Services with a .NET backend.  The template has an implementation of a back end for a to-do list.  What this means is that I will be attaching geo-location information to to-do items.

Here’s the code for the GeoPoint and TodoItem entities.

 

 public class GeoPoint:EntityData
 {
        public double Latitude { get; set; }
        public double Longitude { get; set; }
  }

 public class TodoItem : EntityData
 {
        public string Text { get; set; }

        public bool Complete { get; set; }

        public virtual GeoPoint Location { get; set; }
 }

What’s really cool is that with this code and relaying on the existing TableController for my TodoItem entity , I can have my mobile application send TodoItems to my back end with geo information attached to them and the information will be persisted in the database, without any more coding!

With the data stored in a database, let’s expose an action that allows a client to retrieve the list of items closest to a geo location and within a maximum distance from it.

From the logic’s flow perspective, for each item in the database, I need to calculate the distance to the given geo-location and then check if it’s less than the maximum distance. Doing this for all the items, implies the need to enumerate all of them,  calculate the distance and check if it’s less than the maximum distance. 

Since calculating the actual distance using the Haversine formula is a complex mathematical operation,  in the code below, first I narrowed the list down by using a simpler trigonometric calculation . The trigonometric approach won’t provide an accurate distance so we can’t use it to determine if it’s within the maximum distance requested by the client, however it will provide the list of the closest items to the geo-point nevertheless.

From the narrowed list, I calculate the distance, using the Haversine formula and then determine if it’s within range and then return the items to the client.

 

Note: An additional benefit of this approach is that it also shares the burden of the calculation between  the application and database servers. If we calculate the Haversine result within the SQL statement then all the heavy lifting will reside on the database.

 

public IEnumerable<TodoItem> GetTodoItemsNearGeoPoint(double longitude, double latitude, int count, int maxDistance)
{
            var closest = Query()
               .OrderBy<TodoItem, double>(t => Math.Pow(longitude - t.Location.Longitude, 2) + Math.Pow(latitude - t.Location.Latitude, 2))
                .Take<TodoItem>(count);

            var withinMaxDistance = new List<TodoItem>();

            foreach (var item in closest)
            {
                var distance = CaculateGreatCircle(longitude, latitude, item.Location.Longitude, item.Location.Latitude);

                if (distance <= maxDistance)
                {
                    withinMaxDistance.Add(item);
                }

            }

            return withinMaxDistance;
        }

private double CaculateGreatCircle(double long1, double lat1, double long2, double lat2)
        {
            var R = 3959; //In Miles           
            var dlong = ToRadians(long1-long2);
            var dLat = ToRadians(lat1-lat2);
            var arc = Math.Sqrt(
                        Math.Pow(Math.Sin(dLat) / 2, 2)
                        +
                        Math.Cos(ToRadians(lat1)) *
                        Math.Cos(ToRadians(lat2)) *
                        Math.Pow(Math.Sin(dlong) / 2, 2)
                    );
            return R * 2 * Math.Atan2(arc,Math.Sqrt(1- arc));
                                       
        }

private double ToRadians(double value)
        {
            return Math.PI * value / 180;
        }

Finally,  please note that distance is assumed to be in Miles.

Conclusion

In this blog post, I show how you can easily associate geo location information to your objects using Azure Mobile Services as well as the implementation of server side logic to retrieve objects that are closest to a given geo-location.


2 Comments

Post Reply