Curls, clouds and code

Representing coordinates in a human readable way

Download the source-code here!
In order to get you up and running quickly you can find the gist of the code here or download a zip containing the LinqPad snippet here.

0. Contents

  1. Introduction
  2. The plan
  3. The code
    3.1 Resolving landmarks
    3.2 Mathematical background
    3.3 Calculating the distance between points
    3.4 Calculating the angle between points
    3.5 The result

1. Introduction

A single coordinate is just a set of numbers indicating a location in a grid of a certain dimension. These numbers themselves are intuitive for humans to interpret at all. We’re going to explore how to turn these numbers into a textual representation which can easily be understood by the common people. While the precision of the coordinate system is higher and more exact, I for myself would be happy if I can tell the difference between Amsterdam, Paris and Berlin based on a set of coordinates.

For more information about the accuracy each decimal in a coordinate represents, see this answer on the GIS StackExchange.

We’re going to try something different. As we can say human interpretation of coordinates is shit, why not try to represent coordinates as something which is nuts for a computer to work with, but actually useful for humans to interpret.

We are going to translate a coordinates into a textual representation which describes the position relative to a known landmark (e.g. a city or mountain). This has been inspired by the way positions are communicated over the radio in aviation.

Aside; if you want to get to know or refresh your knowledge about radio technique in aviation, check out this guide, appropriately called “VFR COMMUNICATIONS FOR IDIOTS”.

2. The plan

My primary use case for this technique will be aviation related. Aircraft are moving all the time, and considering separation of gliders happens visually (meaning the pilots just have to look outside) an accuracy of about 2km is good enough for me.

As we will be using local reference points our result shall be something in the likes of “2 miles north of Steenbergen at 1200 feet”. This little line contains all the information we need to accurately identify a location:

  1. A local (well known) reference point.
  2. A direction from the reference point (360 degrees).
  3. A certain distance from the reference point following the heading.
  4. An altitude. Always easy in aviation.

We could always add more information about the movements of the aircraft (like heading north-northwest at 50 knots), but that should be trivial in relation to this post.

3. The code

We’re going to write a little library which will solve most of the problems of translating coordinates to a human readable format. A while ago I made a pull-request to the Humanizer repository which added degree-heading to word capabilities, which will help us along the way later.

3.1 Resolving landmarks

First we have to retrieve data about local landmarks. Essentially what we need is a dictionary (list of key-value pairs) which contain coordinates and a label. Thankfully there are sources on the internet which provide databases of (big) cities and their coordinates we will use for this post. One of these is the GeoNames project. You can download various types of files for free from here. The file I go with is the `cities5000.zip` file in order to get a text file which contains all cities with more than 5000 inhabitants.

There are various ways to efficiently filter through a dictionary with location data. For starters I would recommend putting this information in a database and to use the database engine to do spatial queries. I am not going to cover this, and for the sake of the demo I’ll just use a `Dictionary` to store and filter the data in-memory.

We will need a helper method to filter out the cities closest to a given location. Since NTS (NetTopologySuite) is super useful in general when dealing with spatial data we’re using it’s K-D tree implementation for filtering through location data.

Using it is not too difficult. Honestly, in a few lines we could populate it and find the nearest position to a point. Don’t mind my helper methods. You’ll get the gist of it.

var tree = new KdTree<LocationEntry>();

GeoNames.ExtractData(file)
    .ToList()
    .ForEach((i) => tree.Insert(new Coordinate(i.Latitude, i.Longitude), i));

var landmark = tree.NearestNeighbor(coordinate);

3.2 Mathematical background

We need to know the angle from the point of reference to the coordinate we want to make more human readable. The math to do this has been figured out by people way smarter than me and has been around for a long time. There is this website that does a great job explaining latitudal/longitudal calculations, and I recommend you check it out if you want to know all about it. It features some interactive calculations and shows the math right there with some calculation.

3.3 Calculating the distance between points

In order to calculate the distance we use the haversine formula to calculate the shortest route over a sphere between two points, also known as the short circle distance.

The following code is derived from the GeoCoordinate class in the System.Device.Location namespace (System.Device.dll assembly). A .NET Standard port can be found here.

public static double DistanceTo(double lat1, double long1, double lat2, double long2)
{
    if (double.IsNaN(lat1) || double.IsNaN(long1) || double.IsNaN(lat2) ||
        double.IsNaN(long2))
    {
        throw new ArgumentException("Argument latitude or longitude is not a number");
    }

    var d1 = lat1 * (Math.PI / 180.0);
    var num1 = long1 * (Math.PI / 180.0);
    var d2 = lat2 * (Math.PI / 180.0);
    var num2 = long2 * (Math.PI / 180.0) - num1;
    var d3 = Math.Pow(Math.Sin((d2 - d1) / 2.0), 2.0) +
                Math.Cos(d1) * Math.Cos(d2) * Math.Pow(Math.Sin(num2 / 2.0), 2.0);

    return 6376500.0 * (2.0 * Math.Atan2(Math.Sqrt(d3), Math.Sqrt(1.0 - d3)));
}

3.4 Calculating the angle between points

