MySQL Great Circle Distance (формула Хаверсайна)

184

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

if ($distance != "Any" && $customer_zip != "") { //get the great circle distance

    //get the origin zip code info
    $zip_sql = "SELECT * FROM zip_code WHERE zip_code = '$customer_zip'";
    $result = mysql_query($zip_sql);
    $row = mysql_fetch_array($result);
    $origin_lat = $row['lat'];
    $origin_lon = $row['lon'];

    //get the range
    $lat_range = $distance/69.172;
    $lon_range = abs($distance/(cos($details[0]) * 69.172));
    $min_lat = number_format($origin_lat - $lat_range, "4", ".", "");
    $max_lat = number_format($origin_lat + $lat_range, "4", ".", "");
    $min_lon = number_format($origin_lon - $lon_range, "4", ".", "");
    $max_lon = number_format($origin_lon + $lon_range, "4", ".", "");
    $sql .= "lat BETWEEN '$min_lat' AND '$max_lat' AND lon BETWEEN '$min_lon' AND '$max_lon' AND ";
    }

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

Ник Вудхэмс
источник
4
Основываясь на всех превосходных ответах ниже, вот рабочий образец формулы Хаверсайна в действии
StartupGuy
Спасибо за то, что поделились этим Michael.M
Ник Вудхамс
stackoverflow.com/a/40272394/1281385 Есть пример того, как убедиться, что индекс попал
exussum

Ответы:

357

Из Google Code FAQ - Создание локатора магазина с помощью PHP, MySQL и Google Maps :

Вот оператор SQL, который найдет ближайшие 20 мест, которые находятся в радиусе 25 миль от координаты 37, -122. Он рассчитывает расстояние на основе широты / долготы этой строки и целевой широты / долготы, а затем запрашивает только те строки, в которых значение расстояния меньше 25, упорядочивает весь запрос по расстоянию и ограничивает его 20 результатами. Для поиска по километрам вместо миль замените 3959 на 6371.

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) 
* cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin(radians(lat)) ) ) AS distance 
FROM markers 
HAVING distance < 25 
ORDER BY distance 
LIMIT 0 , 20;
Павел Чучува
источник
2
SQL заявление действительно хорошо. но где я могу передать свои координаты в это утверждение? я не могу видеть, где бы ни прошли координаты
Манн
32
Замените 37 и -122 вашими координатами.
Павел Чучува
5
Интересно о влиянии на производительность этого, если есть миллионы мест (+ тысячи посетителей) ...
Halil Özgür
12
Вы можете сузить запрос для повышения производительности, как описано в этом документе: tr.scribed.com/doc/2569355/Geo-Distance-Search-with-MySQL
maliayas
2
@FosAvance Да, этот запрос будет работать, если у вас есть markersтаблица с полями id, lan и lng.
Павел Чучува
32

$greatCircleDistance = acos( cos($latitude0) * cos($latitude1) * cos($longitude0 - $longitude1) + sin($latitude0) * sin($latitude1));

с широтой и долготой в радианах.

так

SELECT 
  acos( 
      cos(radians( $latitude0 ))
    * cos(radians( $latitude1 ))
    * cos(radians( $longitude0 ) - radians( $longitude1 ))
    + sin(radians( $latitude0 )) 
    * sin(radians( $latitude1 ))
  ) AS greatCircleDistance 
 FROM yourTable;

ваш запрос SQL

чтобы получить результаты в км или милях, умножьте результат на средний радиус Земли ( 3959миль, 6371км или 3440морских миль)

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

SELECT 
  id
FROM spatialEnabledTable
WHERE 
  MBRWithin(ogc_point, GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))'))
Jacco
источник
13

Если вы добавите вспомогательные поля в таблицу координат, вы сможете улучшить время ответа на запрос.

Как это:

CREATE TABLE `Coordinates` (
`id` INT(10) UNSIGNED NOT NULL COMMENT 'id for the object',
`type` TINYINT(4) UNSIGNED NOT NULL DEFAULT '0' COMMENT 'type',
`sin_lat` FLOAT NOT NULL COMMENT 'sin(lat) in radians',
`cos_cos` FLOAT NOT NULL COMMENT 'cos(lat)*cos(lon) in radians',
`cos_sin` FLOAT NOT NULL COMMENT 'cos(lat)*sin(lon) in radians',
`lat` FLOAT NOT NULL COMMENT 'latitude in degrees',
`lon` FLOAT NOT NULL COMMENT 'longitude in degrees',
INDEX `lat_lon_idx` (`lat`, `lon`)
)    

Если вы используете TokuDB, вы получите еще большую производительность, если добавите кластеризованные индексы к любому из предикатов, например, так:

alter table Coordinates add clustering index c_lat(lat);
alter table Coordinates add clustering index c_lon(lon);

Вам понадобятся базовые значения lat и lon в градусах, а также sin (lat) в радианах, cos (lat) * cos (lon) в радианах и cos (lat) * sin (lon) в радианах для каждой точки. Затем вы создаете функцию mysql, что-то вроде этого:

CREATE FUNCTION `geodistance`(`sin_lat1` FLOAT,
                              `cos_cos1` FLOAT, `cos_sin1` FLOAT,
                              `sin_lat2` FLOAT,
                              `cos_cos2` FLOAT, `cos_sin2` FLOAT)
    RETURNS float
    LANGUAGE SQL
    DETERMINISTIC
    CONTAINS SQL
    SQL SECURITY INVOKER
   BEGIN
   RETURN acos(sin_lat1*sin_lat2 + cos_cos1*cos_cos2 + cos_sin1*cos_sin2);
   END

Это дает вам расстояние.

Не забудьте добавить индекс по широте / долготе, чтобы ограничивающий бокс мог помочь в поиске, а не замедлять его (индекс уже добавлен в запросе CREATE TABLE выше).

INDEX `lat_lon_idx` (`lat`, `lon`)

Учитывая старую таблицу только с координатами широта / долгота, вы можете настроить скрипт для ее обновления следующим образом: (php используя meekrodb)

$users = DB::query('SELECT id,lat,lon FROM Old_Coordinates');

foreach ($users as $user)
{
  $lat_rad = deg2rad($user['lat']);
  $lon_rad = deg2rad($user['lon']);

  DB::replace('Coordinates', array(
    'object_id' => $user['id'],
    'object_type' => 0,
    'sin_lat' => sin($lat_rad),
    'cos_cos' => cos($lat_rad)*cos($lon_rad),
    'cos_sin' => cos($lat_rad)*sin($lon_rad),
    'lat' => $user['lat'],
    'lon' => $user['lon']
  ));
}

Затем вы оптимизируете фактический запрос, чтобы вычисление расстояния выполнялось только тогда, когда это действительно необходимо, например, путем ограничения круга (ну, овала) изнутри и снаружи. Для этого вам нужно предварительно рассчитать несколько показателей для самого запроса:

// assuming the search center coordinates are $lat and $lon in degrees
// and radius in km is given in $distance
$lat_rad = deg2rad($lat);
$lon_rad = deg2rad($lon);
$R = 6371; // earth's radius, km
$distance_rad = $distance/$R;
$distance_rad_plus = $distance_rad * 1.06; // ovality error for outer bounding box
$dist_deg_lat = rad2deg($distance_rad_plus); //outer bounding box
$dist_deg_lon = rad2deg($distance_rad_plus/cos(deg2rad($lat)));
$dist_deg_lat_small = rad2deg($distance_rad/sqrt(2)); //inner bounding box
$dist_deg_lon_small = rad2deg($distance_rad/cos(deg2rad($lat))/sqrt(2));

Учитывая эти приготовления, запрос выглядит примерно так (php):

