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

227

В настоящее время у меня есть чуть менее миллиона мест в базе данных 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.

Райан Детцель
источник
31
Формула, которую вы даете, кажется, содержит много постоянных элементов. Можно ли предварительно рассчитать данные и сохранить эти значения в вашей БД? Например, 3959 * acos (cos (радианы (42.290763)) является константой, но в ней есть 4 основных вычисления. Вместо этого вы можете просто хранить 6696.7837?
Peter M
1
Или хотя бы предварительно вычислить константы вне запроса? Это сократит объем работы, которая должна быть выполнена.
Питер М
2
@Peter M Кажется вероятным, что любая приличная база данных SQL оптимизировалась бы так, чтобы ее вычисляли только один раз.
mhenry1384
25
Для тех, кто интересуется, 42.290763 - это широта, а -71.35368 - это долгота точки, из которой вычисляются расстояния.
user276648
14
Для справки: Расстояние, рассчитанное по этой формуле, указывается в милях, а не в километрах. Пожалуйста, замените 3959 на 6371, чтобы получить результаты в километрах
Сахил

Ответы:

115
  • Создайте свои очки, используя Pointзначения Geometryтипов данных в MyISAMтаблице. Начиная с Mysql 5.7.5, InnoDBтаблицы теперь также поддерживают SPATIALиндексы.

  • Создать SPATIALиндекс по этим точкам

  • Используйте, MBRContains()чтобы найти значения:

    SELECT  *
    FROM    table
    WHERE   MBRContains(LineFromText(CONCAT(
            '('
            , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
            , ' '
            , @lat + 10 / 111.1
            , ','
            , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
            , ' '
            , @lat - 10 / 111.1 
            , ')' )
            ,mypoint)

или, внутри MySQL 5.1и выше:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

Это выберет все точки примерно в пределах окна (@lat +/- 10 km, @lon +/- 10km).

На самом деле это не прямоугольник, а сферический прямоугольник: связанный с широтой и долготой сегмент сферы. Это может отличаться от простого прямоугольника на Земле Франца-Иосифа , но довольно близко к нему в большинстве населенных мест.

  • Примените дополнительную фильтрацию, чтобы выделить все внутри круга (не квадрата)

  • Возможно применение дополнительной тонкой фильтрации для учета большого круга (для больших расстояний)

Quassnoi
источник
15
@Quassnoi: пара исправлений: вы, вероятно, захотите переключить порядок координат на lat, long. Кроме того, продольные расстояния пропорциональны косинусу широты , а не долготы. И вы захотите изменить его с умножения на деление, поэтому ваша первая координата будет исправлена ​​как @lon - 10 / ( 111.1 / cos(@lat))(и будет второй в паре, когда все будет правильно.
М. Дейв Ауаян,
8
ВНИМАНИЕ : Основная часть ответа НЕ была отредактирована в соответствии с очень правильным комментарием, сделанным @M. Дейв Ауаян. Дополнительные примечания: этот метод становится грушевидным, если круг интересов (а) включает в себя полюс или (b) пересекается меридианом долготы +/- 180 градусов. Также использование cos(lon)является точным только для небольших расстояний. См. Janmatuschek.de/LatitudeLongitudeBoundingCoordinates
Джон Мачин
3
Можно ли каким-то образом понять, что представляют собой константы (10, 111.11, @lat, @lon, mypoint)? Я предполагаю, что 10 для расстояния в километрах, @lat и @lon представляют предоставленную широту и долготу, но что представляют 111.11 и mypoint в примере?
Ashays
4
@ashays: есть примерно 111.(1)км в градусе широты. mypointполе в таблице, в котором хранятся координаты
Quassnoi
1
Другая коррекция ошибок - вам не хватает закрытия) на секунду до последней строки
ИНА
100

Не специфичный для MySql ответ, но он улучшит производительность вашего оператора SQL.

То, что вы эффективно делаете, это вычисление расстояния до каждой точки в таблице, чтобы увидеть, находится ли оно в пределах 10 единиц от данной точки.

То, что вы можете сделать перед запуском этого sql, это создать четыре точки, которые нарисуют прямоугольник на 20 единиц на стороне, с вашей точкой в ​​центре, т.е. (х1, у1). , , (x4, y4), где (x1, y1) - это (дано + 10 единиц, дано +10 единиц). , , (дано долго - 10 единиц, дано - 10 единиц). На самом деле, вам нужны только две точки, верхний левый и нижний правый вызов их (X1, Y1) и (X2, Y2)

Теперь ваш оператор SQL использует эти точки, чтобы исключить строки, которые определенно находятся на расстоянии более 10u от вашей заданной точки, он может использовать индексы по широтам и долготам, поэтому будет на несколько порядков быстрее, чем у вас в настоящее время.

например

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

Боксовый подход может возвращать ложные срабатывания (вы можете подобрать точки в углах поля, которые находятся на расстоянии> 10u от заданной точки), поэтому вам все равно нужно рассчитать расстояние до каждой точки. Однако это снова будет намного быстрее, потому что вы резко ограничили количество проверяемых точек до точек внутри блока.

Я называю эту технику «Мышление внутри коробки» :)

РЕДАКТИРОВАТЬ: это можно поместить в один оператор SQL?

Я понятия не имею, на что способны mySql или Php, извините. Я не знаю, где лучше всего построить четыре точки или как их можно передать в запрос mySql в Php. Однако, когда у вас есть четыре пункта, ничто не помешает вам объединить свой собственный оператор SQL с моим.

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 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

Я знаю, что с помощью MS SQL я могу построить оператор SQL, который объявляет четыре числа с плавающей запятой (X1, Y1, X2, Y2) и вычисляет их перед «основным» оператором выбора, как я уже сказал, я понятия не имею, можно ли это сделать с помощью MySql. Однако я все же был бы склонен построить четыре точки в C # и передать их в качестве параметров в SQL-запрос.

Извините, я не могу помочь, если кто-то может ответить на определенные части MySQL и Php этого, не стесняйтесь редактировать этот ответ, чтобы сделать это.

Двоичный Беспорядок
источник
4
Вы можете найти процедуру mysql для этого подхода в этой презентации: scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
Lucia
37
Для поиска по километрам вместо миль замените 3959 на 6371.
ErichBSchulz
4
+1, отличный вариант; добавление поля уменьшило мой запрос с 4 до 0,03 с.
Jvenema
1
Хотя это кажется такой логичной, вы оставляете за собой награду за это решение! В базе данных с записями в 2 миллиона человек запрос увеличился с 16 до 0,06 секунды. Примечание: это даже быстрее (для больших таблиц), если вы вырезаете вычисление расстояния из запроса и выполняете вычисление для расстояния в программном коде!
NLAnaconda
2
@Binary Worrier: Значит, X1, X2 и Y1, Y2 будут Минутой и Макс. Долготы и Минутами и Макс. Широтой в соответствии с приведенным здесь примером: blog.fedecarg.com/2009/02/08/… пожалуйста, сообщите.
Прабхат
14

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

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(
  geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), 
  geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) 
    + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) 
    * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) 
    * 60 * 1.1515);
