Il modo più veloce per trovare la distanza tra due punti lat / long

https://stackoverflow.com/questions/1006654

06-07-2019
|

Domanda

Al momento ho poco meno di un milione di posizioni in un database mysql tutte con informazioni su longitudine e latitudine.

Sto cercando di trovare la distanza tra un punto e molti altri punti tramite una query. Non è così veloce come voglio che sia soprattutto con oltre 100 colpi al secondo.

Esiste una query più veloce o forse un sistema più veloce diverso da mysql per questo? Sto usando questa query:

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;

Nota: la distanza fornita è in Miglia . Se hai bisogno di chilometri , usa 6371 invece di 3959.

Soluzione

Crea i tuoi punti usando i valori Point dei tipi di dati Geometry nella tabella MyISAM . A partire da Mysql 5.7.5, le tabelle InnoDB ora supportano anche gli indici SPATIAL .
Crea un indice SPATIAL su questi punti

Usa MBRContains () per trovare i valori:

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)

o, in MySQL 5.1 e versioni successive:

    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
                    )

Questo selezionerà tutti i punti approssimativamente all'interno del riquadro (@lat +/- 10 km, @lon +/- 10km) .

In realtà non si tratta di una scatola, ma di un rettangolo sferico: segmento della sfera associato a latitudine e longitudine. Questo può differire da un semplice rettangolo sulla Terra di Franz Joseph , ma abbastanza vicino ad esso nella maggior parte dei luoghi abitati.

Applica un filtro aggiuntivo per selezionare tutto all'interno del cerchio (non il quadrato)
Eventualmente applicare un filtro fine aggiuntivo per tenere conto della grande distanza del cerchio (per grandi distanze)

Altri suggerimenti

Non è una risposta specifica per MySql, ma migliorerà le prestazioni della tua dichiarazione sql.

Quello che stai effettivamente facendo è calcolare la distanza da ogni punto della tabella, per vedere se è entro 10 unità da un dato punto.

Quello che puoi fare prima di eseguire questo sql è creare quattro punti che disegnano una scatola di 20 unità su un lato, con il tuo punto al centro, cioè ... (x1, y1). . . (x4, y4), dove (x1, y1) è (dato lungo + 10 unità, dato Lat + 10 unità). . . (datoLungo - 10 unità, datoLat -10 unità). In realtà, hai solo bisogno di due punti, in alto a sinistra e in basso a destra chiamali (X1, Y1) e (X2, Y2)

Ora la tua istruzione SQL usa questi punti per escludere righe che sono sicuramente più di 10u dal tuo dato punto, può usare gli indici alle latitudini & amp; longitudinali, quindi gli ordini di grandezza saranno più veloci di quelli attualmente disponibili.

per es.

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

L'approccio box può restituire falsi positivi (puoi raccogliere punti negli angoli del box che sono > 10u da un dato punto), quindi devi ancora calcolare la distanza di ciascun punto. Tuttavia, questo sarà di nuovo molto più veloce perché hai drasticamente limitato il numero di punti da testare ai punti all'interno del riquadro.

Io chiamo questa tecnica " Pensare dentro la scatola " :)

EDIT: può essere inserito in un'istruzione SQL?

Non ho idea di cosa sia capace mySql o Php, scusa. Non so dove sia il posto migliore per costruire i quattro punti o come possano essere passati a una query mySql in Php. Tuttavia, una volta che hai i quattro punti, non c'è niente che ti impedisce di combinare la tua istruzione SQL con la mia.

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;

So che con MS SQL posso creare un'istruzione SQL che dichiari quattro float (X1, Y1, X2, Y2) e li calcoli prima di "main" Selezionare la dichiarazione, come ho detto, non ho idea se questo può essere fatto con MySql. Tuttavia, sarei ancora propenso a costruire i quattro punti in C # e passarli come parametri alla query SQL.

Mi dispiace non poter essere più di aiuto, se qualcuno può rispondere a MySQL & amp; Parti specifiche di PHP di questo, sentiti libero di modificare questa risposta per farlo.

Controlla questa presentazione per una buona risposta. Fondamentalmente mostra i due diversi approcci mostrati nei commenti, con una spiegazione dettagliata del perché / quando dovresti usare l'uno o l'altro e perché il "nel riquadro". il calcolo può essere molto interessante.

Ricerca geografica a distanza con MySQL

on questo post sul blog , è stata pubblicata la seguente funzione MySql. Non l'ho provato molto, ma da quello che ho raccolto dal post, se i campi di latitudine e longitudine sono indicizzati , questo potrebbe funzionare bene per te:

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 ;

Esempio di utilizzo: Supponendo una tabella chiamata Luoghi con campi latitudine e amp; longitudine:

seleziona get_distance_in_miles_between_geo_locations (-34.017330, 22.809500, latitudine, longitudine) come distance_from_input dai luoghi;