$neighbors = DB::query("SELECT id, type, lat, lon,
       geodistance(sin_lat,cos_cos,cos_sin,%d,%d,%d) as distance
       FROM Coordinates WHERE
       lat BETWEEN %d AND %d AND lon BETWEEN %d AND %d
       HAVING (lat BETWEEN %d AND %d AND lon BETWEEN %d AND %d) OR distance <= %d",
  // center radian values: sin_lat, cos_cos, cos_sin
       sin($lat_rad),cos($lat_rad)*cos($lon_rad),cos($lat_rad)*sin($lon_rad),
  // min_lat, max_lat, min_lon, max_lon for the outside box
       $lat-$dist_deg_lat,$lat+$dist_deg_lat,
       $lon-$dist_deg_lon,$lon+$dist_deg_lon,
  // min_lat, max_lat, min_lon, max_lon for the inside box
       $lat-$dist_deg_lat_small,$lat+$dist_deg_lat_small,
       $lon-$dist_deg_lon_small,$lon+$dist_deg_lon_small,
  // distance in radians
       $distance_rad);

EXPLAIN в приведенном выше запросе может сказать, что он не использует индекс, если нет достаточно результатов для его запуска. Индекс будет использоваться, когда в таблице координат будет достаточно данных. Вы можете добавить FORCE INDEX (lat_lon_idx) в SELECT, чтобы он использовал индекс безотносительно к размеру таблицы, поэтому вы можете проверить с помощью EXPLAIN, что он работает правильно.

С приведенными выше примерами кода у вас должна быть работающая и масштабируемая реализация поиска объектов по расстоянию с минимальной ошибкой.

силвио
источник
10

Я должен был разобраться с этим в некоторых деталях, поэтому я поделюсь своим результатом. Это использует zipтаблицу с latitudeи longitudeтаблицами. Это не зависит от Google Maps; скорее вы можете адаптировать его к любой таблице, содержащей lat / long.

SELECT zip, primary_city, 
       latitude, longitude, distance_in_mi
  FROM (
SELECT zip, primary_city, latitude, longitude,r,
       (3963.17 * ACOS(COS(RADIANS(latpoint)) 
                 * COS(RADIANS(latitude)) 
                 * COS(RADIANS(longpoint) - RADIANS(longitude)) 
                 + SIN(RADIANS(latpoint)) 
                 * SIN(RADIANS(latitude)))) AS distance_in_mi
 FROM zip
 JOIN (
        SELECT  42.81  AS latpoint,  -70.81 AS longpoint, 50.0 AS r
   ) AS p 
 WHERE latitude  
  BETWEEN latpoint  - (r / 69) 
      AND latpoint  + (r / 69)
   AND longitude 
  BETWEEN longpoint - (r / (69 * COS(RADIANS(latpoint))))
      AND longpoint + (r / (69 * COS(RADIANS(latpoint))))
  ) d
 WHERE distance_in_mi <= r
 ORDER BY distance_in_mi
 LIMIT 30

Посмотрите на эту строку в середине этого запроса:

    SELECT  42.81  AS latpoint,  -70.81 AS longpoint, 50.0 AS r

Это ищет 30 ближайших записей в zipтаблице в пределах 50.0 миль от широты / длинной точки 42.81 / -70.81. Когда вы встраиваете это в приложение, здесь вы указываете свою точку и радиус поиска.

Если вы хотите работать в километрах, а не в милях, измените 69на 111.045и измените 3963.17на6378.10 в запросе.

Вот подробное описание. Надеюсь, это кому-нибудь поможет. http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

О. Джонс
источник
3

Я написал процедуру, которая может рассчитать то же самое, но вы должны ввести широту и долготу в соответствующей таблице.

drop procedure if exists select_lattitude_longitude;

delimiter //

create procedure select_lattitude_longitude(In CityName1 varchar(20) , In CityName2 varchar(20))

begin

    declare origin_lat float(10,2);
    declare origin_long float(10,2);

    declare dest_lat float(10,2);
    declare dest_long float(10,2);

    if CityName1  Not In (select Name from City_lat_lon) OR CityName2  Not In (select Name from City_lat_lon) then 

        select 'The Name Not Exist or Not Valid Please Check the Names given by you' as Message;

    else

        select lattitude into  origin_lat from City_lat_lon where Name=CityName1;

        select longitude into  origin_long  from City_lat_lon where Name=CityName1;

        select lattitude into  dest_lat from City_lat_lon where Name=CityName2;

        select longitude into  dest_long  from City_lat_lon where Name=CityName2;

        select origin_lat as CityName1_lattitude,
               origin_long as CityName1_longitude,
               dest_lat as CityName2_lattitude,
               dest_long as CityName2_longitude;

        SELECT 3956 * 2 * ASIN(SQRT( POWER(SIN((origin_lat - dest_lat) * pi()/180 / 2), 2) + COS(origin_lat * pi()/180) * COS(dest_lat * pi()/180) * POWER(SIN((origin_long-dest_long) * pi()/180 / 2), 2) )) * 1.609344 as Distance_In_Kms ;

    end if;

end ;

//

delimiter ;
Абдул Манаф
источник
3

Я не могу комментировать приведенный выше ответ, но будьте осторожны с ответом @Pavel Chuchuva. Эта формула не вернет результат, если обе координаты совпадают. В этом случае расстояние равно нулю, поэтому строка не будет возвращена с этой формулой как есть.

Я не эксперт по MySQL, но мне кажется, что это работает:

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance 
FROM markers HAVING distance < 25 OR distance IS NULL ORDER BY distance LIMIT 0 , 20;
Джон Креншоу
источник
2
Если позиции идентичны, он должен быть не NULL, а как ноль (как ACOS(1)0). Вы могли бы видеть проблемы округления с xaxis * xaxis + yaxis * yaxis + zaxis * zaxis, выходящие за пределы диапазона для ACOS, но вы, кажется, не защищаете это?
Роуленд Шоу,
3
 SELECT *, (  
    6371 * acos(cos(radians(search_lat)) * cos(radians(lat) ) *   
cos(radians(lng) - radians(search_lng)) + sin(radians(search_lat)) *         sin(radians(lat)))  
) AS distance  
FROM table  
WHERE lat != search_lat AND lng != search_lng AND distance < 25  
 ORDER BY distance  
FETCH 10 ONLY 

на расстояние 25 км

Хариш Лалвани
источник
Последнее (радианы (лат) должны быть грехом (радианы (лат))
KGs
я получаю ошибку "неизвестное расстояние до столбца", почему это?
Джилл Джон
@JillJohn, если вам нужно только расстояние, вы можете полностью удалить порядок по расстоянию. Если вы хотите отсортировать результаты, вы можете использовать это - ORDER BY (6371 * acos (cos (радианы (search_lat)) * cos (радианы (lat)) * cos (радианы (lng) - радианы (search_lng)) + sin (радианы (search_lat)) * sin (радианы (лат)))).
Хариш Лалвани
2

Я думал, что моя реализация javascript будет хорошей ссылкой на:

/*
 * Check to see if the second coord is within the precision ( meters )
 * of the first coord and return accordingly
 */
function checkWithinBound(coord_one, coord_two, precision) {
    var distance = 3959000 * Math.acos( 
        Math.cos( degree_to_radian( coord_two.lat ) ) * 
        Math.cos( degree_to_radian( coord_one.lat ) ) * 
        Math.cos( 
            degree_to_radian( coord_one.lng ) - degree_to_radian( coord_two.lng ) 
        ) +
        Math.sin( degree_to_radian( coord_two.lat ) ) * 
        Math.sin( degree_to_radian( coord_one.lat ) ) 
    );
    return distance <= precision;
}

/**
 * Get radian from given degree
 */
function degree_to_radian(degree) {
    return degree * (Math.PI / 180);
}
Сэм Влёбергс
источник
0

рассчитать расстояние в Mysql

 SELECT (6371 * acos(cos(radians(lat2)) * cos(radians(lat1) ) * cos(radians(long1) -radians(long2)) + sin(radians(lat2)) * sin(radians(lat1)))) AS distance

Таким образом, значение расстояния будет рассчитано, и любой может подать заявку, как требуется.

Раджеш Прасад Ядав
источник