Nearest GPS coordinate based on distance from a given point

Question

I have a list of GPS locations in a MySQL server database. The user will be entering a GPS coordinate in the application and he should get the nearest GPS coordinate.

I don't mind the distance calculation is based on "crow's flight" or anything else. It should be fast enough to search thousands of GPS locations.

I prefer solution in C#, else I will try to get the logic and apply myself.

Answer 1

There's one question on MySQL lat/long distance search in Need help optimizing a lat/Lon geo search for mysql

For C# distance calculation, most sites use the Haversine formula - here's a C# implementation - http://www.storm-consultancy.com/blog/development/code-snippets/the-haversine-formula-in-c-and-sql/ - this also has a SQL (MS SQL) implementation too.

/// <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 };

For most queries... you are probably OK splitting the work between C# and SQL

• use MySQL to select "close" lat/lng points, e.g. say where lat and lng are within 1.0 of your target
• then use C# to calculate a more accurate distance and to select "the best".

If you were using MS SQL 2008 then I'd recommend using the MS SQL geography types as these have built-in optimised indexing and calculation features - I see that MySQL also has some extensions - http://dev.mysql.com/tech-resources/articles/4.1/gis-with-mysql.html - but I've no experience with these.

Answer 2

What you're trying to do is called a nearest-neighbor search and there are many good data structures which can speed up these sorts of searches. You may want to look into kd-trees, for example, as they can give expected sublinear time (O(√ n) in two dimensions) queries for the point in a data set nearest to some arbitrary test point. They're also surprisingly easy to implement if you're comfortable writing a modified binary search tree.