In order to calculate the angle between two points we use a “rhumb line”. The rhumb line is a line you can follow from one point to another by following the same compass heading. Note that this is not the short circle distance, which we talked about earlier. For most applications the distances are so small that it doesn’t really matter anyway.

The following code to calculate the angle of the rhumb line is copied from this StackOverflow answer.

public static double DegreeBearing(
        double lat1, double lon1,
        double lat2, double lon2)
{
    var dLon = ToRad(lon2 - lon1);
    var dPhi = Math.Log(
        Math.Tan(ToRad(lat2) / 2 + Math.PI / 4) / Math.Tan(ToRad(lat1) / 2 + Math.PI / 4));
    if (Math.Abs(dLon) > Math.PI)
        dLon = dLon > 0 ? -(2 * Math.PI - dLon) : (2 * Math.PI + dLon);
    return ToBearing(Math.Atan2(dLon, dPhi));
}

public static double ToRad(this double degrees)
{
    return degrees * (Math.PI / 180);
}

public static double ToDegrees(this double radians)
{
    return radians * 180 / Math.PI;
}

public static double ToBearing(this double radians)
{
    // convert radians to degrees (as bearing: 0...360)
    return (ToDegrees(radians) + 360) % 360;
}

It might be interesting to you to figure out the difference between “heading”, “bearing” and “course” if you do not already know. Someone described the differences here.

3.5 The result

I bet you could come up with this yourself, but essentially we have all the individual components to for a textual representation of a coordinate.

We figured out:

It’s fairly simple to put it together now:

var text = $"{distance}km {bearing.ToHeading(HeadingStyle.Full)} of {landmark.Data.Name}";

Which might result in “3km south of Bergen op Zoom”.

Generic data loaders for Entity Framework in GraphQL

This article contains specific information potentially useful for users of both the GraphQL .NET and Entity Framework Core libraries. This article described the process to get by the result. If you just want inspiration for a generic data loader, feel free to skip to the end.

GraphQL is an amazing framework for creating (re)usable API’s. Don’t ask me why, but I ended up stuck with Entity Framework Core as my data access layer. When you are trying to develop a well thought out, usable and performant API you will get to use the data loader rather sooner than later.

Figuring out how to work with the data loader I absolutely refuse to write the same kind of code over and over again. I did not feel like writing a different data loader resolver for each and every entity type I need to retrieve in my API. If this is also the case for you, read on!

The dataloader itself

Feel free to skip this part if you know about the dataloader. This part is mainly for people just starting out with the dataloader, or completely unfamiliar with it.

Just to refresh on the data loader mechanism shipped with the GraphQL.net library. This mechanism is only there to help you retrieve data somewhat efficiently in batches. Imagine the following data structure (from one of my hobby projects):

flight {
    departure {
        airfield {
            name
        }
        time
    }
    arrival {
        airfield {
            name
        }
        time
    }
}

The departure and arrival objects are of the same type, but represent a different piece of information. The way this information would be retrieved without dataloader is as follows:

  1. All queried flights are retrieved from the database
  2. For each flight result a database request for departure information is made
    • This departure type requests information about the airfield this flight departed from
  3. For each flight another request for it’s arrival information is made
    • For which a request for airfield information is made again.

For a single result in the result set (which is usually about 20 items long), about 5 requests need to be made. For a full page of information this results in 100 database roundtrips, which obviously is not performant.

Assuming we have a 15ms latency to the database server from our dev machine, and each database call takes about 5ms, this would become a 2 second call. All but performant.

By using the dataloader to batch our requests based on the entities we are loading we can reduce this to three different calls (3% of the previous number of roundtrips):

  1. A call for the flight entities
  2. A request to retrieve flight information (departure and arrival)
  3. A request for airfield information

We’ll get to the technical implementation of a dataloader later in the aricle.

What do we need?

There is something common about every data loader I have ever written. It’s either one of the following two:

Practical examples include these queries:

q => ids.Contains(q.Id)

or

q => ids.Contains(q.ParentId)

The differences are in the way we load the data. The first one will usually have a 1:1 mapping, while the 2nd example will usually involve a 1:many relationship. The common ground is that we always aim to retrieve a single entity type. There are only a few differences in each data loader method we usually have to write manually:

  1. The type of data loader being initialized
  2. The type for which we create the dataloader
  3. The predicate provided

Working with expression trees

LINQ queries are totally amazing! I love them, and I’d prefer to use these above weakly typed strings any time. In my GraphQL endpoints I only care about the data I want to request, and not so much the implementation details related to the dataloader. Therefore my goal: I want to provide a predicate, and a value for provided predicate, and retrieve all records where this evaluates to true.

I found using LinqPad highly beneficial while working with expression trees. You can easily dump the result of a subexpression to see what you’re working with.

The predicate shall be provided in the Expression<Func<T, TKey>> form. This could be used to provide a LINQ predicate like q => q.Id.

