210

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

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

Note: The provided distance is in Miles. If you need Kilometers, use 6371 instead of 3959.

  • Что представляет собой значение 1.1515? Ранее я видел подобную формулу, но она использовала 1,75 вместо 1,1515.

    от
  • В ответ на мой собственный вопрос, я думаю, что ответ может лежать здесьstackoverflow.com/a/389251/691053

    от
  • Похоже, что слайдшер не содержит информации о пространственных ключах, вместо этого он использует запутанные формулы ... также он имеет несколько ошибок, таких как ввод lat lng как int 11?

    от
  • @Quassnoi: пара исправлений: вы, вероятно, захотите изменить порядок координат на широту и долготу. Кроме того, продольные расстояния пропорциональны косинусуlatitude, а не долгота. И вы захотите изменить его с умножения на деление, поэтому ваша первая координата будет исправлена как@lon - 10 / ( 111.1 / cos(@lat)) (и станьте вторым в паре, когда все будет правильно.

    от
  • Это очень хорошая и легко читаемая альтернатива. имейте в виду, что порядок параметров для POINT () равен (lng, lat), в противном случае вы можете получить "close" но все же очень отличные результаты от других методов здесь. увидеть:stackoverflow.com/questions/35939853/…

    от
  • WARNING : Тело ответа НЕ было отредактировано в соответствии с очень правильным комментарием, сделанным @M. Дейв Ауаян. Дальнейшие примечания: Этот метод становится грушевидным, если круг интересов (а) включает в себя полюс или (b) пересекается меридианом долготы +/- 180 градусов. Также используяcos(lon) точен только для небольших расстояний. Увидетьjanmatuschek.de/LatitudeLongitudeBoundingCoordinates

    от
  • Хотя это кажется логичным, вы оставляете за собой награду за это решение! В базе данных с записями в 2 миллиона человек запрос увеличился с 16 до 0,06 секунды.Note: Это даже быстрее (для больших таблиц), если вы вырезаете вычисление расстояния из запроса и выполняете вычисление для расстояния в программном коде!

    от
  • @Binary Worrier: Значит, X1, X2 и Y1, Y2 будут иметь долготу Min и Max, а Latitude Min и Max в соответствии с приведенным здесь примером:blog.fedecarg.com/2009/02/08/… пожалуйста, порекомендуйте.

    от
  • или просто идите прямо: выберите * из тех мест, где get_distance_in_miles_between_geo_locations (-34.017330, 22.809500, широта, долгота) & gt; 5000;

    от
  • Я попробовал это, и он отлично работает, но почему-то он не позволяет мне вставить оператор WHERE, основанный на distance_from_input. Есть идеи почему бы и нет?

    от
  • Вы можете найти процедуру mysql для этого подхода в этой презентации:scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

    от
  • Для поиска по километрам вместо миль замените 3959 на 6371.

    от
  • +1, отличный вариант; добавление поля уменьшило мой запрос от m 4s до 0,03 с.

    от
  • Вы можете сделать это как дополнительный выбор: выберите * из (...) как t, где distance_from_input & gt; 5;

    от
  • Можно ли каким-то образом понять, что представляют собой константы (10, 111.11, @lat, @lon, mypoint)? Я предполагаю, что 10 для расстояния в километрах, @lat и @lon представляют предоставленную широту и долготу, но что представляют 111.11 и mypoint в примере?

    от
  • Tx, это сделало трюк :)

    от
  • Метры возврата: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

    от
  • @all отредактировал ответ, чтобы исправить ошибку, обнаруженную Дейвом.

    от
  • @ashays: есть примерно111.(1) км в градусе широты.mypoint поле в таблице, в котором хранятся координаты

    от
  • Разве это не было бы неправильно, поскольку lng_min / lng_max должен был бы использовать lat_min и lat_max в математике радиуса?

    от
  • Я искал это всегда. Не знал, что это может быть так просто. Огромное спасибо.

    от
  • Километр в 1 латиттуде составляет 111 км. Миля в 1 латиттуде составляет 69 миль. и 69 миль = 111 км. Вот почему мы использовали параметры в преобразованиях.

    от
  • Что такое 69 в этом случае? Как это сделать в случае, если у нас есть радиус Земли?

    от
  • Пожалуйста, приведите свои источники. Это из:blog.fedecarg.com/2009/02/08/…

    от
  • Формула, которую вы даете, кажется, содержит много постоянных элементов. Можно ли предварительно рассчитать данные и сохранить эти значения в вашей БД? Например, 3959 * acos (cos (радианы (42.290763)) - это константа, но в ней 4 основных вычисления. Вместо этого вы могли бы просто хранить 6696.7837?

    от Peter M
  • Для сведения: расстояние, рассчитанное по этой формуле, указывается в милях, а не в километрах. Пожалуйста, замените 3959 на 6371, чтобы получить результаты в километрах

    от sahil sethi
  • Для тех, кто интересуется, 42.290763 - это широта, а -71.35368 - это долгота точки, из которой вычисляются расстояния.

    от user276648
  • Или хотя бы предварительно вычислить константы вне запроса? Это сократит объем работы, которая должна быть выполнена.

    от Peter M
  • @Peter M Кажется вероятным, что любая приличная база данных SQL будет оптимизирована так, что она будет вычислена только один раз.

    от mhenry1384
16 ответов
  • 4

    Code:

       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;
    

  • -1

    Code:

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

  • 7

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

    источник

  • 5

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

  • 111

    Create your points using

    Point values of Geometry data types in MyISAM table. As of Mysql 5.7.5, InnoDB tables now also support SPATIAL indices.

    Create a SPATIAL index on these points

    Use MBRContains() to find the values:

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

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

    Apply additional filtering to select everything inside the circle (not the square)

    Possibly apply additional fine filtering to account for the big circle distance (for large distances)

  • 3

    Прочитайте, решение

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

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

    the use of abs in the select statement on p8. I just omitted abs and it worked.

    the spatial search distance function on p27 does not convert to radians or multiply longitude by cos(latitude), unless his spatial data is loaded with this in consideration (cannot tell from context of article), but his example on p26 indicates that his spatial data POINT is not loaded with radians or degrees.

  • 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/experiments/haversine/

    Увидеть:https://stackoverflow.com/a/24372831/5155484

    Увидеть:http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

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

  • 3

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

  • 13

    на

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

    Sample usage: Предполагается, что таблица зывается Places с полями latitude & amp; долгота:

    select get_distance_in_miles_between_geo_locations(-34.017330, 22.809500, latitude, longitude) as distance_from_input from places;

    всезацепил этот пост

  • 9

    Это запрос вычисления расстояния между точками в MySQL

    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
    

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

  • 16

    Проверьте эту презентацию для хорошего ответа.

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

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

  • 3

    Вот очень подробное описание Geo Distance Search с MySQL решение

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

  • 93

    Не специфичный для MySql ответ

    но он улучшит производительность вашего оператора SQL.

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

    То, что вы можете сделать перед запуском этого sql, это создать четыре точки, которые нарисуют прямоугольник на 20 единиц на стороне, с вашей точкой в центре, т.е. (x1, y1). , , (x4, y4), где (x1, y1) - это (дано + 10 единиц, дано +10 единиц). , , (дано долго - 10 единиц, дано - 10 единиц). Actually, you only need two points, top left and bottom right call them (X1, Y1) and (X2, Y2)

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

    например

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

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

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

    EDIT: Можно ли это поместить в один оператор 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) и вычисляет их перед & quot; main & quot; оператор select, как я уже сказал, я не знаю, можно ли это сделать с помощью MySql. Однако я все еще склонен строить четыре точки в C # и передавать их в качестве параметров в SQL-запрос.

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

  • 3

    Мне нужно было решить аналогичную проблему (фильтрация строк по рассто

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

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

    map

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