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

Question

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

Answer 1

• Создайте свои баллы, используя 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).

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

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

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

Answer 2

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

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

То, что вы можете сделать перед запуском этого sql, - это создать четыре точки, которые нарисуют прямоугольник на 20 единиц на стороне, с вашей точкой в ​​центре, т.е. (x1, y1). , , (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 этого, не стесняйтесь редактировать этот ответ, чтобы сделать это.

Answer 3

Проверьте эту презентацию для хорошего ответа.В основном это показывает два разных подхода, показанных в комментариях, с подробным объяснением того, почему / когда вы должны использовать один или другой, и почему вычисление «в коробке» может быть очень интересным.

Поиск географического расстояния с MySQL

Answer 4

на этом блоге , была опубликована следующая функция 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 ;

Пример использования: Предположим, что таблица называется Места с полями широта и долгота:

выберите get_distance_in_miles_between_geo_locations (-34.017330, 22.809500 (широта, долгота) в виде distance_from_input из мест;

все извлечено из этого поста

Answer 5

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, я использовал его в длинной базе данных, он работает отлично! Примечание: внесите изменения (имя базы данных, имя таблицы, столбец и т. Д.) В соответствии с вашими требованиями.

Answer 6

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

источник

Answer 7

, если вы используете 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

Answer 8

   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;

Answer 9

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

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

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

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

Answer 10

Мне нужно было решить аналогичную проблему (фильтрация строк по расстоянию от одной точки), и, комбинируя оригинальный вопрос с ответами и комментариями, я нашел решение, которое идеально подходит для меня как на 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 index
6371 для расчета расстояния в километрах
56.946285 - широта для центральной точки
24.105078 - долгота для центральной точки
10 - максимальное расстояние в километрах

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

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

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