We face two problems:

  1. In order to be able to query data we need to use the Expression<Func<T, TKey>> in a way that we get to a Expression<Func<T, bool>> in order to use it as argument in the IQueryable<T>.Where(Expression<Func<T, bool>>) method. It can be compared with writing a T.Where(q => q.Id == 1) query.
  2. We do not only need to write a where query, but we need to compare values from a database to a list we created locally. (EF Core will translate this into a SQL IN ('', '', ...) statement.)

The combination of those two is interesting because we are going to be calling value methods through expression trees.

The code we would usually be writing will look a bit like this:

dbSet.Where(q => list.Contains(q.Id));

Let’s go through our variant built with expression trees.

Calling the contains method

var containsExpression = Expression.Call(
    Expression.Constant(ids),
    typeof(ICollection<TValue>)
        .GetMethod("Contains", new[] { typeof(TValue) }),
    predicate.Body
);

The Expression.Call method takes 3 arguments:

  1. The object to call a method on (of the type ICollection<TValue>)
  2. The method to call (on a type of ICollection<TValue>, with a single argument of TValue)
  3. The arguments (in this case of TValue) to invoke the method with.

If we were to dump the contents of the predicate body in LinqPad we can see what it could look like:

Expression body contents

The result we have now would look like the list.Contains(q.Id) section of a linq query. It will form the body of our LINQ final query.

Building the full expression

What’s left for us to do is to wrap the call in a where clause, and provide an actual value to run the expression with. This actual value will be provided by the .Where linq method.

var expression = Expression.Lambda<Func<T, bool>>(
    containsExpression,
    predicate.Parameters
);

As predicate.Parameters seems pretty vague at first sight; it’s nothing more than this data structure, which tells us variable q represents the type of Flight (it can be any type you want it to be if it’s generic):

predicate.Parameters

The full result

So to make a quick recap, these are the extension methods I am using to create a data-loader for a certain type.

public static class GenericDataLoader
{
    public static Expression<Func<T, bool>> MatchOn<T, TValue>(
        this ICollection<TValue> items,
        Expression<Func<T, TValue>> predicate)
    {
        return Expression.Lambda<Func<T, bool>>(
            Expression.Call(
                Expression.Constant(items),
                typeof(ICollection<TValue>).GetMethod("Contains", new[] { typeof(TValue) }),
                predicate.Body
            ),
            predicate.Parameters
        );
    }

    /// <summary>
    /// Register a dataloader for T by the predicate provided.
    /// </summary>
    /// <typeparam name="T">The type to retrieve from the DbSet</typeparam>
    /// <typeparam name="TValue">The value to filter on</typeparam>
    /// <param name="dataLoader">A dataloader to use</param>
    /// <param name="dbSet">Entity Framework DbSet</param>
    /// <param name="predicate">The predicate to select a key to filter on</param>
    /// <param name="value">Value to filter items on</param>
    /// <returns>T as specified by the predicate and TValue</returns>
    public static async Task<T> EntityLoader<T, TValue>(
        this IDataLoaderContextAccessor dataLoader,
        DbSet<T> dbSet,
        Expression<Func<T, TValue>> predicate,
        TValue value)
        where T : class
    {
        if (value == null) return default;

        var loader = dataLoader.Context.GetOrAddBatchLoader<TValue, T>(
            $"{typeof(T).Name}-{predicate.ToString()}",
            async (items) =>
        {
            return await dbSet
                .AsNoTracking()
                .Where(items
                    .ToList()
                    .MatchOn(predicate))
                .ToDictionaryAsync(predicate.Compile());
        });

        var task = loader.LoadAsync(value);
        return await task;
    }

    /// <summary>
    /// Register a dataloader for an IEnumerable<T> by the predicate provided.
    /// </summary>
    /// <typeparam name="T">The type to retrieve from the DbSet</typeparam>
    /// <typeparam name="TValue">The value to filter on</typeparam>
    /// <param name="dataLoader">A dataloader to use</param>
    /// <param name="dbSet">Entity Framework DbSet</param>
    /// <param name="predicate">The predicate to select a key to filter on</param>
    /// <param name="value">Value to filter items on</param>
    /// <returns>IEnumerable<T> as specified by the predicate and TValue</returns>
    public static async Task<IEnumerable<T>> EntityCollectionLoader<T, TValue>(
        this IDataLoaderContextAccessor dataLoader,
        DbSet<T> dbSet,
        Expression<Func<T, TValue>> predicate,
        TValue value)
        where T : class
    {
        if (value == null) return default;

        var loader = dataLoader.Context.GetOrAddCollectionBatchLoader<TValue, T>(
            $"{typeof(T).Name}-{predicate.ToString()}",
            async (items) =>
        {
            var compiledPredicate = predicate.Compile();

            return dbSet
                .AsNoTracking()
                .Where(items
                    .ToList()
                    .MatchOn(predicate))
                .ToLookup(compiledPredicate);
        });

        var task = loader.LoadAsync(value);
        return await task;
    }
}

To summarize above code:

What’s next?

As I’m progressing with the GraphQL dotnet library I’m starting to understand more and more about the design principles used while building this framework. This enables me to abstract more logic away than ever before. Right now I’m working on some additional general purpose data-loaders and I’m planning to release them as NuGet package somewhere soon.

I’ll let you know when this library is available.