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

https://stackoverflow.com/questions/1006654

06-07-2019
|

Вопрос

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

Решение

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

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

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

Другие советы

Это не конкретный ответ для 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) и вычисляет их перед "основным" оператором select, как я уже сказал, я понятия не имею, можно ли это сделать с MySQL.Однако я все равно был бы склонен построить четыре точки на C # и передать их в качестве параметров SQL-запроса.

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

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

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

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

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

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

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

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

источник

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

   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;

Полный код с подробной информацией о том, как установить как плагин 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;
}

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

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

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

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

<Ол>

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

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

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

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

координаты - это поле с типом POINT и индексом SPATIAL
6371 для расчета расстояния в километрах
56.946285 - широта центральной точки
24.105078 - долгота центральной точки
10 - максимальное расстояние в километрах

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

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

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

Использование 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/ гаверсинус-MySQL-ближайших LOC /

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow