Distance du Grand Cercle MySQL (formule Haversine)

Question

J'ai un script PHP fonctionnel qui récupère les valeurs de longitude et de latitude et les introduit ensuite dans une requête MySQL. J'aimerais que ce soit uniquement MySQL. Voici mon code PHP actuel :

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

Quelqu'un sait-il comment en faire un système entièrement MySQL ? J'ai parcouru un peu l'Internet, mais la plupart des publications à ce sujet sont assez confuses.

Answer 1

De FAQ sur le code Google - Création d'un localisateur de magasin avec PHP, MySQL et Google Maps :

Voici l'instruction SQL qui trouvera les 20 lieux les plus proches dans un rayon de 25 miles des coordonnées 37, -122. Elle calcule la distance en fonction de la latitude/longitude de cette ligne et de la latitude/longitude cible, puis ne demande que les lignes où la valeur de la distance est inférieure à 25, ordonne l'ensemble de la requête par distance et la limite à 20 résultats. Pour effectuer une recherche en kilomètres au lieu de miles, remplacez 3959 par 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;

Answer 2

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

avec la latitude et la longitude en radian.

donc

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

est votre requête SQL

pour obtenir vos résultats en Km ou en miles, multipliez le résultat avec le rayon moyen de la Terre (3959 miles, 6371 Km ou 3440 miles nautiques)

La chose que vous calculez dans votre exemple est une boîte de délimitation. Si vous placez vos données de coordonnées dans un colonne MySQL activée spatialement vous pouvez utiliser Les fonctionnalités intégrées de MySQL pour interroger les données.

SELECT 
  id
FROM spatialEnabledTable
WHERE 
  MBRWithin(ogc_point, GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))'))

Answer 3

Si vous ajoutez des champs d'aide à la table des coordonnées, vous pouvez améliorer le temps de réponse de la requête.

Comme ça :

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

Si vous utilisez TokuDB, vous obtiendrez des performances encore meilleures si vous ajoutez des index de clustering sur l'un ou l'autre des prédicats, par exemple, comme ceci :

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

Vous aurez besoin des coordonnées de base lat et lon en degrés ainsi que sin(lat) en radians, cos(lat)*cos(lon) en radians et cos(lat)*sin(lon) en radians pour chaque point. Ensuite, vous créez une fonction mysql, un peu comme ceci :

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

Cela vous donne la distance.

N'oubliez pas d'ajouter un index sur lat/lon afin que le rectangle englobant puisse aider la recherche au lieu de la ralentir (l'index est déjà ajouté dans la requête CREATE TABLE ci-dessus).

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

Étant donné une ancienne table avec seulement des coordonnées lat/lon, vous pouvez mettre en place un script pour la mettre à jour comme ceci : (php utilisant 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']
  ));
}

Ensuite, vous optimisez la requête proprement dite pour ne calculer la distance que lorsque c'est vraiment nécessaire, par exemple en délimitant le cercle (enfin, l'ovale) de l'intérieur et de l'extérieur. Pour cela, vous devrez précalculer plusieurs métriques pour la requête elle-même :

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

Compte tenu de ces préparatifs, la requête ressemble à ceci (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 sur la requête ci-dessus pourrait dire qu'elle n'utilise pas l'index à moins qu'il y ait suffisamment de résultats pour le déclencher. L'index sera utilisé lorsqu'il y aura suffisamment de données dans la table des coordonnées. Vous pouvez ajouter FORCE INDEX (lat_lon_idx) au SELECT pour qu'il utilise l'index sans tenir compte de la taille de la table, afin que vous puissiez vérifier avec EXPLAIN que cela fonctionne correctement.

Avec les exemples de code ci-dessus, vous devriez avoir une implémentation fonctionnelle et évolutive de la recherche d'objets par distance avec un minimum d'erreurs.

Answer 4

J'ai dû travailler sur ce point de manière assez détaillée, et je vais donc partager mon résultat. Cela utilise un zip table avec latitude et longitude tables. Il ne dépend pas de Google Maps ; vous pouvez l'adapter à n'importe quelle table contenant des 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

Regardez cette ligne au milieu de cette requête :

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

Cela permet de rechercher les 30 entrées les plus proches dans le zip dans un rayon de 80 km autour du point de longitude 42.81/-70.81 . Lorsque vous intégrez ce système dans une application, c'est là que vous placez votre propre point et votre propre rayon de recherche.

Si vous voulez travailler en kilomètres plutôt qu'en miles, changez 69 à 111.045 et le changement 3963.17 à 6378.10 dans la requête.

Voici un compte-rendu détaillé. J'espère que cela aidera quelqu'un. http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

Answer 5

J'ai écrit une procédure qui peut calculer la même chose, mais vous devez entrer la latitude et la longitude dans la table respective.

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 ;