A maneira mais rápida de encontrar a distância entre dois pontos lat / longos

227

Atualmente, tenho pouco menos de um milhão de locais em um banco de dados mysql, todos com informações de longitude e latitude.

Estou tentando encontrar a distância entre um ponto e muitos outros pontos através de uma consulta. Não é tão rápido quanto eu quero, especialmente com mais de 100 hits por segundo.

Existe uma consulta mais rápida ou possivelmente um sistema mais rápido que não seja o mysql para isso? Estou usando esta consulta:

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: A distância fornecida é em milhas . Se você precisar de Quilômetros , use em 6371vez de 3959.

Ryan Detzel
fonte
31
A fórmula que você dá parece ter muitos elementos constantes. É possível pré-calcular os dados e armazenar esses valores também no seu banco de dados? Por exemplo 3959 acos * (cos (radianos (42,290763)) é uma constante, mas tem 4 grandes cálculos nele Em vez disso você pode simplesmente armazenar 6696,7837.?
Peter M
1
Ou pelo menos pré-calcule constantes fora da consulta? Isso reduzirá o trabalho que precisa ser feito.
22668 Peter M
2
@ Peter M Parece provável que qualquer banco de dados SQL decente seja otimizado para que seja computado apenas uma vez.
precisa saber é o seguinte
25
Para aqueles que se perguntam, 42.290763 é a latitude e -71.35368 é a longitude do ponto a partir do qual calcular as distâncias.
User276648
14
Apenas para informação, Distância caluclated por esta fórmula é em milhas, não em kilometers.Please Substitua 3959 a 6371 para obter resultados em quilômetros
Sahil

Respostas:

115
  • Crie seus pontos usando Pointvalores de Geometrytipos de dados na MyISAMtabela. A partir do Mysql 5.7.5, as InnoDBtabelas agora também suportam SPATIALíndices.

  • Crie um SPATIALíndice nesses pontos

  • Use MBRContains()para encontrar os valores:

    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)

ou MySQL 5.1acima e abaixo:

    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
                    )

Isso selecionará todos os pontos aproximadamente dentro da caixa (@lat +/- 10 km, @lon +/- 10km).

Na verdade, isso não é uma caixa, mas um retângulo esférico: segmento da esfera de latitude e longitude. Isso pode diferir de um retângulo simples na Terra Franz Joseph , mas bastante próximo a ele na maioria dos lugares habitados.

  • Aplique filtragem adicional para selecionar tudo dentro do círculo (não o quadrado)

  • Possivelmente aplique filtragem fina adicional para levar em consideração a grande distância do círculo (para grandes distâncias)

Quassnoi
fonte
15
@Quassnoi: Algumas correções: você provavelmente vai querer mudar a ordem das coordenadas para lat, longo. Além disso, as distâncias longitudinais são proporcionais ao cosseno da latitude , não à longitude. E você deseja alterá-lo da multiplicação para a divisão, para que sua primeira coordenada seja corrigida como @lon - 10 / ( 111.1 / cos(@lat))(e seja a segunda no par quando tudo estiver correto).
M. Dave Auayan
8
AVISO : O corpo da resposta NÃO foi editado para concordar com o comentário muito válido feito por @M. Dave Auayan. Observações adicionais: Esse método fica em forma de pera se o círculo de interesse (a) incluir um polo ou (b) for interceptado pelo meridiano de longitude +/- 180 graus. O uso também cos(lon)é preciso apenas para distâncias pequenas. Veja janmatuschek.de/LatitudeLongitudeBoundingCoordinates
John Machin
3
Existe alguma maneira de termos alguma ideia do que as constantes (10, 111.11, @lat, @lon, mypoint) representam? Suponho que o 10 seja para quilômetros de distância, @lat e @lon representam a latte e a longitude fornecidas, mas o que 111.11 e mypoint representam no exemplo?
ashays
4
@ ashays: existem aproximadamente 111.(1)km em um grau de latitude. mypointé o campo na tabela que armazena as coordenadas.
Quassnoi
1
Outra correção de erro - você está faltando um fechamento) na segunda à última linha
ina
100

Não é uma resposta específica do MySql, mas melhorará o desempenho da sua instrução sql.

O que você está efetivamente fazendo é calcular a distância de cada ponto da tabela, para ver se está dentro de 10 unidades de um determinado ponto.

O que você pode fazer antes de executar este sql é criar quatro pontos que desenham uma caixa de 20 unidades de um lado, com o seu ponto no centro, ou seja. (x1, y1). . . (x4, y4), onde (x1, y1) é (dado + 10 unidades, dado + Lat + 10 unidades). . . (determinadoLongo - 10 unidades, dadoLat -10 unidades). Na verdade, você só precisa de dois pontos, superior esquerdo e inferior direito, chame-os (X1, Y1) e (X2, Y2)

Agora, sua instrução SQL usa esses pontos para excluir linhas que definitivamente são mais de 10u do seu ponto especificado, ela pode usar índices nas latitudes e longitudes, portanto haverá ordens de magnitude mais rápidas do que as que você possui atualmente.

