Найти ближайшее совпадение к массиву пар

Учитывая приведенный ниже код, как мне сравнить список значений объектов с тестовым значением?

Я создаю приложение геолокации. Я буду проходить по долготе и широте и хотел бы, чтобы служба ответила с местоположением, наиболее близким к этим значениям.

Я начал с преобразования в строку и форматирования значений до двух десятичных знаков, но это казалось слишком гетто, и я ищу более элегантное решение.

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
 }
Источник

4 ответа

Решение

Я нашел это, которое кто-то создал, который вычисляет расстояния между двумя расстояниями по всему земному шару, используя один из нескольких различных методов. Мне пришлось преобразовать проект.NET в обновленную версию VS2008, но, похоже, она работала нормально. Затем я просто добавил этот проект в свое решение и сделал ссылку на него.

Мой код стал:

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;
}
Источник

Вы захотите использовать правильную формулу расстояния для этого, если не хотите получать странные результаты:

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

Я надеюсь, что это правильная формула, моя математика может быть немного ржавой здесь. Все параметры должны быть в rads, поэтому, если вы берете ввод в градусах, напишите также служебный метод:

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

В любом случае, после этого вы можете определить кратчайшее расстояние как:

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

Технически это не самое эффективное решение, так как оно должно выполнять сортировку, но нет красивого метода расширения Linq, который бы делал min с проекцией. Если вы хотите этого, вам придется написать свой собственный foreach цикл:

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;
}
Источник

Насколько точно вы должны быть? Это называется Великим круговым расстоянием.

Смотрите, например, http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

Источник

Я думаю, что проще всего было бы сделать следующее. Но не самый производительный:)

Выполните итерацию по списку и рассчитайте расстояние между каждым местоположением и вашим ссылочным местоположением. На каждом шаге проверяйте, является ли это самое короткое расстояние, которое вы когда-либо видели, и сохраняйте его. Как только вы получите конец списка, у вас будет ближайшее местоположение в вашей сохраненной переменной.

Если вы говорите об очень большом количестве местоположений и планируете выполнять много пространственных запросов такого рода, вы можете подумать о создании индекса квадродерева для данных.

Вот ссылка, которую я нашел после быстрого "Bing", он должен помочь в расчете расстояния, я надеюсь. Пожалуйста, обратитесь по этой ссылке:

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

Источник
Другие вопросы по тегам