all strappato da questo post

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

Questa è la query di calcolo della distanza tra i punti in MySQL, l'ho usato in un lungo database, funziona perfettamente! Nota: apportare le modifiche (nome del database, nome della tabella, colonna ecc.) In base alle proprie esigenze.

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

source

se si utilizza MySQL 5.7. *, è possibile utilizzare 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;

Il codice completo con i dettagli su come installare come plugin MySQL sono qui: https://github.com/lucasepe / lib_mysqludf_haversine

Ho pubblicato lo scorso anno come commento. Dal momento che @TylerCollier mi ha gentilmente consigliato di postare come risposta, eccolo qui.

Un altro modo è quello di scrivere una funzione UDF personalizzata che restituisca la distanza haversine da due punti. Questa funzione può contenere input:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

Quindi possiamo scrivere qualcosa del genere:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

per recuperare tutti i record con una distanza inferiore a 40 chilometri. Oppure:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

per recuperare tutti i record con una distanza inferiore a 25 piedi.

La funzione principale è:

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

Un'approssimazione veloce, semplice e accurata (per distanze minori) può essere fatta con una proiezione sferica . Almeno nel mio algoritmo di routing ottengo un aumento del 20% rispetto al calcolo corretto. Nel codice Java sembra:

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

Non sono sicuro di MySQL (scusate!).

Assicurati di conoscere la limitazione (il terzo parametro di assertEquals indica l'accuratezza in chilometri):

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

Ecco una descrizione molto dettagliata di Geo Distance Search con MySQL una soluzione basata sull'implementazione di Haversine Formula su mysql. La descrizione completa della soluzione con teoria, implementazione e ulteriore ottimizzazione delle prestazioni. Sebbene la parte di ottimizzazione spaziale non abbia funzionato correttamente nel mio caso. http://www.scribd.com/doc/2569355/Geo -Distanza-Search-con-MySQL

Leggi Ricerca Geo Distance con MySQL , una soluzione basato sull'implementazione di Haversine Formula su MySQL. Questa è una soluzione completa descrizione con teoria, implementazione e ulteriore ottimizzazione delle prestazioni. Sebbene la parte di ottimizzazione spaziale non abbia funzionato correttamente nel mio caso.

Ho notato due errori in questo:

l'uso di abs nell'istruzione select a p8. Ho appena omesso abs e ha funzionato.
la funzione di distanza di ricerca spaziale su p27 non converte in radianti o moltiplica la longitudine per cos (latitudine) , a meno che i suoi dati spaziali non siano caricati con questo in considerazione (non si può dire dal contesto di articolo), ma il suo esempio a p26 indica che i suoi dati spaziali POINT non sono caricati con radianti o gradi.

Una funzione MySQL che restituisce il numero di metri tra le due coordinate:

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

Per restituire il valore in un formato diverso, sostituire 6371000 nella funzione con il raggio della Terra nella scelta dell'unità. Ad esempio, i chilometri sarebbero 6371 e le miglia sarebbero 3959 .

Per usare la funzione, chiamala come faresti con qualsiasi altra funzione in MySQL. Ad esempio, se avessi una tabella city , potresti trovare la distanza tra ogni città e ogni altra città:

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`

Avevo bisogno di risolvere un problema simile (filtrando le righe in base alla distanza dal singolo punto) e combinando la domanda originale con risposte e commenti, ho trovato una soluzione che funziona perfettamente per me sia su MySQL 5.6 che 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

coordinate è un campo con tipo POINT e ha l'indice SPATIAL
6371 serve per calcolare la distanza in chilometri
56.946285 è la latitudine per il punto centrale
24.105078 è la longitudine per il punto centrale
10 è la distanza massima in chilometri

Nei miei test, MySQL utilizza l'indice SPATIAL sul campo coordinate per selezionare rapidamente tutte le righe che si trovano all'interno del rettangolo e quindi calcola la distanza effettiva per tutti i luoghi filtrati per escludere i luoghi dagli angoli dei rettangoli e lasciare solo i luoghi all'interno cerchio.

Questa è la visualizzazione del mio risultato:

Le stelle grigie visualizzano tutti i punti sulla mappa, le stelle gialle sono quelle restituite dalla query MySQL. Le stelle grigie all'interno degli angoli del rettangolo (ma il cerchio esterno) sono state selezionate da MBRContains () e quindi deselezionate dalla clausola HAVING .

Uso di 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;

Vedi: https://andrew.hedges.name/experiments/haversine/

Vedi: https://stackoverflow.com/a/24372831/5155484

Vedi: http://www.plumislandmedia.net/mysql/ haversine-mysql-vicina-Loc /

NOTA: LEAST viene utilizzato per evitare valori nulli come suggerito da un commento su 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";

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow