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

Из FAQ по коду Google – создание локатора хранилища с помощью 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; 

$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))')) 

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

Как это:

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

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

 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 

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

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

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

Учитывая старую таблицу с только координатами lat / lon, вы можете настроить скрипт для его обновления следующим образом: (php using 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); - $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); - $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, что он работает правильно.

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

Мне пришлось подробно разобраться в этом, поэтому я поделюсь своим результатом. Это использует таблицу zip с таблицами latitude и longitude . Это не зависит от Карт Google; скорее, вы можете адаптировать его к любой таблице, содержащей 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 миль от точки lat / long 42.81 / -70.81. Когда вы создаете это в приложении, вы помещаете свою точку и радиус поиска.

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

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

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

 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 ; 

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

Я не эксперт по 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; 

  SELECT *, ( 6371 * acos(cos(radians(search_lat)) * cos(radians(lat) ) * cos(radians(lng) - radians(search_lng)) + sin(radians(search_lat)) * (radians(lat))) ) AS distance FROM table WHERE lat != search_lat AND lng != search_lng AND distance < 25 ORDER BY distance FETCH 10 ONLY 

для расстояния 25 км

Я думал, что реализация 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); }