Самый быстрый способ найти расстояние между двумя точками широты и долготы - PullRequest
Новая
       70

Самый быстрый способ найти расстояние между двумя точками широты и долготы

212 голосов
/ 17 июня 2009

В настоящее время в базе данных mysql у меня чуть меньше миллиона мест с информацией о долготе и широте.

Я пытаюсь найти расстояние между одной точкой и многими другими точками с помощью запроса. Это не так быстро, как я хочу, особенно с 100+ ударами в секунду.

Существует ли более быстрый запрос или, возможно, более быстрая система, кроме mysql для этого? Я использую этот запрос: 

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

Примечание. Указанное расстояние указано в милях . Если вам нужно Километры , используйте 6371 вместо 3959.

Ответы [ 16 ]

3 голосов
/ 03 марта 2016

Функция MySQL, которая возвращает количество метров между двумя координатами: 

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

Чтобы вернуть значение в другом формате, замените 6371000 в функции на радиус Земли в выбранной вами единице измерения. Например, километры будут 6371, а мили - 3959.

Чтобы использовать функцию, просто вызовите ее, как любую другую функцию в MySQL. Например, если у вас есть таблица city, вы можете найти расстояние между каждым городом и любым другим городом: 

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`
3 голосов
/ 04 сентября 2015

Прочитайте Geo Distance Search с MySQL , решение основанный на реализации формулы Haversine для MySQL. Это полное решение описание с теорией, реализацией и дальнейшей оптимизацией производительности. Хотя часть пространственной оптимизации не работала правильно в моем случае.

Я заметил две ошибки в этом:

  1. использование abs в операторе выбора на p8. Я просто опустил abs, и это сработало.

  2. функция расстояния пространственного поиска на p27 не конвертируется в радианы и не умножает долготу на cos(latitude), если только его пространственные данные не загружены с учетом этого (не может сказать из контекста статьи), но его пример на p26 указывает, что его пространственные данные POINT не загружены в радианах или градусах.

3 голосов
/ 22 ноября 2013

Вот очень подробное описание Geo Distance Search с MySQL - решения, основанного на реализации формулы Haversine для mysql. Полное описание решения с теорией, реализацией и дальнейшей оптимизацией производительности. Хотя часть пространственной оптимизации не работала правильно в моем случае. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

3 голосов
/ 29 июня 2012

Быстрое, простое и точное (для меньших расстояний) приближение может быть выполнено с помощью сферической проекции . По крайней мере, в моем алгоритме маршрутизации я получаю повышение на 20% по сравнению с правильным расчетом. В коде Java это выглядит так: 

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

Не уверен насчет MySQL (извините!).

Убедитесь, что вы знаете об ограничении (третий параметр assertEquals означает точность в километрах): 

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);
0 голосов
/ 16 января 2019

Использование mysql 

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

См .: https://andrew.hedges.name/experiments/haversine/

См .: https://stackoverflow.com/a/24372831/5155484

См .: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

ПРИМЕЧАНИЕ: LEAST используется, чтобы избежать нулевых значений в качестве комментария, предложенного для https://stackoverflow.com/a/24372831/5155484

0 голосов
/ 09 апреля 2015 
$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";
Страница:
...