por exemplo

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

A abordagem da caixa pode retornar falsos positivos (você pode pegar pontos nos cantos da caixa que são> 10u a partir do ponto especificado), portanto, você ainda precisa calcular a distância de cada ponto. No entanto, isso novamente será muito mais rápido, porque você limitou drasticamente o número de pontos a serem testados nos pontos dentro da caixa.

Eu chamo essa técnica de "Pensar dentro da caixa" :)

Edição: isso pode ser colocado em uma instrução SQL?

Não tenho idéia do que o mySql ou Php é capaz, desculpe. Eu não sei onde o melhor lugar é construir os quatro pontos, ou como eles podem ser passados ​​para uma consulta mySql em Php. No entanto, depois de ter os quatro pontos, não há nada que o impeça de combinar sua própria instrução SQL com a minha.

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;

Eu sei que com o MS SQL eu posso criar uma instrução SQL que declara quatro carros alegóricos (X1, Y1, X2, Y2) e os calcula antes da instrução de seleção "principal", como eu disse, não tenho idéia se isso pode ser feito com MySql. No entanto, eu ainda estaria inclinado a criar os quatro pontos em C # e passá-los como parâmetros para a consulta SQL.

Desculpe, não posso ajudar mais, se alguém puder responder a partes específicas do MySQL e Php, sinta-se à vontade para editar essa resposta.

Preocupação binária
fonte
4
Você pode encontrar um procedimento de mysql para esta abordagem nesta apresentação: scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL
Lucia
37
Para procurar por quilômetros em vez de milhas, substitua 3959 com 6371.
ErichBSchulz
4
+1, ótima opção; adicionar a caixa reduziu minha consulta de 4s para 0,03s avg.
Jvenema
1
Embora pareça tão lógico, você reserva um prêmio por esta solução! Em um banco de dados de 2 milhões de registros, a consulta passou de 16 segundos para 0,06 segundos. Nota: É ainda mais rápido (para tabelas grandes) se você cortar o cálculo da distância da consulta e fazer o cálculo da distância no código do seu programa!
NLAnaconda
2
@ Preocupante binário: Portanto, o X1, X2 e Y1, Y2 serão Longitude Min e Max e Latitude Min e Max conforme o exemplo aqui: blog.fedecarg.com/2009/02/08/… por favor informe.
Prabhat
14

A seguinte função MySQL foi publicada nesta postagem do blog . Não testei muito, mas pelo que coletei na postagem, se seus campos de latitude e longitude estiverem indexados , isso poderá funcionar bem para você:

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 ;

Uso da amostra:

Assumindo uma tabela chamada placescom campos latitude& longitude:

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;
Brad Parks
fonte
Eu tentei isso e funciona perfeitamente, mas de alguma forma não me permite colocar uma declaração WHERE com base em distance_from_input. Alguma idéia por que não?
precisa
você poderia fazer isso como uma sub-seleção: selecione * de (...) como t onde distance_from_input> 5;
Brad Parks
2
ou simplesmente siga em frente com: selecione * nos locais em que get_distance_in_miles_between_geo_locations (-34.017330, 22.809500, latitude, longitude)> 5000;
Brad Parks
2
return Meters:SELECT ROUND(((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lnt1 - lnt2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515) * 1.609344 * 1000) AS distance
Mohammad
13

Eu precisava resolver um problema semelhante (filtrando linhas pela distância do ponto único) e, combinando a pergunta original com respostas e comentários, criei uma solução que funciona perfeitamente para mim no MySQL 5.6 e 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

coordinatesé campo com tipo POINTe tem SPATIALíndice
6371é para calcular distância em quilômetros
56.946285é latitude para ponto central
24.105078é longitude para ponto central
15é distância máxima em quilômetros

Nos meus testes, o MySQL usa o índice SPATIAL no coordinatescampo para selecionar rapidamente todas as linhas que estão dentro do retângulo e depois calcula a distância real de todos os locais filtrados para excluir locais dos cantos dos retângulos e deixar apenas locais dentro do círculo.

Esta é a visualização do meu resultado:

mapa

Estrelas cinzas visualizam todos os pontos no mapa, estrelas amarelas são aquelas retornadas pela consulta do MySQL. Estrelas cinzas dentro dos cantos do retângulo (mas fora do círculo) foram selecionadas MBRContains()e desmarcadas pela HAVINGcláusula.

Māris Kiseļovs
fonte
Não é possível aprovar isso o suficiente. Pesquisando em uma tabela com aproximadamente 5 milhões de registros e em um índice espacial com esse método, o tempo de pesquisa é de 0,005 segundos em um processador A8 antigo. Eu sei que 6371 pode ser substituído por 3959 para obter resultados em milhas, mas os valores de 111.133 e 111.320 precisam ser ajustados ou são universalmente constantes?
Wranorn 26/11/19
Ótima solução.
SeaBiscuit 18/03
Como criar Point is POINT (lat, lng) ou POINT (lng, lat)
user606669
2
@ user606669 It's POINT (português, lat)
Māris Kiseļovs
A função X () e Y () deve ser ST_Y e ST_X hoje em dia.
Andreas
11

se você estiver usando o MySQL 5.7. *, poderá usar st_distance_sphere (POINT, POINT) .

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance
alriyami
fonte
1
essa é uma alternativa muito boa e fácil de ler. lembre-se, a ordem dos parâmetros para POINT () é (lng, lat), caso contrário, você poderá terminar com "close", mas ainda com resultados muito diferentes dos outros métodos aqui. Veja: stackoverflow.com/questions/35939853/…
Andy P
9
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

Esta é a consulta de cálculo de distância entre os pontos no MySQL, eu a usei em um banco de dados longo, funcionando perfeitamente! Nota: faça as alterações (nome do banco de dados, nome da tabela, coluna etc.) conforme seus requisitos.

Sanni Poriya
fonte
O que o valor 1.1515 representa? Eu já vi uma fórmula semelhante antes, mas ela usava 1,75 em vez de 1,1515.
TryHarder
1
Em resposta à minha própria pergunta, acho que a resposta pode estar aqui stackoverflow.com/a/389251/691053
TryHarder 20/07/16
8
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);