END $$

DELIMITER ;

Пример использования:

Предположим, что таблица вызывается placesс полями latitude& longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;
Брэд Паркс
источник
Я попробовал это, и это работает отлично, но почему-то это не позволяет мне вставить оператор WHERE, основанный на distance_from_input. Есть идеи почему бы и нет?
Крис Виссер
Вы можете сделать это как дополнительный выбор: выберите * из (...) как t где distance_from_input> 5;
Брэд Паркс
2
или просто прямо: выберите * из мест, где get_distance_in_miles_between_geo_locations (-34.017330, 22.809500, широта, долгота)> 5000;
Брэд Паркс
2
Метры возвращения:SELECT ROUND(((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lnt1 - lnt2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) * 1.609344 * 1000) AS distance
Мохаммед
13

Мне нужно было решить аналогичную проблему (фильтрация строк по расстоянию от одной точки), и, комбинируя оригинальный вопрос с ответами и комментариями, я нашел решение, которое идеально подходит для меня как на MySQL 5.6, так и на 5.7.

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinatesПоле с типом POINTи имеет SPATIALиндекс
6371для расчета расстояния в километрах.
56.946285Широта для центральной точки.
24.105078Долгота для центральной точки.
15Максимальное расстояние в километрах.

В моих тестах MySQL использует SPATIAL index для coordinatesполя, чтобы быстро выбрать все строки, которые находятся внутри прямоугольника, а затем вычисляет фактическое расстояние для всех отфильтрованных мест, чтобы исключить места из углов прямоугольников и оставить только места внутри круга.

Это визуализация моего результата:

карта

Серые звезды визуализируют все точки на карте, желтые звезды возвращаются по запросу MySQL. Серые звезды внутри углов прямоугольника (но за пределами круга) были выбраны MBRContains()и затем отменены HAVING.

Марис Киселовс
источник
Не могу отказать этому достаточно. При поиске в таблице с приблизительно 5 миллионами записей и пространственным индексом с помощью этого метода время поиска составляет 0,005 секунды на старом процессоре A8. Я знаю, что 6371 можно заменить на 3959, чтобы получить результаты в милях, но нужно ли корректировать значения 111.133 и 111.320 или они являются универсально постоянными?
Wranorn
Отличное решение.
SeaBiscuit
Как создать Point это POINT (лат, lng) или POINT (lng, лат)
user606669
2
@ user606669 Это ТОЧКА (lng, lat)
Марис Киселов
В настоящее время функции X () и Y () должны быть ST_Y и ST_X.
Андреас
11

если вы используете MySQL 5.7. *, то вы можете использовать st_distance_sphere (POINT, POINT) .

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance
alriyami
источник
1
Это очень хорошая и легко читаемая альтернатива. имейте в виду, что для POINT () порядок параметров равен (lng, lat), в противном случае вы можете получить "close", но все же результаты, отличные от других методов здесь см .: stackoverflow.com/questions/35939853/…
Энди П
9
SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

Это запрос вычисления расстояния между точками в MySQL, я использовал его в длинной базе данных, он работает отлично! Примечание: внесите изменения (имя базы данных, имя таблицы, столбец и т. Д.) В соответствии с вашими требованиями.

Санни Пория
источник
Что представляет собой значение 1.1515? Я видел подобную формулу раньше, но она использовала 1,75 вместо 1,1515.
TryHarder
1
В ответ на мой собственный вопрос, я думаю, что ответ может лежать здесь stackoverflow.com/a/389251/691053
TryHarder
8
set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

источник

Abhigyan
источник
11
Пожалуйста, приведите ваши источники. Это от: blog.fedecarg.com/2009/02/08/…
redburn
Что такое 69 в этом случае? Как это сделать в случае, если у нас есть радиус Земли?
CodeRunner
2
Километр в 1 латиттуде - 111 км. Миля в 1 латиттуде составляет 69 миль. и 69 миль = 111 км. Вот почему мы использовали параметры в преобразованиях.
CodeRunner
Я искал это всегда. Не знал, что это может быть так просто. Огромное спасибо.
Викас
Разве это не было бы неправильно, поскольку lng_min / lng_max должен был бы использовать lat_min и lat_max в математике радиуса?
Бен
6
   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;
user3113927
источник
5

Функция 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`
Роберт
источник
4

Полный код с подробной информацией о том, как установить плагин MySQL, находится здесь: https://github.com/lucasepe/lib_mysqludf_haversine

Я опубликовал это в прошлом году как комментарий. Так как любезно @TylerCollier предложил мне опубликовать как ответ, вот оно.

Другой способ - написать пользовательскую функцию UDF, которая возвращает расстояние боярышника от двух точек. Эта функция может принимать на входе:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

Таким образом, мы можем написать что-то вроде этого:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

получить все записи с расстояния менее 40 километров. Или:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

получить все записи с расстояния менее 25 футов.

Основная функция:

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}
Лука Сепе
источник
3

Быстрое, простое и точное (для меньших расстояний) приближение может быть выполнено с помощью сферической проекции . По крайней мере, в моем алгоритме маршрутизации я получаю повышение на 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);
Karussell
источник
3

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

Константин Воронов
источник
3

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

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

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

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

Ричард Сандос
источник
0
$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";
Нирадж Шарма
источник
0

Использование 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/experiment/haversine/

Смотрите: https://stackoverflow.com/a/24372831/5155484

Смотрите: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

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

Уильям Деспортес
источник