find nearest match to array of doubles

Question

Given the code below, how do I compare a List of objects's values with a test value?

I'm building a geolocation application. I'll be passing in longitude and latitude and would like to have the service answer back with the location closest to those values.

I started down the path of converting to a string, and formatting the values down to two decimal places, but that seemed a bit too ghetto, and I'm looking for a more elegant solution.

public class Location : IEnumerable
{
    public string label { get; set; }
    public double lat { get; set; }
    public double lon { get; set; }

    //Implement IEnumerable
    public IEnumerator GetEnumerator()
    {
        return (IEnumerator)this;
    }

}
[HandleError]
public class HomeController : Controller
{
    private List<Location> myList = new List<Location>
 {             
    new Location {
        label="Atlanta Midtown", 
        lon=33.657674, 
        lat=-84.423130},
    new Location {
        label="Atlanta Airport", 
        lon=33.794151, 
        lat=-84.387228},
    new Location {
        label="Stamford, CT", 
        lon=41.053758, 
        lat=-73.530979}, ...
}

 public static int Main(String[] args)
 {
     string inLat = "-80.987654";
     double dblInLat = double.Parse(inLat);

     // here's where I would like to find the closest location to the inLat
     // once I figure out this, I'll implement the Longitude, and I'll be set
 }

Answer 1

You're going to want to use the correct distance formula for this if you don't want to end up with weird results:

double CalculateDistance(double lat1, double lon1, double lat2, double lon2)
{
    const double R = 6371;
    return Math.Acos(
        Math.Sin(lat1) * Math.Sin(lat2) +
        Math.Cos(lat1) * Math.Cos(lat2) * Math.Cos(lon2 - lon1)) * R;
}

I hope that's the right formula, my math might be a little rusty here. All of the parameters need to be in rads, so if you're taking inputs in degrees, write a utility method as well:

double DegToRad(double deg)
{
    return deg * Math.PI / 180.0;
}

Anyway, after that, you can figure out the shortest distance as:

Location GetClosestLocation(Location origin)
{
    double olatr = DegToRad(origin.Lat);
    double olonr = DegToRad(origin.Lon);
    return
        (from l in locations
         let latr = DegToRad(l.Lat)
         let lonr = DegToRad(l.Lon)
         orderby CalculateDistance(latr, lonr, olatr, olonr))
        .FirstOrDefault();
}

This isn't technically the most performant solution, since it has to do a sort, but there's no nice-looking Linq extension method to do min with a projection. If you want that, you'll have to write your own foreach loop:

Location GetClosestLocation(Location origin)
{
    double olatr = DegToRad(origin.Lat);
    double olonr = DegToRad(origin.Lon);
    Location closest = null;
    double minDistance = double.MaxValue;
    foreach (Location l in locations)
    {
        double latr = DegToRad(l.Lat);
        double lonr = DegToRad(l.Lon);
        double dist = CalculateDistance(latr, lonr, olatr, olonr));
        if (dist < minDistance)
        {
            minDistance = dist;
            closest = l;
        }
    }
    return closest;
}

Answer 2

I think the easiest would be to do the following. But not most performant :)

Iterate through the list and calculate the distance between each location and your reference location. At each step, check to see if this is the shortest distance you have seen so far and store that. Once you get the the end of the list, you will have the closest location in your stored variable.

If you are talking about a very large number of locations and you plan to do many spacial queries of this nature you might consider setting up a quadtree index on the data.

Here is a link I found after doing a quick 'Bing', it should help with the distance calculation, I hope. Please refer this Link:

http://www.delphiforfun.org/Programs/Math_Topics/Lat-Long%20Distance.htm

Answer 3

How accurate do you need to be? It's called the Great Circle Distance.

See for example http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

Answer 4

I found this which someone created that calculates distances between two distances across the globe using one of several different methods. I had to convert the .NET project to the updated VS2008, but that seemed to work fine. Then I just added this project to my solution and made a reference to it.

My code then became:

string inLat = "-80.987654";
string inLon = "33.521478";
var miles = GetNearestLocation(inLat, inLon);

public double GetNearestLocation(string lat, string lon)
{
    double dblInLat = double.Parse(lat);
    double dblInLon = double.Parse(lon);

    // instantiate the calculator
    GeodeticCalculator geoCalc = new GeodeticCalculator();

    // select a reference elllipsoid
    Ellipsoid reference = Ellipsoid.WGS84;

    // set user's current coordinates
    GlobalCoordinates userLocation;
    userLocation = new GlobalCoordinates(
        new Angle(dblInLon), new Angle(dblInLat)
    );

    // set example coordinates- when fully fleshed out, 
    //    this would be passed into this method
    GlobalCoordinates testLocation;
    testLocation= new GlobalCoordinates(
        new Angle(41.88253), new Angle(-87.624207) // lon, then lat
    );

    // calculate the geodetic curve
    GeodeticCurve geoCurve = geoCalc.CalculateGeodeticCurve(reference, userLocation, testLocation);
    double ellipseKilometers = geoCurve.EllipsoidalDistance / 1000.0;
    double ellipseMiles = ellipseKilometers * 0.621371192;
    /*
    Console.WriteLine("2-D path from input location to test location using WGS84");
    Console.WriteLine("   Ellipsoidal Distance: {0:0.00} kilometers ({1:0.00} miles)", ellipseKilometers, ellipseMiles);
    Console.WriteLine("   Azimuth:              {0:0.00} degrees", geoCurve.Azimuth.Degrees);
    Console.WriteLine("   Reverse Azimuth:      {0:0.00} degrees", geoCurve.ReverseAzimuth.Degrees);
    */
    return ellipseMiles;
}