fonte

Abhigyan
fonte
11
Por favor, cite suas fontes. Isto é de: blog.fedecarg.com/2009/02/08/…
redburn
O que é 69 neste caso? Como fazer caso tenhamos o raio da terra?
código é o seguinte
2
O quilômetro em 1 latitude é 111 KM. A milha em 1 latitude é de 69 milhas. e 69 milhas = 111 quilômetros. É por isso que usamos os parâmetros nas conversões.
código é o seguinte
Eu estava procurando por isso desde sempre. Não sabia que pode ser assim tão simples. Muito obrigado.
Vikas
Isso não seria incorreto, pois lng_min / lng_max precisaria usar lat_min e lat_max na matemática do raio?
Ben
6
   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;
user3113927
fonte
5

Uma função MySQL que retorna o número de metros entre as duas coordenadas:

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

Para retornar o valor em um formato diferente, substitua o 6371000na função pelo raio da Terra em sua unidade escolhida. Por exemplo, quilômetros seriam 6371e milhas seriam 3959.

Para usar a função, basta chamá-la como faria com qualquer outra função no MySQL. Por exemplo, se você tivesse uma mesa city, poderia encontrar a distância entre todas as cidades e todas as outras cidades:

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`
Robert
fonte
4

O código completo com detalhes sobre como instalar como plugin do MySQL está aqui: https://github.com/lucasepe/lib_mysqludf_haversine

Eu publiquei este ano passado como comentário. Desde que gentilmente @TylerCollier me sugeriu postar como resposta, aqui está.

Outra maneira é escrever uma função UDF personalizada que retorne a distância do haversine de dois pontos. Esta função pode receber entrada:

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

Então, podemos escrever algo como isto:

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

buscar todos os registros a uma distância menor que 40 quilômetros. Ou:

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

buscar todos os registros com uma distância inferior a 25 pés.

A função principal é:

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;
}
Luca Sepe
fonte
3

Uma aproximação rápida, simples e precisa (para distâncias menores) pode ser feita com uma projeção esférica . Pelo menos no meu algoritmo de roteamento, recebo um aumento de 20% em comparação com o cálculo correto. No código Java, ele se parece com:

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

Não tenho certeza sobre o MySQL (desculpe!).

Certifique-se de conhecer a limitação (o terceiro parâmetro de assertEquals significa a precisão em quilômetros):

    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);
Karussell
fonte
3

Aqui está uma descrição muito detalhada da Geo Distance Search com MySQL, uma solução baseada na implementação da Haversine Formula no mysql. A descrição completa da solução com teoria, implementação e otimização de desempenho adicional. Embora a parte de otimização espacial não funcionou corretamente no meu caso. http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Konstantin Voronov
fonte
3

Leia a Pesquisa por distância geográfica com o MySQL , uma solução baseada na implementação da Haversine Formula no MySQL. Esta é uma descrição completa da solução com teoria, implementação e otimização de desempenho adicional. Embora a parte de otimização espacial não funcione corretamente no meu caso.

Notei dois erros nisso:

  1. o uso de absna instrução select na p8. Eu apenas omiti abse funcionou.

  2. a função de distância de busca espacial na p27 não converte em radianos ou multiplica a longitude por cos(latitude), a menos que seus dados espaciais sejam carregados com isso em consideração (não é possível distinguir do contexto do artigo), mas seu exemplo na p26 indica que seus dados espaciais POINTnão são carregados com radianos ou graus.

Richard Sandoz
fonte
0
$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";
Neeraj Sharma
fonte
0

Usando o 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;

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

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

Veja: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

NOTA: LEASTé usado para evitar valores nulos como um comentário sugerido em https://stackoverflow.com/a/24372831/5155484

William Desportes
fonte