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

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

Ответы

Ответ 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).

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

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

Ответ 2

Не специфичный для 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. Однако я все же был бы склонен построить четыре точки в С# и передать их в качестве параметров в SQL-запрос.

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

Ответ 3

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

Geo Distance Search с MySQL

Ответ 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 ;

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

Предполагая таблицу с именем places с полями latitude & longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

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

Ответ 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);

источник

Ответ 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

Ответ 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;

Ответ 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;
}

Ответ 10

Функция 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'

Ответ 11

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

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

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

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

Ответ 12

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

Ответ 13

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

Ответ 14

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

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

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

Ответ 15

$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";

Ответ 16

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

Смотрите: fooobar.com/info/614261/...

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

ПРИМЕЧАНИЕ. LEAST используется, чтобы избежать нулевых значений, как комментарий, предложенный на fooobar.com/info/614261/...