MySQL Great Circle Distance (formula Haversine)

Question

Ho uno script PHP funzionante che ottiene i valori di Longitudine e Latitudine e quindi li inserisce in una query MySQL. Mi piacerebbe renderlo solo MySQL. Ecco il mio codice PHP attuale:

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

Qualcuno sa come renderlo completamente MySQL? Ho navigato un po 'su Internet ma la maggior parte della letteratura su di esso è piuttosto confusa.

Answer 1

Da Google Code FAQ - Creating a Store Locator with PHP, MySQL & Google Maps:

Ecco l'istruzione SQL che troveranno i più vicini 20 posizioni che si trovano entro un raggio di 25 miglia a 37, -122 coordinate. Calcola la distanza in base alla latitudine/longitudine di quella riga e alla latitudine/longitudine obiettivo, quindi richiede solo le righe in cui il valore della distanza è inferiore a 25, ordina l'intera query per distanza e limita a 20 risultati. Per cercare per chilometri, invece di miglia, sostituire 3959 con 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));

con latitudine e longitudine in radianti.

così

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

è la query SQL

per ottenere i risultati in km o miglia, moltiplicare il risultato con il raggio medio della Terra (3959 miglia, 6371 km o 3440 miglia nautiche)

La cosa che stai calcolando nel tuo esempio è una scatola di delimitazione. Se si inseriscono i dati delle coordinate in un spatial enabled MySQL column, è possibile utilizzare MySQL's build in functionality per interrogare i dati.

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

Answer 3

Ho scritto una procedura in grado di calcolare la stessa, ma si deve inserire la latitudine e longitudine nella rispettiva tabella.

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 ; 

Answer 4

Se si aggiungono campi helper alla tabella delle coordinate, è possibile migliorare i tempi di risposta della query.

Ti piace questa:

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

Se stai usando TokuDB, si otterrà prestazioni ancora migliori se si aggiunge il clustering indici su uno dei predicati, per esempio, in questo modo:

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

Avrai bisogno del lat lat e lon in gradi e del sin (lat) in radianti, cos (lat) * cos (lon) in radianti e cos (lat) * sin (lon) in radianti per ogni punto . Poi si crea una funzione mysql, smth come questo:

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 

Questo vi dà la distanza.

Non dimenticare di aggiungere un indice su lat/lon in modo che il boxing di delimitazione possa aiutare la ricerca anziché rallentarlo (l'indice è già stato aggiunto nella query CREATE TABLE sopra).

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

Dato un vecchio tavolo con solo le coordinate Lat/Lon, è possibile impostare uno script per aggiornare in questo modo: (php usando 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'] 
)); 
} 

Poi si ottimizzare la query effettiva solo eseguire il calcolo della distanza quando è veramente necessario, ad esempio vincolando il cerchio (bene, ovale) dall'interno e dall'esterno. Per questo, avrete bisogno di precalculate diverse metriche per la query stessa:

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

A fronte di tali preparati, la query più o meno così (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); 

contare sulla query precedente potrebbe dire che non sta usando l'indice a meno che non ci siano risultati sufficienti per far scattare tale. L'indice sarà usato quando ci sono abbastanza dati nella tabella delle coordinate. È possibile aggiungere FORCE INDEX (lat_lon_idx) a SELECT per fare in modo che utilizzi l'indice indipendentemente dalle dimensioni della tabella, in modo da poter verificare con EXPLAIN che funzioni correttamente.

Con gli esempi di codice sopra riportato si dovrebbe avere un'implementazione funzionante e scalabile della ricerca di oggetti per distanza con errore minimo.

Answer 5

ho pensato che la mia implementazione JavaScript sarebbe un buon riferimento a:

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

Answer 6

Non posso commentare sulla risposta di cui sopra, ma stare attenti con la risposta di @Pavel Chuchuva. Quella formula non restituirà un risultato se entrambe le coordinate sono uguali. In tal caso, la distanza è nullo e quindi quella riga non verrà restituita con quella formula così com'è.

io non sono un esperto di MySQL, ma questo sembra funzionare per me:

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; 

Answer 7

ho dovuto lavorare su questo in dettaglio, così io condividere il mio risultato. Questo utilizza una tabella zip con tabelle latitude e longitude. Non dipende da Google Maps; piuttosto puoi adattarlo a qualsiasi tabella contenente 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 

Guardate questa linea nel mezzo di quella query:

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

Questo cerca le 30 voci più vicine nella tabella zip entro 50.0 miglia del lat punto lungo/42.81/-70,81. Quando lo costruisci in un'app, è lì che inserisci il tuo punto e il raggio di ricerca.

Se si desidera lavorare in chilometri piuttosto che miglia, cambiare 69 a 111.045 e cambiare 3963.17-6378.10 nella query.

Ecco una descrizione dettagliata. Spero che aiuti qualcuno.http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

Answer 8

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 

per la distanza di 25 km