Ближайшая координата GPS на основе расстояния от заданной точки

Question

У меня есть список местоположений GPS в базе данных сервера MySQL. Пользователь будет вводить GPS-координату в приложении, и он должен получить ближайшую GPS-координату.

Я не возражаю против вычисления расстояния, основанного на "полете вороны" или чем-то еще. Это должно быть достаточно быстро, чтобы искать тысячи местоположений GPS.

Я предпочитаю решение в C#, иначе я попытаюсь понять логику и применить себя.

Answer 1

Существует один вопрос по поиску по широте / дальности в MySQL в разделе Требуется помощь в оптимизации поиска по лат / ге для mysql

Для расчета расстояния C# большинство сайтов используют формулу Хаверсайна - вот реализация C# - http://www.storm-consultancy.com/blog/development/code-snippets/the-haversine-formula-in-c-and-sql/ - это также имеет реализацию SQL (MS SQL).

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

Для большинства запросов... вы, вероятно, в порядке, разделяя работу между C# и SQL

• используйте MySQL, чтобы выбрать "закрыть" точки широты и долготы, например, сказать, где широта и долгота находятся в пределах 1,0 от вашей цели
• затем используйте C#, чтобы рассчитать более точное расстояние и выбрать "лучшее".

Если бы вы использовали MS SQL 2008, то я бы порекомендовал использовать типы географии MS SQL, поскольку они имеют встроенные оптимизированные функции индексации и расчета - я вижу, что MySQL также имеет некоторые расширения - http://dev.mysql.com/tech-resources/articles/4.1/gis-with-mysql.html - но у меня нет опыта работы с ними.

Answer 2

То, что вы пытаетесь сделать, называется поиском ближайшего соседа, и есть много хороших структур данных, которые могут ускорить этот вид поиска. Например, вы можете захотеть взглянуть на kd-деревья, так как они могут дать ожидаемое сублинейное время (O(√ n) в двух измерениях) для запросов в наборе данных, ближайшем к некоторой произвольной контрольной точке. Их также удивительно легко реализовать, если вам удобно писать модифицированное двоичное дерево поиска.

Answer 3

Обратите внимание, что при работе со сферической геометрией наша евклидова геометрия не совсем точна (a^2+b^2=c^2), но для небольших частей Земли она может быть достаточно приблизительной.

В противном случае: http://en.wikipedia.org/wiki/Great-circle_distance

Answer 4

Если у вас есть данные координат, хранящиеся в базе данных, вы можете запросить базу данных напрямую, особенно если существует большой объем данных. Однако для этого вам нужна конкретная поддержка базы данных (обычные индексы не помогают). Я знаю, что MSSQL поддерживает данные о географии, я не тестировал MySQL, но онлайн-документация, похоже, также предлагает подобную поддержку. Как только вы создали пространственно-ориентированную базу данных, вы получите результаты с помощью простого запроса.